Tensor invariants of SL(n), wave graphs and L-tris ^{∗}

Aleksandrs Mihailovs Department of Mathematics University of Pennsylvania Philadelphia, PA 19104-6395 mihailov@math.upenn.edu http://www.math.upenn.edu/∼mihailov/

March 2, 1998

Abstract The space of invariants of a tensor product of representations of SL(n) is provided with the basis parametrized by wave graphs introduced here especially for this purpose. The proof utilizes a game similar to Tetris, named here L-tris.

1 Introduction

In my earlier work [2, 3] among other results, I gave the new proof of the famous theorem of Rumer, Teller and Weyl [4] parametrizing a basis of the subspace of SL(2)-invariants of V^{⊗m} = V ⊗ ⋯ ⊗ V (m times), where V is the two-dimensional linear space with the standard action of SL(2), by 1regular graphs with the vertices 1, 2, …, m, edges of which can be drawn in the upper half-plane without intersections.

In this work I construct a basis of the subspace of SL(n)-invariants of V^{⊗m}, where V is the ndimensional linear space with the standard action of SL(n), by the n-wave graphs with m vertices. An n-wave graph is a graph with the vertices 1, 2, …, m, each connected component of which is a path of length n − 1, edges of which can be drawn in the book with n − 1 pages, i. e. n − 1 copies of the upper half-plane, glued along ℝ, such that the first edge of each connected component, {i_{1}i_{2}}, is drawn on the first page, the second edge, {i_{2}i_{3}}, on the second page, and so on, such that i_{1} < i_{2} < ⋯ < i_{n}, without intersections.

∗This research was partially supported by ONR grant N00014-97-1-0505.

2-wave graphs are exactly the same graphs as were used for the description of SL(2)-invariants. Here are two of a total number of five of 3-wave graphs with 6 vertices:

[figure]

The corresponding invariants are

((x ∧ y ∧ z) ⊗ (x ∧ y ∧ z))^{σ_{i}} , i = 1, 2,  (1)

where

σ_{1} = (34) ∈ S_{6}, σ_{2} = (24)(35) ∈ S_{6}.  (2)

Note that the choice (2) of the permutations σ_{i} in (1), is not unique for the given wave graphs. Multiplying σ_{i} by (14)(25)(36), we obtain the same result.

For a wave graph G, denote t_{G} the analogous tensor products of the basic wedge n-forms, see (10).

Theorem 1. Tensors t_{G} parametrized by all n-wave graphs with m vertices, form a basis in the space of SL(n)-invariants in V^{⊗m}.

The proof uses a game similar to Tetris, named here L-tris.

2 The main theorem

In this section we give all the necessary definitions and prove the main theorem.

Let f be a field of characteristic 0, and SL(n) —the group of n × n f-matrices with determinant 1, acting on n-dimensional linear f-space V with basis (x_{1}, …, x_{n}) by the standard way.

Recall some fundamental facts about the representations of SL(n). The word representation will mean below a polynomial finite dimensional linear representation over f. Every representation of SL(n) is equivalent to a sum of irreducible representations. All classes of equivalence of the irreducible representations are parametrized by partitions of length < n. Denote L_{n} the set of partitions of length < n, and denote ρ_{λ} the irreducible representation corresponding to a partition λ ∈ L_{n}. Then ρ_{0} is a trivial representation of dimension 1 and ρ_{1} is the standard representation in V mentioned above. To describe the decomposition of tensor products of irreducible representations, we’ll use Young diagrams.

For a moment, let us draw the Young diagrams rotated by 90^{∘} counterclockwise. Then we can interpret a Young diagram of a partition of length < n as a Tetris position on a Tetris game field of width n, with non-increasing height of columns (looking from the left hand side to the right).

Definition 1. For a partition μ of length < n, denote T_{n}(μ) the set of partitions, Young diagram of which can be obtained from the Young diagram of μ by dropping to it a 1 × 1 block and applying the Tetris rules, i. e. deleting of rows of length n if possible.

Then

ρ_{μ} ⊗ ρ_{1} ≃ ∑_{λ∈T_{n}(μ)} ρ_{λ}  (3)

Lemma 1.

ρ_{1}^{⊗m} ≃ ∑_{\begin{matrix}λ∈L_{n},|λ|≤m \\ |λ|≡mmodn \end{matrix}} f^{τ(λ,m,n)}ρ_{λ},  (4)

where |λ| denotes the weight (i. e. the sum of all parts) of a partition λ; τ(λ, m, n) = λ ⋃ n^{(m−|λ|)/n} is the partition of weight m, Young diagram of which can be obtained from the Young diagram of λ by adding the necessary number of Tetris rows of length n, and f^{τ} is the number of standard tableaux of shape τ.

Proof. By induction on m, by iteration of (3), the Young diagrams of the partitions λ in the right hand side of (4) can be obtained by dropping m 1 × 1 blocks on the Tetris game field and applying the Tetris rules. Sequential numbering of dropping blocks from 1 to m gives us the standard tableaux of shape τ. Conversely, each standard tableaux defines the places where to put each dropping block. Thus, we have a bijection between the set of standard tableaux of shape τ(λ, m, n) and the set of irreducible components of type ρ_{λ} in the total decomposition of the left hand side of (4) according to (3).

Lemma 2. The subspace of SL(n)-invariants of V^{⊗n} is one-dimensional, and we can choose

ω = x_{1} ∧ x_{2} ∧ ⋯ ∧ x_{n}  (5)

as a basis element in that space.

Proof. For a ∈ SL(n),

aω = det a · ω = ω  (6)

It means that ω is invariant. By Lemma 1, the dimension of the space of invariants is equal to f^{τ(0,n,n)} = f^{n} = 1.

Lemma 3. The dimension of the subspace of SL(n)-invariants of V^{⊗m} is nonzero iff m = kn for some integer k, in which case it equals

\frac{m! (1! 2! … (n − 1)!)}{k! (k + 1)! … (k + n − 1)!}.  (7)

Proof. It follows from Lemma 1 that the dimension equals f^{n^{k}}. Using the hook length formula [1], one obtains (7).

Definition 2. An n-wave graph is a graph with the vertices 1, 2, …, m, each connected component of which is a path of length n − 1, edges of which can be drawn in the book with n − 1 pages, i. e. n−1 copies of the upper half-plane, glued along ℝ, such that the first edge, {i_{1}i_{2}}, of each connected component is drawn on the first page, the second edge, {i_{2}i_{3}}, on the second page, and so on, such that i_{1} < i_{2} < ⋯ < i_{n}, without intersections.

Lemma 4. The number of n-wave graphs with m vertices is nonzero iff m = kn for some integer k, in which case it equals (7).

Proof. We’ll construct a bijection between the set of standard rectangular tableaux of shape n^{k} and the set of n-wave graphs with m = kn vertices. More precisely, we’ll construct a bijections between each of the mentioned sets and the set of the lattice words of length m, containing equally k of each letter from the alphabeth A_{n} = {1, 2, …, n}. A lattice word means that reading it from the beginning to any letter, one meets at least as many 1’s as 2’s, at least as many 2’s as 3’s and so on.

Consider a standard tableau as a notation of a Tetris game described above, consisting of sequential dropping of m 1 × 1 blocks. Writing sequentially for each dropping block the number of the column where it drops, one gets a word of length m in the alphabeth A_{n}. It is a lattice word, because we require that the blocks form a Young diagram on every step. For a rectangular tableau of shape n^{k} we’ll get exactly k copies of each letter. Conversely, each word of length m in the alphabeth A_{n} can be considered as a notation of some Tetris game consisting of sequential dropping of m 1 × 1 blocks; each letter shows where the corresponding block drops. Lattice words restrict us to the games in which dropped blocks form a Young diagram on every step, and words containing k copies of each letter, correspond to the tableaux of rectangular n^{k} shape. The constructed mappings are mutually inverse. Thus, we got a bijection.

Now we’ll construct another one. First we’ll work with case n = 2. Use induction on k. For k = 0 each of the sets contain just one element: empty word and empty graph—these sets are bijective. Suppose that we got a bijection for all the values of k less than given. Let α_{1} … α_{2k} be a lattice word containing k 1’s and k 2’s. By definition, α_{1} = 1. Let i be the smallest index such that the subword α_{1} … α_{i} contains the equal number of 1’s and 2’s. Then we draw an edge from 1 to i on the upper half-plane. Deleting 1 and i from the given word, we obtain either one or two words. They are lattice words of length less than 2k, containing equal number of 1’s and 2’s each. By induction, we know the outerplanar graphs corresponding to them. Draw the graph corresponding to the word α_{2} … α_{i−1}, on the vertices 2, …, i − 1, and the graph corresponding to the word α_{i+1} … α_{2k}, on the vertices i + 1, …, 2k; instead of the standard indexing of vertices {1, 2, …, } of outerplanar graphs, preserving only the order; and we obtain an outerplanar graph with vertices 1, 2, …, 2k. Conversely, setting for each edge (i, j) of an outerplanar graph with 2k vertices, with i < j, α_{i} = 1 and α_{j} = 2, we obtain a word α_{1} … α_{2k} with all the necessary conditions. One can check, inductively, that the constructed mappings are mutually inverse. Thus, we got a bijection for the case n = 2.

In the general case, for n > 2, for each lattice word with equally k 1’s, 2’s, …, and n’s; its subwords containing all of the two subsequent letters: 1 and 2, or 2 and 3, …, or n − 1 and n, are lattice words in two-letter alphabets with equally k copies of each letter. Drawing the outerplanar graph corresponding to the first subword on the first page, to the second subword—on the second page, and so on, with the numeration of vertices, coming from the original lattice word using n letters, we obtain a wave graph. Conversely, setting for each edge (i, j) lying on N-th page of a wave graph, where 1 ≤ N ≤ n − 1, with i < j, α_{i} = N, α_{j} = N + 1, we obtain a lattise word α_{1} … α_{m} having k 1’s, k 2’s, …, k n’s. The constructed mappings are mutually inverse. Thus we constructed a bijection.

To complete the proof of the lemma, the same as for the proof of Lemma 3, one can use the hook length formula [1].

Definition 3. For an n-wave graph G, denote O(G) the set of directed n-hypergraphs, the underlying wave graph of which is G. A directed n-hypergraph means a set of vertices V equipped with a set of directed n-edges, i. e. totally ordered subsets of n elements of V. For V = {1, 2, …, m}, the underlying wave graph is a simple graph with the set of vertices V, constructed from the given directed n-hypergraph by drawing for each of its edges (i_{1}, …, i_{n}) a path (j_{1}, j_{2}), (j_{2}, j_{3}), …, (j_{n} − 1, j_{n}) where (j_{1}, …, j_{n}) is such permutation of (i_{1}, …, i_{n}) that j_{1} < j_{2} < ⋯ < j_{n} and we draw each edge (j_{N}, j_{N+1}) on the N-th page of our book.

To define an element of O(G), we have to introduce a linear ordering on every connected component of G. Hence, the number of elements of O(G) is equal to (n!)^{k} for a n-wave graph with m = kn vertices.

Definition 4. For g ∈ O(G) denote

b_{g} = x_{1}(g) ⊗ ⋯ ⊗ x_{m}(g) ∈ V^{⊗m},  (8)

where x_{i}(g) = x_{or i}, and or i is the ordinal number of vertex i in the unique n-edge of g it belongs. Also denote

t_{G} = ∑_{g∈O(G)}(−1)^{inv g}b_{g},  (9)

where inv g is the number of inversions in g, i. e. the number of pairs of vertices i < j ordered in an opposite way in a directed n-edge of g.

Note that t_{G} is equal to the tensor product of wedge products x_{1} ∧ ⋯ ∧ x_{n} corresponding to the connected components, i. e. waves, of G. In more detail, for a graph G with waves (1, 2, …, n), (n + 1, …, 2n), …, ((k − 1)n + 1, …, kn)

t_{G} = (x_{1} ∧ ⋯ ∧ x_{n})^{⊗k},  (10)

and for other n-wave graphs, t_{G} can be obtained from (10) by corresponding permutation (not unique, in general).

Theorem 1. Tensors t_{G} parametrized by all n-wave graphs with m vertices, form a basis in the space of SL(n)-invariants in V^{⊗m}.

Proof. Lemmas 3 and 4 show that the number of n-wave graphs with m vertices is exactly the same as the dimension of the corresponding space of SL(n)-invariants. The paragraph just before the theorem, Lemma 2 and the fact that a tensor product of invariants is invariant and permutations of the components of a tensor product commute with the action of SL(n), show that t_{G} are SL(n)- invariant. Hence if we prove linearly independence of the set of t_{G}, our theorem will be proven. The proof is completely analogous to the proof of the particular case n = 2 given in my articles [2, 3].

Denote B the standard basis of V^{⊗m}, consisting of n^{m} tensor products X_{1} ⊗ ⋯ ⊗ X_{m} with X_{1}, …, X_{m} ∈ {x_{1}, …, x_{n}}. We suppose that B is ordered lexicographically. Note that b_{g} ∈ B for any g ∈ O(G). Notice that for each G exists exactly one g_{0} ∈ O(G) without inversions—with the orientation of each n-edge from the left to the right. Changing of orientation of g_{0} increases b_{G} in the lexicographical order of B. It means that b_{g_{0}} is the minimal element with a non-zero coefficient in the decomposition of t_{G} in the basis B. Denote b_{G} = b_{g_{0}}. Notice that after deleting all x’s and all ⊗ signs in b_{G}, the remaining indexes form the lattice word corresponding to G by the bijection constructed in the proof of Lemma 4. So, we have f^{n^{k}} elements b_{G} —one for each G.

To prove the linear independence of the set of t_{G}, we can show that the rank of the f^{n^{k}} × n^{m} matrix of the coefficients of t_{G} in the basis B is equal to f^{n^{k}}. To do that, we can find a non-zero f^{n^{k}} ×f^{n^{k}} minor of that matrix. Consider the f^{n^{k}} ×f^{n^{k}} submatrix with rows numbered by G ordered the same way as b_{G}, and columns corresponding to b_{G}. As we noticed above, b_{G} is the first element with a nonzero coefficient in the row G, and this coefficient equals 1 by definition. So, this matrix is unipotent, its determinant equals 1, that completes the proof of the linear independence of t_{G}.

Acnowledgements. I would like to thank my thesis formal and informal advisors, Fan Chung Graham and Alexandre Kirillov, the supervisor of the part of the research supported by ONR grant, Andre Scedrov, our Mathematics Department and Graduate Group Chairpersons, Dennis DeTurck and Chris Croke, as well as UPenn Professors Christos Athanasiadis, Ching-Li Chai, Ted Chinburg, Murray Gerstenhaber, Herman Gluck, Michael Larsen, David Shale, Stephen Shatz, Herb Wilf, and Wolfgang Ziller for useful discussions, and my Gorgeous and Brilliant Wife, Bette, for her total support and love.

References

[1] J. S. Frame, G. de B. Robinson, R. M. Thrall, The hook lengths of S_{n}, Canad. J. Math. 6 (1954), 316–324.

[2] Aleksandrs Mihailovs, Tensor invariants of SL(2) and outerplanar graphs (1997). \underline{http://www.math.upenn.edu/∼mihailov/sl2.dvi} or \underline{sl2.ps}

[3] Aleksandrs Mihailovs, Tensor decompositions for SL(2) and outerplanar graphs (1997). \underline{http://www.math.upenn.edu/∼mihailov/sl2ten.dvi} or \underline{sl2ten.ps}

[4] G. Rumer, E. Teller, and H. Weyl, Eine für die Valenztheorie geeignete Basis der binaren Vektorinvarianten, Nachr. Ges. Wiss. Göttingen Math. -Phys. Kl. (1932), 499–504.