MSC 2010 codes:

1 Overview

The irreducible representations of the symmetric group S n were worked out by Young and Specht in the early twentieth century, and they remain omnipresent in algebraic combinatorics. The symmetric group S n has a unique irreducible representation for each partition of \(n \in \mathbb{N}\). For example, S 4 has exactly five irreducible representations corresponding to the integer partitions (4), (3, 1), (2, 2), (2, 1, 1) and (1, 1, 1, 1). Young and Specht constructed these irreducible representations, which are now called Specht modules . Young [20] gave a matrix representation and Specht [18] gave a combinatorial spanning set. Garnir [8] later explained how to rewrite Specht’s spanning set in terms of Young’s basis, which are now called Garnir relations. Modern accounts can be found in Sagan [16] or James and Kerber [10].

The classical approach, however, privileges Young’s basis over other bases and the Garnir relations over other linear dependencies. Focusing on Young’s basis and the Garnir relations immediately breaks the symmetry of Specht’s spanning set and ignores its other combinatorial properties. Certainly, there are linear relations other than those given by Garnir and bases other than those given by Young to investigate!

To this end, we introduce the Specht matroid , which encodes all the linear dependencies among the vectors of Specht’s spanning set. We also introduce the Specht polytope , which provides a way to visualize the Specht module, since the polytope sits inside the corresponding real vector space with positive volume, and the action of the symmetric group takes the polytope to itself. In the case of the partition (n − 1, 1), we recover both classical constructions and objects of current research interest. The corresponding Specht polytope is essentially the root polytope of type A n . In Theorem 7.5, we record a result of Ardila, Beck, Hoşten, Pfeifle and Seashore [2] describing the faces of this polytope. The Specht matroid for the partition (n − 1, 1) is the matroid of the braid arrangement, and hence its Chow ring is the cohomology ring for the moduli space \(\overline{\mathcal{M}_{0,n}}\) of n marked points on the complex projective line [4, 6]. We compute further examples of Chow rings in Sect. 5, including the solution to Problem 1 on Grassmannians in [19], which partially inspired this project. We state a combinatorial conjecture for the graded dimensions of the Chow rings for the Specht matroid for the partition (2, 1n−1). However, we do not study any further connections with moduli spaces.

Our approach allows us to upgrade familiar combinatorial coefficients to matroids and polytopes. By analogy with categorification, which sometimes upgrades numbers to vector spaces, we call this process matroidification, or polytopification when working over the reals. This is the subject of Sect. 8. In Theorem 8.3, we polytopify the Kronecker coefficients , building the Kronecker polytopes. We also construct the Kronecker matroids encoding the Garnir-style rewriting rules that govern linear dependence in a tensor product of Specht modules. An analogue of Young’s basis for the Kronecker matroid would provide a combinatorial rule for computing Kronecker coefficients. In Theorems 8.6 and 8.9, we give similar results for Littlewood–Richardson coefficients and plethysm coefficients.

The outline of the article is as follows. We begin in Sect. 2 with a self-contained construction of the Specht module. This construction is a bit unusual in that it makes no mention of tabloids, polytabloids, standard tableaux, or the group algebra. In Sect. 4, 5, and 6, we introduce respectively the Specht matroid, its Chow ring, and the Specht polytope; we then prove some basic general facts about them. Section 7 is devoted to the partitions (n − 1, 1) and (2, 1n−1), for which the Specht matroids and polytopes coincide with other well-studied objects. We describe Kronecker, Littlewood–Richardson, and plethysm matroids and polytopes in Sect. 8. Section 9 includes code for calculating the objects described in this paper.

2 Introduction to Specht Modules

This section gives an exposition of the representation theory of the symmetric group motivated by elementary combinatorics. The reader who wishes to start with the main statements should first look at Definitions 2.14 and 2.16, and Theorem 2.18.

We begin with an elementary combinatorics problem: In how many distinct ways can the letters in a word TENNESSEE be rearranged? There are 9! ways to move the letters around, but since some letters are repeated, some of these rearrangements give the same string. For example, the four Es can be rearranged to appear in any order without affecting the string. This reasoning gives the following answer:

$$\displaystyle{\#\{\text{rearrangements of}\ {\mathtt{TENNESSEE}}\} = \tfrac{9!} {1!\,4!\,2!\,2!}\,.}$$

The idea of rearranging letters can be formalized as an action of the symmetric group. In our example, the symmetric group S 9 acts on the word TENNESSEE. The stabilizer subgroup of S 9 with respect to the word TENNESSEE is isomorphic to S 1 × S 4 × S 2 × S 2. Hence, the given argument provides an isomorphism of S 9 -sets, which is to say, a bijection that commutes with the group action:

$$\displaystyle{\{\text{rearrangements of }{\mathtt{TENNESSEE}}\} \simeq \tfrac{S_{9}} {S_{1}\times S_{4}\times S_{2}\times S_{2}}.}$$

Using the orbit-stabilizer theorem, we recover the numerical answer above.

Now, we add a layer of complexity. Suppose we wish to understand the S 9-set

$$\displaystyle{\{\text{rearrangements of}\ {\mathtt{TENNESSEE}}\}\times \{\text{rearrangements of }{\mathtt{SASSAFRAS}}\},}$$

where S 9 acts diagonally on the two factors. This diagonal action makes sense because SASSAFRAS has the same number of letters as TENNESSEE. Each factor in this Cartesian product has a single S 9-orbit, but the product certainly does not. The pairs

$$\displaystyle{ \begin{array}{rllll} &\binom{\mathtt{EEEENNSST}}{\mathtt{SSSSAAAFR}}&&\text{and}&\binom{\mathtt{TENNESSEE}}{\mathtt{SASSAFRAS}}\end{array} }$$

cannot be in the same orbit because the upper Es and lower Ss always appear together in the first pair but not in the second. Alternatively, their orbits have different sizes. If we consider a column, such as \({\mathtt{E}\above 0.0pt \mathtt{S}}\), as a compound letter, then the total number of distinct rearrangements of the first compound word is 9! ∕(4! 2! 1! 1! 1! ) = 7560, which does not equal the number 9! ∕(1! 3! 2! 1! 1! 1! ) = 30240 of rearrangements of the second compound word.

For the construction of the Specht module , we are interested in free orbits; an orbit is free if each of its points has trivial stabilizer. In our context, a non-trivial stabilizer comes from repeated columns, so a pair is in a free orbit if and only if all of its columns are distinct. For example, the pair

$$\displaystyle{\binom{\mathtt{SNETNEESE}}{\mathtt{SASSSAFAR}}}$$

has no repeated columns, so its orbit is free. We claim the following:

  • There is only one free orbit, and we have already found it.

  • The proof is basically a picture, and the proof-picture-idea is strong enough to construct a complete set of irreducible representations over \(\mathbb{C}\) for the symmetric group S n . These are the Specht modules . (The story would be the same for any field of characteristic zero.)

In Fig. 1, the boxes provide a simultaneous histogram tallying the letter multiplicities for each word. From the picture, we see that the letter E from the word TENNESSEE must appear once with each of the letters S, A, F, and R. Indeed, in order to keep distinct the four columns in which E appears, E must be paired with each of the four available letters in the bottom row. Removing the four Es from the pool along with one copy of each of the letters S, A, F, and R, we may proceed to pair off N with the two letters S and A. Continuing inductively, we see that the combinations that appear in a valid pair of rearrangements give the boxes in the diagram.

Fig. 1
figure 1

A simultaneous histogram

Full size image

We give some definitions that encode these pictures.

Definition 2.1

A partition of \(n \in \mathbb{N}\) is an integer vector λ: = (λ 1, λ 1, … , λ ℓ ) such that λ 1 ≥ λ 2 ≥ ⋯ ≥ λ ℓ > 0 with λ 1 + λ 2 + ⋯ + λ ℓ = n. The number ℓ: = ℓ(λ) is the length of the partition.

Definition 2.2

A diagram is a finite subset of \(\mathbb{N}_{\geq 1}^{2}\). The elements of a diagram are called boxes. The diagram associated to a partition λ is D(λ): = {(i, j): 1 ≤ j ≤ λ i } where, by convention, λ i = 0 if i > ℓ(λ).

The partition in our running example is (4, 3, 1, 1); its associated diagram is

$$\displaystyle{\{(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(3,1),(4,1)\}.}$$

Throughout, we use matrix coordinates, so (2, 3) denotes the box in the second row and third column.

The following proposition is immediate.

Proposition 2.3

A diagram D corresponds to a partition λ if and only if D is closed under natural coordinatewise partial order. In other words, D = D(λ) for some partition λ if and only if, for any (i, j) ∈ D and any (a, b) with 1 ≤ a ≤ i and 1 ≤ b ≤ j, we have (a, b) ∈ D.

Definition 2.4

We say two words w 1, w 2 of the same length n have complementary rearrangements if the diagonal action of S n on the product

$$\displaystyle{\{\text{rearrangements of }w_{1}\} \times \{\text{rearrangements of }w_{2}\}}$$

has a unique free orbit. Furthermore, if (w 1, w 2) is in this free orbit, then we say w 1 and w 2 are complementary.

As Fig. 1 shows, the words TENNESSEE and SASSAFRAS have complementary rearrangements; these words are not complementary, but the rearrangements TENENEESS and SASSAFRAS are.

Theorem 2.5

Two words w 1, w 2 have complementary rearrangements if and only if there exists a parititon diagram D with the simultaneous histogram property:

$$\displaystyle{\#\,\mathit{\text{occurrences in }}w_{i}\mathit{\text{ of its }}j\mathit{\text{th most-common letter}} = \#\{(d_{1},d_{2}) \in D: d_{i} = j\}\,.}$$

Proof

If we have a partition diagram D with the simultaneous histogram property, then we can put in the box (d 1, d 2) the d 1-th most common letter in w 1 and the d 2-th most common letter in w 2 breaking ties arbitrarily. The boxes have distinct pairs, so there exists at least one free orbit; this orbit is unique by the iterative argument below Fig. 1. In the other direction, rewrite the words using positive integers, so that in each word k appears at least as often as k + 1, and take

$$\displaystyle{D =\{ (d_{1},d_{2}): d_{1}\text{ appears in a column with }d_{2}\text{ in the unique free orbit}\}\,.}$$

□

We use the idea of complementary words to construct irreducible representations of the symmetric group S n . Before doing so, we collect some basic definitions in representation theory.

Definition 2.6

Let G be a group. A (complex) representation of G is a \(\mathbb{C}\)-vector space V along with a linear action of G on V: for any vectors v, w ∈ V, any scalar \(c \in \mathbb{C}\), and any element g ∈ G, we have g ⋅ v + g ⋅ w = g ⋅ (v + w), and c(g ⋅ v) = g ⋅ (cv). Alternatively, the data of a representation can be encoded in a group homomorphism \(G \rightarrow \mathop{\mathrm{GL}}\nolimits (V )\), where \(\mathop{\mathrm{GL}}\nolimits (V )\) is the group of invertible linear automorphisms of V.

Definition 2.7

For representations V and W of the group G, a linear transformation φ: V → W is a map of G representations if φ commutes with the action of G: for all g ∈ G and all v ∈ V, we have φ(g ⋅ v) = g ⋅ (φ(v)).

Definition 2.8

If V and W are representations of G, then the tensor product V ⊗ W is a representation of G under the action g ⋅ (v ⊗ w) = (g ⋅ v) ⊗ (g ⋅ w).

Definition 2.9

If V is a representation of G, then its dual \(V ^{\vee }:=\mathop{ \mathrm{Hom}}\nolimits (V, \mathbb{C})\) has the linear action of G such that, for f ∈ V ∨ and g ∈ G, the functional g ⋅ f satisfies (g ⋅ f)(v) = f(g −1 ⋅ v) for any v ∈ V.

We also need two definitions specific to the symmetric group S n .

Definition 2.10

For any \(n \in \mathbb{N}\), the representation ɛ is the one-dimensional vector space on which S n acts by sign. More precisely, for v ∈ ɛ, we have g ⋅ v = v if g is an even permutation and g ⋅ v = −v if g is an odd permutation. If V is any representation of S n , then V ⊗ɛ is isomorphic to V as a vector space, but the action of S n differs in that the action of an odd permutation picks up a sign.

Definition 2.11

Given a word w, the representation V (w) is the vector space with basis given by the rearrangements of w, with S n acting by permuting our basis according to how it rearranges words.

The representation V (w) is special in that the action of S n is actually induced from a combinatorial action of S n on a basis of V (w). This property has a useful consequence.

Lemma 2.12

Given any word w of length n, we have a canonical isomorphism of S n representations V (w) ≃ V (w)∨ given by identifying our basis of rearrangements with its dual basis.

Proof

Since V (w 1) has a canonical basis {v r }, where r is an arbitrary rearrangement, the vector space V (w 1)∨ has a dual basis {f r }, and

$$\displaystyle{(\sigma \cdot f_{r})(v_{r^{{\prime}}}) = \left \{\begin{array}{ll} 1&\text{if }r^{{\prime}} =\sigma \cdot r, \\ 0&\text{if }r^{{\prime}}\neq \sigma \cdot r. \end{array} \right.}$$

Since σ ⋅ f r = f σ⋅ r , the map v r ↦ f r is an isomorphism of S n representations. □

We are now ready to construct representations of S n using the combinatorics of complementary words; see Definition 2.4.

Corollary 2.13

If w 1 and w 2 are words of length n with complementary rearrangements, then there is a unique-up-to-scaling map φ: V (w 2) ⊗ɛ ⟶ V (w 1) of S n representations and the image of φ is an irreducible representation.

Proof

Consider an arbitrary map Ψ: V (w 2) ⊗ V (w 1)∨ → ε of S n representations; the linear map Ψ satisfies σ ⋅ Ψ(v) = Ψ(σ ⋅ v) for all v. Any such map must factor through the quotient V (w 2) ⊗ V (w 1)∨∕W, where W is the subspace spanned by elements of the form \(\big(\mathop{\mathrm{sign}}\nolimits (\sigma )v -\sigma v\big)\) for all v. In this quotient, any element of S n acts on the image of any vector by sign. Pairs of rearrangements form a basis for the tensor product, so the images of these basis vectors still span the quotient. If some pair of rearrangements has a repeated column, then swapping those columns fixes the pair. The vectors indexed by such pairs become zero in the quotient because transpositions are odd.

By Theorem 2.5, the action on pairs has a unique free orbit. Any two vectors in the free orbit are related by a unique permutation, and so any vector spans the quotient, which must therefore be one-dimensional. Using tensor-hom adjunction,

$$\displaystyle\begin{array}{rcl} \mathop{\mathrm{Hom}}\nolimits \big(V (w_{2}) \otimes V (w_{1})^{\vee }/W,\varepsilon \big)& \simeq & \mathop{\mathrm{Hom}}\nolimits \big(V (w_{ 2}) \otimes V (w_{1})^{\vee },\varepsilon \big) {}\\ & \simeq & \mathop{\mathrm{Hom}}\nolimits \big(V (w_{2})\otimes \varepsilon,V (w_{1})\big)\,, {}\\ \end{array}$$

where the first space is one-dimensional by the first paragraph. All isomorphisms are natural. We may take φ to be any nonzero vector in the last hom-space. This shows we have a unique-up-to-scaling linear map φ: V (w 2) ⊗ɛ ⟶ V (w 1).

Now, we show that \(V =\mathop{ \mathrm{Im}}\nolimits \varphi\) is irreducible. Suppose U ⊂ V is a proper subrepresentation. By Maschke’s Theorem, there exists a complementary subrepresentation U ′ ⊆ V with the property that V = U ⊕ U ′. Let π: V → V denote the projection with kernel U ′ and image U. But the composite \(V (w_{2}) \otimes \varepsilon \longrightarrow V \mathop{\longrightarrow }\limits^{\pi }V \longrightarrow V (w_{1})\) cannot be a scalar multiple of φ because it is nonzero and has a different image. □

The next definition helps us write an explicit example of the linear map φ.

Definition 2.14

Let w 1, w 2 be fixed words of length n, and let r 1 and r 2 be arbitrary rearrangements of w 1 and w 2 respectively. Define Young’s character to be

$$\displaystyle{\mathop{\mathrm{Y}}\nolimits _{w_{1},w_{2}}(r_{1},r_{2}):=\sum _{\sigma }\mathop{\mathrm{sign}}\nolimits (\sigma ),}$$

where σ ∈ S n ranges over all permutations such that σ ⋅ w 1 = r 1 and σ ⋅ w 2 = r 2.

Proposition 2.15

Young’s character takes values in { − 1, 0, 1}. Whenever writing r 2 on top of r 1 has a repeated column, we have \(\mathop{\mathrm{Y}}\nolimits _{w_{1},w_{2}}(r_{1},r_{2}) = 0\) . If w 1 and w 2 are complementary, then \(\mathop{\mathrm{Y}}\nolimits _{w_{1},w_{2}}(r_{1},r_{2})\neq 0\) exactly when all columns are distinct.

Proof

If there is a repeated column, then interchanging those columns does not change the value of \(\mathop{\mathrm{Y}}\nolimits\), but it also introduces a sign change (since interchanging two columns is an odd permutation). It follows that \(\mathop{\mathrm{Y}}\nolimits = 0\) in this case. If all the columns are distinct, then there is at most one permutation carrying each row back to w i , and so the sum either is empty or has a single term. In the event that w 1 and w 2 are complementary, the sum is nonempty. □

Definition 2.16

If w 1, w 2 are complementary words of length n, the Specht matrix φ(w 1, w 2) is the {rearrangements of w 1} ×{rearrangements of w 2} matrix with (r 1, r 2)-entry equal to \(\mathop{\mathrm{Y}}\nolimits _{w_{1},w_{2}}(r_{1},r_{2})\). If w 1 and w 2 are not complementary but have complementary rearrangements, then we choose complementary rearrangements w 1 ′ and w 2 ′ of w 1 and w 2 respectively and define the Specht matrix φ(w 1, w 2) to be φ(w 1 ′, w 2 ′). The column-span of the Specht matrix (as a subspace of V (w 1)) is the Specht module V (w 1, w 2). The symmetric group acts on V (w 1, w 2) by permuting the rearrangements of w 1.

When w 1 and w 2 are not themselves complementary, the Specht matrix φ(w 1, w 2) is only defined up to a global choice of sign depending on which complementary rearrangements are chosen, but the Specht module is independent of this choice.

Example 2.17

For the words w 1 = 1 1 2 2 and w 2 = 1 2 1 2, the Specht matrix φ(1 1 2 2, 1 2 1 2) is shown in Table 1. We now describe the action of S n on the rows of this Specht matrix. Consider the action of σ = (1 2 3) on the row word w 1. This action changes the order of rows to 2 1 1 2, 1 2 1 2, 2 2 1 1, 1 2 2 1, 2 1 2 1 and 1 1 2 2. What effect does it have on the columns of the Specht matrix? Let us look, for example, at the first column, labelled by 1 1 2 2. With the new row order this column becomes c = (−1, 1, 0, −1, 1, 0), which is the original column for r 2 = 2 1 1 2. If we consider also the action of σ on the rearrangements of w 2, we see that the rearrangement r 2 = 2 1 1 2 of w 2 becomes σ ⋅ 2112 = 1 1 2 2, which is the label of the first column. The permutation σ acts this way on the Specht module.

Table 1 Specht matrix φ(1 1 2 2, 1 2 1 2)
Full size table

We have the following fundamental fact about this representation.

Theorem 2.18

The Specht module V (w 1, w 2) is an irreducible representation of S n .

Proof

By the proof of Corollary 2.13, we see that having a unique free orbit gives a unique-up-to-scaling map φ: V (w 2) ⊗ɛ → V (w 1) whose image is irreducible. It remains only to show that the Specht matrix provides an explicit choice for φ. This was accomplished in Proposition 2.15, which shows that \(\mathop{\mathrm{Y}}\nolimits\) provides a map ɛ → V (w 1) ⊗ V (w 2)∨, where we have used the fact that the actions of S n on V (w 2) and V (w 2)∨ are canonically equal. □

The representation does not actually depend on the words but only on the partition diagram, so we make the following definition:

Definition 2.19

If λ is a partition of n, then the Specht module V (λ) is the Specht module V (w 1, w 2) for any choice of complementary w 1 and w 2 such that the diagram showing w 1 and w 2 are complementary is D(λ). We call w 1 the row word and w 2 the column word.

For example, the matrix in Example 2.17 is the Specht matrix V (2, 2).

Remark 2.20

Since every entry of the Specht matrix is a 0, 1, or − 1, the Specht module can be similarly defined over any field. However, over a field of positive characteristic, Maschke’s Theorem does not hold. Nevertheless, over any field of characteristic other than 2, the statements above show that the Specht module is indecomposable, meaning that V (w 1, w 2) cannot be written as the direct sum of two subrepresentations.

If w 1 and w 2 are complementary words with associated diagram D, then w 2 and w 1 are also complementary, with an associated diagram which is the transpose of D. It will be useful to have a definition describing this relationship.

Definition 2.21

Given a partition λ, the conjugate partition λ ∗ is the partition whose diagram D(λ ∗) is the transpose of the diagram D(λ). Formally, we have λ i ∗ = #{k: λ k ≥ i}.

For example, if λ = (4, 3, 1, 1), then λ ∗ = (4, 2, 2, 1). This natural combinatorial construction has the following representation-theoretic meaning.

Theorem 2.22

We have an isomorphism of S n representations V (λ ∗) ≃ V (λ)∨⊗ɛ.

Proof

Transposing the Specht matrix ϕ(w 1, w 2) gives the Specht matrix ϕ(w 2, w 1), which is the Specht matrix for the conjugate partition. After transposing, the symmetric group acts on ϕ(w 2, w 1) by rearranging the column word w 1. This is not the correct action of the symmetric group on the Specht matrix; the action is off only by a sign and a dual because, by the identity \(\mathop{\mathrm{Y}}\nolimits (w_{2},\sigma w_{1}) = (-1)^{\sigma } \cdot \mathop{\mathrm{Y}}\nolimits (\sigma ^{-1}w_{2},w_{1})\), the symmetric group acts on the row word w 2 by σ −1 and picks up a sign with odd permutations. □

Remark 2.23

We have not needed it, but it is actually the case that Specht modules are self-dual in the sense that there is an abstract isomorphism V (λ)∨ ≃ V (λ). Choosing a basis from the columns of the Specht matrix, it would be possible to write matrices for the action of the symmetric group. Evidently, these matrices would contain only real numbers—in fact, only rational numbers—and so their traces would be real as well. It follows that the character of a Specht module is real, and so its dual, whose character is given by complex conjugation, is the same. With this fact in mind, Theorem 2.22 gives that \(V (\lambda ^{{\ast}})\cong V (\lambda )\otimes \varepsilon\).

We remark briefly on the relationship between the construction above and the more traditional presentation found in James and Kerber [10, Chap. 7.1] or Sagan [16, Chap. 2.3]. In the usual construction, one defines a column-strict filling of λ to be a labelling of D(λ) by the integers {1, 2, … , n} such that every column is strictly increasing. Then, for each column-strict filling T, one associates an element v T in an abstractly defined vector space, and the Specht module is the span of the vectors v T as one takes all possible fillings T. In the definition of Specht module V (λ) used here (Definition 2.19), we start with a word w 2, which we can take to be \(w_{2} = 1^{\mu _{1}}2^{\mu _{2}}\cdots k^{\mu _{k}}\), where μ = λ ∗ and k = λ 1. Each rearrangement r of the word w 2 gives a column of the corresponding Specht matrix, which we can interpret as a vector v r , and V (λ) is defined as the span of the vectors v r as one takes all possible rearrangements r. For each rearrangement r of w 2, one can define an associated filling T r : the one where the labels in column i are the positions of the appearances of i in r. For example, if λ = (4, 3, 1, 1), so w 2 = 111122334, and we take r = 131243112 (or r = ESENTSEEN if we let w 2 = TENNESSEE), then T r is

This correspondence between column-strict fillings and rearrangements essentially gives the correspondence between our version and the usual version. Our version, however, sometimes differs by a sign (when the minimal rearrangement of w 2 to r is by an odd permutation). This sign turns out to be useful; for instance, Theorem 6.2 would be harder to state otherwise.

3 A Complete Set of Irreducible Representations

The Specht modules V (λ) as λ varies over all partitions of n form a complete set of finite-dimensional irreducible representations for S n . The usual proof, found in [16, Sect. 2.4], shows that \(V (\lambda )\not\cong V (\mu )\) for λ ≠ μ. Since there are as many conjugacy classes of S n as there are partitions of n, we have all the irreducible representations. We give a new and different argument that the Specht modules are a complete set of irreducibles assuming an unproven combinatorial conjecture.

Definition 3.1

In a diagram D, the hook of a box d ∈ D consists of the box d, all boxes directly to the right of d, and all boxes directly below d. In other words, if d = (i, j) ∈ D, the hook of d is the set of all (a, b) ∈ D such that a ≥ i and b = j or a = i and b ≥ j. The hook length of a box Γ(d) is the number of boxes in its hook.

Fig. 2
figure 2

A hook with six boxes inside the diagram D(λ) for λ = (6, 5, 3, 3)

Full size image

Definition 3.2

The dimension of a diagram D with n boxes is \(\dim D:= \frac{n!} {\prod _{d\in D}\varGamma (d)}\).

By a beautiful result of Frame, Robinson, and Thrall [7], the dimension of a diagram equals the number of standard Young tableaux, which is the dimension of its Specht module . A bijective proof of this result was later given by Novelli, Pak, and Stoyanovskii [13]. Consequently, dimD is always an integer (Fig. 2).

An ordered set partition of a finite set S is a sequence (P 1, P 2, … , P ℓ ) of subsets of S such that each P i is nonempty, \(P_{i} \cap P_{j} = \varnothing\) for all i ≠ j, and \(\bigcup _{i}P_{i} = S\). An ordered set partition is properly ordered if the parts are nonincreasing in size, so #P i ≥ #P i+1 for all i. For each properly ordered set partition P = (P 1, P 2, … , P ℓ ) of the set {1, 2, … , n}, pick a word w P of length n so that the ith and jth letters of w P match if and only if i and j are in the same P k . For each P, choose also a word w P ′ so that w P and w P ′ are complementary. Every properly ordered set partition P gives rise to an underlying partition λ(P) with λ(P) i = #P i . A set partition with parts of distinct sizes will have only one proper ordering, but a set partition with parts of equal sizes will have more. For notational simplicity, set \(d(P):=\dim D\big(\lambda (P)\big)\).

While searching for a Specht matrix proof that every irreducible representation of the symmetric group is isomorphic to some Specht module, we uncovered the following conjecture, which has been checked for n ≤ 5.

Conjecture 3.3

If σ, τ ∈ S n are two permutations, then Young’s character in Definition 2.14 satisfies

$$\displaystyle{\sum _{P}\sum _{r}d(P)^{2}\mathop{ \mathrm{Y}}\nolimits (\sigma w_{ P},r)\mathop{\mathrm{Y}}\nolimits (\tau w_{P},r) = \left \{\begin{array}{@{}l@{\quad }l@{}} (n!)^{2}\quad &\text{if }\sigma =\tau \\ 0 \quad &\text{if }\sigma \neq \tau, \end{array} \right.}$$

where the first sum is over all properly ordered set partitions of {1, 2, … , n}, and the second sum is over all rearrangements of the word w P ′.

For our application, we desire a proof of the conjecture that does not make use of the following theorem.

Theorem 3.4

Every irreducible representation of S n arises exactly once from a diagram with n boxes.

Proof

This proof assumes Conjecture 3.3. There are three parts: first, we build a block matrix whose blocks are built from Specht matrices; second, we use the conjecture to show that this matrix has full rank; finally, we conclude that the regular representation \(\mathbb{C}S_{n}\) is spanned by a sum of Specht modules .

Build a block matrix M with a single block row and a block column for every properly ordered set partition P of the set {1, 2, … , n}. The block M P associated to P is a matrix whose rows are indexed by S n and whose columns are indexed by the rearrangements of w P ′. The (σ, r)-entry of M P is \(\mathop{\mathrm{Y}}\nolimits _{w_{P},w_{P}^{{\prime}}}(\sigma w_{P},r)\). The rows of M P come directly from the Specht matrix associated to the complementary pair (w P , w P ′), so the column-span of M P is isomorphic to the Specht module V (λ P ).

Conjecture 3.3 asserts that the rows of this block matrix are orthogonal under the inner product given by the diagonal inner product 〈u, v〉 = ∑ P; r d(P)2 ⋅ (u P; r v P; r ), where u P; r denotes the entry of u in the column indexed by P and r. Consequently, the block matrix M has full rank.

The natural action of S n by permuting the rows of this matrix is the regular representation \(\mathbb{C}S_{n}\). Since M has full rank, the image of M must be the regular representation. On the other hand, the image of M is the span of the images of M P , and the image of each M P is isomorphic to some Specht module V (λ P ). Hence, the regular representation is spanned by a sum of Specht modules .

The regular representation always contains a copy of every irreducible representation, so every irreducible representation of S n is isomorphic to the Specht module V (λ) for some partition λ. Since there are as many conjugacy classes of S n as there are partitions of n, and the number of distinct irreducible representations is always equal to the number of conjugacy classes, the Specht modules must be distinct. □

4 Specht Matroids

A matroid is a combinatorial generalization of the dependence relations among a finite set of vectors in a vector space. This structure can be defined in many equivalent ways, each with an axiomatization on some collection of subsets of a ground set E, which is the abstraction of our original set of vectors. Because of the presence of many equivalent definitions, each useful in a different context, it has become customary not to define the word “matroid” but instead to only give definitions of the bases, independent sets, circuits, rank function, or other linear algebra notion associated to the underlying object M, the matroid. Since we will only work with matroids that come from a set of vectors in a \(\mathbb{C}\)-vector space (so called \(\mathbb{C}\) -representable matroids), we do not give any of these abstract definitions. We refer the interested reader to [15].

Let E be a finite set, which we take to be {1, 2, … , k} for convenience, and let {v i : i ∈ E} be a set of vectors spanning a vector space \(\mathbb{C}^{n}\). A subset B ⊆ E is a basis of the matroid M(v 1, v 2, … , v k ) if {v i : i ∈ I} is a basis of \(\mathbb{C}^{n}\). A subset C ⊆ E is a circuit of M if it is a minimal dependent set: v(C) = {v i : i ∈ C} is dependent but any proper subset of v(C) is independent. Given some subset A ⊂ E, the rank of A, denoted r(A), is the dimension of the subspace spanned by {v i : i ∈ A}. A flat of M is a maximal subset of E of a given rank; in other words, F ⊆ E is a flat if r(F ∪{ i}) > r(F) for all i ∉ F. One can think of each flat F as representing the subspace spanned by {v i : i ∈ F}, which gives a bijection between subspaces spanned by a subset of {v 1, v 2, … , v k } and flats. This correspondence shows that the flats of a matroid M form a lattice under inclusion, called the lattice of flats of M.

Given a partition λ, we define the Specht matroid M(λ) to be the matroid formed from the columns of the Specht matrix for λ. The Specht matrix depends on a global choice of sign coming from the complementary words chosen, but the matroid is independent of this choice.

Example 4.1

We describe the matroid M(2, 2), which is the matroid represented by the columns of the Specht matrix in Example 2.17. The circuits are {1122, 2211}, {1212, 2121}, and {1221, 2112} and all sets of three vectors not containing one of the first three sets. The bases are the 12 different sets of 2 vectors not containing a circuit. One can choose any of the six vectors as the first vector in the basis, which leaves four choices for the second vector, but this procedure chooses every basis twice. The five flats are \(\varnothing\), the three circuits of size 2, and the set of all six vectors.

We characterize the possible circuits of size 2, which also characterizes the flats of rank 1.

Theorem 4.2

The Specht matroid M(λ) has a circuit with two elements if and only if the diagram of λ has two columns of the same size.

Proof

For simplicity, we let μ = λ ∗ and let our complementary words be x and w, where \(w = 1^{\mu _{1}}2^{\mu _{2}}\cdots k^{\mu _{k}}\) (with k = λ 1) and x = 12⋯μ 11⋯μ 2⋯1⋯μ k . The pair (x, w) is part of the free orbit on the rearrangements of (x, w). We could give a proof describing the circuits involving any arbitrary rearrangement r of w. However, since the symmetric group S n acts transitively on the matroid M(λ), we may choose our favorite rearrangement of w, which is w itself. For any other rearrangement r, we have a circuit of two elements involving r if and only if there is a circuit of two elements involving w.

Suppose λ has two columns of the same size, so there exists some i such that μ i = μ i+1. Consider w and the rearrangement r where all the i’s and (i + 1)’s have been switched, so \(r = 1^{\mu _{1}}2^{\mu _{2}}\cdots (i - 1)^{\mu _{i-1}}(i + 1)^{\mu _{i}}(i)^{\mu _{i}}(i + 2)^{\mu _{i+2}}(i + 3)^{\mu _{i+3}}\cdots k^{\mu _{k}}\). For any rearrangement s of the row word, we have \(Y (s,w) = (-1)^{\mu _{i}}Y (s,r)\). Hence, \(v_{w} - (-1)^{\mu _{i}}v_{r} = 0\), and {w, r} forms a circuit.

Now, suppose all the columns of λ are distinct. Suppose r is some rearrangement of w with r ≠ w. We show there is some rearrangement s of the row word such that Y (s, w) ≠ Y (s, r). Let k be the smallest integer such that w k ≠ r k , and let i = w k and j = r k . By our construction of w, j > i, and since the columns of λ are distinct, μ j < μ i . We also have r M = i for some M > m, where m = μ 1 + μ 2 + ⋯ + μ i is the position of the last occurrence of the letter i in w. Now, consider the rearrangement s of the row word switching x k and x m . The pair (s, w) is part of the free orbit, and, in fact, Y (s, w) = −1. However, we have Y (s, r) = 0 because (s M , r M ) = (a, i) for some a < x k and \((s_{k-x_{k}-a},r_{k-x_{k}-a}) = (a,i)\). Therefore, the vectors v r and v w do not form a circuit for any rearrangement r. □

Matroids have a number of interesting invariants. One is the characteristic polynomial, a generalization of the chromatic polynomial for a graphical matroid. The characteristic polynomial p M (t) for a matroid M can be calculated recursively by deletion and contraction, so it is a specialization of the Tutte polynomial T M (x, y). It would be interesting to find formulas or characterizations of the Tutte or characteristic polynomials of Specht matroids.

Example 4.3

For the Specht matroid M(2, 1, 1, 1), we use Sage to compute the Tutte polynomial: T M(2, 1, 1, 1)(x, y) = x 4 + x 3 + x 2 + x + y. The characteristic polynomial is related to the Tutte polynomial by the formula p M (t) = (−1)r(M) T M (1 − t, 0). Since \(r\big(M(2,1,1,1)\big) = 4\), we get p M(2, 1, 1, 1)(t) = t 4 − 5t 3 + 10t 2 − 10t + 4. Similar computations produce p M(3, 2)(t) = t 5 − 15t 4 + 90t 3 − 260t 2 + 350t − 166 and p M(2, 2, 1)(t) = t 5 − 10t 4 + 45t 3 − 105t 2 + 120t − 51.

5 Chow Rings

Given a matroid M, Feichtner and Yuzvinksy [6] (following DeConcini and Procesi [4] in the representable case) define the Chow ring \(A^{{\ast}}(M) \simeq \mathbb{Q}[x_{F}]/I_{M}\) of M as follows. There is one generator x F for each nonempty flat F, and the ideal I M is generated by the following two types of relations: x F x G ∈ I M whenever F and G are incomparable, and ∑ F ⊃ {e} x F ∈ I M for every element e in the ground set.

Remark 5.1

The definition of Feichtner and Yuzvinsky also requires as input a building set, which is a subset of the flats satisfying some combinatorial properties with respect to the lattice. The definition we have given here is the case of the maximal building set, which is the one containing every nonempty flat. A slightly different presentation of the Chow ring appears also in the literature. In [1], Adiprasito, Huh, and Katz use a presentation that differs from the one of Feichtner and Yuzvinksy in not using the generator (which can be rewritten in terms of other generators) corresponding to the entire ground set of M.

The next example gives a solution to Problem 1 on Grassmannians in [19].

Example 5.2

Let us consider the matroid M which is formed from the columns of the matrix

$$\displaystyle{\left [\begin{array}{*{10}c} 1&0&0&1&1&1\\ 0 &1 &0 &2 &3 &4 \\ 0&0&1&0&0&1\\ \end{array} \right ]\,,}$$

where the columns are labelled 0, 1, … , 5. This matrix represents a point in \(\mathop{\mathrm{Gr}}\nolimits (3, \mathbb{C}^{6})\) with 16 nonzero Plücker coordinates . To determine the Chow ring of M, first we list all nonempty flats of M:

$$\displaystyle\begin{array}{rcl} & & \{0\},\{0,1,2,3,4,5\},\{0,1,3,4\},\{0,2\},\{0,5\},\{1\},\{1,2\},\{1,5\}, {}\\ & & \qquad \quad \qquad \qquad \qquad \qquad \{2\},\{2,3\},\{2,4\},\{2,5\},\{3\},\{3,5\},\{4\},\{4,5\},\{5\}. {}\\ \end{array}$$

There is one generator x F of the Chow ring A ∗(M) for each nonempty flat F. The monomial generators in I M coming from pairs of incomparable flats are

$$\displaystyle\begin{array}{rcl} & & x_{0}x_{12}\,,x_{0}x_{15}\,,x_{0}x_{23}\,,x_{0}x_{24}\,,x_{0}x_{25}\,,x_{0}x_{35}\,,x_{0}x_{45}\,,x_{1}x_{02}\,,x_{1}x_{05}\,,x_{1}x_{23}\,,x_{1}x_{24}\,,x_{1}x_{25}\,, {}\\ & & \phantom{W} x_{1}x_{35}\,,x_{1}x_{45}\,,x_{2}x_{05}\,,x_{2}x_{15}\,,x_{2}x_{35}\,,x_{2}x_{45}\,,x_{2}x_{0134}\,,x_{3}x_{02}\,,x_{3}x_{12}\,,x_{3}x_{05}\,,x_{3}x_{15}\,, {}\\ & & \phantom{WW} x_{3}x_{24}\,,x_{3}x_{25}\,,x_{3}x_{45}\,,x_{4}x_{02}\,,x_{4}x_{12}\,,x_{4}x_{05}\,,x_{4}x_{15}\,,x_{4}x_{23}\,,x_{4}x_{25}\,,x_{4}x_{35}\,,x_{5}x_{02}\,, {}\\ & & \phantom{WWW} x_{5}x_{12}\,,x_{5}x_{23}\,,x_{5}x_{24}\,,x_{5}x_{0134}. {}\\ \end{array}$$

The relations in I M of the second type are

$$\displaystyle\begin{array}{rcl} & & x_{0} + x_{02} + x_{05} + x_{0134} + x_{012345}\,,x_{1} + x_{12} + x_{15} + x_{0134} + x_{012345}\,, {}\\ & & \phantom{W} x_{2} + x_{02} + x_{12} + x_{23} + x_{24} + x_{25} + x_{012345}\,,x_{3} + x_{23} + x_{35} + x_{0134} + x_{012345}\,, {}\\ & & \phantom{WW} x_{4} + x_{24} + x_{45} + x_{0134} + x_{012345}\,,\ x_{5} + x_{05} + x_{15} + x_{25} + x_{35} + x_{45} + x_{012345}.{}\\ \end{array}$$

Copying these generators and relations into Macaulay2 (either by hand or using the Sage code in Sect. 9), we obtain that the Hilbert series of A ∗(M) is 1 + 11T + T 2.

Table 2 lists the dimensions of A i(M(λ)) for all partitions λ of n = 4 and n = 5. Every row of Table 2 is palindromic, so \(\dim A^{i}\big(M(\lambda )\big) =\dim A^{d-1-i}\big(M(\lambda )\big)\) for all i, where d = dimV (λ). In fact, the Chow ring A ∗(M) satisfies an algebraic version of Poincaré duality for any matroid M. Feichtner and Yuzvinsky [6, Corollary 2] prove this fact for a representable matroid M by showing that A ∗(M) is the cohomology ring of a smooth, proper algebraic variety. This equality of dimensions is extended to non-representable matroids by Adiprasito, Huh, and Katz [1, Theorem 6.19] as the first major step in their proof of the log-concavity of coefficients of the characteristic polynomial of an arbitrary matroid. Finding a combinatorial interpretation of these dimensions remains an interesting open problem.

Table 2 Dimensions of Chow groups of M(λ)
Full size table

By finding a Gröbner basis for I M and determining the standard monomials, Feichtner and Yuzvinsky describe a monomial basis for A ∗(M) as follows [6, Corollary 1].

Theorem 5.3 (Paraphrased from [6], Corollary 1)

The ring A ∗(M) has a basis consisting of the monomials 1 and \(\prod _{i=1}^{k}x_{F_{i}}^{d_{i}}\) such that F 1 ⊆ F 2 ⊆ ⋯ ⊆ F k and \(0 <d_{i} <\mathop{ \mathrm{rank}}\nolimits (F_{i}) -\mathop{\mathrm{rank}}\nolimits (F_{i-1})\) for all i (considering \(\mathop{\mathrm{rank}}\nolimits (F_{0}) = 0\) by convention).

The next example illustrates how to use Theorem 5.3.

Example 5.4

Consider the Specht matroid M(2, 1, 1, 1), which is a uniform matroid on five elements. Denote the elements of its ground set by {0, 1, 2, 3, 4}. Using Sage , we get the list of nonempty flats of M(2, 1, 1, 1) in Table 3. By considering one element sequences of flats, we get one monomial of degree 1 from each flat of rank greater than 1. This gives 21 monomials of degree 1. Flats of rank 1 do not contribute to the list of monomials because there is no integer d such that 0 < d < 1.

Table 3 Nonempty flats of M(2, 1, 1, 1)
Full size table

We can get a monomial of degree 2 in two ways. Quadratic monomials which are a square of only one variable are obtained from one element sequences consisting of flats of rank greater than 2. There are 11 such flats. For the other quadratic monomials, we need to consider sequences of flats of length 2 such that the rank of the first element and the difference between the ranks of the two elements are each at least 2. In our case we get 10 such sequences. They are of the form F k ⊂ F {0, 1, 2,3,4}, where F k is a flat of rank 2.

The only way to obtain a monomial of degree 3 is from the one element sequence F {0, 1, 2,3,4}. Since the biggest rank of a flat in our matroid is 4, there are no monomials of degree 4 of higher. The dimensions we obtained are 1, 21, 21, 1, which agrees with the next-to-last row of Table 2.

In the case where a matroid M is a Specht matroid , Theorem 5.3 has an appealing consequence. We say that a finite-dimensional representation V of a finite group G is a permutation representation if the group action on V arises from an action of G on a basis of V. In other words, the vector space V has a basis v 1, v 2, … , v d such that, for all i with 1 ≤ i ≤ d and all g ∈ G, we have g ⋅ v i = v j for some basis element v j . These representations are particularly easy to understand because one only has to understand the combinatorics of a group acting on a finite set.

Given an element v r of the ground set of the Specht matroid, the action of any permutation σ ∈ S n on V (w 1) takes v r to \((-1)^{\sigma }v_{\sigma ^{-1}r}\). Therefore, given a flat F, which we think of as the subspace spanned by \(\{v_{r_{1}},v_{r_{2}},\mathop{\ldots },v_{r_{k}}\}\), a permutation σ sends F to the flat σ −1 F corresponding to the subspace spanned by \(\{v_{\sigma ^{-1}r_{1}},v_{\sigma ^{-1}r_{2}},\mathop{\ldots },sv_{\sigma ^{-1}r_{k}}\}\). This action on flats induces an action on the Chow ring \(A^{{\ast}}\big(M(\lambda )\big)\) sending a monomial \(\prod _{i=1}^{k}x_{F_{i}}^{d_{i}}\) to \(\prod _{i=1}^{k}x_{\sigma ^{-1}F_{i}}^{d_{i}}\). Since a monomial satisfies the conditions of Theorem 5.3 if and only if its image under the action of σ does, the action of S n on A ∗(M(λ)) is a permutation action. If one understood the action of S n on the set of flags of flats of M(λ), one would be able to easily determine the graded character of \(A^{{\ast}}\big(M(\lambda )\big)\) by substituting characters for dimensions in the computations of Feichtner and Yuzvinsky [6, p. 526]

6 Specht Polytopes

Given a partition λ, \((\frac{n} {\lambda } )\) we define the Specht polytope P(λ) to be the convex hull in \(\mathbb{R}^{N}\), where \(N = \binom{n}{\lambda }\), of the columns of the Specht matrix. This polytope is defined only up to a global sign; this choice will be irrelevant for our purposes because any polytope is projectively equivalent to its negative.

Example 6.1

Consider the partition (2, 1, 1). The row and column words for this partition are 1 1 2 3 and 1 2 1 1, respectively. The Specht matrix appears in Table 4. Using Macaulay2 , we can verify that the polytope in \(\mathbb{R}^{12}\) which is the convex hull of the columns of the matrix in Table 4 is a three-dimensional simplex.

Table 4 Specht matrix for (2, 1, 1)
Full size table

Theorem 6.2

Every column of the Specht matrix is a vertex of P(λ).

Proof

Suppose some column of the Specht matrix can be written as a non-trivial convex combination of the others. Since S n acts transitively on the columns of the Specht matrix, this would mean that every column can be written as a convex combination of the others, which would mean P(λ) has no vertices, which is impossible. □

Theorem 6.3

Every Specht polytope other than P(1, 1, … , 1) contains the origin.

Proof

First, we show that each row of a Specht matrix corresponding to a partition different from (1, 1, … , 1) contains the same number of 1’s as of − 1’s. Let r be some permutation of a row word, and let \(\mathop{\mathrm{Stab}}\nolimits (r)\) be the set of all permutations preserving the word r. Since we excluded the partition (1, 1, … , 1), the stabilizer \(\mathop{\mathrm{Stab}}\nolimits (r)\) is a nontrivial direct product of symmetric groups. Nonzero entries in the row corresponding to r in the Specht matrix have values 1 or − 1 depending on the signature of an element in \(\mathop{\mathrm{Stab}}\nolimits (r)\). Since \(\mathop{\mathrm{Stab}}\nolimits (r)\) has an equal number of odd and even permutations, the entries add up to 0. If c 1, c 2, … , c m are the columns of the Specht matrix, then we have \(\sum _{i=1}^{m} \frac{1} {m}c_{i} = 0\), which finishes the proof. □

Theorem 6.4

The dimension of the Specht polytope matches the dimension of the Specht module for any partition other than (1, 1, … , 1).

Proof

Since the Specht module is the span of the columns of a Specht matrix, its dimension is equal to the rank of this matrix. By Theorem 6.3, the corresponding polytope contains the origin, so its dimension matches the dimension of the linear span of its vertices. □

We conclude this section with Table 5, which gives f-vectors and dimensions of some of the Specht polytopes . We have not found yet any interpretation of these data.

Table 5 Dimensions and f-vectors of Specht polytopes
Full size table

7 Examples: The Partitions (2, 1n−1) and (n − 1, 1)

In the previous section, we saw that the Specht polytope for the partition (2, 1, 1) is a simplex. In fact, any partition of the form (2, 1n−1) corresponds to a simplex.

Theorem 7.1

The Specht polytope P(2, 1n−1) is an (n − 1)-dimensional simplex.

Proof

The Specht module M(2, 1n−1) of size n has dimension n − 1. By Theorem 6.4, the Specht polytope has the same dimension. The partition (2, 1n−1) has the column word 1 2 1 1⋯1, which has n rearrangements. Hence, the Specht polytope P(2, 1n−1) has at most n vertices and dimension n − 1, so it must be an (n − 1)-simplex. □

Correspondingly, for λ = (2, 1n−1), the matroid M(λ) is the generic matroid on n elements of total rank n − 1. The Hilbert series for A ∗(M) for any generic matroid M is calculated by Feichtner and Yuzvinsky. It is not too difficult to modify their computation to include information on the action of S n . The dimensions of the Chow groups of this Specht matroid appear in Table 6. We make the following conjecture with the help of the OEIS [14].

Table 6 Dimensions of \(A^{k}\big(M(2,1^{n-1})\big)\)
Full size table

Conjecture 7.2

The dimension of \(A^{k}\big(M(2,1^{n-1})\big)\) is the number of permutations in S n with no fixed points and k + 1 excedances (OEIS A046739).

A fixed point of a permutation σ ∈ S n is an index i such that σ(i) = i, and an excedance is an index i such that σ(i) > i. Consider the cyclic subgroup C n ⊂ S n generated by the n-cycle c = (12⋯n). Conjugation by c preserves the number of fixed points and the number of excedances, so, for any fixed n and k, the cyclic group C n acts on the set of permutations of S n with no fixed points and k + 1 excedances. As in Sect. 5, the symmetric group S n acts on the Feichtner–Yuzvinsky basis of \(A^{k}\big(M(2,1^{n-1})\big)\), and C n acts by restricting this action. A possible refinement of the conjecture asserts that the orbit structures of these two actions coincide; we have checked this refinement for n ≤ 6. For n = 6 and k = 2, both actions have 1 orbit of size 1, 2 orbits of size 2, 4 orbits of size 3, and 24 orbits of size 6.

We switch our attention to partitions of the form (n − 1, 1). We start by describing the Specht matrices coming from this partition.

Proposition 7.3

Each column of a Specht matrix for the partition (n − 1, 1) is of the form e i − e j , where e i is a standard unit vector in \(\mathbb{R}^{n}\) , and, for n ≥ 4, e i − e j and e j − e i are both columns of the Specht matrix for any i, j with 1 ≤ i < j ≤ n.

Proof

For the partition (n − 1, 1), a choice of row word is w 1 = 1 1⋯1 1 2 and a choice of column word is w 2 = 1 2 3⋯(n − 1) 1. Let r 2 be a rearrangement of the column word w 2. In the column for r 2, there are exactly two nonzero entries, namely the entries corresponding to the rearrangements of w 1 in which the 2 is in the same position as one of the 1’s in r 2. Let us call these rearrangements r 1 and r 1 ′. If σ is a permutation such that σw 1 = r 1 and σw 2 = r 2, and σ ′ is a permutation such that σ ′ w 1 = r 1 ′ and σ ′ w 2 = r 2, then σ and σ ′ differ by a transposition, so we have Y (r 1, r 2) = −Y (r 1 ′, r 2). Given i and j, to obtain e i − e j and e j − e i , use the column corresponding to some rearrangement r of w 2 with the 1’s in the ith and jth positions and the column corresponding to rearrangement r ′ obtained from switching the positions of the 2 and 3 in r. □

For the partition (3, 1), the Specht polytope naturally lives in a four-dimensional space, but as it is a three-dimensional object, it can be drawn in a 3-space; see Fig. 3.

Fig. 3
figure 3

Specht polytope (3, 1)

Full size image

In what follows, we denote a vertex of a Specht polytope P(n − 1, 1) by v i, j if the corresponding column in the Specht matrix has 1 in the ith position and − 1 in the jth position. It turns out that the Specht polytopes P(n − 1, 1) have already been studied by Ardila, Beck, Hoşten, Pfeifle, and Seashore [2].

Definition 7.4

A root polytope \(P_{A_{n}}\) of type A n is the convex hull of the points e i − e j for 1 ≤ i ≠ j ≤ n where i, j ∈ {1, 2, … , n}.

This definition is different from the definition of Gelfand, Graev, and Postnikov [9], which uses only the positive roots and zero. For this class of polytopes, Ardila, Beck, Hoşten, Pfeifle and Seashore [2, Proposition 8] give the following description of their edges and facets.

Theorem 7.5

The polytope \(P_{A_{n}} \in \mathbb{R}^{n+1}\) has dimension n and is contained in the hyperplane \(H_{0} =\{ x \in \mathbb{R}^{n+1}:\sum _{ i=0}^{n}x_{i} = 0\}\) . It has (n − 1)n(n + 1) edges, which are of the form v ij v ik and v ik v jk for i, j, k distinct. It has 2n+1 − 2 facets, which can be labelled by the proper subsets S of [0, n]: = {0, 1, … , n}. The facet F S is defined by the hyperplane \(H_{S}:=\big \{x \in \mathbb{R}^{n+1}:\sum _{i\in S}x_{i} = 1\big\}\) , and it is congruent to the product of simplices Δ S ×Δ T , where T = [0, n] − S.

The main idea in the proof of this theorem is that, if f is a linear functional and i, j, k, l are all different, then f(v i, j ) + f(v k, l ) = f(v i, l ) + f(v k, j ). Hence f cannot be maximized at only one of the line segments v i, j v k, l or v i, l v k, j , so neither can be an edge. A similar argument works both for ruling out pairs of vertices of the form v i, j and v j, k as edges and for determining the facets.

Ardila, Beck, Hoşten, Pfeifle and Seashore also gave the following description of the lattice points inside \(P_{A_{n}}\).

Theorem 7.6

The only lattice points in \(P_{A_{n}}\) are its vertices and the origin.

Proof

A polytope \(P_{A_{n}}\) is contained in an (n − 1)-sphere with radius \(\sqrt{2}\) and centre 0. The only lattice points in this sphere are ± e i and ± e i ± e j for 1 ≤ i, j ≤ n. Since \(P_{A_{n}}\) is contained in the hyperplane \(H_{0} =\{ x \in \mathbb{R}^{n+1}:\sum _{ i=0}^{n}x_{i} = 0\}\), the only lattice points contained in \(P_{A_{n}}\) are the vertices and the origin. □

The matroid M(n − 1, 1) is the matroid for the braid arrangement of S n . This was one of the original motivations of DeConcini and Procesi [4] for studying Chow rings of representable matroids. Moreover, A ∗(M) is the cohomology ring for the moduli space \(\overline{M}_{0,n}\) of n marked points on the complex projective line, which DeConcini and Procesi [3] show can be realized as the successive blowup of \(\mathbb{P}^{n-2}\) at all the subspaces in the intersection lattice of the braid arrangement. For more information on \(\overline{M}_{0,n}\), see [12].

This matroid is also the graphical matroid on the complete graph K n on n vertices. By the usual translation between graphical matroids and graphs, vectors in the matroid correspond to (directed) edges of the graph, and a basis of the matroid corresponds to a spanning tree for the graph. To be precise, we can label the vertices of K n by {1, 2, … , n}, and, with this labelling, the edge from i to j corresponds to the vector e j − e i . If we start with the column word w 2 = 1 1 2 3⋯n, then the vector e j − e i is v r for the rearrangement r where a 1 appears in the ith and jth positions and the remaining letters 2, 2, … , n appear in order. In terms of the usual presentation of the Specht matroid in terms of fillings, this vector corresponds to the filling with an i and a j in the first column and the remaining integers in order along the first row. The usual basis of the Specht module given by Standard Young Tableaux corresponds to the tree with edges between vertex 1 and vertex j for every j > 1, and declaring i to be the “smallest” letter in our filling alphabet gives a similar tree with vertex i having degree n − 1. Of course, K n has many other types of spanning trees, so the Specht matroid has many bases that look completely different than the standard one!

8 Matroidification

Many constructions in the representation theory of S n involve tensor products or \(\mathop{\mathrm{Hom}}\nolimits\) spaces of Specht modules. Since Specht modules have a distinguished symmetric spanning set, so do their tensor products. Hence, we can extend our definitions of Specht matroids and Specht polytopes to these other contexts. In this section, we build matroids and polytopes for three famous collections of numbers arising in combinatorics and representation theory: Kronecker coefficients, Littlewood–Richardson coefficients, and plethysm coefficients.

Definition 8.1

If λ, μ, ν are partitions of n, then the Kronecker coefficient g λ, μ, ν is defined to be the dimension of the S n -invariants of the tensor product

$$\displaystyle{g_{\lambda,\mu,\nu }:=\dim \big (\mathop{\mathrm{Specht}}\nolimits (\lambda ) \otimes \mathop{\mathrm{Specht}}\nolimits (\mu ) \otimes \mathop{\mathrm{Specht}}\nolimits (\nu )\big)^{S_{n} }\,.}$$

In Definitions 8.2, 8.5, and 8.8, we denote by x 1 and x 2 a pair of complementary words of length n that correspond via Theorem 2.5 to the partition λ. Similarly, y 1 and y 2 correspond to μ, and w 1 and w 2 to ν.

Definition 8.2

The Kronecker matrix has rows indexed by the product

$$\displaystyle{\{\text{rearrangements of }x_{1}\} \times \{\text{rearrangements of }y_{1}\} \times \{\text{rearrangements of }w_{1}\}}$$

and columns indexed by the product

$$\displaystyle{\{\text{rearrangements of }x_{2}\} \times \{\text{rearrangements of }y_{2}\} \times \{\text{rearrangements of }w_{2}\}\,,}$$

where the \(\big((p,q,r),(s,t,u)\big)\) entry is given by the formula

$$\displaystyle{\sum _{\sigma \in S_{n}}\mathop{ \mathrm{Y}}\nolimits (\sigma s,p) \cdot \mathop{\mathrm{Y}}\nolimits (\sigma t,q) \cdot \mathop{\mathrm{Y}}\nolimits (\sigma u,r).}$$

Its columns define the Kronecker matroid and the convex hull of its columns defines the Kronecker polytope.

Theorem 8.3

The dimension of the Kronecker polytope is g λ, μ, ν .

Proof

The tensor product \(\mathop{\mathrm{Specht}}\nolimits (\lambda ) \otimes \mathop{\mathrm{Specht}}\nolimits (\mu ) \otimes \mathop{\mathrm{Specht}}\nolimits (\nu )\) is given by the column span of the matrix with entries \(\mathop{\mathrm{Y}}\nolimits (p,s) \cdot \mathop{\mathrm{Y}}\nolimits (q,t) \cdot \mathop{\mathrm{Y}}\nolimits (r,u)\). The summation over S n produces S n -invariant vectors. □

Definition 8.4

If λ, μ, ν are partitions of l, m, and l + m respectively, then the Littlewood–Richardson coefficient c λ, μ ν is defined by

$$\displaystyle{c_{\lambda,\mu }^{\nu }:=\dim \Big (\mathop{\mathrm{Specht}}\nolimits (\lambda ) \boxtimes \mathop{\mathrm{Specht}}\nolimits (\mu ) \otimes \mathop{\mathrm{Res}}\nolimits _{ S_{l}\times S_{m}}^{S_{l+m} }\big(\mathop{\mathrm{Specht}}\nolimits (\nu )\big)\Big)^{S_{l}\times S_{m} }\,,}$$

where S l × S m acts on \(\mathop{\mathrm{Specht}}\nolimits (\lambda ) \boxtimes \mathop{\mathrm{Specht}}\nolimits (\mu )\) separately in the two tensor factors, and S l × S m acts on \(\mathop{\mathrm{Res}}\nolimits _{S_{l}\times S_{m}}^{S_{l+m}}\big(\mathop{\mathrm{Specht}}\nolimits (\nu )\big)\) by considering S l × S m as a subgroup of S l+m and using the S l+m -action on \(\mathop{\mathrm{Specht}}\nolimits (\nu )\). We use the notation ⊠ for the tensor product with this separated action in order to contrast with the diagonal action that we indicate by ⊗.

Definition 8.5

The Littlewood–Richardson matrix has rows indexed by the product

$$\displaystyle{\{\text{rearrangements of }x_{1}\} \times \{\text{rearrangements of}y_{1}\} \times \{\text{rearrangements of }w_{1}\}}$$

and columns indexed by the product

$$\displaystyle{\{\text{rearrangements of }x_{2}\} \times \{\text{rearrangements of}y_{2}\} \times \{\text{rearrangements of }w_{2}\}\,,}$$

where the ((p, q, r), (s, t, u)) entry is given by the formula

$$\displaystyle{\sum _{\sigma \times \tau \in S_{l}\times S_{m}}\mathop{ \mathrm{Y}}\nolimits (\sigma s,p) \cdot \mathop{\mathrm{Y}}\nolimits (\tau t,q) \cdot \mathop{\mathrm{Y}}\nolimits \big((\sigma \times \tau )u,r\big)\,.}$$

Its columns define the Littlewood–Richardson matroid and the convex hull of its columns defines the Littlewood–Richardson polytope.

Littlewood–Richardson polytope for λ = 2 + 1, μ = 2 + 1, ν = 3 + 2 + 1 appears in Fig. 4. Since c λ, μ ν = 2, this polytope is actually a polygon.

Fig. 4
figure 4

Littlewood– Richardson polytope for c (2, 1),(2,1) (3,2,1) = 2

Full size image

Theorem 8.6

The dimension of the Littlewood–Richardson polytope is c λμ ν .

Proof

The proof for this theorem is analogous to that of Theorem 8.3. □

We now study restriction to the wreath subgroup S l ≀ S m ⊆ S lm . Thinking of lm as an l × m array of dots to be permuted, the wreath subgroup is generated by the permutations in which every dot stays in its row together with the permutations that perform the same operation in every column simultaneously. Abstractly, the wreath subgroup is isomorphic to the semidirect product \((S_{l})^{m} \rtimes S_{m}\) where the second factor acts on the first by permuting coordinates.

Definition 8.7

If λ, μ, and ν are partitions of l, m, and l ⋅ m respectively, then the plethysm coefficient p λ, μ ν is defined by

$$\displaystyle{p_{\lambda,\mu }^{\nu } =\dim \Big (\mathop{\mathrm{Specht}}\nolimits (\lambda )^{\boxtimes m} \otimes ^{\!\rtimes }\mathop{ \mathrm{Specht}}\nolimits (\mu ) \otimes \mathop{\mathrm{Res}}\nolimits _{ S_{l}\wr S_{m}}^{S_{lm} }\big(\mathop{\mathrm{Specht}}\nolimits (\nu )\big)\Big)^{S_{l}\wr S_{m} }\,,}$$

where \((S_{l})^{m} \rtimes S_{m}\) acts on \(\mathop{\mathrm{Specht}}\nolimits (\lambda )^{\boxtimes m} \otimes ^{\!\rtimes }\mathop{ \mathrm{Specht}}\nolimits (\mu )\) by S m on the second factor, and the normal subgroup \((S_{l})^{m} \trianglelefteq (S_{l})^{m} \rtimes S_{m}\) acts naturally on the first factor.

As before, let x 1, x 2 be a complementary pair of words of length l that correspond via Theorem 2.5 to the partition λ, and similarly suppose that y i correspond to μ, and that w i correspond to ν.

Definition 8.8

The plethysm matrix has rows indexed by the product

$$\displaystyle{\{\text{rearrangements of }x_{1}\}^{m} \times \{\text{rearrangements of }y_{ 1}\} \times \{\text{rearrangements of }w_{1}\}}$$

and columns indexed by the product

$$\displaystyle{\{\text{rearrangements of }x_{2}\}^{m} \times \{\text{rearrangements of }y_{ 2}\} \times \{\text{rearrangements of }w_{2}\},}$$

where the \(\big((\hat{p},q,r),(\hat{s},t,u)\big)\) entry is given by the formula

$$\displaystyle{\sum _{\hat{\sigma }\rtimes \tau \in S_{l}\wr S_{m}}\mathop{ \mathrm{Y}}\nolimits (\hat{\sigma }_{1}\hat{s}_{1},\hat{p}_{1}) \cdot \mathop{\mathrm{Y}}\nolimits (\hat{\sigma }_{2}\hat{s}_{2},\hat{p}_{2})\cdots \mathop{\mathrm{Y}}\nolimits (\hat{\sigma }_{m}\hat{s}_{m},\hat{p}_{m}) \cdot \mathop{\mathrm{Y}}\nolimits (\tau t,q) \cdot \mathop{\mathrm{Y}}\nolimits \big((\hat{\sigma }\rtimes \tau )u,r\big)\,.}$$

Its columns define the plethysm matroid , and the convex hull of its columns defines the plethytope.

Theorem 8.9

The dimension of the plethytope is p λμ ν .

Proof

The proof for this theorem is also analogous to that of Theorem 8.3. □

9 Computer Calculations

The following Sage [17] code generates the Specht matrix given a row word and a column word.

def distinctColumns(w1, w2):     if len(w2) != len(w2): return False     seen = set()     for i in range(len(w1)):         t = (w1[i], w2[i])         if t in seen: return False         seen.add(t)     return True

def YoungCharacter(w1, w2):     assert distinctColumns(w1, w2)     wp = [(w1[i], w2[i]) for i in range(len(w1))]     def ycfunc(r1, r2):         if not distinctColumns(r1, r2):             return 0         rp = [(r1[i], r2[i]) for i in range(len(w1))]         po = [wp.index(rx) + 1 for rx in rp]         return Permutation(po).sign()     return ycfunc

def SpechtMatrix(w1, w2):     yc = YoungCharacter(w1, w2)     mat = []     for r1 in Permutations(w1):         row = []         for r2 in Permutations(w2):             row = row + [yc(r1, r2)]         mat = mat + [row]     return matrix(QQ, mat)

sm22 = SpechtMatrix([1,1,2,2], [1,2,1,2]) print sm22

The output of the code is

[ 0  1 -1 -1  1  0] [-1  0  1  1  0 -1] [ 1 -1  0  0 -1  1] [ 1 -1  0  0 -1  1] [-1  0  1  1  0 -1] [ 0  1 -1 -1  1  0]

Having a Specht matrix , we can use Macaulay2 [11] package Polyhedra [5] to obtain some information about Specht polytopes .

loadPackage "Polyhedra"; V = matrix{{ 0, 1,-1,-1, 1, 0}, {-1, 0, 1, 1, 0,-1},            { 1,-1, 0, 0,-1, 1}, { 1,-1, 0, 0,-1, 1},            {-1, 0, 1, 1, 0,-1}, { 0, 1,-1,-1, 1, 0}} P = convexHull V fVector P

The output of the above code, line by line, is

      | 0  1  -1 -1 1  0  |       | -1 0  1  1  0  -1 |       | 1  -1 0  0  -1 1  |       | 1  -1 0  0  -1 1  |       | -1 0  1  1  0  -1 |       | 0  1  -1 -1 1  0  |

                6        6       Matrix ZZ  <--- ZZ

      {ambient dimension => 6           }        dimension of lineality space => 0        dimension of polyhedron => 2        number of facets => 3        number of rays => 0        number of vertices => 3

       {3, 3, 1}

The following commands give us a description of the faces of codimension i and the vertices on each face of a polytope P:

F_i = faces(i,P) apply(F_i,vertices)

For i = 1, the output is

       {{ambient dimension => 6           },         dimension of lineality space => 0         dimension of polyhedron => 1         number of facets => 2         number of rays => 0         number of vertices => 2

        {{ambient dimension => 6           },         dimension of lineality space => 0         dimension of polyhedron => 1         number of facets => 2         number of rays => 0         number of vertices => 2

        {{ambient dimension => 6           }}         dimension of lineality space => 0         dimension of polyhedron => 1         number of facets => 2         number of rays => 0         number of vertices => 2

      {| -1 1  |, | 0  -1 |, | 0  1  |}        | 1  0  |  | -1 1  |  | -1 0  |        | 0  -1 |  | 1  0  |  | 1  -1 |        | 0  -1 |  | 1  0  |  | 1  -1 |        | 1  0  |  | -1 1  |  | -1 0  |        | -1 1  |  | 0  -1 |  | 0  1  |

The following Sage code computes the Hilbert series of the Chow ring for a given matroid . The code computing the Chow ring was contributed to the Sage system by Travis Scrimshaw. In the example, we use the Specht matrix sm22 computed above.

def chow_ring_dimensions(mm, R=None):     # Setup     if R is None:         R = ZZ     # We only want proper flats     flats = [X for i in range(1, mm.rank())              for X in mm.flats(i)]     E = list(mm.groundset())     flats_containing = {x: [] for x in E}     for i,F in enumerate(flats):         for x in F:             flats_containing[x].append(i)     # Create the ambient polynomial ring     from sage.rings.polynomial\         .polynomial_ring_constructor     import PolynomialRing     try:         names = [’A{}’.format(’’.join(str(x)                  for x in sorted(F)))                  for F in flats]         P = PolynomialRing(R, names)     except ValueError: # variables have                        # improper names         P = PolynomialRing(R, ’A’, len(flats))         names = P.variable_names()     gens = P.gens()     # Create the ideal of quadratic relations     Q = [gens[i] * gens[i+j+1]          for i,F in enumerate(flats)          for j,G in enumerate(flats[i+1:])          if not (F < G or G < F)]     # Create the ideal of linear relations     L = [sum(gens[i] for i in flats_containing[x])          - sum(gens[i] for i in flats_containing[y])          for j,x in enumerate(E) for y in E[j+1:]]     # Compute Hilbert series using Macaulay2     macaulay2.eval("restart")     macaulay2.eval("R=QQ[" + str(gens)[1:-1] + "]")     macaulay2.eval("I=ideal(" + str(Q)[1:-1] + ",     " + str(L)[1:-1] + ")")     hs = macaulay2.eval("toString hilbertSeries I")     T = PolynomialRing(RationalField(),"T").gen()     return sage_eval(hs, locals={’T’:T}) chow_ring_dimensions(Matroid(sm22))

The output of the code for our example is

T+1

We now give the code for Examples 5.2 and 5.4. The following Sage commands compute the matroid corresponding to a given matrix, the lattice of flats of a matroid, a list of flats of a given rank, and the characteristic polynomial of a matroid.

X = matrix([[1, 0, 0, 1, 1, 1], [0, 1, 0, 2, 3, 4], [0, 0, 1, 0, 0, 1]]) M = Matroid(X) M M.lattice_of_flats() sorted([sorted(F) for F in M.lattice_of_flats()]) F1 = M.flats(1) sorted([sorted(F) for F in F1]) rank = M.rank() Tutte_polynomial = M.tutte_polynomial() Tutte_polynomial var(’t’) char_poly = (-1)^rank * expand(Tutte_polynomial(1-t,0)) char_poly

The output of the above code is

Linear matroid of rank 3 on 6 elements represented over the Rational Field Finite lattice containing 18 elements [[], [0], [0, 1, 2, 3, 4, 5], [0, 1, 3, 4], [0, 2], [0, 5], [1], [1, 2], [1, 5], [2], [2, 3], [2, 4], [2, 5], [3], [3, 5], [4], [4, 5], [5]] [[0], [1], [2], [3], [4], [5]] x^3 + x*y^2 + y^3 + 3*x^2 + 2*x*y + 2*y^2 + 3*x + 3*y t t^3 - 6*t^2 + 12*t - 7