GROUP REPRESENTATIONS

AND

SYMMETRIC FUNCTIONS

Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027 sagan@math.msu.edu

I. Group representations II. Representations of the symmetric group, 𝔖_{n} III. Associated combinatorics IV. Symmetric functions Copies available at

http://www.mth.msu.edu/~sagan References

1. C. W. Curtis and I. Reiner, “Representation Theory of Finite Groups and Associative Algebras,” Pure and Applied Science, Vol. 11, Wiley-Intersci-ence, New York, 1966.

2. G. D. James, “The Representation Theory of Symmetric Groups,” Lecture Notes in Math., Vol. 682, Springer-Verlag, New York, 1978.

3. I. G. Macdonald, “Symmetric Functions and Hall polynomials,” 2nd ed., Oxford University Press, Oxford, 1995.

4. B. E. Sagan, The ubiquitous Young tableau, in “Invariant Theory and Tableaux,” Dennis Stanton ed., IMA Volumes in Math. and its Applications 19 (1990), 262–298.

5. B. E. Sagan, The symmetric group: representations, combinatorial algorithms, and symmetric functions, Wadsworth & Brooks/ Cole, Pacific Grove, 1991; 2nd ed., Springer-Verlag, New York, to appear.

6. R. P. Stanley, “Enumerative Combinatorics, I,” Wadsworth & Brooks/Cole, Pacific Grove, 1986.

I. Group representations: A. Modules

All groups G will be finite and all vector spaces V will be over ℂ.

A matrix representation (rep) of a group G is a group homomorphism

X : G → GL_{d}(ℂ).

A G-module is a vector space V, dim V = d, with a group homomorphism

ρ : G → GL(V).

This gives a linear action of G on V: gv = ρ(g)v.

The parameter d is called the degree or dimension of the rep. We will freely go between matrix rep’s and G-modules.

The group algebra is the G-module

ℂ[G] = {_{g∈G}^{∑} c_{g}g | c_{g} ∈ ℂ}

with action gh = k if gh = k in G. The corresponding matrix rep in the basis B = {g | g ∈ G} is called the (left) regular rep. The corresponding matrices X(g) are permutation matrices (cf. Cayley’s Theorem).

Ex. Every group G has the trivial rep X^{tri}

X^{tri}(g) = (1) for all g ∈ G.

A module for this rep is V with dim V = 1 and

gv = v for all g ∈ G, v ∈ V.

Ex. For a cyclic group G = {g, g^{2}, …, g^{n} = ϵ} any 1-dim rep would have X(g) = (c) where

(c^{n}) = X(g^{n}) = X(ϵ) = (1).

So c is an nth root of 1 and all such nth roots give 1-dim rep’s.

If n = 2 then the group algebra is ℂ[G] = {c_{1}ϵ+c_{2}g} with action gϵ = g, gg = ϵ. So the left regular rep is

X(ϵ) = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) , X(g) = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) .

Changing basis to {ϵ + g, ϵ − g} gives an equivalent rep

Y (ϵ) = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) , Y (g) = ( \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} )

which is a direct sum of the rep’s for √1 = ±1.

If G acts on a set S then one obtains a representation by linearly extending to the vector space

ℂ[S] = {_{s∈S}^{∑} c_{s}s | c_{s} ∈ ℂ}.

The basis S gives a rep by permutation matrices.

Ex. Given any group G, a subgroup H ≤ G, and a set of all distinct left cosets

S = {t_{1}H, …, t_{l}H}

there is an action gt_{j}H = t_{i}H if gt_{j}H = t_{i}H. The module ℂ[S] is called a coset rep. If H = G (resp. H = {ϵ}) then it’s the trivial (resp. regular) rep.

Ex. The symmetric group 𝔖_{n} acts by definition on

S = {1, 2, …, n}.

The corresponding module ℂ[1, …, n] is the defining rep. If n = 2 then (1, 2)1 = 2, (1, 2)2 = 1 so

X(ϵ) = ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) , X((1, 2)) = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) .

Also 𝔖_{n} has the 1-dim sign rep

X(π) = (sgn π) sgn π = \{ \begin{matrix}+1 & if π is even \\ −1 & if π is odd. \end{matrix}

B. Reducibility and Maschke’s Theorem

A submodule W of G-module V, W ≤ V, is a subspace closed under G’s action. Every G-module has trivial submodules W = {0}, V. Module V is irreducible (irr) or an irrep if it has no non-trivial submodules. Every 1-dim module is an irrep.

Ex. The group algebra ℂ[G] has submodule

W = ℂ[_{g∈G}^{∑} g]

since h ∑_{g} g = ∑_{g} g. This W gives the trivial rep.

If G = 𝔖_{n} then we can get the sign rep with

U = ℂ[_{π∈𝔖_{n}}^{∑}(sgn π)π].

Ex. If G = 𝔖_{n} and V = ℂ[1, …, n] then

W = ℂ[1 + 2 + ⋯ + n]

is a submodule for the trivial rep. Consider the inner product on V: ⟨i, j⟩ = δ_{i,j} (Kronekcer δ). Then

W^{⊥} = {_{i}^{∑} c_{i}i | _{i}^{∑} c_{i} = 0}

is also a submodule and V = W ⊕ W^{⊥} with W, W^{⊥} irr. (Clear for W, not for W^{⊥}.)

A G-module V is completely reducible if

V = W^{(1)} ⊕ ⋯ ⊕ W^{(k)}

where each W^{(i)} is irr.

Theorem 1 (Maschke) If G is finite then every complex G-module V is completely reducible.

Proof. If V is irr, we are done. If not, let W be a non-trivial submodule. Pick a basis for V B = {v_{1}, …, v_{d}} with corresponding inner product ⟨v_{i}, v_{j}⟩ = δ_{i,j}. Now define another inner product

⟨v, w⟩′ = _{g∈G}^{∑}⟨gv, gw⟩

which is G-invariant:

⟨hv, hw⟩′ = _{g∈G}^{∑}⟨ghv, ghw⟩ = _{g∈G}^{∑}⟨gv, gw⟩ = ⟨v, w⟩′.

Now W^{⊥} (with respect to ⟨·, ·⟩′) is a submodule since if v ∈ W^{⊥}, w ∈ W, and g ∈ G then

⟨gv, w⟩′ = ⟨v, g^{−1}w⟩′ = 0.

So V = W ⊕ W^{⊥} and done by induction on dim V.

Note: 1. Maschke may not be true if |G| = ∞ or the field is different from ℂ.

2. Henceforth we can just concentrate on irreps.

C. G-homomorphisms and Schur’s Lemma

A G-homomorphism (hom) of G-modules V, W is a linear map θ : V → W such that for all g ∈ G, v ∈ V

θ(gv) = gθ(v).

A bijective θ is called a G-isomorphism (iso) and then V, W are G-equivalent (equiv), V ≅ W. Turning everything into matrices

T X(g)v = Y (g)T v for all g ∈ G, v ∈ ℂ^{d} ⇒ T X(g) = Y (g)T for all g ∈ G

⇒^{def} T X = Y T.

Ex. Let V = ℂ[v] be the trivial rep and W = ℂ[G] be the group algebra. Then a G-hom is θ : V → W defined by

θ(v) = _{g∈G}^{∑} g.

Ex. Let G = 𝔖_{2}, let V = ℂ[1, 2] be the defining rep and W = ℂ[ϵ, (1, 2)] be the group algebra. Then θ : V → W by 1 ↦ ϵ, 2 ↦ (1, 2) is an 𝔖_{2}-iso, e.g.,

θ((1, 2)2) = θ(1) = ϵ = (1, 2)(1, 2) = (1, 2)θ(2).

Lemma 2 (Schur) If V, W are irreducible modules and θ : V → W is a G-homomorphism then either

1. θ is a G-isomorphism or

2. θ is the zero map.

Proof. Since θ is a G-hom, ker θ and im θ are Gsubmodules of V and W, respectively. Since V, W are irr, ker θ = {0} or V and im θ = {0} or W. If ker θ = {0} and im θ = W then θ is a G-iso. All other cases lead to the zero map.

Schur’s Lemma is valid for infinite groups and arbitrary fields. For ℂ more is true.

Corollary 3 If X is an irreducible matrix representation (irrep) of G over ℂ and T commutes with X then T = cI, c ∈ ℂ.

Proof. Let c be an eigenvalue of T. Then

T X = XT ⇒ (T − cI)X = X(T − cI).

By Schur, T − cI is invertible or zero and the former can’t happen by the choice of c.

D. The endomorphism algebra

A G-module V has endomorphism algebra

End V = {θ : V → V | θ is a G-homomorphism }.

For a d-dim matrix representation X this becomes

End X = {T ∈ Mat_{d} | T X = XT }.

To describe End X we use block matrix operations

S⊕T = ( \begin{matrix}S & 0 \\ 0 & T \end{matrix} ) , S⊗T = (S_{i,j}T) where S = (S_{i,j}) .

Suppose that X decomposes as

X = X^{(1)} ⊕ X^{(2)} ⊕ ⋯ ⊕ X^{(l)}

where the X^{(i)} are irr. Let T = (T_{i,j}) ∈ End X have the same block form. Then XT = XT implies T_{i,j}X^{(j)} = X^{(i)}T_{i,j} so

T_{i,j} = \{ \begin{matrix}0 & if X^{(i)} ≅ X̸^{(j)} (Schur) \\ c_{i,j}I & if X^{(i)} ≅ X^{(j)} (Cor). \end{matrix}

Renaming the irreps to collect equiv ones and letting d_{i} = dim X^{(i)}

\begin{matrix}X = ⊕_{i=1}^{k} m_{i}X^{(i)} ⇒ \\ End X = \{⊕_{i=1}^{k} (M_{m_{i}} ⊗ I_{d_{i}}) | M_{m_{i}} ∈ Mat_{m_{i}} ∀i\}. \end{matrix}

Otherwise put

End X ≅ ⊕_{i=1}^{k} Mat_{m_{i}} .

The center Z_{Mat_{m}} = {cI | c ∈ ℂ} and so

Z_{End X} = {⊕_{i=1}^{k} c_{i}I_{m_{i}d_{i}} | c_{i} ∈ ℂ for all i } ≅ Diag _{k}, where Diag _{k} are the diagonal matrices in Mat_{k}. Summarizing and taking dimensions: Theorem 4 Let X be a matrix rep of G with

X = m_{1}X^{(1)} ⊕ m_{2}X^{(2)} ⊕ ⋯ ⊕ m_{k}X^{(k)} where the X^{(i)} are inequiv, irr and with dimensions dim X^{(i)} = d_{i}. Then

1. End X ≅ ⊕_{i=1}^{k} Mat_{m_{i}},

2. Z_{End X} ≅ Diag _{k},

3. dim X = m_{1}d_{1} + m_{2}d_{2} + ⋯ + m_{k}d_{k},

4. dim (End X) = m_{1}^{2} + m_{2}^{2} + ⋯ + m_{k}^{2},

5. dim Z_{End X} = k.

E. Group characters and inner products Matrix rep X has character (char) χ : G → ℂ where

χ(g) = tr X(g).

A G-module also has a unique character since any two bases give conjugate matrix reps. Ex. If dim X = 1 then χ is called a linear char and

χ(gh) = tr X(gh) = tr X(g) tr X(h) = χ(g)χ(h). Ex. If V = ℂ[G] (regular rep) then the char is

χ^{reg} (g) = |\{h : gh = h\}| = \{ \begin{matrix}|G| & if g = ϵ \\ 0 & else. \end{matrix}

Ex. If V = ℂ[1, …, n] (defining rep of 𝔖_{n}), then

χ^{def} (π) = number of fixed points of π . Proposition 5 Let group G have matrix representation X with dim X = d and character χ.

1. χ(ϵ) = d,

2. If K is a conjugacy class: g, h ∈ K ⇒ χ(g) = χ(h),

3. If rep Y has char ψ: X ≅ Y ⇒ χ = ψ.

Character χ is a class function since it is constant on conjugacy classes K. Let χ_{K} = χ(g), g ∈ K. The character table of G has rows indexed by the irreps (χ^{tri} first) columns indexed by the conjugacy classes ({ϵ} first) and entries χ_{K}. It is square.

Ex. If G = 𝔖_{3} then we have

{ϵ} {(1, 2); (1, 3); (2, 3)}  {(1, 2, 3); (1, 3, 2)}
χ^{tri}  1  1  1
χ^{sgn} 1  −1  1
χ^{mys} ?  ?  ?

The inner product of χ, ψ : G → ℂ is

⟨χ, ψ⟩ := \frac{1}{|G|} _{g∈G}^{∑} χ(g)ψ(g) = \frac{1}{|G|} _{K}^{∑} |K|χ_{K}ψ_{K}.

If G-module V has char ψ then an orthonormal basis for V with respect to a G-invariant inner product on V gives matrices for ψ which are unitary and

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

If G = 𝔖_{n} then g and g^{−1} are conjugate and so

⟨χ, ψ⟩ = \frac{1}{n!} _{K}^{∑} |K|χ_{K}ψ_{K}.

Theorem 6 (Character relations, the 1st kind) If χ, ψ are irreducible characters of a group G then

⟨χ, ψ⟩ = δ_{χ,ψ}. (∗)

Proof sketch. Let χ, ψ come from reps X, Y. Let Z = (z_{i,j}) and W = |G|^{−1} ∑_{g∈G} X(g)ZY (g^{−1}). Then XW = W Y and by Schur’s Lemma

W = \{ \begin{matrix}0 & if X ≅ Y̸, \\ cI & if X ≅ Y. \end{matrix}

Since this is true for all Z, one can get equations relating the entries of X and Y giving (*).

Corollary 7 Let X ≅ ⊕_{i=1}^{k} m_{i}X^{(i)} where the X^{(i)} are pairwise inequiv with char’s χ^{(i)}.

1. χ = m_{1}χ^{(1)} + m_{2}χ^{(2)} + ⋯ + m_{k}χ^{(k)},

2. ⟨χ, χ^{(i)}⟩ = m_{i},

3. ⟨χ, χ⟩ = m_{1}^{2} + m_{2}^{2} + ⋯ + m_{k}^{2},

4. X is irr ⇔ ⟨χ, χ⟩ = 1 (use 3),

5. If Y has char ψ then X ≅ Y ⇔ χ = ψ (use 2).

Ex. Let G = 𝔖_{3} and V = ℂ[1, 2, 3] (defining rep) with char χ = χ^{def} . Then

χ(π) = number of fixed points of π χ(ϵ) = 3, χ((1, 2)) = 1, χ((1, 2, 3)) = 0.

Also

χ = m_{1}χ^{tri} + m_{2}χ^{sgn} + m_{3}χ^{mys} where
m_{1} = (1 · 3 · 1 + 3 · 1 · 1 + 2 · 0 · 1)/3! = 1
m_{2} = (1 · 3 · 1 + 3 · 1(−1) + 2 · 0 · 1)/3! = 0.

So

χ = χ^{tri} + m_{3}χ^{mys} .

Consider the character

\begin{matrix}ψ = χ − χ^{tri}, \\ ψ(ϵ) = 2, ψ((1, 2)) = 0, ψ((1, 2, 3)) = −1. \end{matrix}

Then ψ is irreducible since

⟨ψ, ψ⟩ = (1 · 2^{2} + 3 · 0^{2} + 2(−1)^{2})/3! = 1.

So m_{3} = 1 and χ^{mys} = ψ giving the complete table

{ϵ} {(1, 2); (1, 3); (2, 3)}  {(1, 2, 3); (1, 3, 2)}
χ^{tri}  1  1  1
χ^{sgn} 1  −1  1
χ^{mys} 2  0  −1

Note: For general n, χ^{def} − χ^{tri} is irreducible.

F. Decomposing the group algebra Proposition 8 Let ℂ[G] = ⊕_{i}m_{i}V^{(i)} where the V^{(i)} are a complete list of all inequiv irreps

1. m_{i} = dim V^{(i)} (so all irreps occur),

2. ∑_{i}(dim V^{(i)})^{2} = |G|,

3. # of irreps = # of conjugacy classes K of G. Proof sketch. 1. Let χ = χ^{reg} . Then

m_{i} = \frac{∑_{g∈G} χ(g)χ^{(i)}(g^{−1})}{|G|} = \frac{χ(ϵ)χ^{(i)}(ϵ)}{|G|} = dim V^{(i)}.

2. Follows from 1. 3.# of irreps = dim Z_{End ℂ[G]}. End ℂ[G] = {ϕ_{v} : ϕ_{v}(w) = wv} ≅ ℂ[G].

Now z ∈ Z_{ℂ[G]} iff z = hzh^{−1} for all h ∈ G. So for each conjugacy class K of G, Z_{ℂ[G]} has a basis element

z_{K} = _{k∈K}^{∑} k.

Corollary 9 1. The character table of G is square.

2. The irr characters χ of G form an orthonormal basis for the space R(G) of class functions on G.

3. (Character relations of the second kind) If K, L are conjugacy classes of G and χ is irreducible

_{χ}^{∑} χ_{K}χ_{L} = \frac{|G|}{|K|}δ_{K,L}.

Proof. 1 and 2 follow from part 3 of the Proposition and the character relations of the first kind.

3. The relations of the first kind also give that the modified character table U = (√|K|/|G|χ_{K}) has orthonormal rows, thus orthonormal columns.

Ex. We can find χ^{mys} for 𝔖_{3} another way. By the Proposition, part 2,

1^{2} + 1^{2} + χ^{mys} (ϵ)^{2} = 3! ⇒ χ^{mys} (ϵ) = 2.

The other two entries are found using the relations of the second kind. For example, taking K = {ϵ} and L = {(1, 2), …}

0 = 1 · 1 + 1(−1) + 2χmys_{L} ⇒ χmys_{L} = 0.

G. Representations of products and subgroups

If X, Y are matrix reps of G, H respectively then the tensor product rep of G × H is

(X ⊗ Y)(g, h) = X(g) ⊗ Y (h).

Proposition 10 1. X ⊗ Y is a rep of G × H. If X, Y are irreps then so is X ⊗ Y.

2. As X^{(i)}, Y^{(j)} run over complete lists of inequiv irreps for G, H resp, X^{(i)} ⊗Y^{(j)} runs over a complete list of inequiv irreps for X ⊗ Y.

3. If X, Y, X ⊗Y have characters χ, ψ, χ⊗ψ resp then

(χ ⊗ ψ)(g, h) = χ(g)ψ(h).

Proof of 2. Suppose that X^{(i)}, Y^{(j)} have chars χ^{(i)}, ψ^{(j)} resp. Then inequivalence follows from

\begin{matrix}⟨χ^{(i)} ⊗ ψ^{(j)}, χ^{(k)} ⊗ ψ^{(l)}⟩ = ⟨χ^{(i)}, χ^{(k)}⟩⟨ψ^{(j)}, ψ^{(l)}⟩ \\ = δ_{i,k}δ_{j,l} = δ_{(i,j),(k,l)} . \end{matrix}

For list completeness, just check we have the right number of irreps. Let k(·) =# of conjugacy classes.

# of irreps of G × H = k(G × H) = k(G)k(H) =(# of irreps of G)(# of irreps of H).

If H ≤ G and X is a rep of G then the restriction of X to H, X ↓_{H}= X ↓_{H}^{G}, is

X ↓_{H} (h) = X(h).

It is clear the X ↓_{H} is a rep, but if X is irr then X ↓_{H} need not be. For example, if X is the 2-dim irrep of 𝔖_{3} and H = {ϵ, (1, 2)} := 𝔖_{{1,2}} ≅ 𝔖_{2} then

X ↓_{H}≅ X^{tri} ⊕ X^{sgn} .

If Y is a rep of H then Y (g) := 0 for g ∉ H doesn’t give a rep. But if G = ⊎_{i}t_{i}H then the induction of Y to G, Y ↑^{G}= Y ↑_{H}^{G}, has block matrices

Y ↑^{G} (g) = (Y (t_{i}^{−1}gt_{j})).

Ex. Consider 1 ↑^{G} for the trivial char 1 of H. Then

1(g) = \{ \begin{matrix}1 & if g ∈ H, \\ 0 & if g ∉ H. \end{matrix}

So

1(t_{i}^{−1}gt_{j}) = 1 ⟺ t_{i}^{−1}gt_{j} ∈ H ⟺ gt_{j}H = t_{i}H.

So 1 ↑^{G} equals the coset rep ℂ[H] in the standard basis H = {t_{1}H, …, t_{l}H} and so consists of permutation matrices. In general, Y ↑^{G} consists of block permutation matrices.

Proposition 11 1. Y ↑^{G} is a representation of G which may be reducible even if Y is an irrep of H.

2. Two transversals of H give equiv induced reps.

3. If Y, Y ↑^{G} have chars ψ, ψ ↑^{G} resp then

ψ ↑^{G} (g) = \frac{1}{|H|} _{x∈G}^{∑} ψ(x^{−1}gx).

4. (Frobenius Reciprocity) If χ is a char of G then ⟨ψ ↑^{G}, χ⟩ = ⟨ψ, χ ↓_{H}⟩.

Proof of 4. We have

⟨ψ ↑^{G}, χ⟩ = \frac{1}{|G|} _{g∈G}^{∑} ψ ↑^{G} (g)χ(g^{−1})
= \frac{1}{|G||H|} _{x,g∈G}^{∑} ψ(x^{−1}gx)χ(g^{−1})
= \frac{1}{|G||H|} _{x,y∈G}^{∑} ψ(y)χ(xy^{−1}x^{−1})
= \frac{1}{|G||H|} _{x,y∈G}^{∑} ψ(y)χ(y^{−1})
= \frac{1}{|H|} _{y∈G}^{∑} ψ(y)χ(y^{−1})
= \frac{1}{|H|} _{y∈H}^{∑} ψ(y)χ(y^{−1}) = ⟨ψ, χ ↓_{H}⟩.

H. The group determinant Indeterminates {c_{g}|g ∈ G} give the group matrix

Γ = (c_{g^{−1}h})_{g,h∈G}.

In the case G = {g, g^{2}, …, g^{n} = ϵ}, Γ is a circulant. Ex. If n = 3 with rows and cols indexed ϵ, g, g^{2}

Γ = ( \begin{matrix}c_{ϵ} & c_{g} & c_{g^{2}} \\ c_{g^{2}} & c_{ϵ} & c_{g} \\ c_{g} & c_{g^{2}} & c_{ϵ} \end{matrix} ) := ( \begin{matrix}c_{0} & c_{1} & c_{2} \\ c_{2} & c_{0} & c_{1} \\ c_{1} & c_{2} & c_{0} \end{matrix} ) .

Theorem 12 (Frobenius) If the irreps G are X^{(i)}, dim X^{(i)} = d_{i}, 1 ≤ i ≤ k, then

det Γ = k ; ∏ ; i=1 Δ_{i}^{d_{i}} with Δ_{i} := |_{g∈G}^{∑} X^{(i)}(g)c_{g}| irr.

Corollary 13 |c_{j−i}| =_{ζ^{n}=1}^{∏} (c_{0}+c_{1}ζ+⋯+c_{n−1}ζ^{n−1}).

Ex. | \begin{matrix}c_{0} & c_{1} \\ c_{1} & c_{0} \end{matrix} | = c_{0}^{2} − c_{1}^{2} = (c_{0} + c_{1})(c_{0} − c_{1}).

Open Problem. Find a combinatorial proof of the corollary: The det counts 𝔖_{n} with weight wt_{1}. The product counts F = {f : {1, …, n} → {1, …, n}} with weight wt_{2}. Partition 𝔖_{n} = ⊎_{i}S_{i}, F = ⊎_{j}F_{j} s.t. ∑_{f∈F_{j}} wt_{2} f = 0 for certain F_{j} and for the rest there’s a weight preserving bijection with the S_{i}.

II. Reps of 𝔖_{n}: A. Permutation modules

The number of irreps of 𝔖_{n} is the number of conjugacy classes which is the same as the number of partitions λ = (λ_{1}, …, λ_{l}) of n, λ ⊢ n, i.e.,

λ ∈ (ℤ^{+} )^{l} is weakly decreasing and ∑_{i} λ_{i} = n.

To every λ is associated a Young subgroup

𝔖_{λ} = 𝔖_{{1,...,λ_{1}}} × 𝔖_{{λ_{1}+1,...,λ_{1}+λ_{2}}} × ⋯

The corresponding coset rep M^{λ} (for 1 ↑_{𝔖_{λ}}^{𝔖_{n}}) is called a permutation module. These are not irreducible, but we will find an ordering > of partitions such that

M^{λ} = S^{λ} ⊕ _{μ>λ}^{⨁} K_{μλ}S^{μ}

where the S^{μ} are irreps and the K_{μλ} multiplicities.

To conveniently describe M^{λ}: The Ferrers diagram of λ is the set of dots or cells

λ = {(i, j) ∈ (ℤ^{+} )^{2} | 1 ≤ j ≤ λ_{i}}.

Ex.

(4, 4, 2) = \begin{matrix}• & • & • & • \\ • & • & • & • \\ • & • \end{matrix} =  (2,3)  .

A Young tableau of shape λ or λ-tableau, written t = t^{λ} or sh t = λ, is a bijection

t : λ → {1, 2, …, n}, t_{i,j} := t(i, j).

A tabloid, {t}, is an equivalence class of tableaux with the same corresponding rows.

Ex. All tableaux of shape (2, 1) are

\begin{matrix}1 & 2, & 2 & 1, & 1 & 3, & 3 & 1, & 2 & 3, & 3 & 2. \\ 3 & & 3 & & 2 & & 2 & & 1 & & 1 \end{matrix}

If t is the first tableau in the list

\{t\} = \left\{{1 2,  2 1 \atop 3  3}\right\} := 1 2 3 .

A π ∈ 𝔖_{n} acts on tableau t = (t_{i,j}) by πt = (πt_{i,j}) and thus acts on tabloids. With this action

M^{λ} = ℂ[{t} | all λ-tabloids {t} ].

Ex. λ = (n) gives the trivial rep

M^{(n)} = ℂ[ 1 2 ⋯ n ].

λ = (1, 1, …, 1) := (1^{n}) gives the regular rep

M^{(1^{n})} ≅ ℂ[𝔖_{n}].

λ = (n−1, 1) gives the defining rep (ignore 1st row)

M^{(n−1,1)} ≅ ℂ[1, 2, …, n].

B. Orderings on partitions For partitions λ = (λ_{1}, …, λ_{l}) and μ = (μ_{1}, …, μ_{m}) of n, the dominance partial order, λ ⊵ μ, is

for all i ≥ 1: λ_{1} + ⋯ + λ_{i} ≥ μ_{1} + ⋯ + μ_{i} and the lexicographic (lex) total order, λ > μ, is

for some i ≥ 1: λ_{i} > μ_{i} and λ_{j} = μ_{j} for j < i. Ex. (3, 3) ⊳ (3, 2, 1) : 3 ≥ 3, 3 + 3 > 3 + 2, … (3, 3), (4, 1, 1) incomp in ⊵ : 3 < 4, 3 + 3 > 4 + 1. (4, 1, 1) > (3, 3) : 4 > 3. (3, 3) > (3, 2, 1) : 3 = 3, 3 > 2. Proposition 14 1. λ ⊵ μ implies λ ≥ μ.

2. (Dominance Lemma, DL) If ∀i entries of row i of tableau s^{μ} are in different col’s of t^{λ} then λ ⊵ μ. Proof. 2. Sort each column of t^{λ} so the entries in the first i rows of s^{μ} lie in the first i rows of t^{λ}. ∑_{j≤i} λ_{j} = # elements in first i rows of t^{λ}

≥ # elements in first i rows of s^{μ} = ∑_{j≤i} μ_{j}.

C. The irreducible Specht modules If H ⊆ 𝔖_{n} then let

H^{−} = _{π∈H}^{∑}(sgn π)π ∈ ℂ[𝔖_{n}].

If tableau t has columns C_{1}, …, C_{m} then let C_{t} := 𝔖_{C_{1}} × ⋯ × 𝔖_{C_{m}} (the column group) ,

κ_{t} := C_{t}^{−} = κ_{C_{1}}κ_{C_{2}} ⋯ κ_{C_{m}},
e_{t} := κ_{t}{t} (the polytabloid) .

Ex. If t = 4 1 2 3 5 then

\begin{aligned}C_{t} & = & 𝔖_{\{3,4\}} × 𝔖_{\{1,5\}} × 𝔖_{\{2\}}, \\ κ_{t} & = & ϵ − (3, 4) − (1, 5) + (3, 4)(1, 5) \\ & = & (ϵ − (3, 4))(ϵ − (1, 5)), \\ e_{t} & = & 4 1 2 3 5 − 3 1 2 4 5 − 4 5 2 3 1 + 3 5 2 4 1 \end{aligned} .

Lemma 15 If π ∈ 𝔖_{n} and t is a tableau then κ_{πt} = πκ_{t}π^{−1} and e_{πt} = πe_{t}.

Partition λ has Specht module

S^{λ} = ℂ[e_{t}| all λ-tableaux t ].

Ex. 1. λ = (n) gives the trivial rep: Any (n)-tableau

t has e_{t} = 1 2 ⋯ n so

πe_{t} = e_{πt} = e_{t}.

2. λ = (1^{n}) gives the sign rep: For any t = t^{(1^{n})}

πe_{t} = π𝔖_{n}^{−}{t} = (sgn π)e_{t}.

3. λ = (n − 1, 1): Abbreviate t = t^{λ} to the 2nd row

e_{t} = \begin{matrix}i & ⋯ & k \\ j \end{matrix} − \begin{matrix}j & ⋯ & k \\ i \end{matrix} = j − i,
S^{(n−1,1)} = ℂ[j − i|1 ≤ i < j ≤ n],
= {∑_{i=1}^{n} c_{i}i| ∑_{i=1}^{n} c_{i} = 0}.

A G-module U is cyclic, generated by u ∈ U if

U = ℂ[gu | g ∈ G].

Corollary 16 S^{λ} is cyclic generated by any e_{t} ∈ S^{λ}.

Define an 𝔖_{n}-invariant inner product on M^{λ} by

⟨{t}, {s}⟩ = δ_{{t},{s}}.

Lemma 17 (Sign Lemma, SL) Let H ≤ 𝔖_{n}.

1. π ∈ H ⇒ πH^{−} = H^{−}π = (sgn π)H^{−}.

2. u, v ∈ M^{λ} ⇒ ⟨H^{−}u, v⟩ = ⟨u, H^{−}v⟩.

3. (b, c) ∈ H ⇒ H^{−} = k(ϵ−(b, c)) for some k ∈ ℂ[𝔖_{n}].

4. b, c in the same row of tableau s and (b, c) ∈ H ⇒ H^{−}{s} = 0.

Corollary 18 I. If sh t = λ, sh s = μ with κ_{t}{s} ≠ 0 then λ ⊵ μ. If λ = μ then κ_{t}{s} = ±e_{t}.

II. (James’ Submodule Theorem) If U is a submodule of M^{μ} then U ⊇ S^{μ} or U ⊆ S^{μ⊥}.

III. The S^{μ}, μ ⊢ n, are all inequiv 𝔖_{n}-irreps over ℂ.

Proof. I. b, c in the same row of s ⇒ b, c not in the same col of t (else κ_{t}{s} = 0 by SL4) ⇒ λ ⊵ μ (DL). If λ = μ ⇒ {s} = π{t} for some π ∈ 𝔖_{n} and by SL1

κ_{t}{s} = κ_{t}π{t} = (sgn π)κ_{t}{t} = ±e_{t}.

II. If u ∈ U and t = t^{μ} ⇒ κ_{t}u = ce_{t} for c ∈ ℂ by I. If some c ≠ 0 ⇒ e_{t} ∈ U and S^{μ} ⊆ U. Else use SL2 to show U ⊆ S^{μ⊥}.

D. The standard tableaux basis for S^{λ} Tableau t is standard if its rows and col’s increase.

Ex. 1 3 4 2 5 is standard; 2 3 4 1 5 is not.

Theorem 19 A basis for S^{λ} is

{e_{t} | t a standard λ-tableau }.

Independence. A composition is a permutation of a partition. If {t} is a tabloid, for i ≥ 1 let

{t}^{i} = tabloid of all entries ≤ i in {t} ,
λ^{i} = the shape of {t}^{i}, a composition.

Ex. If {t} = 2 3 1 then

\begin{aligned}\{t\}^{1} & = \begin{matrix}∅ \\ 1 \end{matrix} & \{t\}^{2} & = 2 1 & \{t\}^{3} & = 2 3 1 \\ λ^{1} & = (0, 1) & λ^{2} & = (1, 1) & λ^{3} & = (2, 1). \end{aligned}

Dominance order on tabloids is

{t} ⊵ {s} ⟺ λ^{i} ⊵ μ^{i} ∀i.

Proposition 20 1. (Tabloid Dominance Lemma) If k < l and k is lower than l in {t} then (k, l){t} ⊳ {t}.

2. t standard and {s} appears in e_{t} ⇒ {t} ⊵ {s}.

3. The standard e_{t} are independent.

Span. To show e_{t} a lin comb of standard e_{s} one can assume the col’s of t increase. (Else ∃π ∈ C_{t} with col’s of πt increasing and e_{πt} = (sgn π)e_{t}.) If t has row descent a > b, it suffices to find tableaux s s.t.

1. e_{t} = − ∑_{s}(sgn π_{s})e_{s} where π_{s}t = s,

2. [s] ⊳ [t] for all s, [s] = col tabloid.

A (resp B) := entries of t below a (resp above b).

t =  \begin{aligned}& B \\ a & b \\ A \end{aligned}  .

The s are all tableaux gotten by permuting A ∪ B s.t. the elements of A∪B still increase in their col’s.

Ex. If t = 2 1 5 3 4 6 with 2 > 1 ⇒ A = {2, 3}, B =

{1},

s_{1} = 1 3 5 2 4 6  s_{2} = 1 2 5 3 4 6
π_{1} = (1, 3, 2)  π_{2} = (1, 2)
e_{t} = −(e_{s_{1}} − e_{s_{2}}).

E. Young’s natural representation The matrix rep X^{λ} for S^{λ} in the standard basis is Young’s natural rep. Since (k, k+1), 1 ≤ k < n, generate 𝔖_{n} it suffices to compute M = X^{λ}((k, k + 1)). If t is standard than to find M_{t,t} we must express (k, k + 1)e_{t} in the standard basis.

1. If k, k + 1 in the same col of t ⇒ (k, k + 1) ∈ C_{t} ∴ (k, k + 1)e_{t} = −e_{t}.

2. If k, k + 1 in the same row of t ⇒ (k, k + 1)t has row descent k + 1 > k

∴ (k, k + 1)e_{t} = e_{t} ± other e_{s} with [s] ⊳ [t].

3. Else (k, k + 1)t = t′ where t′ is standard ∴ (k, k + 1)e_{t} = e_{t′}.

Ex. If λ = (2, 1) then the standard tableaux are

t_{1} = 1 3 2 and t_{2} = 1 2 3 .

If (k, k + 1) = (1, 2) then

(1, 2)e_{t_{1}} = 2 3 1 − 1 3 2 = −e_{t_{1}}.

(1, 2)e_{t_{2}} was essentially computed last slide.

∴ X^{(2,1)} ((1, 2)) = ( \begin{matrix}−1 & −1 \\ 0 & 1 \end{matrix} ) .

F. The Branching and Young Rules Partition λ has inner corner (i, j) ∈ λ if

λ^{−} = λ \ (i, j) is a partition,

and outer corner (i, j) ∉ λ if

λ^{+} = λ ∪ (i, j) is a partition.

Ex. If λ = \begin{matrix}• & • & • & • \\ • & • \\ • & • \end{matrix} then

\begin{matrix}λ^{−} : & \begin{matrix}• & • & • \\ • & • \\ • & • \end{matrix} & \begin{matrix}• & • & • & • \\ • & • \\ • \end{matrix} \\ λ^{+} : & \begin{matrix}• & • & • & • & • \\ • & • \\ • & • \end{matrix} & \begin{matrix}• & • & • & • \\ • & • & • \\ • & • \end{matrix} & \begin{matrix}• & • & • & • \\ • & • \\ • & • \\ • \end{matrix} \end{matrix}

Theorem 21 (Branching Rule) If λ ⊢ n then 1. S^{λ} ↓_{𝔖_{n−1}} ≅ ⨁_{λ^{−}} S^{λ^{−}},

2. S^{λ} ↑^{𝔖_{n+1}} ≅ ⨁_{λ^{+}} S^{λ^{+}} .

Ex. From the example above

\begin{aligned}S^{(4,2,2)} ↓_{𝔖_{7}} & ≅ & S^{(3,2,2)} ⊕ S^{(4,2,1)} , \\ S^{(4,2,2)} ↑^{𝔖_{9}} & ≅ & S^{(5,2,2)} ⊕ S^{(4,3,2)} ⊕ S^{(4,2,2,1)} . \end{aligned}

Tableau T is called semistandard if it has strictly increasing columns while its rows weakly increase. The content of T, ct T, is the composition μ s.t.

μ_{i} = # of i’s in T .

Ex. T = 1 1 4 2 4 has content μ = (2, 1, 0, 2).

The Kostka numbers are

K_{λμ} = # of semistandard T, shape λ, content μ .

Theorem 22 (Young’s Rule)

M^{μ} ≅ _{λ⊵μ}^{⨁} K_{λμ}S^{λ}.

Ex. If μ = (2, 1, 1) then the possible λ ⊵ μ are

λ : (2, 1, 1) (2, 2)  (3, 1)  (4)
T : 1 1 2 3  1 1 2 3 1 1 2 3 ^{1 1 2 3}

1 1 3 2

So M^{(2,1,1)} ≅ S^{(2,1,1)} ⊕ S^{(2,2)} ⊕ 2S^{(3,1)} ⊕ S^{(4)} .

Note: For any μ, K_{μμ} = 1 = K_{(n)μ}.

III. Combinatorics: A. Schensted’s algorithm

Let SYT (λ) be the set of standard λ-tableaux and

f^{λ} := | SYT (λ)| = dim S^{λ}.

For any group with irreps V^{(i)}: ∑_{i}(dim V^{(i)})^{2} = |G|. If G = 𝔖_{n} the formula can be proved combinatorially

_{λ⊢n}^{∑}(f^{λ})^{2} = n!

Proof. Construct the Robinson-Schensted bijection

π ⟷^{R−S} (P, Q)

where π ∈ 𝔖_{n} and P, Q ∈ SYT (λ) for some λ.

π →^{R−S} (P, Q): Insert x ∈ ℤ^{+} into increasing tableau P to get increasing tableau P′, r_{x}(P) = P′, by

1. Let i := 1

2. If x > every element of row i of P, put it at the end of the row and stop.

3. Else exchange x and the smallest P_{i,j} > x. (We say x bumps P_{i,j}.) Set i := i + 1 and go to 2.

Ex. Suppose x = 2

P = 1 3 ← 2 1 2  1 2  1 2 = r_{2}(P).
4 5  4 5 ← 3 3 5  3 5
← 4 4

Now if π = x_{1} … x_{n} then construct a sequence of pairs (∅, ∅) = (P_{0}, Q_{0}), …, (P_{n}, Q_{n}) = (P, Q) by

P_{k} = r_{x_{k}}(P_{k−1}),
Q_{k} = Q_{k−1} ⊎ k with k in sh P_{k} \ sh P_{k−1}.

Ex. π = 1 2 3 4 5 3 2 4 1 5 →^{R−S} ( \begin{matrix}1 & 4 & 5 \\ 2 \\ 3 \end{matrix} , \begin{matrix}1 & 3 & 5 \\ 2 \\ 4 \end{matrix} ) by

P_{k} : ∅, 3, 2, 2 4, 1 4, 1 4 5 = P
3 3 2 2
3  3
Q_{k} : ∅, 1, 1, 1 3, 1 3, 1 3 5 = Q
2 2 2 2
4  4

(P, Q) →^{R−S} π: Delete P_{i,j}, r_{(i,j)}^{−1}P = (P′, x), by

1. Remove x := P_{i,j} from its row and set i := i − 1.

2. While i ≥ 1 exchange x and the greatest R_{i,j} < x and set i := i − 1. Ex. Do the Ex on the previous page backwards. Starting with (P, Q) we obtain the reverse sequence (P_{n}, Q_{n}), …, (P_{0}, Q_{0}) and π = x_{1} … x_{n} by

\begin{aligned}Q_{k−1} & = & Q_{k} \ k \\ (P_{k−1}, x_{k}) & = & r_{(i,j)}^{−1}P_{k} where Q_{i,j} = k. \end{aligned}

B. Properties of Robinson-Schensted If π →^{R−S} (P, Q) then the P -tableau of π is P (π) = P and the Q-tableau of π is Q(π) = Q. If π = x_{1} … x_{n} then π^{r} = x_{n} … x_{1}. A subsequence of π = x_{1} … x_{n}, σ ⊆ π, is

σ = x_{k_{1}}, x_{k_{2}}, …, x_{k_{m}} with k_{1} < k_{2} < … < k_{m}.

Proposition 23 1. P (π^{r}) = P (π)^{t} (the transpose)

2. If sh P (π) = (λ_{1}, …, λ_{l}) then

λ_{1} = length of a longest increasing σ ⊆ π,
l = length of a longest decreasing σ ⊆ π.

3. If π →^{R−S} (P, Q) then π^{−1} →^{R−S} (Q, P).

4. ∑_{λ⊢n} f^{λ} = # of involutions in 𝔖_{n} .

Proof. 1. One can define column insertion c_{y}(P) and prove r_{x}c_{y}(P) = c_{y}r_{x}(P). Then

\begin{matrix}P (π^{r}) = r_{x_{1}} ⋯ r_{x_{n}}(∅) = r_{x_{1}} ⋯ r_{x_{n−1}}c_{x_{n}}(∅) \\ = c_{x_{n}}r_{x_{1}} ⋯ r_{x_{n−1}}(∅) = … = c_{x_{n}} ⋯ c_{x_{1}}(∅) = P (π)^{t}. \end{matrix}

4. By 3: π →^{R−S} (P, P) iff π = π^{−1}. So _{λ⊢n}^{∑} f^{λ} = # of P = # of involutions π .

When does P (π) = P (σ)?

Ex. For 𝔖_{3}: P (123) = 1 2 3, P (321) = (1 2 3)^{t},

P (213) = P (231) = {1 3 \atop 2} , P (132) = P (312) = {1 2 \atop 3} .

π, σ differ by a Knuth transposition if for x < y < z:

\begin{matrix}1. \{π, σ\} = \{x_{1} … yxz … x_{n}, x_{1} … yzx … x_{n}\}, or \\ 2. \{π, σ\} = \{x_{1} … zxy … x_{n}, x_{1} … xzy … x_{n}\}. \end{matrix}

Also π, σ are Knuth equivalent, π ≅^{K} σ, if

π = π_{1}, π_{2}, …, π_{k} = σ

with π_{i}, π_{i+1} differing by a Knuth transposition ∀i.

Ex. 2 1 3 ≅^{K} 2 3 1 and 1 3 2 ≅^{K} 3 1 2.

Theorem 24 (Knuth) P (π) = P (σ) ⟺ π ≅^{K} σ.

Proof sketch. “⇐” Type 1 transposition: x’s (resp z’s) insertion path is weakly left (resp strictly right) of y’s so P (π) = P (σ). Type 2: then π^{r}, σ^{r} differ by type 1 and

P (π^{r}) = P (σ^{r}) ⇒ P (π)^{t} = P (σ)^{t} ⇒ P (π) = P (σ).

C. Schützenberger’s jeu de taquin

If μ ⊆ λ then one has the skew diagram

λ/μ = {(i, j) | (i, j) ∈ λ, (i, j) ∉ μ}.

Ex. If μ = (2, 1) and λ = (4, 4, 1)

λ/μ = .

If P is an increasing tableau, sh P = λ/μ, a backward slide into an inner corner c of μ, j^{c}(P) = P′, is

While c = (i, j) is not an inner corner of λ, exchange c and the smaller of P_{i+1,j} , P_{i,j+1} .

Ex. If c = (1, 2) then

P =  • 1 5, 1 • 5, 1 3 5,  1 3 5 = j^{c}(P).
2 3 7  2 3 7  2 • 7  2 7 •
4  4  4  4

A forward slide into outer corner d = (i, j) of λ, j_{d}(P) = P′, exchanges d with the larger of the numbers P_{i−1,j}, P_{i,j−1}, etc. until an outer corner of μ is reached. Clearly if j^{c}(P) = P′ vacating d then

j_{d}j^{c}(P) = P and j^{c}j_{d}(P′) = P′.

Let δ_{n} = (n − 1, n − 2, …, 1). Any π = x_{1} … x_{n} has a δ_{n+1} /δ_{n}-tableau with x_{j} in (n − j + 1, j).

Ex. π = 132 has tableau π = 2 3 1 .

A backward slide sequence for P = P_{1} is

(c_{1}, …, c_{l}) with P_{i+1} = j^{c_{i}}(P_{i}) defined ∀i.

If l = |μ| where sh P = λ/μ let j(P) := j^{c_{l}} ⋯ j^{c_{1}}(P). Ex. (cont) If c_{1} = (2, 1), c_{2} = (1, 2), c_{3} = (1, 1)

π = 2 3 1 , {2 \atop 1 3} , {2 \atop 1 3} , {1 2 \atop 3} = j(π).

Theorem 25 (Schützenberger) j(π) = P (π).

Proof sketch. If P has rows R_{1}, …, R_{l} then its row word is ρ(P) = R_{l}R_{l−1} … R_{1}.

Ex. P = {1 3 5 7 \atop 2 4 6} has ρ(P) = 2 4 6 1 3 5 7.

It is easy to prove P (ρ(P)) = P. Furthermore if P

is skew and P′ = j^{c}(P) then ρ(P′) ≅^{K} ρ(P). So

ρ(j(π)) ≅^{K} ρ(π) = π ⇒^{apply P} j(π) = P (π).

D. The hook formula The hook and hooklength of (i, j) ∈ λ are H_{i,j} = {(i′, j), (i, j′) ∈ λ | i′ ≥ i, j′ ≥ j}, h_{i,j} = |H_{i,j}|. The arm length and leg length of the hook are a_{i,j} = |{(i, j′) ∈ λ | j′ > j}|, l_{i,j} = |{(i′, j) ∈ λ | i′ > i}|. Ex. In λ = (4^{2}, 3, 1)

H_{2,2} = \begin{matrix}• & a & a \\ l \end{matrix} and h_{2,2} = 4, a_{2,2} = 2, l_{2,2} = 1.

Theorem 26 (Frame-Robinson-Thrall) If we have λ ⊢ n, then

f^{λ} = \frac{n!}{_{(i,j)∈λ}^{∏} h_{i,j}} .

Ex. (3, 2) ⊢ 5 has hooklengths

4 3 1 2 1 .

So f^{(3,2)} = \frac{5!}{4·3·2·1^{2}} = 5 which agrees with

\begin{matrix}1 2 3, & 1 2 4, & 1 2 5, & 1 3 4, & 1 3 5. \\ 4 5 & 3 5 & 3 4 & 2 5 & 2 4 \end{matrix}

The Novelli-Pak-Stoyanovskii Proof. Preprint: http://www.math.harvard.edu/~pak/papers

Show n! = f^{λ} ∏_{(i,j)} h_{i,j} with a bijection

T ⟷ (P, J)

where sh T = sh P = sh J = λ, T is any Young tableau, P is standard, and

−l_{i,j} ≤ J_{i,j} ≤ a_{i,j} ∀(i, j) ∈ λ.

T → (P, J): If T is standard of shape λ/μ and entry x ∈ ℤ^{+} is in c then j^{c}(T) has x moving in place of • and terminating when it becomes standard.

Ex. If c = (1, 2) contains 6

T =  6 1 5, 1 6 5, 1 3 5 = j^{c}(T).
2 3 7  2 3 7  2 6 7
4  4  4

Lex order λ’s cells c_{1} > c_{2} > … > c_{n}. Define

T = T_{1}, …, T_{n} = P where T_{k} = j^{c_{k}}(T_{k−1}).

Define J_{1}, …, J_{n} = J by J_{1} = 0 and if j^{c_{k}} starts in c_{k} = (i, j) and ends in (i′, j′) then J_{k} = J_{k−1} except

(J_{k})_{i,l} = \{ \begin{matrix}(J_{k−1})_{i,l+1} + 1 & for j ≤ l < j′, \\ i − i′ & for l = j′. \end{matrix}

Ex. For spacing purposes we use ¯1 for −1.

T_{1} = 645, 645, 645, 643, 623, 123 = P.
231 213 123 125 145 456
J_{1} = 000, 000, 000, 00¯1, 0¯1¯1, 00¯1 = J.
000 010 200 200 200 200

(P, J) → T: To reconstruct (P, J) = (T_{n}, J_{n}), …, (T_{1}, J_{1}) = (T, 0), assume (T_{k}, J_{k}) has been constructed. The possible cells for c_{k} = (i, j) in T_{k} are

P = {(i′, j′)|i′ ≥ i, j′ ≥ j, (J_{k})_{i,j′} ≤ 0, i′ = i − (J_{k})_{i,j′}}.

Define j_{d} for d ∈ P by having the slide stop at c_{k}. (must prove well-defined) The code of j_{d} replaces each move north (resp west) with N (resp W) written in reverse order.

Ex. For c_{6} = (1, 1): P = {(1, 1), (1, 2), (2, 3)} and

j_{1,1} : ∅, j_{1,2} : W, j_{2,3} = NW W.

Lex order the codes using W < ∅ < N. Then

T_{k−1} = j_{d}(T_{k}) where d ∈ P has maximum code.

Also if c_{k} = (i, j), d = (i′, j′) then J_{k−1} = J_{k} except

(J_{k−1})_{i,l} = \{ \begin{matrix}(J_{k})_{i,l−1} − 1 & for j < l ≤ j′ \\ 0 & for l = j. \end{matrix}

E. The determinantal formula

Theorem 27 (Frobenius) If (λ_{1}, …, λ_{l}) ⊢ n then

f^{λ} = n! det (1/(λ_{i} − i + j)!)

where the determinant is l × l and 1/r! = 0 if r < 0.

Ex. f^{(3,2)} = 5! | \begin{matrix}1/3! & 1/4! \\ 1/1! & 1/2! \end{matrix} | = 5.

Proof. It suffices to show the determinant equals the hook formula. We have

λ_{i} + l = h_{i,1} + i ⇒ λ_{i} − i + j = h_{i,1} − l + j.

So every row of the determinant is of the form

[⋯ 1/(h − 2)! 1/(h − 1)! 1/h!] .

After factoring out ∏_{i} 1/h_{i,1}! we get rows

[⋯ h(h − 1) h 1]

which by column operations can be turned into

[⋯ (h − 1)(h − 2) h − 1 1] .

Putting ∏_{i} 1/(h_{i,1}−1)! back in we get ∏_{i} 1/h_{i,1} times the det for λ with its first column removed, so we’re done by induction.

IV. Symmetric functions: A. Bases

Let x = {x_{1}, x_{2}, …} and also consider ℂ[[x]], the corresponding formal power series algebra. Then π ∈ 𝔖_{n} acts on f ∈ ℂ[[x]] by

πf(x_{1}, x_{2}, …) = f(x_{π1}, x_{π2}, …), π(m) := m, m > n.

We say f is symmetric if

πf = f, ∀π ∈ 𝔖_{n}, ∀n.

Each partition λ = (λ_{1}, …, λ_{l}) has an associated monomial symmetric function

m_{λ} = m_{λ}(x) = ∑ x_{i_{1}}^{λ_{1}} ⋯ x_{i_{l}}^{λ_{l}}

where the sum is over all distinct monomials that have exponents λ_{1}, …, λ_{l}.

Ex.

m_{(2,2,1)} = x_{1}^{2}x_{2}^{2}x_{3} + x_{1}^{2}x_{2}x_{3}^{2} + x_{1}x_{2}^{2}x_{3}^{2} + x_{1}^{2}x_{2}^{2}x_{4} + ⋯

The algebra of symmetric functions is

Λ = Λ(x) = ℂ[m_{λ}].

Note: f = ∏_{i≥1}(1 + x_{i}) is symmetric but isn’t in Λ. We have a grading by degree

Λ = ⊕_{n≥0}Λ^{n}, dim Λ^{n} = p(n), the # of λ ⊢ n. p_{n} := m_{(n)} = _{i≥1}^{∑} x_{i}^{n} (power sum).

e_{n} := m_{(1^{n})} = _{i_{1}<...<i_{n}}^{∑} x_{i_{1}} ⋯ x_{i_{n}} (elementary).

h_{n} := _{λ⊢n}^{∑} m_{λ} = _{i_{1}≤...≤i_{n}}^{∑} x_{i_{1}} ⋯ x_{i_{n}} (complete homo).

Ex. \begin{aligned}p_{3} & = & x_{1}^{3} + x_{2}^{3} + x_{3}^{3} + ⋯ \\ e_{3} & = & x_{1}x_{2}x_{3} + x_{1}x_{2}x_{4} + x_{1}x_{3}x_{4} + ⋯ \\ h_{3} & = & x_{1}^{3} + ⋯ + x_{1}^{2}x_{2} + ⋯ + x_{1}x_{2}x_{3} + ⋯ \end{aligned}

Proposition 28 We have the generating functions

\begin{aligned}1. E(t) & := & ∑_{n≥0} e_{n}(x)t^{n} & = & _{i≥1}^{∏}(1 + x_{i}t). \\ 2. H(t) & := & ∑_{n≥0} h_{n}(x)t^{n} & = & _{i≥1}^{∏} \frac{1}{1 − x_{i}t}. \\ 3. P (t) & := & ∑_{n≥1} p_{n}(x)t^{n} & = & ln _{i≥1}^{∏} \frac{1}{1 − x_{i}t}. \end{aligned}

If f = p, e, or h and λ = (λ_{1}, …, λ_{l}) let f_{λ} = ∏_{i} f_{λ_{i}}.

Theorem 29 Three bases for Λ^{n} are

1. {e_{λ} | λ ⊢ n}, 2. {h_{λ} | λ ⊢ n}, 3. {p_{λ} | λ ⊢ n}.

Proof. 1 ⇒ XS2. |{h_{λ}}| = p(n) so it suffices to show every e_{n} is a polynomial in h_{k}. But H(t)E(−t) = 1 and taking the coefficient of t^{n}, n ≥ 1,

n ; ∑ ; k=0 (−1)^{k}h_{n−k}e_{k} = 0 ⇒ e_{n} = h_{1}e_{n−1} − h_{2}e_{n−2} + ⋯

B. Schur functions For tableau T let x^{T} = x^{μ} = x^{μ_{1}} ⋯ x^{μ_{m}} where T ’s content is μ = (μ_{1}, …, μ_{m}). A Schur function is

s_{λ}(x) = _{T}^{∑} x^{T}

summed over all semistandard T of shape λ. Note s_{(n)} = h_{n} and s_{(1^{n})} = e_{n}.

Ex. \begin{aligned}T : & 1 1 & 1 2 & … & 1 2 1 3 & … \\ & 2 & 2 & & 3  2 \\ s_{(2,1)} = & x_{1}^{2}x_{2} + & x_{1}x_{2}^{2} + & ⋯ + & 2x_{1}x_{2}x_{3} + & ⋯ \end{aligned}

The alternant for λ = (λ_{1}, …, λ_{l}) is

a_{λ} = |x_{i}^{λ_{j}}|_{1≤i,j≤l}.

If δ = (l − 1, l − 2, …, 0) then a_{δ} = Vandermonde. Let χ^{λ} be an irr character and k_{μ} be the size of a conjugacy class in 𝔖_{n}. Let K_{λμ} be a Kostka number. Theorem 30 If λ = (λ_{1}, …, λ_{l}) then

1. {s_{λ} | λ ⊢ n} is a basis of Λ^{n}.

2. s_{λ} = ∑_{μ⊴λ} K_{λμ} m_{μ}.

3. s_{λ} = \frac{1}{n!} ∑_{μ⊢n} k_{μ} χ_{μ}^{λ} p_{μ}.

4. s_{λ}(x_{1}, …, x_{l}) = \frac{a_{λ+δ}}{a_{δ}} .

5. (Jacobi-Trudi) s_{λ} = |h_{λ_{i}−i+j} |_{1≤i,j≤l}.

Proof of 5. (Gessel-Viennot-Lindström) A lattice path in ℤ^{2} is p = s_{1}, s_{2}, … where each s_{i} is a unit step N or E. Label the E steps by

N(s_{i}) = (number of N steps preceding s_{i}) + 1.

[figure: p =; s_{1}; s_{2}; 2; s_{3}; 2; s_{4}; s_{5}; 3; s_{6}; 3; s_{7}; s_{8}; x^{P} = x_{2}^{2}x_{3}^{2}.]

If p is from (a, b) to (c, d) write (a, b) →^{p} (c, d). Let

x^{p} := _{s_{i}=E∈p}^{∏} x_{N(si)} ⇒ h_{n} = _{(a,b)→^{p}(a+n,∞)}^{∑} x^{p}.

Fix (u_{1}, …, u_{l}), (v_{1}, …, v_{l}) & form P = (p_{1}, …, p_{l}) where for all i : u_{i} →^{p_{i}} v_{πi} for some π ∈ 𝔖_{l}. Let

x^{P} := _{i}^{∏} x^{p_{i}} and sgn P := sgn π.

[figure: P =; u_{4}; u_{3}; u_{2}; u_{1}; ⋮; ⋮; ⋮; ⋮; v_{4}; v_{3}; v_{2}; v_{1}; \begin{aligned}x^{P} & = & x_{2}^{4}x_{3}^{2}x_{4}, \\ sgn P & = & sgn (1, 2, 3)(4) \\ & = & +1. \end{aligned}]

Given λ = (λ_{1}, …, λ_{l}) pick

u_{i} := (1 − i, 0)  and v_{i} := (λ_{i} − i + 1, ∞) ⇒
h_{λ_{i}−i+j} = _{u_{j}→^{p}v_{i}}^{∑} x^{p} and |h_{λ_{i}−i+j} | = _{P}^{∑}(sgn P)x^{P}.

Define a sign-reversing involution P ⟷^{ι} P′ by

1. If P is non-∩ then P′ = P.

2. Else, let (i, j) be the lex least pair s.t. p_{i} ∩ p_{j} ≠ ∅, and w ∈ p_{i} ∩ p_{j} be SW -most, so P′ = (P \ p_{i}, p_{j}) ∪ p′_{i}, p′_{j}.

p′_{i} := u_{i} →^{p_{i}} w →^{p_{j}} v_{πj} and p′_{j} := u_{j} →^{p_{j}} w →^{p_{i}} v_{πi}._{[figure: u_{4}; u_{3}; u_{2}; u_{1}; v_{4}; v_{3}; v_{2}; v_{1}; w; →^{ι}; u_{4}; u_{3}; u_{2}; u_{1}; v_{4}; v_{3}; v_{2}; v_{1}; w]}

All terms in the det cancel except P for non-∩ paths which correspond to semistandard λ-tableaux T.

[figure: P =; u_{3}; u_{2}; u_{1}; v_{3}; v_{2}; v_{1}; 4; 2; 3; 1; 2; 2; T = 1 2 2 2 3 4 .]

C. Knuth’s algorithm Theorem 31 (Littlewood) If y = {y_{1}, y_{2}, …} then

_{λ}^{∑} s_{λ}(x)s_{λ}(y) = _{i,j≥1}^{∏} 1/(1 − x_{i}y_{j}).

Proof (Knuth). Want a wt-preserving bijection

π ⟷^{R−S−K} (T, U)

where T, U are semistandard of the same shape,

wt(T, U) = x^{T} y^{U}.

Furthermore, π is a generalized permutation: a 2line array with entries in ℤ^{+} in lex order, and

wt π = ∏ x_{j}y_{i}

where the product is over all col ( \begin{matrix}i \\ j \end{matrix} ) ∈ π.

Ex. π = 1 1 1 2 2 2 3 3 1 2 with wt π = x_{1}x_{2}^{2}x_{3}^{2}y_{1}^{3}y_{2}^{2}.

The bijection is now the same as R-S. Ex. (cont)

T_{i} : ϕ , 2 , 2 3 , 2 3 3 , 1 3 3 , 1 2 3 = T,
2  2 3
U_{i} : ϕ , 1 , 1 1 , 1 1 1 , 1 1 1 , 1 1 1 = U.
2  2 2

D. The characteristic map

Let R^{n} = R(𝔖_{n}) (class functions) and R = ⊕_{n≥0}R^{n}. The characteristic map, ch : R → Λ, linearly extends

ch(χ) := \frac{1}{n!} _{μ⊢n}^{∑} k_{μ} χ_{μ} p_{μ} where χ ∈ R^{n}.

If χ^{λ} is an irr character then ch(χ^{λ}) = s_{λ} so ch is a v.s. iso which becomes an isometry if we define

⟨s_{λ}, s_{μ}⟩ = δ_{λ,μ}.

Finally for χ, ψ chars of 𝔖_{n}, 𝔖_{m} let

χ · ψ = (χ ⊗ ψ) ↑^{𝔖_{n+m}}

and extend linearly. Then we have

ch(χ · ψ) = ⟨χ · ψ, p⟩
= ⟨(χ ⊗ ψ) ↑^{𝔖_{n+m}} , p⟩
= ⟨(χ ⊗ ψ), p ↓_{𝔖_{n}×𝔖_{m}} ⟩
= \frac{1}{n!m!} _{λ⊢n, μ⊢m}^{∑} k_{λ}k_{μ}χ_{λ}ψ_{μ}p_{λ}p_{μ}
= ch(χ) ch(ψ).

Theorem 32 The map ch : R → Λ is an isomorphism of algebras.

E. The Littlewood-Richardson Rule Word R = r_{1} … r_{n} ∈ (ℤ^{+} )^{n} is a lattice permutation (lp) if for all R_{i} = r_{1} … r_{i} and all j ∈ ℤ^{+}

number of j’s ≥ number of j + 1’s in R_{i}. Such R corresponds to a standard tableau P by

if r_{i} = j then put i in row j of P.

Ex. R = 1 1 2 3 2 1 3 ⟷ P = 1 2 6 3 5 4 7 .

Theorem 33 (Littlewood-Richardson, L-R) If s_{λ}s_{μ} = _{ν}^{∑} c_{λμ}^{ν}s_{ν}

then c_{λμ}^{ν} is the number of semistandard T such that 1. sh T = ν/λ and ct T = μ,

2. the reverse row word ρ(T)^{r} is an lp. Ex. For s_{(2)} s_{(2,1)}

T : • • 1 1, • • 1, • • 1, • •
2 1 2 1 1 1
2  2
s_{(2)} s_{(2,1)} = s_{(4,1)} + s_{(3,2)} + s_{(3,1^{2})} + s_{(2^{2},1)}

The L-R rule generalizes both the Branching Rule (for s_{λ}s_{(1)} ) and Young’s Rule (for s_{(l)}s_{(m)}).

F. The Murnagham-Nakayama Rule A rim hook, H, is a skew shape that’s a lattice path. A rim hook tableau T has rows and cols weakly increasing and all i’s in a rim hook for each i ∈ T.

Ex. H = and T = 1 1 1 2 4 2 2 2 2 4 3 3 3 4 4 .

Rim hook H has leg length

l(H) = (number of rows of H) − 1

and a rim hook tableau T has sign sgn T = _{H∈T}^{∏}(−1)^{l(H)}.

Ex. (cont) l(H) = 2, sgn T = (−1)^{0+1+0+2} = −1. Theorem 34 (Murnagham-Nakayama) We have

χ_{μ}^{λ} = _{T}^{∑} sgn T

sum over all rim hook tableaux, sh T = λ, ct T = μ. Note χ_{(1^{n})}^{λ} = f^{λ} is a special case.

Ex. For χ = χ^{(2,1)}

μ (1^{3}) (2, 1) (3)
T 1 2, 1 3  1 1, 1 2 1 1
3 2 2 1 1
χ_{μ} 1 + 1 = 2  1 − 1 = 0 −1

G. Chromatic symmetric functions A proper coloring of G = (V, E) is c : V → {1, …, t}

uv ∈ E ⇒ c(u) ≠ c(v).

The chromatic polynomial of G is P (G) = P (G, t) := # of proper c : V → {1, …, t}.

Ex. If G = [figure: v_{1}; v_{2}; v_{3}] then P (G) = _{i}^{∏} (# of c(v_{i})) = t(t − 1)(t − 2).

The chromatic symmetric function of G is X(G) = X(G, x) = _{proper c:V →ℤ^{+}}^{∑} x_{c(v_{1})} ⋯ x_{c(v_{n})}.

Ex. \begin{matrix}G : & [figure: 1; 2; 1] & [figure: 2; 1; 2] & ⋯ & [figure: 1; 2; 3] & ⋯ \\ X(G) = & x_{1}^{2}x_{2} + & x_{1}x_{2}^{2} + & ⋯ + & 6x_{1}x_{2}x_{3} + & ⋯ \end{matrix}

Poset P has incomparability graph G = inc P with

V = P, E = {uv | u, v incomparable in P } and is 3 + 1-free if it has no induced {a < b < c, d}. Conjecture 35 (Stanley-Stembridge) If poset P is 3+1-free and X(inc P) = ∑_{λ} c_{λ}e_{λ} ⇒ c_{λ} ∈ ℤ^{+} ∪{0}. Gasharov has proved this with e_{λ} replaced by s_{λ}.

Acknowledgment. I would like to thank Shalom Eliahou for carefully reading these slides and pointin out a number of errata.