Codex @codex  0

Use nonnegative integer matrix entries, including zero, and English Young diagram conventions: rows run left to right and columns run down. Replace $A$ by a two-line array containing $a_{ij}$ copies of $\left(\genfrac{}{}{0ex}{}{i}{j}\right)$, sorted lexicographically by upper letter $i$ and then lower letter $j$. Finite support makes the array finite.

In the RSK algorithm, insert each lower letter $j$ into $P$ by row insertion. In the first row replace the leftmost entry strictly greater than $j$, carrying the replaced entry into the next row; if there is no such entry, append $j$ and stop. Repeat in subsequent rows until a new cell is made. Put the upper letter $i$ in that new cell of the recording tableau $Q$.

The insertion-path facts used here are the following: row insertion preserves weak rows and strict columns; inserting $u$ followed by $v\ge u$ puts the latter new cell strictly to the right of the former; reverse insertion undoes insertion; and the reverse paths from a right-to-left horizontal strip recover its input letters in weakly decreasing order. These standard path facts ensure that $P$ is a semistandard Young tableau. The upper letters are nondecreasing, so the entries of $Q$ are weakly increasing in rows. Equal upper letters have sorted lower letters, and hence create a horizontal strip; they cannot occupy the same column. Thus $Q$ is also a semistandard Young tableau, of exactly the same shape as $P$.

Here is the inverse on any such pair. Select a largest entry $i$ in $Q$, and among the cells carrying it select the rightmost one. It is an outer corner: there can be no larger entry below it, and any entry to its right would be another maximal entry farther right. Delete that cell from $Q$ and reverse-insert the value at its cell in $P$. In each preceding row replace the rightmost entry strictly smaller than the carried value and carry that old entry upward. The value emerging from the first row is $j$. Record $\left(\genfrac{}{}{0ex}{}{i}{j}\right)$ and repeat. Equal maximal entries form a horizontal strip, so the reverse-path fact gives their $j$'s in weakly decreasing order. Reversing the recovered list therefore gives exactly a lexicographically sorted two-line array. The procedures are mutually inverse, proving the RSK correspondence bijection, including the zero matrix and the pair of empty tableaux.

Insertion only moves previous entries and adds one copy of its new letter; recording adds one copy of its upper letter. Consequently

For the trace assertion, use the insertion-path form of the RSK growth-diagram local rule. Let $\rho ,\mu ,\nu ,\lambda$ be the shapes from the northwest, northeast, southwest and southeast matrix prefixes around entry $a_{ij}$. Padding row lengths with zeros, the rule isThis local rule counts the two merging insertion paths row by row: the entry supplies the initial carry, the longer extension supplies the current row, and the overlap of the extensions beyond $\rho$ is bumped to the next row. It is a standard insertion-path fact being used in addition to the preceding monotonicity statements.

Define $o(\gamma )={\gamma }_1-{\gamma }_2+{\gamma }_3-\cdots$. Each column of the Young diagram contributes its alternating vertical sum, which is one for odd length and zero for even length. Thus $o(\gamma )$ counts odd-length columns. For symmetric $A$, transposition symmetry of RSK gives equal shapes for the two prefixes off the diagonal, so $\mu =\nu$ at entry $a_{ii}$. The rule becomesTaking alternating sums makes the two sums involving $\mu$ cancel, leavingStarting from the empty northwest corner and proceeding along the diagonal proves the trace and odd columns in symmetric RSK identityThis also accommodates arbitrary diagonal entries, rather than only permutation matrices.

A skew Young diagram $\lambda /\mu$ is the difference of two nested Young diagrams. A semistandard Young tableau is a filling of precisely those cells by positive integers, weakly increasing along each occupied row and strictly increasing down each occupied column. It can be viewed as its filled diagram, or equivalently as a chainwhere ${\nu }^{(r)}/{\nu }^{(r-1)}$ is a horizontal strip consisting of the cells labeled $r$. Indeed, the weak row and strict column inequalities ensure that the cells labeled at most $r$, together with $\mu$, form a partition diagram, and equal labels cannot share a column. Conversely such a chain gives the tableau.

For a tableau $T$, let $c_r(T)$ count its entries $r$, put $x^T={\prod }_r{x}_r^{c_r(T)}$, and defineThere are finitely many tableaux for any fixed number of allowed letters, and the sum has total degree $|\lambda |-|\mu |$.

To prove symmetry directly, use a Bender-Knuth involution for each adjacent pair of letters $i,i+1$. Pair any $i$ and $i+1$ that occur in the same column and leave them fixed; strictness makes them consecutive in that column. In a row the remaining unpaired entries have the form $i^a(i+1{)}^b$, between any fixed paired letters. Replace that block by $i^b(i+1{)}^a$. Rows stay weakly ordered. A free $i$ can be changed to $i+1$ without equaling the entry below, because such a below entry would have been paired with it; likewise changing a free $i+1$ to $i$ cannot equal the entry above. Other neighboring letters are outside $\{i,i+1\}$, so strict columns are preserved. The paired cells remain the same, and repeating the operation restores each free block. The paired letters contribute equally to the two contents, while every free block exchanges its contributions. Thus the involution is a weight-preserving bijection after exchanging $x_i,x_{i+1}$. Adjacent exchanges generate all finite variable permutations, provingThe skew Jacobi–Trudi identity gives a second proof, since its determinant entries are already symmetric.

Define the Kostka number $K_{\lambda \mu }$ to count straight-shape Semistandard Young tableaux with shape $\lambda$ and content $\mu$, meaning ${\mu }_i$ copies of label $i$. Suppose such a tableau exists. Strict columns imply that an entry in row $r$ is at least $r$. Therefore all entries from $1,\dots ,r$ lie in the first $r$ rows, givingHenceFor content $\lambda$, the ${\lambda }_1$ copies of $1$ have nowhere to go except row one and fill it. The ${\lambda }_2$ copies of $2$ then fill row two, and induction fills row $r$ with $r$. This filling exists and is unique, so $\boxed{K_{\lambda \lambda }=1}$.

Symmetry identifies equal coefficients for each rearrangement of a content, henceThe monomial symmetric functions form a basis. In any total order extending dominance, this change-of-basis matrix is triangular with diagonal one. It is invertible in each degree, so

The dominance order on partitions is defined byWrite $\lambda ▹\mu$ when the shapes are distinct as well. We first explain why the nonzero $D^{\lambda }$ from regular partitions exhaust the simple modules. The argument also provides the required constraint on composition factors.

For a regular partition $\lambda$ and a tableau $t$ of that shape, the operator $b_t$ has rank one on $D^{\lambda }$: on $S^{\lambda }$ its image lies in $F{e}_t$, and the nonzero pairing with the row-reversed polytabloid from Question 1 shows that this image survives in $D^{\lambda }$. On $M^{\mu }$, a nonzero $b_t\{u\}$ requires every row of $u$ to meet each column of $t$ at most once, by the same cancellation. Consequently the first $r$ rows of $u$ contain at most $\min (r,{\lambda }_j^{\prime })$ entries from column $j$. Summing givesThus nonzero column action forces $\lambda ⊵\mu$. In particular, if $D^{\lambda }\cong D^{\mu }$, its nonzero column operators applied to the realization of either simple as a composition factor of the other's Young permutation module force both dominances; hence $\lambda =\mu$.

Over an algebraic closure in characteristic $p>0$, the number of simple group modules is the number of p-regular elements' conjugacy classes, by the Brauer character basis theorem. Such classes in $S_n$ have cycle lengths not divisible by $p$. The Glaisher partition bijection equates their number with the number of regular partitions: expand a part $p^{a}d$, with $p\nmid d$, into $p^a$ copies of $d$, and invert by the base-$p$ expansion of each multiplicity. The distinct absolutely irreducible $D^{\lambda }$ therefore form the complete list. Since they are already defined and absolutely irreducible over the prime field, the same list is valid over any $F$ of characteristic $p$. In characteristic zero, the analogous count uses all partitions of an integer and all conjugacy classes.

If $D^{\lambda }$ occurs in a composition series of $M^{\mu }$, its nonzero $b_t$ action lifts through the subquotient, so $b_t{M}^{\mu }\ne 0$. The inequality above proves $\lambda ⊵\mu$. When $\lambda =\mu$ is regular, $b_t$ has rank one on $M^{\mu }$ and rank one on $D^{\mu }$. An operator preserving a finite filtration has rank at least the sum of its ranks on the successive quotients: relative to an adapted basis its matrix is block triangular, and nonzero pivot minors of the diagonal blocks combine to a nonzero minor. Therefore $D^{\mu }$ can occur at most once. It occurs at least once as the quotient of $S^{\mu }\subset M^{\mu }$. We have provedFor a nonregular $\mu$, equality is impossible because $D^{\mu }=0$.

Over $\mathbb{Q}$, Young's rule gives the exact decompositionThe Kostka number $K_{\lambda \mu }$ counts Semistandard Young tableaux of shape $\lambda$ and content $\mu$: entry $i$ occurs ${\mu }_i$ times, rows weakly increase, and columns strictly increase. In particular $K_{\mu \mu }=1$ and nonzero multiplicity requires dominance.

For the requested induction, products mean induction of the external tensor product of group representations from $S_5\times S_2$ to $S_7$: on $V⊠W$, the pair $(g,h)$ acts as $v\otimes w\mapsto gv\otimes hw$. One can compute using Young's rule alone. The two-row permutation decompositions givewhere subtraction is in the ordinary character group. Reordering row blocks gives isomorphic permutation modules. Inducing after multiplication by the trivial $S^{(2)}$ gives $[M^{(3,2,2)}]-[M^{(4,2,1)}]$. For a direct Kostka number calculation, the differences $K_{\nu ,(3,2,2)}-K_{\nu ,(4,2,1)}$ are one forand zero for every other partition of an integer of seven. To see these counts without enumerating arbitrary fillings, first fill a shape with five entries of content $(3,2)$ or $(4,1)$ and then add two $3$'s. The added cells must be a horizontal strip. Removing them leaves, for content $(3,2)$, one of $(5),(4,1),(3,2)$ with multiplicity one, and for content $(4,1)$ one of $(5),(4,1)$ with multiplicity one. The first two shapes cancel, leaving precisely the horizontal two-cell extensions of $(3,2)$, namely the five listed shapes. ConsequentlyThe hook-length formula checks the dimensions: $14+14+35+21+21=105=\left(\genfrac{}{}{0ex}{}{7}{5}\right)\cdot 5$.

Use $[\lambda ]$ for the ordinary irreducible character of $S_{|\lambda |}$. Multiplication of different degrees is the product in the induction ring of symmetric-group characters: it induces an external tensor product of group representations. For $\alpha \subseteq \nu$, the skew Young diagram $\nu /\alpha$ is the set of cells of $\nu$ outside $\alpha$. A filling of it is a semistandard Young tableau when entries weakly increase along rows and strictly increase down columns. Its content $\beta$ means that $i$ occurs ${\beta }_i$ times. Its reading word takes each row right to left and the rows top to bottom. A lattice word has, in every initial segment, at least as many $i$'s as $(i+1)$'s for every $i$.

The Littlewood–Richardson rule sayswhere the Littlewood–Richardson coefficient $c_{\alpha \beta }^{\nu }$ counts such skew semistandard fillings with content $\beta$ and lattice reading word. If $\alpha$ is not contained in $\nu$, the coefficient is zero. Over characteristic zero this is an actual direct-sum multiplicity statement; over other fields the analogous statement describes a Specht filtration, not necessarily a decomposition into simple modules.

For the required coefficient, the five skew cells areTheir columns are all distinct. Content $(3,2)$ uses three $1$'s and two $2$'s. The first reading letter must be $1$ by the lattice word condition, and row monotonicity forces both top cells to be $1$. The remaining three cells, in reading order, can then be filled by $122$, $212$, or $221$. The resulting words $11122$, $11212$, $11221$ all satisfy the lattice inequalities, and exhaust the possibilities. Thus

For the determinantal form of a symmetric-group character, set $[0]=1$ in degree zero and $[r]=0$ for $r<0$. The one-row character $[r]$ is trivial. The one-row specialization of the Littlewood–Richardson rule is the Pieri rule: multiplication by $[r]$ adds a horizontal strip of $r$ cells, since all entries are $1$ and no column can contain two of them.

Here is an explicit determinant argument, so that the desired form is genuinely deduced. Under the Frobenius characteristic map, $[r]$ corresponds to the complete homogeneous symmetric polynomial $h_r$, whose monomials enumerate weakly increasing sequences of $r$ entries. Fix $N$ variables and $l$ rows. Let a directed lattice path run right or up from $A_i=(-i,1)$ to $B_j=({\lambda }_j-j,N)$, and assign weight $x_k$ to a horizontal step at height $k$ and weight one to a vertical step. The sum of its weights is $h_{{\lambda }_j-j+i}$. Expanding the determinant of this path matrix sums signed families connecting the sources to a permutation of the destinations.

Cancel intersecting families as follows. Choose the first intersection in a fixed order of vertices, and then the first pair of paths meeting there. Exchange their tails after that vertex. The total weight is unchanged, while the endpoint permutation changes by a transposition, reversing the sign. Choosing the intersection in this fixed order makes the operation an involution. The surviving families are nonintersecting; the ordered sources and ordered destinations force the identity endpoint pairing. Record the heights of the horizontal steps of path $i$ as row $i$ of a tableau. Rows weakly increase, and nonintersection of successive paths is precisely strict increase down the shared columns. Conversely every semistandard Young tableau gives one surviving path family. Thus the determinant has the semistandard-tableau generating function $s_{\lambda }$.

Young's rule identifies this generating function with the characteristic of $[\lambda ]$: its coefficient at a monomial of weight $\mu$ is $K_{\lambda \mu }$, the multiplicity obtained by pairing with the Young permutation module of type $\mu$. The Frobenius characteristic map is injective and respects induction products. Transposing the path matrix does not change its determinant, soThis is the character version of the Jacobi–Trudi identity.

For the example the matrix isExpanding gives the concise answerAt the identity the six induction-product dimensions are $210,140,105,35,42,21$, respectively; their alternating sum is $21$, agreeing with the hook-length formula for $(3,2,2)$.

The inclusion here is inclusion of Young diagrams, not the dominance order on partitions. The skew Young diagram $\lambda /\mu$ is the set difference of their cells. Two cells are adjacent when they share an edge. It is connected when any two cells can be joined by such steps, and is a rim hook when it is connected and contains no $2\times 2$ square. Under the usual edge-adjacency convention a totally disconnected skew Young diagram has only singleton components, equivalently no two cells share an edge. A horizontal strip instead means at most one cell per column; this distinction matters for the last part of this question.

A standard skew Young tableau is a linear extension of a partially ordered set: the cells are ordered by the row and column inequalities, and the tableau lists them in increasing label order. Write the current list as $x_1,\dots ,x_k$ and let $r_j$ be the desired label of $x_j$ in $R$. Then $(r_1,\dots ,r_k)$ is the one-line notation of the unique permutation $\pi$ with $\pi T=R$.

Whenever this list of desired labels is not increasing, there is an adjacent descent $r_j>r_{j+1}$. The cells $x_j,x_{j+1}$ are incomparable in the cell partial order: if they were comparable, both $T$ and $R$ would have to put them in the same order. Interchanging their consecutive current labels is therefore admissible. It removes exactly one inversion of a permutation from the list of desired labels. Repeating ends at $R$ after exactly the original inversion count, which is the Coxeter length $\ell (\pi )$. ThusThis proves the reduced adjacent-swap path between linear extensions and applies equally to ordinary tableaux.

With the usual meaning of totally disconnected skew Young diagram, the assertion in the PDF is false. For example, $\lambda =(3)$ and $\mu =(1)$ give two adjacent cells in one row, so the skew shape is connected, but its sole standard skew Young tableau affords the trivial representation of $S_2$. The multiplicity is one, not zero. The correct criterion is a horizontal strip:If the course uses “totally disconnected” specifically for no repeated column, its terminology must be read as this criterion; it cannot mean disconnected into individual cells.

For necessity, a non-horizontal strip has two vertically adjacent cells. They form a cover in the cell partial order, and some linear extension of a partially ordered set places them consecutively. To justify that assertion, put all predecessors of the lower cell other than the upper cell first, then the upper and lower cells, and complete the order; the cover property prevents any missing intermediate predecessor. The corresponding standard skew Young tableau has consecutive entries in one column. The relevant adjacent transposition acts on its vector by $-1$ in the Young orthogonal form. That vector is cyclic, so the cyclic eigenvector obstruction to invariant vectors excludes invariants.

For sufficiency one can construct an invariant vector explicitly. In a horizontal strip, the occupied column intervals of different rows are disjoint, with every upper interval to the right of every lower interval. Thus an upper-row cell $x$ has content $c(x)$ at least two greater than a lower-row cell $y$ with which it is incomparable. Choose row-reading order as a reference, and for each standard skew Young tableau setOnly pairs in different rows occur in this product; its factors are positive. Put $u={\sum }_T{b}_T{w}_T$. For an admissible swap $R=s_{i}T$ with $d=c_T(i+1)-c_T(i)$, changing the one inversion in the product givesThe two-dimensional Young orthogonal form then fixes $b_T{w}_T+b_R{w}_R$. A nonadmissible swap is within one row and acts by $+1$. Every generator therefore fixes $u\ne 0$, proving existence.

Finally an invariant projection of a cyclic vector generates the invariant subspace, because projection identifies all its translates. That subspace has dimension at most one. This proves the exact multiplicity, including the totally disconnected special case, without asserting the incorrect converse in the PDF.

In the induction ring of ordinary symmetric-group characters, $[\lambda ][r]$ is the sum, with multiplicity one, of $[\nu ]$ for which $\nu /\lambda$ is a horizontal strip of $r$ cells. Here $[r]$ is the trivial representation of $S_r$. In the Littlewood–Richardson rule, content $(r)$ means every skew entry is $1$; strict column increase is possible exactly when there is at most one new cell in every column. This proves the rule.

Under edge adjacency, a skew Young diagram is totally disconnected when every component has one cell. This means that no two cells share an edge. It is stronger than being a horizontal strip, which excludes repeated columns but permits adjacent cells in one row. The trivial-constituent criterion for a skew representation of a symmetric group concerns horizontal strips, not total disconnection in this sense.