4.19. Lecture 19

4.19.1. Morphisms between permutation modules

We aim to complete the proof of Theorem 4.17.12 by showing that $(\pi,{\mathcal{S}}^{\lambda})$ and $(\pi,{\mathcal{S}}^{\mu})$ are non-isomorphic representations of $S_{n}$ if $\lambda\neq\mu$ .

To do this, we introduce a partial order $\unlhd$ on the set of all Young diagrams of size $n$ .

Definition 4.19.1.

Let $\lambda,\mu\vdash n$ . We write $\lambda\unlhd\mu$ if

\sum_{i=1}^{m}\lambda_{i}\leq\sum_{i=1}^{m}\mu_{i},

for all $1\leq m\leq\min\{|\lambda|,|\mu|\}$ .

Proposition 4.19.2.

The relation $\unlhd$ defines a partial order on the set of all Young diagrams of size $n$ .

Proof.

This is Problem 4.19.3 (not examinable). ∎

Example 4.19.3.

For the partitions of $6$ , we have

(4,2)\unlhd(5,1)\unlhd(6),

and

(3,2,1)\unlhd(4,1,1)\unlhd(4,2),

as well as

(3,2,1)\unlhd(3,3)\unlhd(4,2).

Observe that we $(3,3)\not\unlhd(4,1,1)$ , since $4+1<3+3$ , but also $(4,1,1)\not\unlhd(3,3)$ , since $3<4$ .

Proposition 4.19.4.

Let $\lambda,\mu\vdash n$ . Suppose that there exists $t\in\mathbf{YT}^{\lambda}$ such that the morphism

P_{t}=\sum_{\sigma\in C(t)}\operatorname{sgn}(\sigma)\pi(\sigma)

on ${\mathcal{M}}^{\mu}$ is non-zero. Then $\mu\unlhd\lambda$ .

Proof.

If $P_{t}\neq 0$ , then there exists a Young tableau $s$ of shape $\mu$ such that $P_{t}[s]\neq 0$ . Let $i$ and $j$ be two numbers from the same row of $s$ . If $i$ and $j$ were in the same column of $t$ , then $(ij)\in C(t)$ , and in a similar way to the proof of Proposition 4.18.4, writing $H=\langle(ij)\rangle=\{e,(ij)\}$ and letting $r_{1},\ldots,r_{m}\in C(t)$ be a set of representatives for $C(t)/H$ (i.e. $C(t)=r_{1}H\sqcup r_{2}H\sqcup\ldots\sqcup r_{m}H$ ), we would then have

P_{t}[s]=\sum_{j}\pi(r_{j})\big{(}\pi(e)-\pi(ij)\big{)}[s]=0.

Thus any two numbers from the same row of $s$ are in different columns of $t$ . There are $\mu_{1}$ numbers in the first row of $s$ , which must be placed into different columns of $t$ ; $t$ has $\lambda_{1}$ columns, hence $\mu_{1}\leq\lambda_{1}$ . After placing out the numbers from the first row, we then must place out the $\mu_{2}$ numbers into the columns of $t$ . Having already placed out the numbers of the first row of $s$ , there are then $(\lambda_{1}-\mu_{1})+\lambda_{2}$ columns available to put them in, hence $\mu_{2}\leq(\lambda_{1}-\mu_{1})+\lambda_{2}$ , i.e. $\mu_{1}+\mu_{2}\leq\lambda_{1}+\lambda_{2}$ . Proceeding in this manner gives $\mu\unlhd\lambda$ . ∎

Proposition 4.19.5.

If there exists an $S_{n}$ -homomorphism from $(\pi,{\mathcal{M}}^{\lambda})$ to $(\pi,{\mathcal{M}}^{\mu})$ whose restriction to ${\mathcal{S}}^{\lambda}$ is non-zero, then $\mu\unlhd\lambda$ .

Proof.

Letting $T\in\operatorname{Hom}_{S_{n}}({\mathcal{M}}^{\lambda},{\mathcal{M}}^{\mu})$ be such that $T|_{{\mathcal{S}}^{\lambda}}\neq 0$ , i.e. we can find one of the spanning vectors ${\bf e}_{t}\in{\mathcal{S}}^{\lambda}$ such that $T({\bf e}_{t})\neq 0$ . Since ${\bf e}_{t}=P_{t}[t]$ , we then have

0\neq T({\bf e}_{t})=T(P_{t}[t])=P_{t}T([t]).

The morphism $P_{t}$ evaluated at $T([t])\in{\mathcal{M}}^{\mu}$ is non-zero, so by Proposition 4.19.4 $\mu\unlhd\lambda$ . ∎

Finishing the proof of Theorem 4.17.12.

Suppose that $(\pi,{\mathcal{S}}^{\lambda})$ and $(\pi,{\mathcal{S}}^{\mu})$ are isomorphic, with $T\in\operatorname{Hom}_{G}({\mathcal{S}}^{\lambda},{\mathcal{S}}^{\mu})$ . We decompose ${\mathcal{M}}^{\lambda}$ as

(\pi,{\mathcal{M}}^{\lambda})=(\pi,{\mathcal{S}}^{\lambda})\oplus(\pi,({% \mathcal{S}}^{\lambda})^{\perp}),

and trivially extend $T$ to an morphism $\widetilde{T}$ on all of ${\mathcal{M}}^{\lambda}$ by setting it to zero on $({\mathcal{S}}^{\lambda})^{\perp}$ , i.e.

\widetilde{T}({\bf v}+{\bf w}):=T({\bf v})\qquad\forall{\bf v}\in{\mathcal{S}}% ^{\lambda},\;{\bf w}\in({\mathcal{S}}^{\lambda})^{\perp}.

This is also a $S_{n}$ -homomorphism since $(\pi,({\mathcal{S}})^{\perp})$ is a subrepresentation. Since $T$ is non-zero, so is $\widetilde{T}$ , allowing us to apply the Proposition 4.19.5 to get $\mu\unlhd\lambda$ . By symmetry (i.e. carrying out the same argument with $T^{-1}$ in place of $T$ ), we also have $\lambda\unlhd\mu$ , thus $\lambda=\mu$ . ∎

4.19.2. Standard Young Tableaux

Definition 4.19.6.

A Young tableau is said to be standard if the numbers in each row and column are increasing left to right and top to bottom.

The set of all standard Young tableaux of shape $\lambda$ is denoted $\mathbf{SYT}^{\lambda}$ . We define

f_{\lambda}=|\mathbf{SYT}^{\lambda}|.

We have the following combinatorial result which is a generalisation of the Robinson–Schensted correspondence (1938,1961).

Theorem 4.19.7 (Robinson–Schensted–Knuth correspondence, 1970).

There is a bijection between $S_{n}$ and $\bigcup_{\lambda\vdash n}\mathbf{SYT}^{\lambda}\times\mathbf{SYT}^{\lambda}$ . In particular,

n!=\sum_{\lambda\vdash n}(f_{\lambda})^{2}.

We do not have the time to prove this here. A nice discussion for the interested reader can be found in Chapter 4 of Young Tableaux by William Fulton.

Theorem 4.19.8.

The set $\{{\bf e}_{t}\,|\,t\in\mathbf{SYT}^{\lambda}\}$ is a basis of ${\mathcal{S}}^{\lambda}$ .

Proof.

We will show that for each $\lambda\vdash n$ , the set $\{{\bf e}_{t}\,|\,t\in\mathbf{SYT}^{\lambda}\}$ is linearly independent. From this, we then get that

\operatorname{dim}({\mathcal{S}}^{\lambda})\geq|\{{\bf e}_{t}\,|\,t\in\mathbf{% SYT}^{\lambda}\}|=f_{\lambda}.

By Theorem 1.6.6(ii), Theorem 4.17.12, and Theorem 4.19.7, we then have

n!=\sum_{\lambda\vdash n}\operatorname{dim}({\mathcal{S}}^{\lambda})^{2}\geq% \sum_{\lambda\vdash n}(f_{\lambda})^{2}=n!,

which gives $\operatorname{dim}({\mathcal{S}}^{\lambda})=f_{\lambda}$ , i.e. the set $\{{\bf e}_{t}\,|\,t\in\mathbf{SYT}^{\lambda}\}$ spans ${\mathcal{S}}^{\lambda}$ , and is therefore a basis.

So it remains to show that the ${\bf e}_{t}$ , $t\in\mathbf{SYT}^{\lambda}$ , are linearly independent. Before this, we need to introduce another order. ∎

Definition 4.19.9.

Define the relation $\prec$ on $\mathbf{YTD}^{\lambda}$ as follows. We say $[s]\prec[t]$ if there exists an $1\leq i\leq n$ such that for each $j<i$ we have $j$ in the same row in both $[s]$ and $[t]$ and $i$ appears in a row of $[s]$ below the row it appears in $[t]$ .

Example 4.19.10.

The six elements of $\mathbf{YTD}^{(2,2)}$ are

\ytableausetup{tabloids}\ytableaushort{12,34},\quad\ytableaushort{13,24},\quad% \ytableaushort{14,23},\quad\ytableaushort{34,12},\quad\ytableaushort{24,13},% \quad\ytableaushort{23,14}.

The order of these elements is

\ytableausetup{tabloids}\ytableaushort{34,12}\prec\ytableaushort{24,13}\prec% \ytableaushort{23,14}\prec\ytableaushort{14,23}\prec\ytableaushort{13,24}\prec% \ytableaushort{12,34}.

Proposition 4.19.11.

The relation $\prec$ defines a total order on $\mathbf{YTD}^{\lambda}$

Proof.

This is Problem 4.19.3 (not examinable). ∎

Lemma 4.19.12.

For any $t\in\mathbf{SYT}^{\lambda}$ we have $[\sigma\cdot t]\prec[t]$ for all $\sigma\in C(t)\setminus\{e\}$ .

Proof.

Given $\sigma\in C(t)\setminus\{e\}$ , let $i$ be the smallest number in $\{1,\ldots,n\}$ such that $i$ is in a different position in $\sigma\cdot t$ than in $t$ . Since $i$ is moved to a place in the same column, it must be moved down to a lower row, since otherwise it would displace a number above it in the same column, which is necessarily smaller than $i$ , as $t$ is standard. This would contradict the minimality in the choice of $i$ . Thus, for every $j<i$ , $[\sigma\cdot t]$ and $[t]$ have $j$ in the same row, and $[\sigma\cdot t]$ has $i$ in a lower row, hence $[\sigma\cdot t]\prec[t]$ . ∎

Finishing the proof of Theorem 4.19.8.

Suppose that $\{{\bf e}_{t}\,|\,t\in\mathbf{SYT}^{\lambda}\}$ is linearly dependent. Then there exist $z_{t}$ (not all zero) such that

\sum_{t\in\mathbf{SYT}^{\lambda}}z_{t}{\bf e}_{t}=0.

(4.19.13)

Suppose $t_{0}\in\mathbf{SYT}^{\lambda}$ such that $[t_{0}]$ is maximal among all $[t]$ where $z_{t}\neq 0$ . Since the tabloids form a basis of ${\mathcal{M}}^{\lambda}$ , once all the ${\bf e}_{t}$ with non-zero $z_{t}$ have been expanded into tabloids, the coefficient in front of $[t_{0}]$ must be zero. But $[t_{0}]$ cannot appear as a component in any of the other ${\bf e}_{t}$ , since by assumption $[t]\prec[t_{0}]$ , hence by Lemma 4.19.12, we have $[s]\prec[t]\prec[t_{0}]$ for any $[s]$ a component of $[{\bf e}_{t}]$ . Thus $z_{t_{0}}=0$ , a contradiction. ∎

4.19.3. Exercises

Problem 95. Verify that $\unlhd$ is a partial order on the set of partitions of $n$ (not examinable).

Problem 96. Verify that $\prec$ is a strict total order on $\mathbf{YTD}^{\lambda}$ (not examinable).

Problem 97. Show that if $s,t\in\mathbf{SYT}^{\lambda}$ , then $[s]\neq[t]$ if and only if $s\neq t$ .

Problem 98. Use Proposition 4.19.5 to compute the characters of $(\pi,{\mathcal{S}}^{(4,2)})$ and then $(\pi,{\mathcal{S}}^{(3,3)})$ Challenging! Hint: Proposition 4.19.5 puts a restriction on the shapes of the ${\mathcal{S}}^{\lambda}$ that can appear as subrepresentations of ${\mathcal{M}}^{(4,2)}$ and ${\mathcal{M}}^{(3,3)}$ .