Separation of Variables and the Computation of Fourier Transforms on Finite Groups, II

Introduction

The Fast Fourier Transform (FFT) remains among the most important family of algorithms in information processing . It efficiently computes the discrete Fourier transform (DFT) which is equivalent to the matrix-vector multiplication

Let $T_{G}(R)$ denote the computational complexity of the Fourier transform on a group $G$ at a set of inequivalent irreducible representations $R$. Then $C(G)$ denotes the complexity of the group $G$, defined as

The Cooley-Tukey algorithm is undoubtedly the most famous of the FFTs. It is a divide-and-conquer algorithm whose basic idea was first recorded by Gauss in unpublished work (see e.g. for a brief history of the algorithm). The key step is to rewrite the DFT on a cyclic group $C_{N}$ as a linear combination of DFTs on $C_{n}<C_{N}$ (for $n\mid N$). Iterating this step for a chain of subgroups of $C_{N}$ yields algorithms more efficient than a direct matrix-vector multiplication.

This divide-and-conquer algorithm produces efficiencies by reducing the “big” problem to smaller subproblems that have common structure and in fact are themselves, smaller versions of the original, that can be efficiently combined to produce the required result. In this paper we continue a line of work that generalizes this approach to nonabelian groups . In this case the common subproblems are repeated occurrences of particular pieces of matrix multiplications (e.g., repeated block and thus element-by-element multiplications) whose existence is ensured by working with very specific kinds of bases for the irreducible matrix representations (and associated matrix elements) enabled by choices of group factorizations. Thus, there is in a sense, “divide-and-conquer” going on in both the group and its dual.

The bases are encoded via paths in a Bratteli diagram attached to the group of interest, which in turn means that irreducible matrix elements correspond to pairs of paths in the diagram, which for a given group element may only be nonzero when of a particular form. I.e., the “repeated units” of our divide-and-conquer amount to certain subgraphs of a Bratteli diagram and efficiencies are gained by recognizing their multiple appearances in the corresponding calculation. This is the guts of the “separation of variables” (SOV) approach first introduced in and then extended in via a quiver-based formalism.

$C(D_{n})\leq\frac{n(13n-11)}{2}|D_{n}|.$

Improvements for the complexity of Fourier transforms on related homogeneous spaces are also presented. For example, let $B_{n}/B_{n-k}$ denote the homogenous space of the Weyl group $B_{n}$.

$C(B_{n}/B_{n-k})\leq k(4n-2k-1)\frac{|B_{n}|}{|B_{n-k}|}.$

Moreover, our results extend to chains of semisimple algebras rather than just chains of group algebras. This will be explored in subsequent work .

In Section 2 we outline the preliminaries needed for our results, including a discussion of the mainideas behind the SOV approach, necessarily recapitulated (in an abbreviated format) in order to make this paper as self-contained as possible (although we acknowledge – given the title – the dependence on part I ). In Section 3 we present the improved SOV approach in detail, rewriting an iterated product in the path algebra as a sequence of bilinear maps on the newly defined “configuration spaces” (vector spaces of quiver morphisms). In Section 4 we give factorizations and counts to prove the specific group complexity results (Theorems 1.1,1.2,1.3) and also recover previously known methods for $S_{n}$ and compact Lie groups . The results in Section 4 depend on various important, but very technical details of the explicit computation of the configuration space dimensions. In order to bring the reader to the complexity results as quickly and directly as seems possible, we postpone the presentation of these details to Sections 5 and 6.1. This includes generalizations of some results of Stanley on differential posets used to give explicit methods for finding these dimensions. This may be of independent interest. Some of the more laborious (but necessary) formalisms are collected in three short appendices.

Background

The usual discrete Fourier transform of a finite data sequence may be viewed as a special case of Fourier transforms on finite groups, defined using group representations. Results here assume complex representations, unless spelled out otherwise, although most results go through more generally. For necessary background on the representation theory of finite groups we refer the reader to .

Let $G$ be a finite group and $f$ a complex-valued function on $G$.

Let $\rho$ be a matrix representation of $G$. Then the Fourier transform of $\mathbf{f}$ at $\mathbf{\rho}$, denoted $\hat{f}(\rho)$, is the matrix sum

Let $R$ be a set of matrix representations of $G$. Then the Fourier transform of $\mathbf{f}$ on $\mathbf{R}$ is the direct sum of Fourier transforms of $f$ at the representations in $R$:

When we compute the Fourier transform for a complete set of inequivalent irreducible representations $R$ of $G$ we refer to the calculation as the computation of a Fourier transform on $G$ (with respect to $R$).

Let $G$ be a finite group, $R$ a set of matrix representations of $G$.

Let $+_{G}(R)$ (respectively, $\times_{G}(R)$) denote the minimum number of complex arithmetic additions (resp., multiplications) needed to compute the Fourier transform of $f$ on $R$ via a straight-line programA straight-line program is a list of instructions for performing the operations $\times,\div,+,-$ on inputs and precomputed values . for an arbitrary complex-valued function $f$ defined on $G$. The arithmetic complexity of a Fourier transform on $R$, denoted $T_{G}(R)$, is given by $\max{(+_{G}(R),\times_{G}(R))}$.

The complexity of the group $G$, denoted $C(G)$ is defined by

where $R$ varies over all complete sets of inequivalent irreducible matrix representations of $G$.

The reduced complexity, denoted $t_{G}(R)$, is defined by

Let $\rho_{1},\dots,\rho_{m}$ be a complete set of inequivalent irreducible matrix representations of a group $G$ of dimensions $d_{1},\dots,d_{m},$ respectively. A direct computation of a Fourier transform would require at most $|G|\sum d_{i}^{2}=|G|^{2}$ arithmetic operations. Rewriting, for a direct computation we have

Fast Fourier transforms (FFTs) are algorithms for computing Fourier transforms that improve on this naive upper bound. A priori, the number of operations needed to compute the Fourier transform may depend on the specific representations used.

The classical DFT and FFT. For $G=C_{N}$, the cyclic group of order $N$, the irreducible representations are $1$-dimensional and defined by $\zeta_{j}\rightarrow\zeta_{j}^{k},$ for $\zeta_{j}=e^{2\pi ij/N}$ and $k=0,\dots,N-1$ and $i=\sqrt{-1}$. The corresponding Fourier transform on $C_{N}$ is the usual discrete Fourier transform. Cooley and Tukey’s algorithm showed that for a “highly composite” integer $N$ (an integer $N$ that factors completely as a product of small prime numbers), $C(G)\leq O(N\log_{2}N)$ .

Let $G$ be a finite group, $f$ a complex-valued function on $G$, and $R$ a complete set of inequivalent irreducible matrix representations of $G$. Then

Thus, the Fourier transform of a function $f$ on $G$ with respect to a complete set of inequivalent irreducible representations $R$ of $G$ is an algebra isomorphism

The computation of the Fourier transform of a function $f$ on $G$ with respect to a complete set of irreducible representations $R$ is equivalent to computation (rewriting) of

in the group algebra, relative to a fixed basis for $R$.

2. Adapted bases, Bratteli diagrams, and quivers

The fundamental idea of the SOV approach is a recasting of the Cooley-Tukey algorithm in terms of graded quivers, which is an elaboration of path algebras derived from Bratteli diagrams, which are motivated by the use of adapted or Gel’fand-Tsetlin bases for irreducible representations.

Given a group $G$ with subgroup $H\leq G$, a complete set $R$ of inequivalent irreducible matrix representations of $G$ is $\mathbf{H}$-adapted if there exists a complete set $R_{H}$ of inequivalent irreducible matrix representations of $H$ such that for all $\rho\in R$, $\rho\downarrow_{H}=\bigoplus\gamma_{s}$, for (not neccessarily distinct) representations $\gamma_{s}$ in $R_{H}$. The set $R$ is adapted to the chain $G=G_{n}>G_{n-1}>\cdots>G_{0}$ if for each $1\leq i\leq n$ there is a complete set $R_{i}$ of inequivalent representations of $G_{i}$ such that $R_{i}$ is $G_{i-1}$-adapted and $R_{n}=R$. A set of bases for the representation spaces that give rise to adapted representations is an adapted basis.

For the FFT results of this paper we assume the ability to construct adapted sets of representations. This requirement is not a limitation, as any set of representations is equivalent to an adapted set of representations. One such construction is outlined in .

A quiver $Q$ is a directed multigraph with vertex set $V(Q)$ and edge set $E(Q)$. For an arrow (directed edge) $e\in E(Q)$ from vertex $\beta$ to vertex $\alpha$, we call $\alpha$ the target of $e$ and $\beta$ the source of $e$.

Let $Q$ be a quiver. For each $e\in E(Q)$, let $t(e)$ denote the target of $e$ and $s(e)$ the source of $e$.

Figure 1 is an example of a graded quiver. Each vertex $v$ is labeled by its grading, $gr(v)$.

A Bratteli diagram is a finite graded quiver such that:

there is a unique vertex with grading , called the root,

if $v\in V(Q)$ is not the root then $v$ is the target of at least one arrow,

if $v\in V(Q)$ does not have grading of maximum value then $v$ is the source of at least one arrow,

for each $e\in E(Q)$, $gr(t(e))=1+gr(s(e))$.

Note that the quiver of Figure 1 is not a Bratteli diagram. However, a slight modification produces the Bratteli diagram of Figure 2.

The vertices of grading $i$ are labeled by the (equivalence classes of) irreducible representations of $G_{i}$;

A vertex labeled by an irreducible representation $\gamma$ of $G_{i-1}$ is connected to a vertex labeled by an irreducible representation $\rho$ of $G_{i}$ by $M(\rho,\gamma)$ arrows.

Figure 3 shows two examples of Bratteli diagrams, with the gradings listed at the top.

Both Bratteli diagrams of Figure 3 are examples of multiplicity-free diagrams in that there is at most one edge from any vertex of grading $i$ to any vertex of grading $i+1$.

Given a Bratteli diagram $\mathcal{B}$, there is a canonical chain of algebras associated to $\mathcal{B}$ called the chain of path algebras.

over all arrows $e$ such that the source of $e$ is the target of $P$ (equivalently, of $Q$), and $\circ$ denotes concatenation of paths. Thus, elements in these subalgebras are effectively determined by the initial “legs” (or “bubbles”) of their paths. This is also equivalent to a choice of basis in the corresponding Wedderburn decomposition of the group algebra as a direct sum of matrix algebras, recognizing that for a given element, a number (equal to the total number of distinct paths that have the common middle “source” of tail of $P$) of irreducible matrix elements will take on the same value. Identification of this kind of common “unit” (formalized by the injection of one quiver into another) is the fundamental observation and technique of the quiver-based SOV approach.

and is illustrated in Figure 5. The first arrow represents gluing two pairs of paths along identical middle paths $Q=P^{\prime}$ and the second arrow represents summation over all possible gluings.

For further explanation see Appendix A and Section 2.3 of .

Quivers were first introduced by Gabriel in the study of modular representation theory . Bratteli diagrams were first introduced to classify inductive limits of $C^{*}$-algebras . After Elliot’s use of Bratteli diagrams in the classification of AF-algebras , these ideas motivated a program to classify $C^{*}$-algebras in terms of their K-theory . In terms of the representation theory of semisimple algebras, Bratteli diagrams have been used to explicitly construct complete sets of irreducible representations that are analogs of Young’s seminormal form in the symmetric group, and to describe restriction relations of representations .

3. Gel’fand-Tsetlin bases

The analogous concept in the path algebra of adapted bases associated to a group algebra chain is a system of Gel’fand Tsetlin bases.

Let $\mathcal{B}$ be the Bratteli diagram associated to a chain of group algebras. A system of Gel’fand-Tsetlin bases for $\mathbf{\mathcal{B}}$ consists of a collection of bases for the representation spaces $\{V_{\alpha}|\;\alpha\in V(\mathcal{B})\}$ of the representations corresponding to $\alpha$ indexed by paths from the root to $\alpha$, along with maps from the paths to the basis vectors; i.e., a set of basis vectors along with knowledge of the path corresponding to each vector.

Systems of Gel’fand-Tsetlin bases were originally developed by Gel’fand and Tsetlin to calculate the matrix coefficients of compact groups . Clausen was the first to apply them to the efficient computation of Fourier transforms on finite groups .

In Remark A.5 of Appendix A, we show systems of Gel’fand-Tsetlin bases for the chain of path algebras corresponding to a group algebra chain are equivalent to adapted bases for the chain of subgroups. The notion of an adapted basis coincides with that of a set, for each $1\leq i\leq n$, of $G_{i}$-equivariant maps between the representation spaces of representations in $R_{i}$ and those in $R_{i+1}$. For further details, see Appendix A.

The computation of the Fourier transform of a function $f$ on a group $G$ with respect to a complete set of inequivalent irreducible representations $R$ is the same as computation of

Young’s orthogonal form gives an example of a complete set of irreducible matrix representations for $S_{n}$ adapted to the chain $S_{n}>S_{n-1}>\cdots>S_{1}$. Since restriction of representations from $S_{n}$ to $S_{n-1}$ is multiplicity-free, the basis vectors of a system of Gel’fand-Tsetlin bases for the irreducible representations relative to this chain are determined up to scalar multiplies, and in the case of $n=3$, the paths are the paths $P_{1},P_{2},P_{3},P_{4}$ of Example 2.15. In , Maslen gives an efficient algorithm for computation of the Fourier transform of a function on $S_{n}$ by considering the computation of $\displaystyle\sum_{s\in S_{n}}f(s)s$ in the group algebra for $S_{n}$ relative to this Gel’fand-Tsetlin basis.

The Separation of Variables Approach

for $Y$ a set of coset representatives for $G/H$ such that for each $y\in Y,$

Lemma 3.1 is a restatement of Lemma 2.10 of and Proposition 1 of . It shows that to compute the Fourier transform of a complex function defined on $G$ at a set of $H$-adapted representations, we compute

for $Y$ a set of coset representatives for $G/H$, or, equivalently, for ease of notation

The heart of the SOV approach is the efficient computation of $\mathcal{F}_{Y}$. It comprises three main steps:

Each factor $x_{i}$ will correspond to an element of the path algebra of a particular form, and thus a particular subgraph of the Bratteli diagram. These subgraphs can be given a vector space structure through an identification with a space of quiver morphisms.

By virtue of the vector space identification, the element multiplication $x_{i}x_{i+1}$ becomes a bilinear map whose complexity can be calculated directly in terms of the dimension of the derived space of graph morphisms.

To give the general idea, the “gluing” and summing operations that are multiplication in the path algebra (cf. Figure 5) mean that only certain kinds of “middle paths” contribute when two path algebra elements are multiplied. I.e., only certain kinds of quivers can be combined to create the target quiver. A complexity estimate thus becomes counting the number of subgraphs (subquivers) wherein this compatibility is respected. This is just a counting of the number of occurrences of subquiver $\mathcal{Q}$ in the corresponding Bratteli diagram $\mathcal{B}$. Ultimately, this is the number of morphisms from $\mathcal{Q}$ into $\mathcal{B}$ (see Definition 5.1). We give a general example below.

To each space $X_{i}$, associate the quiver $Q_{i}$ of Figure 7. (Note that $Q_{i}$ is also the quiver associated to every element of $X_{i}$.) We show in Section 5 that $X_{i}$ has dimension equal to the number of occurrences of $Q_{i}$ in the Bratteli diagram $\mathcal{B}$. Denote this number by $\#\operatorname{Hom}(Q_{i};\mathcal{B})$. An “occurrence” of $Q_{i}$ is the same as an injective map from $Q_{i}$ into $\mathcal{B}$. Thus, $\#\operatorname{Hom}(Q_{i};\mathcal{B})$ is also the dimension of this space of morphisms of $Q_{i}$ into $\mathcal{B}$.

In this setting (bilinear) group algebra multiplication is transformed into a bilinear map on products of associated spaces of quiver morphisms. Call this map $*$. As the notation and details are more technical than illuminating, we defer the explicit definition of $*$ and discussion of its properties to Section 5. However, even with deferring this we can present the algorithm. Keep in mind the identification of the group algebra and the path algebra.

For $1\leq i\leq m$ let $X_{i}$ be as in Definition 3.3. For $\sigma\in S_{m}$, let $w_{i}=x_{\sigma(i)}$. The bilinear map $*$ is such that $x_{1}\cdots x_{m}=(((w_{1}*w_{2})*w_{3})\cdots*w_{m}),$

For $0\leq i<m$, let $W_{i}=\{(w_{i+1},\dots,w_{m})\mid(x_{1},\dots,x_{m})\in X\}$. Let $W_{m}=\emptyset.$ Note that $W_{i}\subseteq X_{\sigma(i+1)}\times\cdots\times X_{\sigma(m)}$.

Define a sequence of functions $L_{i}$ recursively by:

Figure 8 shows the quivers $Q_{i}$ and the quiver $\mathcal{Q}$ formed by gluing $Q_{1}$ to $Q_{2}$ to $Q_{3}$.

For $\sigma=(123)$, $w_{1}*w_{2}*w_{3}=x_{2}*x_{3}*x_{1}$. The complexity of $x_{2}*x_{3}$ is $\#\operatorname{Hom}(Q_{2}\cup Q_{3};\mathcal{B})$, where $Q_{2}\cup Q_{3}$ is as in Figure 9, the subquiver of $\mathcal{Q}$ corresponding to $Q_{2}$ and $Q_{3}$ (note that in Figure 9 we show only the subquiver formed by the segments of $Q_{2}\cup Q_{3}$ where not all three – top, bottom and the summed over middle – of the paths agree). The complexity of $(x_{2}*x_{3})*x_{1}$ is $\#\operatorname{Hom}((Q_{2}\triangle Q_{3})\cup Q_{1};\mathcal{B})$, where $Q_{2}\triangle Q_{3}$ is the quiver of Figure 9 associated to the space containing $x_{2}*x_{3}$. Note that as per the notation $Q_{2}\triangle Q_{3}$ is in fact the symmetric difference of $Q_{2}$ and $Q_{3}$, i.e., the edges of $Q_{2}\cup Q_{3}$ not in $Q_{2}\cap Q_{3}$ (see Definition 5.6).

For $Q_{i}$ (respectively, $Q_{j}$) the quiver associated to $X_{i}$ (respectively, $X_{j}$), computation of $x_{i}*x_{j}$ requires at most $\#\operatorname{Hom}(Q_{i}\cup Q_{j};\mathcal{B})$ scalar multiplications and fewer additions.

We postpone the proof of this key counting lemma to Section 5. With Lemma 3.7 we now have our main general result:

Stage $1$: Compute $L_{1}$ for all $(w_{2},\dots,w_{m})$ in $W_{1}$.

Stage $i$: Compute $L_{i}$ given $W_{i-1}$ and $L_{i-1}$.

Stages and $1$ require no multiplications. For $2\leq i\leq m$, condition (2) and the definition of $*$ implies that stage $i$ requires $|W_{i-1}|\#\operatorname{Hom}((Q_{1}^{\sigma}\triangle\cdots\triangle Q_{i}^{\sigma})\cup Q_{i+1}^{\sigma};\mathcal{B})$ multiplications. ∎

For an explicit additions count, see Theorem 5.14 in Section 5.

The Complexity of Fourier Transforms on Finite Groups

The SOV approach computes path algebra sums by first factoring each element and then translating multiplication into maps indexed by subgraphs. The complexity is determined by the size of the factorization sets and the number of occurrences of these subgraphs in the Bratteli diagram. Thus, our main results require methods to determine these counts. In this section we demonstrate the subgraphs determined by the SOV apporach and defer the proofs of the complexity counts to Section 6.1 and the appendices. In this way we hope to give the visual sense (and attendant justification of the proofs) of the algorithm without an overload of technical notation.

For our first application of the SOV approach we consider the Fourier transform of functions on the Weyl groups of type $B_{n}$ and $D_{n}$. We improve upon the results of .

Let $R$ be a complete set of irreducible matrix representations of (Weyl group) $B_{n}$ adapted to the subgroup chain $B_{n}>B_{n-1}>\cdots>B_{0}=\{e\}.$ Then

Let $s_{1},\dots,s_{n}$ denote the simple reflections for $B_{n}$, labeled as per the usual Dynkin diagram schema (see e.g., ) in Figure 10.

Recall from that elements in a set of minimal coset representatives for $B_{n}/B_{n-1}$ have the following factorizations:

Then for $A_{i}=\{e,s_{i}\}=A_{i}^{\prime}$, a complete set of coset representatives is contained in $Y=\{a_{n}\cdots a_{2}a_{1}a_{2}^{\prime}\cdots a_{n}^{\prime}|\;a_{i},a_{i}^{\prime}\in A_{i}\}$.

Let $\sigma\in S_{2n}$ be the permutation reordering $X$ so that $W_{0}$ is the set $\{(F_{a_{n}\cdots a_{2}a_{1}a_{2}\cdots a_{n}},a_{2}^{\prime},a_{3}^{\prime},\dots a_{n}^{\prime},a_{1},a_{2},a_{3},\dots,a_{n})\}.$ Then

By Theorem 3.8, we may compute $\sum yF_{y}$ in at most

multiplications, with $(Q_{1}^{\sigma}\triangle\cdots\triangle Q_{i}^{\sigma})\cup Q_{i+1}^{\sigma}$ as in Figure 13. Thus, the complexity of the computation comes down to determining $\#\operatorname{Hom}((Q_{1}^{\sigma}\triangle\cdots\triangle Q_{i}^{\sigma})\cup Q_{i+1}^{\sigma};\mathcal{B})$, i.e., the number of occurrences of each quiver of Figure 13 in the Bratteli diagram $\mathcal{B}$. Figure 14 gives the general kinds of quivers that appear in Figure 13. The first $n$ quivers of Figure 13 (the top row) have general form $\mathcal{H}_{i}^{n}$, as in Figure 13. The $n$th quiver (bottom left quiver of Figure 13) has form $\mathcal{K}^{n}$, while the remaining quivers have general form $\mathcal{J}_{i}^{n}$.

where for a subquiver $Q$ of $\mathcal{Q}$, $\operatorname{Hom}(Q\uparrow\mathcal{Q};\mathcal{B})$ denotes the number of quiver morphisms from $Q$ to $\mathcal{B}$ that extend to morphisms from $\mathcal{Q}$ to $\mathcal{B}$ (see Definition 5.1).

multiplications (and fewer additions). By Lemma 3.1,

Analogous arguments give the following result for Weyl groups of type $D_{n}$.

For the Weyl group $D_{n}$ and $R$ a complete set of irreducible matrix representations of $D_{n}$ adapted to the subgroup chain $D_{n}>D_{n-1}>\cdots>D_{0}=\{e\},$

Let $s_{1},\dots,s_{n}$ denote the simple reflections for $D_{n}$, labeled according to its standard Dynkin diagram (see Figure 15).

Recall from that elements in a set of minimal coset representatives for $D_{n}/D_{n-1}$ have the following factorizations:

Then for $A_{i}=\{e,s_{i}\}=A_{i}^{\prime}$, following the proof of Theorem 1.1 shows we need only determine $\#\operatorname{Hom}(\mathcal{H}_{i}^{n}\uparrow\mathcal{Q};\mathcal{B}),$ $\#\operatorname{Hom}(\mathcal{J}_{i}^{n}\uparrow\mathcal{Q};\mathcal{B}),$ and $\#\operatorname{Hom}(\mathcal{K}^{n}\uparrow\mathcal{Q};\mathcal{B}),$ for $\mathcal{H}_{i}^{n},\mathcal{J}_{i}^{n},\mathcal{K}^{n}$ the quivers of Figure 14. As before,

By Lemma D.6 and Corollary D.8 of Appendix D,

so by Theorem 3.8 we may compute $\sum yF_{y}$ in at most

multiplications (and fewer additions). Then by Lemma 3.1,

2. The General Linear Group

For the matrix group $Gl_{n}(q)$ and $R$ a complete set of irreducible matrix representations of $Gl_{n}(q)$ adapted to the subgroup chain $Gl_{n}(q)>Gl_{n-1}(q)>\cdots>\{e\}$

Let $P$ be the set of permutation matrices of $Gl_{n}(q)$. By Proposition E.4 in Appendix E.1, for $p\neq 2$,

contains a complete set of coset representatives for $GL_{n}(q)/Gl_{n-1}(q)$, where $s_{i}$ has form

for $t_{j}$ the permutation matrix corresponding to $(j\;j-1)$, and

with $(q-1)$ possible matrices for $u_{j}$ and $u_{j}^{\prime}$, and $q^{2}$ possible matrices for $v_{j}$.

By Lemma 3.1 computation of the Fourier transform of a complex function $f$ on $GL_{n}(q)$ is equivalent to computation of:

then multiply by $\pi$ and sum. To compute sums of the form (8):

Fig. 16 shows the various component subquivers corresponding to the coset representatives. They combine together as per Fig. 17 to give the factorization of $yF_{y}$. Thus, the algorithm proceeds by gluing together quivers $Q_{i}$ of Figure 16 to build the quiver $\mathcal{Q}$ of Figure 17.

Let $\sigma\in S_{n+m-1}$ be the permutation reordering $X$ so that

By Theorem 3.8, we may compute (8) in at most

multiplications, with $(Q_{1}^{\sigma}\triangle\cdots\triangle Q_{k-1}^{\sigma})\cup Q_{k}^{\sigma}$ as in Figure 18.

Then as in the proof of Theorem 4.1 for $\mathcal{H}_{j}^{n},\mathcal{J}_{j}^{n}$ the quivers of Figure 19,

First consider the quiver $\mathcal{H}_{j}^{n}$ of Figure 19, which corresponds to:

and so for all quivers $(Q_{1}^{\sigma}\triangle\cdots\triangle Q_{k-1}^{\sigma})\cup Q_{k}^{\sigma}$ of form $\mathcal{H}_{j}^{n}$,

and so for all quivers $(Q_{1}^{\sigma}\triangle\cdots\triangle Q_{k-1}^{\sigma})\cup Q_{k}^{\sigma}$ of form $\mathcal{J}_{j}^{n}$,

Thus, by Theorem 3.8, we may compute (8) in at most

Now suppose $p=2$. By Theorem E.7 in Appendix E.1,

contains a complete set of coset representatives for $Gl_{n}(q)/Gl_{n-1}(q)$, where $s_{i}$ is of form

for $a_{j},b_{j},c_{j}\in Gl_{j}(q)\cap\operatorname{Centralizer}(Gl_{j-2}(q))$ with $(q-1)$ possible matrices for $a_{j}$ and $b_{j}$, $q^{2}$ possible matrices for $v_{j}$, and $c_{j}$ completely determined by $a_{j}$ and $b_{j-1}$. The same arguments as in the $p\neq 2$ case then yield the quiver $\mathcal{Q}$ of Figure 20, from which it is clear that analogous arguments give the result.

3. Generalized Symmetric Group Case

We next give a general result (Theorem 4.4) to find efficient Fourier transforms on groups with special subgroup structure. As the proof follows the same structure of the proofs of Theorems 10, 15, and 1.3, we leave it as an exercise.

Suppose $G_{n}>G_{n-1}>\cdots>G_{0}=e$ is a chain of subgroups with subsets $A_{i}\subseteq G_{i}$ such that

$G_{i}=A_{2}\cdots A_{i}G_{i-1}$ for $2\leq i\leq n$,

Let $\mathcal{B}$ be the Bratteli diagram associated to the chain

Let $G_{i}$, $A_{i}$ be as described above. Then the Fourier transform of a complex function on $G_{n}$ may be computed at a complete set $R$ of irreducible representations of $G_{n}$ adapted to the chain $G_{n}>G_{n-1}>\cdots>G_{0}=e$ in at most

Theorem 4.4 is a refinement of Theorem 3.1 of : rather than considering the maximum length of a factorization in terms of coset representatives, we need only multiply by $\prod|A_{j}|$. Note that our choice of coset representatives in the proofs of Theorems 1.1 and 1.2 were such that $\prod|A_{j}|=1$, much smaller than the length of the longest factorization in terms of coset representatives.

For $G_{i}=S_{i}$, this theorem gives an efficient algorithm for the computation of the Fourier transform of a function on the symmetric group by letting $A_{1}=\{e\}$ and $A_{i}=\{e,t_{i-1}\}$ for $2\leq i\leq n$.

4. The Complexity of Fourier Transforms on Homogeneous Spaces

We next consider the Fourier transform of a function on a homogeneous space, a special case of harmonic analysis on groups. This can be viewed as a coset space $G/K$, so a Fourier transform on a homogeneous space is a Fourier transform of the space of functions on $G/K$ or, equivalently, of the space of associated right-$K$ invariant functions on $G$. See for further background on Fourier transforms on homogeneous spaces and some of their applications.

Note that $\hat{f}(\rho)$ is zero unless the representation space, $V_{\rho}$, contains a nontrivial $K$-invariant vector. Such a representation is said to be class 1 relative to K, and we could restrict to class 1 representations if desired.

Let $G$ be a finite group with subgroup $K$ and let $R$ be a set of representations of $G$.

The arithmetic complexity of a Fourier transform on $R$, denoted $T_{G/K}(R)$, is the minimum number of arithmetic multiplications (or additions, whichever is largest) needed to compute the Fourier transform of $f$ on $R$ via a straight-line program for an arbitrary complex-valued function $f$ defined on $G/K$.

The reduced complexity, denoted $t_{G/K}(R)$, is defined by

Note that the complexity always satisfies the inequalities

Further, the proof of Lemma 3.1 gives an analogous result for the case of homogenous spaces: for $H$ a subgroup of $G$, $R$ a complete $H$-adapted set of inequivalent irreducible representations of $G$, and $Y\subseteq G$ a set of coset representatives,

Then the proofs of Section 4 extend to the following results for homogenous spaces:

For the homogenous space $B_{n}/B_{n-k}$ of the Weyl group $B_{n}$ and $R$ a complete set of irreducible matrix representations of $B_{n}$ adapted to the subgroup chain $B_{n}>B_{n-1}>\cdots>\{e\},$

For the homogenous space $D_{n}/D_{n-k}$ of the Weyl group $D_{n}$ and $R$ a complete set of irreducible matrix representations of $D_{n}$ adapted to the subgroup chain $D_{n}>D_{n-1}>\cdots>\{e\},$

For the homogenous space $Gl_{n}(q)/Gl_{n-k}(q)$ of the general linear group $Gl_{n}(q)$ and $R$ a complete set of irreducible matrix representations of $Gl_{n}(q)$ adapted to the subgroup chain $Gl_{n}(q)>Gl_{n-1}(q)>\cdots>\{e\},$

As in Section 4.3, suppose $G_{n}>G_{n-1}>\cdots>G_{1}=e$ is a chain of groups with subsets $A_{i}\subseteq G_{i}$ such that

$G_{i}=A_{2}\cdots A_{i}G_{i-1}$ for $2\leq i\leq n$.

Let $G_{i}$, $A_{i}$ be as above. For the homogeneous space $G_{n}/G_{n-k}$ and $R$ a complete set of irreducible matrix representations of $G_{n}$ adapted to the chain $G_{n}>G_{n-1}>\cdots>G_{1}=e$,

Configuration Spaces and the Maps ∗*

In Section 3 we gave an overview of the SOV algorithm, assuming the existence of bilinear maps $*$ with the properties described in part II of the SOV approach 3.4. In this section we determine such maps and investigate their properties.

For graded quivers $Q$ and $B$, a morphism $\phi:Q\rightarrow B$ is a mapping from arrows in $Q$ to paths in $B$, along with a grading-preserving mapping between vertices so that $\phi(t(e))=t(\phi(e))$ and $\phi(s(e))=s(\phi(e))$ for all arrows $e\in E(Q)$.

For $Q$, $B$ as in Figure 22, let $\phi:Q\rightarrow B$ send the arrow $e_{1}$ to the path $f_{3}\circ f_{2}\circ f_{1}$.

For two graded quivers $Q$ and $B$, let $\operatorname{Hom}(Q;B)$ denote the set of morphisms from $Q$ to $B$. For $Q,R$, and $B$ graded quivers such that $Q$ is a subquiver of $R$, let $\operatorname{Hom}(Q\uparrow R;B)$ denote the set of morphisms from $Q$ to $B$ that extend to $R$.

When $Q=R$, we simplify notation by writing $A(Q;B)$. If $Q$ is a finite subquiver of $R$ and $B$ is locally finite, i.e. each vertex has finitely many neighbors, then $\#\operatorname{Hom}(Q\uparrow R;B)=\dim A(Q\uparrow R;B)$.

This follows from an application of standard facts about Gel’fand-Tsetlin bases. For futher details, see eg. [29, Lemma 4.1], [19, Proposition 2.3.12]. ∎

For a graded quiver $R$ with subquivers $Q_{1},Q_{2}$, the symmetric difference of $Q_{1}$ and $Q_{2}$ is $Q_{1}\triangle Q_{2}=(Q_{1}\setminus(Q_{1}\cap Q_{2}))\cup(Q_{2}\setminus(Q_{1}\cap Q_{2})).$

The quiver $Q_{2}\triangle Q_{3}$ in Figure 9 is the symmetric difference of $Q_{2}$ and $Q_{3}$, while the quivers $Q_{1}^{\sigma}\triangle Q_{2}^{\sigma}$ in Figures 13 and 19 show the symmetric difference of $Q_{1}^{\sigma}$ and $Q_{2}^{\sigma}$.

Let $B$ be a locally finite graded quiver, $R$ a graded quiver with finite subquivers $Q_{1}$ and $Q_{2}$, and $\iota_{j}$ the inclusion $Q_{j}\hookrightarrow R$, for $j=1,2$. For $(f,g)\in A(Q_{1}\uparrow R;B)\times A(Q_{2}\uparrow R;B)$, define the restricted product relative to R, $*:A(Q_{1}\uparrow R;B)\times A(Q_{2}\uparrow R;B)\rightarrow A(Q_{1}\triangle Q_{2}\uparrow R;B)$, by

It is clear from the definition that the restricted product is bilinear and commutative. In Appendix B we show that the restricted product is associative.

For $B$ a locally finite graded quiver, $R$ a graded quiver with finite subquivers $Q_{1}$ and $Q_{2}$, $f\in A(Q_{1}\uparrow R;B)$, and $g\in A(Q_{2}\uparrow R;B)$, the restricted product $f*g$ requires at most $\#\operatorname{Hom}((Q_{1}\cup Q_{2})\uparrow R;B)$ scalar multiplications and at most $\#\operatorname{Hom}((Q_{1}\cup Q_{2})\uparrow R;B)-\#\operatorname{Hom}((Q_{1}\triangle Q_{2})\uparrow R;B)$ scalar additions.

To compute $f*g$, first compute $(f|_{\eta\circ{\iota_{1}}})(g|_{\eta\circ{\iota_{2}}})$ for each $\eta\in\operatorname{Hom}(Q_{1}\cup Q_{2}\uparrow R;B)$. This requires $\#\operatorname{Hom}(Q_{1}\cup Q_{2}\uparrow R;B)$ scalar multiplications.

Next note that a scalar addition comes from each pair $\eta_{i},\eta_{j}\in\operatorname{Hom}(Q_{1}\cup Q_{2}\uparrow R;B)$ with $\eta_{i}\downarrow_{Q_{1}\triangle Q_{2}}=\eta_{j}\downarrow_{Q_{1}\triangle Q_{2}}=\tau\in\operatorname{Hom}(Q_{1}\triangle Q_{2}\uparrow R;B);$ in total, $\#\operatorname{Hom}((Q_{1}\cup Q_{2})\uparrow R;B)-\#\operatorname{Hom}((Q_{1}\triangle Q_{2})\uparrow R;B)$ scalar additions. ∎

For $P,Q$ paths of length $n$ in $\mathcal{B}$, let $\gamma_{PQ}\in\operatorname{Hom}(Q_{1};\mathcal{B})$ denote the morphism that sends $p$ to $P$ and $q$ to $Q$. Similarly, let $\mu_{PQ}\in\operatorname{Hom}(Q_{2};\mathcal{B})$ (respectively, $\tau_{PQ}\in\operatorname{Hom}(Q1\triangle Q_{2};\mathcal{B})$) denote the morphism that sends $p^{\prime}$ to $P$ and $q^{\prime}$ to $Q$ (respectively, $p$ to $P$ and $q^{\prime}$ to $Q$).

A morphism $\eta\in\operatorname{Hom}(R;\mathcal{B})$ with $\eta\downarrow_{Q_{1}\triangle Q_{2}}=\tau_{PQ^{\prime}}$ must send $p$ to $P$, $q^{\prime}$ to $Q^{\prime}$, and $q,p^{\prime}$ to the same path, $Q$. Then $\eta\circ\iota_{1}=\gamma_{PQ}$, $\eta\circ\iota_{2}=\mu_{QQ^{\prime}}$, and

2. Use of ‘∗*’ in the SOV Algorithm

In this section we combine the results of Section 5.1 with Section 3 to show how the restricted product is used in the SOV algorithm.

More generally, for $x_{i}\in X_{i}$ and the paths of $Q_{i}$ identified as in Figures 25, 26, 27, the product $x_{1}x_{2}\cdots x_{m}$ corresponds to the restricted product $(x_{1}*x_{2}*\cdots*x_{m-1})*x_{m}:A(Q_{1}\triangle\cdots\triangle Q_{m-1};\mathcal{B})\times A(Q_{m};\mathcal{B})\rightarrow A(Q_{1}\triangle\cdots\triangle Q_{m};\mathcal{B}).$

This may be computed in at most $\displaystyle\sum_{i=1}^{m-1}\dim A(Q_{1}^{\sigma}\triangle\cdots\triangle Q_{i}^{\sigma}\cup Q_{i+1}^{\sigma};\mathcal{B})$ scalar multiplications, and fewer additions.

Part 1 follows from Definition 5.8 and Theorem 5.11. To prove Part 2, apply Lemma 5.10, note that the map $\phi^{-1}$ requires no operations to compute, and also note that for any quiver $R$ with subquiver $Q$, $\dim A(Q\uparrow R;\mathcal{B})\leq\dim A(Q;\mathcal{B}).$ ∎

as required by part II of the SOV approach, giving Theorem 3.8:

Determining the Dimension of Configuration Spaces

In Section 5 we developed aspects of the general quiver formalism to provide the technical bedrock for the SOV algorithm (esp., the definitions of configuration space and restricted product, and basic complexity counts in terms of morphisms). The final step in computing the complexities of the algorithms outlined in Section 4 is to finally rewrite the morphism counts in terms of multiplicities for the restriction of representations from one group algebra to another. That is the purpose of this section. Here we accomplish this by adapting earlier work of Stanley’s on differential posets , a context that can also be used for Bratelli diagrams. In this section our main result is the final Corollary (Corollary 6.18) that computes $\#\operatorname{Hom}(Q,\mathcal{B})$ (for a so-called ”n-toothed quiver” $Q$ and Bratteli diagram $\mathcal{B}$) in terms of spectral information from ”up” and ”down” operators on the diagram. We apply these results in Appendix D and Appendix E to give the explicit counts of Section 4.

Recall from Note 5.4 that if $Q$ is a finite subquiver of $R$ and $B$ a locally finite quiver, $\dim A(Q\uparrow R;B)=\#\operatorname{Hom}(Q\uparrow R;B).$ In the SOV approach, $B$ is the Bratteli diagram associated to a chain of semisimple algebras and hence locally finite, so in this section we give results to count $\#\operatorname{Hom}(Q\uparrow R;B)$.

For $B$ a locally finite graded quiver, $\alpha,\beta\in V(B)$, let $M_{B}(\alpha,\beta)$ denote the number of paths from $\beta$ to $\alpha$ in $B$. Note that for $\mathcal{B}$ a Bratteli diagram, $\alpha,\beta\in V(\mathcal{B})$ correspond to irreducible representations $\gamma$, $\rho$ and $M_{\mathcal{B}}(\alpha,\beta)=M(\gamma,\rho),$ as in Definition 2.12.

Let $Q,R,B$ be graded quivers with $Q$ a finite subquiver of $R$ and $B$ locally finite. Then

A morphism specifies the image of each vertex and each arrow. This may be counted by first fixing the image of each vertex and counting all possible arrow images, then varying over all possible images of $V(Q)$. ∎

Theorem 6.1 gives a procedure for computing $\#\operatorname{Hom}(Q\uparrow R;B)$. For a quiver $Q$, let $Q^{i}$ denote the vertices of $Q$ at level $i$. Then:

label each vertex $\alpha_{i}\in Q^{i}$ with a vertex $\alpha_{i}^{\prime}\in B^{i}$ such that this labeling could extend to a map from $R$ into $B$;

label each edge of $Q$ from $\beta$ to $\alpha$ by $M_{B}(\alpha^{\prime},\beta^{\prime})$;

multiply the labels and sum over all possible labellings.

Let $Q_{1}=R_{1}$ be as in Figure 28. Steps $1$ and $2$ then give the labelling of the figure and by Theorem 6.1,

To further simplify counts, we first ‘smooth’ quivers before counting morphisms, i.e. we remove superfluous vertices (see Corollary C.6 in Appendix C.1).

Let $Q_{2}=R_{2}$ be as in Figure 29. Then for $Q_{1},R_{1}$ as in Figure 28, Corollary C.6 gives the isomorphism

To compute $\#\operatorname{Hom}(Q_{2}\uparrow R_{2};B),$ remove vertices $\alpha_{2}$ and $\alpha_{1}$, then use the labelling of Figure 28.

2. Morphisms into Locally Free Bratteli Diagrams

In Section 6.1 we obtained general quiver morphism counting results for $B$ a locally finite quiver. For locally free Bratteli diagrams we rewrite these results in terms of the dimensions of the corresponding subalgebras.

where, by convention, if $\mathcal{B}$ has highest grading $n$, $\mathcal{B}^{-1}=\emptyset=\mathcal{B}^{n+1}=\mathcal{B}^{n+2}=\cdots.$

For $Q_{1}$ as in Example 6.2, trace each arrow on the quiver by starting at the root, moving up four levels to vertex $\alpha_{4}$, down to vertex $\alpha_{3}$, up two levels to vertex $\alpha_{5}$, and back down to the root. It is then easily checked that

In Corollary 6.18 we give explicit formulas for these inner products. For $\alpha\in V(B)$ and $\hat{0}$ the root of $\mathcal{B}$, let $d_{\alpha}=M_{\mathcal{B}}(\alpha,0)$ and let $d_{i}=\sum_{\alpha\in\mathcal{B}^{i}}d_{\alpha}\alpha$.

For $\alpha\in\mathcal{B}^{i}$, $\langle d_{i},\alpha\rangle=d_{\alpha}.$

Let $\mathcal{B}$ be a Bratteli diagram. Then the following properties are equivalent:

For each $i$, $d_{i}$ is an eigenvector of $DU$.

As this proof comes down to definitions and the fact that $D$ is restriction (cf. Note 6.6), we defer it to Appendix C.2. ∎

Let $\mathcal{B}$ be a locally free Bratteli diagram and $\lambda_{i}$ the eigenvalue of $DU$ associated to $d_{i-1}$. Then $\lambda_{i}$ is integral and

Theorem 6.13 below generalizes Theorem 3.7 of and Theorem 2.3 of .

Let $w=w_{l}\cdots w_{1}$ be a word in $U$ and $D$ and let $\mathcal{S}=\{i\mid w_{i}=D\}.$ For each $i\in\mathcal{S}$, let $a_{i}=\#\{D\text{'s in}\;w\;\text{to the right of}\;w_{i}\},$ and similarly let $b_{i}=\#\{U\text{'s in}\;w\;\text{to the right of}\;w_{i}\}.$ If $b_{i}-a_{i}\geq 0$ for all $i\in\mathcal{S}$, we call $w$ an admissible word.

Let $\mathcal{B}$ be a locally free Bratteli diagram and $w=D^{d_{n}}U^{u_{n}}\cdots D^{d_{1}}U^{u_{1}}$ an admissible word in $U$ and $D$. Then for $s=\sum_{i=1}^{n}u_{i}-d_{i}$ and $\alpha\in\mathcal{B}^{s}$,

The proof comes down to inductively showing:

For $\mathcal{B}$ a locally free Bratteli diagram and $Q$ an n-toothed quiver, Theorem 6.13 allows us to determine $\#\operatorname{Hom}(Q;\mathcal{B})$.

A quiver $Q$ is n-toothed if it consists of $2n+1$ (not necessarily distinct) vertices $\gamma_{0},\dots,\gamma_{n},\beta_{1},\dots,\beta_{n}$ and distinct arrows connecting $\gamma_{i-1}$ to $\beta_{i}$ and $\gamma_{i}$ to $\beta_{i}$.

The quiver of Figure 30 is an example of a $3$-toothed quiver.

The quiver $Q_{1}$ of Figure 28 is $2$-toothed, with $\gamma_{0}=\alpha_{0},\gamma_{1}=\alpha_{3},\gamma_{2}=\alpha_{0},\beta_{1}=\alpha_{4},\beta_{2}=\alpha_{5}$ .

Let $\mathcal{B}$ be a locally free Bratteli diagram, $Q$ an $n$-toothed quiver with vertices $\gamma_{i}$ at level $l_{i}$, $\beta_{i}$ at level $m_{i}$. Then for $w=D^{{m_{n}}-{l_{n}}}U^{{m_{n}}-{l_{n-1}}}\cdots D^{{m_{1}}-{l_{1}}}U^{{m_{1}}-{l_{0}}},$

Follows from Theorem 6.1 and induction. ∎

Let $\mathcal{B}$ be a locally free Bratteli diagram, $Q$ an $n$-toothed quiver with vertices $\gamma_{i}$ at level $l_{i}$, $\beta_{i}$ at level $m_{i}$. Then for $w=D^{{m_{n}}-{l_{n}}}U^{{m_{n}}-{l_{n-1}}}\cdots D^{{m_{1}}-{l_{1}}}U^{{m_{1}}-{l_{0}}},$

For $Q_{1}$ as in Example 6.2, we see that

Then $\mathcal{B}^{l_{2}-l_{0}}=\mathcal{B}^{0}=\hat{0}$ and by Corollary 6.18, for $w=D^{5}U^{2}DU^{4}$,

Note that this is the inner product of Example 6.7.

We use Corollary 6.18 in Appendix D and Appendix E to give many of the complexity results needed for the proofs in Section 4.

Further Directions

The SOV approach produces savings by first treating the Fourier transform as a collection of scalar equations and then recursively structuring the summation so as to collect together irreducible matrix elements, viewed under the translation to the path algebra as pairs of paths. Through this translation, a sequence of multiplications becomes a sequence of bilinear maps indexed by subgraphs. Efficiency counts are determined by the size of the factorization sets needed for these multiplications, as well as the number of occurrences of these subgraphs in the Bratteli diagram. The resultant savings are dependent on the choice of factorization as well as combinatorial path-counting methods used to provide the bounds in Appendix D and Appendix E. Different choices of subgroups could provide better bounds, and in fact some applications of the Fourier transform require particular chains of parabolic subgroups , which we will investigate in further work.

In addition, our results can be generalized beyond Fourier transforms on groups. In fact, the path algebra isomorphism of Corollary 2.16 is true for the Bratteli diagram associated to any semisimple algebra. In work being prepared for publication, we extend the SOV approach to Fourier transforms on semisimple algebras and determine complexity results for the Hecke, Brauer and Birman-Wenzl-Murakami algebras .

Appendix A Gel’fand-Tsetlin Bases and Adapted Representations

In Section 2 we introduce adapted bases and systems of Gel’fand Tsetlin bases. Here we make the formal connection between adapted bases of a group algebra chain and systems of Gel’fand Tsetlin bases for the corresponding chain of path algebras.

Given a Bratteli diagram $\mathcal{B}$, a representation of $\mathbf{\mathcal{B}}$ assigns to each $\alpha\in V(\mathcal{B})$ a linear space $V_{\alpha}$ and to each edge $e\in E(\mathcal{B})$ a linear map $L_{e}:V_{s(e)}\rightarrow V_{t(e)}$. Given two representations $(\{V_{\alpha}\}_{\alpha\in V(\mathcal{B})},\{L_{e}\}_{e\in E(\mathcal{B})})$, $(\{W_{\alpha}\}_{\alpha\in V(\mathcal{B})},\{S_{e}\}_{e\in E(\mathcal{B})})$, of $\mathcal{B}$, a morphism $m:V\rightarrow W$ is a family of linear maps $\{m_{\alpha}:V_{\alpha}\rightarrow W_{\alpha}\}_{\alpha\in V(\mathcal{B})}$ such that the diagram

A model representation of $\mathbf{\mathcal{B}}$ is a representation of $\mathcal{B}$ such that for all $e\in E(\mathcal{B})$, $L_{e}$ is injective, and for all nonroot vertices $\alpha\in V(\mathcal{B})$,

A model representation of an algebra chain has a natural basis of paths:

Given a model representation of a chain of subalgebras with Bratteli diagram $\mathcal{B}$, the collection of distinct paths in $\mathcal{B}$ from the root to a vertex $\alpha\in V(\mathcal{B})$ corresponds to a choice of basis for $V_{\alpha}$.

A system of Gel’fand-Tsetlin bases for a Bratteli diagram $\mathcal{B}$ uniquely determines a model representation for $\mathcal{B}$. Conversely, a model representation uniquely determines a system of Gel’fand-Tsetlin bases for $\mathcal{B}$.

Both require a choice of vector space for each vertex of $\mathcal{B}$, so we need only show how a choice of basis corresponds with linear maps $L_{e}$ for each edge $e$.

Given a system of bases and an edge $e\in\mathcal{B}$, a basis vector for $V_{s(e)}$ corresponds to a path $P$ from the root to $s(e)$. Then $e\circ P$ is a path from the root to $t(e)$, which corresponds to a basis vector for $V_{t(e)}$. In other words, we have an injection of $V_{s(e)}$ into $V_{t(e)}$.