Matrix Representations From Labeled Trees

Charlie Liou and Anthony Mendes Mathematics Department California Polytechnic State University San Luis Obispo, CA 93407 USA

                      cbliou@calpoly.edu
                     aamendes@calpoly.edu

Abstract

Let X be the matrix representation induced by the action of the symmetric group on labeled trees with n vertices. We show that the number of times that the irreducible representation of the symmetric group corresponding to the integer partition (n − 1, 1) appears within X is the number of unlabeled trees with certain conditions.

1 Introduction

Let T_{n} be an ordered list of all labeled trees with n vertices (the order in which the trees are listed is arbitrary but fixed). The symmetric group S_{n} acts on the set of labeled trees by permuting vertex labels. In this way, the list T_{n} is permuted by applying σ ∈ S_{n} to each element in T_{n}. We let X(σ) be the permutation matrix for the permutation found by applying σ to T_{n}.

For example, if n = 5 and the 5^{3} labeled trees on 5 vertices are listed in lexicographic order according to their Prüfer codes, then the matrix representation X sends the transposition (1 2) to the matrix depicted below, where black square indicates a 1 and a white square a 0:

A matrix representation of degree k for a finite group G is a group homomorphism from G to the set of k × k invertible matrices over ℂ. Since there are n^{n−2} labeled trees (see sequence \underline{A000272} in the On-Line Encyclopedia of Integer Sequences), the function X is a matrix representation of degree n^{n−2} for the symmetric group S_{n}.

If A_{1} and A_{2} are matrix representations (of any degree) of G, then their direct sum A_{1}(g) ⊕ A_{2}(g) is the block matrix

[\begin{matrix}A_{1}(g) & 0 \\ 0 & A_{2}(g) \end{matrix}] ,

which is also a matrix representation. A matrix representation R(g) is reducible if there is a constant matrix P and two matrix representations A_{1} and A_{2} such that R(g) = P (A_{1}(g) ⊕ A_{2}(g))P^{−1} for all g ∈ G. A representation that is not reducible is irreducible. Every matrix representation can be expressed in the form

P (A_{1}(g) ⊕ A_{2}(g) ⊕ ⋯ ⊕ A_{k}(g))P^{−1}

for all g ∈ G where A_{1}, …, A_{k} are irreducible representations and P is a fixed matrix.

In this paper we count the number of times certain irreducible representations appear within the representation X. In particular, the irreducible representations for the symmetric group are indexed by the integer partitions of n, and our main result (Theorem 3) says that the number of times that the irreducible representation indexed by the integer partition (n − 1, 1) appears in X is equal to the number of unlabeled trees with a marked edge such that the trees on each side of the marked edge are different. This is sequence \underline{A217420}, which starts with

0, 0, 0, 1, 2, 6, 14, 37, 92, 239, 613, 1607, 4215, …

Along the way we find formulas for the number of times the trivial representation (the representation corresponding with the integer partition (n)) and the sign representation (the representation corresponding with the integer partition (1^{n})) appear within X.

Parking functions are tangentially related to the topic at hand. A parking function of length n is a word w of length n with letters in {1, …, n} such that the i^{th} largest integer in w is not greater than i. There are (n + 1)^{n−1} parking functions of length n, and so the parking functions of length n − 1 are in bijection with labeled trees [5].

An action of S_{n} can be defined on the set of parking functions of length n by permuting positions. Using a bijection that can turn parking functions into labeled trees, this provides an action on labeled trees. There are some known results about how the corresponding matrix representation breaks into irreducible components (for example, there are a Catalan number of copies of the trivial representation) [1, 6]. However, to clarify for those readers familiar with the literature on parking functions, our group action is different and our results here are new.

We conclude this introduction by briefly recalling key theorems and concepts. Readers unfamiliar with the topic are pointed to the references [4].

The character of the matrix representation A(g), denoted χ^{A}(g), is the matrix trace of A(g) for all g ∈ G. The inner product of their characters χ^{A} and χ^{B} is

⟨χ^{A}, χ^{B}⟩ = \frac{1}{|G|} ∑_{g∈G} χ^{A}(g)\overline{χ^{B}(g)}.

If B is irreducible, then ⟨χ^{A}, χ^{B}⟩ gives the number of times B appears in A.

The characters of the irreducible representations of S_{n} have a combinatorial interpretation that involves filling Young diagrams of integer partitions with rim hooks. The Young diagram for an integer partition λ = (λ_{1}, λ_{2}, …) is a is a collection of left-justified rows of boxes where row i has λ_{i} boxes reading from top to bottom.

A rim hook of length k is a sequence of k connected cells in the Young diagram for λ that begins in a cell on the southeast boundary and travels up along the southeast edge such that its removal leaves the Young diagram of a smaller integer partition. A rim hook tableau of shape λ and filling μ is a iterative filling of the Young diagram of the integer partition λ with rim hooks of lengths found in the parts in μ. Below we show both rim hook tableaux of shape (8, 1) with filling (3, 3, 2, 1):

1 2 3 4  1 2 3 4

The sign of a rim hook tableau is (−1)^{v} where v is the number of times a rim hook in the tableau has a vertical step. The signs of the above rim hook tableaux are −1 and 1, respectively.

The irreducible representations of S_{n} are indexed by integer partitions of n, and the character χ^{λ} corresponding to the integer partition λ can be found using the Murnaghan-Nakayama rule: if σ ∈ S_{n} has cycle type μ (the cycle type of σ is the integer partition found by listing the lengths of σ in cycle notation), then

χ^{λ}(σ) = ∑_{R} sign(R)  (1)

where the sum ranges over all rim hook tableaux R of shape λ and filling μ. For example, if σ is a permutation with cycle type (3, 3, 2, 1), the two above rim hook tableaux show that χ^{(8,1)}(σ) = 0.

The sum in (1) is unchanged if the order that the rim hooks in μ are inserted into the Young diagram for λ is permuted [3, 7]. For example, if the rim hooks in the above example are inserted in the order (2, 3, 3, 1), then we find the two rim hook tableaux of shape (8, 1) with filling (2, 3, 3, 1) with signed sum still equal to 0:

1 2 3 4  1 2 3 4

A calculation with fewer rim hook tableaux can be had if we place the rim hooks in the order (1, 2, 3, 3), since then there are no possible rim hook tableaux of shape (8, 1) with filling (1, 2, 3, 3), giving a signed sum of 0.

2 Results

We begin with two easy facts about the number of times the trivial and the sign representations appear in X. Even though the proofs are routine, we record the results here because similar ideas are used in Theorem 3. Beyond trees, Theorems 1 and 2 can be generalized in a straightforward manner to any matrix representation defined from a group action.

Theorem 1. The number of times the trivial representation appears in X is the number of unlabeled trees on n vertices.

Proof. The number of times the trivial representation appears in X is

⟨χ^{X}, 1⟩ = \frac{1}{n!} ∑_{σ∈S_{n}} χ^{X}(σ).  (2)

The value of the character χ^{X} on a permutation σ is the trace of X(σ), which is equal to the number of labeled trees fixed by σ. Burnside’s lemma now tells us that (2) is the number of orbits under the group action of S_{n} on labeled trees; in other words, the number of unlabeled trees.

Theorem 2. The number of times the sign representation appears in X is the number of unlabeled trees on n vertices with no odd automorphisms.

Proof. Since χ^{X}(σ) enumerates trees fixed by σ, the number of times the sign representation appears in X is

⟨χ^{X}, sign σ⟩ = \frac{1}{n!} ∑_{σ∈S_{n}} χ^{X}(σ) sign σ = \frac{1}{n!} ∑_{T} ∑_{σ∈aut(T)} sign σ

where the first sum is over all labeled trees T on n vertices and aut(T) is the automorphism group for T. Every subgroup of S_{n} either does not contain an odd automorphism or exactly half of the subgroup contains odd automorphisms. If there are no odd automorphisms, then the proof is complete using the same idea as the proof of Theorem 1. If exactly half of the subgroup is odd, then sum in (2) is 0, as needed.

Theorem 3. Let m be the number of unlabeled trees on n vertices with a marked edge such that the trees on each side of the marked edge are different. The number of copies of the irreducible representation indexed by the integer partition (n − 1, 1) in X is equal to m.

Proof. The number of times that the irreducible representation corresponding to (n − 1, 1) appears in X is

⟨χ^{X}, χ^{(n−1,1)}⟩ = \frac{1}{n!} ∑_{σ∈S_{n}} χ^{X}(σ)\overline{χ^{(n−1,1)}(σ)} = \frac{1}{n!} ∑_{T} ∑_{σ∈aut(T)} ∑_{R} sign(R)

where the first sum is over all labeled trees T on n vertices, aut(T) is the automorphism group for T (expressed as a subgroup of S_{n}), and R is a rim hook tableau of shape (n − 1, 1) with filling the cycle type of σ. So it is enough to prove that

n!m = ∑_{T} ∑_{σ∈aut(T)} ∑_{R} sign(R).

For this we define a sign-reversing involution ϑ on the set of signed triples of the form (T, σ, R) where T is a labeled tree, σ ∈ aut(T), R is a rim hook tableau of shape (n − 1, 1) with filling the cycle type of σ, and the sign is the sign of R. The number of fixed points under ϑ is n!m.

Given (T, σ, R), draw T in the plane in the following way:

1. The center of T is subgraph containing the vertices v that minimize max_{w∈T} d(v, w) where d(v, w) is the distance from v to w. The center of a tree is either a single vertex or a pair of adjacent vertices [2]. Draw the center above all other vertices in T. If the center of the tree contains two vertices, place the vertex with the smaller label on the left.

2. Draw the remaining vertices in T below this center in levels according to their distance to the center. Write the children of each vertex in increasing order from left to right.

For example, the following tree with n = 19 vertices is drawn in this way:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

We can choose the order in which the lengths of the rim hooks are placed into R without affecting (1). Place the rim hooks with lengths given by the cycle lengths of σ in increasing order into R. For example, if we take σ = (2 15)(3 17)(5 11)(4 9 16) to be the permutation in S_{19} that fixes the above tree, then rim hooks of lengths 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3 are placed into the Young diagram of the integer partition (18, 1). One possible choice for such an R is here:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Beginning with the leftmost center vertex, order the vertices in T by when they are first visited in a depth first search. For example, the above tree produces the order

12 1 5 11 7 13 6 2 15 14 19 18 3 8 10 4 9 16 17.

Sort the fixed points of σ in this depth first order. Using the above example for σ, the fixed points in σ are

12 1 7 13 6 14 19 18 8 10.

If σ has a fixed point, a rim hook of length 1 with label 1 is placed first in R. This forces another rim hook of length 1 to occupy the single cell in the second row of R. Suppose the rim hook of length 1 in the second row of R has label k. Underline the k^{th} fixed point in σ to create σ′. It is possible that σ does not have any fixed points, in which case nothing is underlined. In the above example we have k = 8, and so we underline the eighth fixed point in the depth first search order, namely 18. This gives

σ′ = (2 15)(3 17)(5 11)(4 9 16)\underline{(18)}

From T and σ′ we can reconstruct the triple (T, σ, R). If a fixed point is underlined in σ′, then the underlined element can be used to determine which rim hook appears in the second row of R. If there is not an underlined fixed point in σ′, then σ cannot contain any fixed points at all. In this case and only in this case, the rim hook tableau R has sign −1 because its first rim hook spans the first two rows.

Now we can describe the involution ϑ on pairs of the form (T, σ′):

Case 1: σ′ does not have a fixed point.

The sign of R is negative here, and this is the only case that there can be a negative sign.

Since σ does not have a fixed point, the center of T is not a single vertex (because automorphisms preserve the center) and the two trees on either side of the center are isomorphic. Indeed, σ acts on T by interchanging the two vertices in the center, and thus must also interchange the trees on either side. So, if i and j are the elements in the center of T, then the transposition (i j) must be a cycle in σ.

Let α be the lexicographically least element in the automorphism group for T that does not fix the center; that is, α is the lexicographically least element that contains (i j) as a cycle. Define ϑ((T, σ′)) = (T, τ′) where τ′ is ασ with the larger of the two vertices in the center of T underlined. This output is an object accounted for in Case 2.

Case 2: The center of T is two adjacent vertices, the two trees on either side of the center are isomorphic, and the underlined element in σ′ is appears in the center of T.

Because rim hooks are placed into R by placing cycles of length 1 first and since these one cycles are ordered according to the depth first search, the first rim hook inserted into R corresponds to the smaller of the two vertices in the center. Therefore if an element in the center of T is underlined in σ, then it is the larger of the two elements in the center that is underlined.

Define ϑ((T, σ′)) to be the inverse operation as in Case 1. In particular, if α is the lexicographically least element in the automorphism group for T that does not fix the center, then ϑ((T, σ′)) = (T, α^{−1}σ′) where the underline is erased in α^{−1}σ′.

Case 3: Not Case 1 or Case 2.

If we are not in Case 1 or Case 2, then T is not a tree with a center containing two adjacent vertices such that the trees on either side of the center are isomorphic. Further, the permutation σ′ must have a marked fixed point. In this case we define ϑ((T, σ′)) = (T, σ′).

We now show that fixed points under ϑ are counted by n!m. Given (T, σ′) is fixed under ϑ, mark the edge in T that is traversed immediately before

the underlined vertex in σ′ is visited in the depth first search to create T′. The trees on each side of the marked edge in T′ are different by construction. Our running example has vertex 18 underlined, so the edge connecting 12 and 18 would be marked.

We are now counting pairs (T′, σ) where T′ is a labeled tree with n vertices, a marked edge, distinct trees on either side marked edge, and σ is a permutation that fixes T′. Using similar reasoning as in the proof of Theorem 1, Burnside’s lemma says that the number of such pairs is n!m, as needed.

References

[1] A. Berget and B. Rhoades, Extending the parking space, J. Combin. Theory Ser. A 123 (2014), 43–56.

[2] C. Jordan, Sur les assemblages de lignes, J. Reine Angew. Math. 70 (1869), 185–190.

[3] A. Mendes, The combinatorics of rim hook tableaux, Australas. J. Combin. 73 (2019), 132–148.

[4] B. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Springer, 2001.

[5] M. P. Schützenberger, On an enumeration problem, J. Combinatorial Theory 4 (1968), 219–221.

[6] R. P. Stanley, Parking functions and noncrossing partitions, Electron. J. Combin. 4 (2) (1997), #R20.

[7] D. W. Stanton and D. E. White, A Schensted algorithm for rim hook tableaux, J. Combin. Theory Ser. A 40 (1985), 211–247.

2020 Mathematics Subject Classification: Primary 05E10, Secondary 20C30. Keywords: labeled tree, group action, permutation matrix, representation of the symmetric group.

(Concerned with sequences \underline{A000272} and \underline{A217420}.)

Received May 18 2023; revised version received August 14 2023. Published in Journal of Integer Sequences, August 15 2023.

Return to Journal of Integer Sequences home page.