Namespaces
Variants
Actions

Difference between revisions of "Schur functions in algebraic combinatorics"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (AUTOMATIC EDIT (latexlist): Replaced 135 formulas out of 141 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
Line 1: Line 1:
The Schur functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s1200401.png" /> are a special basis for the algebra of symmetric functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s1200402.png" />. They are also intimately connected with representations of the symmetric and general linear groups (cf. also [[Representation of the symmetric groups|Representation of the symmetric groups]]). Standard references are [[#References|[a3]]], [[#References|[a6]]], [[#References|[a8]]], [[#References|[a9]]].
+
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 
 +
Out of 141 formulas, 135 were replaced by TEX code.-->
 +
 
 +
{{TEX|semi-auto}}{{TEX|partial}}
 +
The Schur functions $s_{ \lambda }$ are a special basis for the algebra of symmetric functions $\Lambda$. They are also intimately connected with representations of the symmetric and general linear groups (cf. also [[Representation of the symmetric groups|Representation of the symmetric groups]]). Standard references are [[#References|[a3]]], [[#References|[a6]]], [[#References|[a8]]], [[#References|[a9]]].
  
 
==Definitions.==
 
==Definitions.==
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s1200403.png" /> be a set of variables and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s1200404.png" /> be the algebra of symmetric functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s1200405.png" />. Bases for this algebra are indexed by partitions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s1200406.png" />, i.e., <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s1200407.png" /> is a weakly decreasing sequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s1200408.png" /> non-negative integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s1200409.png" /> called parts. Associated with any partition is an [[alternant matrix|alternant]], which is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004010.png" /> determinant
+
Let $\mathbf{x} = \{ x _ { 1 } , \dots , x _ { l } \}$ be a set of variables and let $\Lambda$ be the algebra of symmetric functions in $\mathbf{x}$. Bases for this algebra are indexed by partitions $\lambda = ( \lambda _ { 1 } , \dots , \lambda _ { l } )$, i.e., $\lambda$ is a weakly decreasing sequence of $l$ non-negative integers $\lambda _ { i }$ called parts. Associated with any partition is an [[alternant matrix|alternant]], which is the $l \times l$ determinant
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004011.png" /></td> </tr></table>
+
\begin{equation*} a_\lambda = \operatorname { det } ( x _ { i } ^ { \lambda_j } ). \end{equation*}
  
In particular, for the partition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004012.png" /> one has the [[Vandermonde determinant|Vandermonde determinant]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004013.png" />. In his thesis [[#References|[a11]]], I. Schur defined the functions which bear his name as
+
In particular, for the partition $\delta = ( l - 1 , l - 2 , \ldots , 0 )$ one has the [[Vandermonde determinant|Vandermonde determinant]] $a _ { \delta } = \prod _ { i &lt; j } ( x _ { i } - x _ { j } )$. In his thesis [[#References|[a11]]], I. Schur defined the functions which bear his name as
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004014.png" /></td> </tr></table>
+
\begin{equation*} s _ { \lambda } = \frac { a _ { \lambda  + \delta} } { a _ { \delta } }, \end{equation*}
  
where addition of partitions is component-wise. It is clear from this equation that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004015.png" /> is a symmetric homogeneous polynomial of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004016.png" />.
+
where addition of partitions is component-wise. It is clear from this equation that $s_{ \lambda }$ is a symmetric homogeneous polynomial of degree $| \lambda | = \Sigma _ { i } \lambda_i$.
  
There is a more combinatorial definition of a Schur function. A partition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004017.png" /> can be viewed as a Ferrers shape, obtained by placing dots or cells in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004018.png" /> left-justified rows with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004019.png" /> boxes in row <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004020.png" />. One obtains a semi-standard Young tableaux, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004021.png" />, of shape <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004022.png" /> by replacing each dot by a positive integer so that rows weakly increase and columns strictly increase (cf. also [[Young tableau|Young tableau]]). For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004023.png" />, then its shape and a possible tableau are
+
There is a more combinatorial definition of a Schur function. A partition $\lambda$ can be viewed as a Ferrers shape, obtained by placing dots or cells in $l$ left-justified rows with $\lambda _ { i }$ boxes in row $i$. One obtains a semi-standard Young tableaux, $T$, of shape $\lambda$ by replacing each dot by a positive integer so that rows weakly increase and columns strictly increase (cf. also [[Young tableau|Young tableau]]). For example, if $\lambda = ( 4,2,1 )$, then its shape and a possible tableau are
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004024.png" /></td> </tr></table>
+
<table class="eq" style="width:100%;"> <tr><td style="width:94%;text-align:center;" valign="top"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004024.png"/></td> </tr></table>
  
Each tableau determines a monomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004025.png" />, e.g., in the example above, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004026.png" />. The second definition of the Schur function is then
+
Each tableau determines a monomial $x ^ { T } = \prod _ { i \in T } x _ { i }$, e.g., in the example above, $x ^ { T } = x _ { 1 } ^ { 3 } x _ { 2 } x _ { 3 } ^ { 2 } x _ { 4 }$. The second definition of the Schur function is then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004027.png" /></td> </tr></table>
+
\begin{equation*} s _ { \lambda } = \sum _ { T } \mathbf{x} ^ { T }, \end{equation*}
  
where the sum is over all semi-standard Young tableaux of shape <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004028.png" /> with entries between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004030.png" />.
+
where the sum is over all semi-standard Young tableaux of shape $\lambda$ with entries between $1$ and $l$.
  
 
==Change of basis.==
 
==Change of basis.==
The Schur functions can also be written in terms of the other standard bases for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004031.png" />. A monomial symmetric function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004032.png" /> is the sum of all monomials whose exponent sequence is some permutation of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004033.png" />. Also, define the Kostka number [[#References|[a5]]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004034.png" /> as the number of semi-standard Young tableaux <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004035.png" /> of shape <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004036.png" /> and content <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004037.png" />, i.e., <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004038.png" /> contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004039.png" /> entries equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004040.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004041.png" />. The combinatorial definition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004042.png" /> immediately gives the following rule, known as Young's rule:
+
The Schur functions can also be written in terms of the other standard bases for $\Lambda$. A monomial symmetric function $m _ { \lambda }$ is the sum of all monomials whose exponent sequence is some permutation of $\lambda$. Also, define the Kostka number [[#References|[a5]]] $K _ { \lambda \mu }$ as the number of semi-standard Young tableaux $T$ of shape $\lambda$ and content $\mu = ( \mu _ { 1 } , \dots , \mu _ { l } )$, i.e., $T$ contains $\mu _ { i }$ entries equal to $i$ for $1 \leq i \leq l$. The combinatorial definition of $s_{ \lambda }$ immediately gives the following rule, known as Young's rule:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004043.png" /></td> </tr></table>
+
\begin{equation*} s _ { \lambda } = \sum _ { \mu } K _ { \lambda \mu } m _ { \mu }. \end{equation*}
  
Now consider the complete homogeneous symmetric functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004044.png" /> and the elementary symmetric functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004045.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004046.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004047.png" />) is the sum of all (respectively, all square-free) monomials of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004048.png" />. Also, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004049.png" /> denote the partition conjugate to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004050.png" />, whose parts are the column lengths of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004051.png" />'s shape. In the preceding example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004052.png" />. For the two bases under consideration, the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004053.png" /> can be described as a determinant (the Jacobi–Trudi identity [[#References|[a2]]], [[#References|[a12]]] and its dual):
+
Now consider the complete homogeneous symmetric functions $h_\lambda = h _ { \lambda _ { 1 } } \ldots h _ { \lambda _ { l } }$ and the elementary symmetric functions $\lambda = e _ { \lambda _ { 1 } } \cdots e _ { \lambda _ { l } }$, where $h _ { \lambda _ { i } }$ (respectively, $e _ { \lambda _ { i } }$) is the sum of all (respectively, all square-free) monomials of degree $\lambda _ { i }$. Also, let $\lambda ^ { \prime }$ denote the partition conjugate to $\lambda$, whose parts are the column lengths of $\lambda$'s shape. In the preceding example, $\lambda ^ { \prime } = ( 3,2,1,1 )$. For the two bases under consideration, the function $s_{ \lambda }$ can be described as a determinant (the Jacobi–Trudi identity [[#References|[a2]]], [[#References|[a12]]] and its dual):
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004054.png" /></td> </tr></table>
+
\begin{equation*} s _ { \lambda } = \operatorname { det } ( h _ { \lambda _ { i } - i + j } ), \end{equation*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004055.png" /></td> </tr></table>
+
\begin{equation*} s _ { \lambda ^ { \prime } } = \operatorname { det } ( e _ { \lambda _ { i } - i + j } ). \end{equation*}
  
 
Note that this identity immediately implies
 
Note that this identity immediately implies
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004056.png" /></td> </tr></table>
+
\begin{equation*} s _{( l )} = h _ { l } \text { and } s _ { ( 1 ^ { l }) }  = e_{ l}, \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004057.png" /> is the partition with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004058.png" /> parts all equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004059.png" />. These specializations also follow directly from the combinatorial definition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004060.png" />.
+
where $( 1 ^ { l } )$ is the partition with $l$ parts all equal to $1$. These specializations also follow directly from the combinatorial definition of $s_{ \lambda }$.
  
 
==Representations.==
 
==Representations.==
The description of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004061.png" /> in terms of the power sum symmetric functions brings in the representation theory of the symmetric group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004062.png" />. The irreducible representations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004063.png" /> are indexed by partitions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004064.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004065.png" />. Given a [[conjugacy class]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004066.png" /> corresponding to a partition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004067.png" />, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004068.png" /> denote its size and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004069.png" /> be the value of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004070.png" />th irreducible character on the class. Now consider the power sum symmetric function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004071.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004072.png" />.
+
The description of $s_{ \lambda }$ in terms of the power sum symmetric functions brings in the representation theory of the symmetric group $\mathcal{S} _ { n }$. The irreducible representations of $\mathcal{S} _ { n }$ are indexed by partitions $\lambda$ such that $| \lambda | = n$. Given a [[conjugacy class]] of $\mathcal{S} _ { n }$ corresponding to a partition $\mu$, let $k _ { \mu }$ denote its size and let $\chi _ { \mu } ^ { \lambda }$ be the value of the $\lambda$th irreducible character on the class. Now consider the power sum symmetric function $p _ { \lambda } = p _ { \lambda _ { 1 } } \cdots p _ { \lambda _ { l } }$, where $p _ { \lambda _ { i } } = x _ { 1 } ^ { \lambda _ { i } } + \ldots + x _ { l } ^ { \lambda _ { i } }$.
  
The following now holds: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004073.png" />, then
+
The following now holds: If $| \lambda | = n$, then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004074.png" /></td> </tr></table>
+
\begin{equation*} s _ { \lambda } = \frac { 1 } { n ! } \sum _ { | \mu | = n } k _ { \mu } \chi _ { \mu } ^ { \lambda } p _ { \mu }. \end{equation*}
  
In other words, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004075.png" /> is the cycle-indicator generating function (in the sense of Polyá–Redfield enumeration) for the irreducible character of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004076.png" /> corresponding to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004077.png" />.
+
In other words, $s_{ \lambda }$ is the cycle-indicator generating function (in the sense of Polyá–Redfield enumeration) for the irreducible character of $\mathcal{S} _ { n }$ corresponding to $\lambda$.
  
Now, consider the complex [[General linear group|general linear group]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004078.png" />. A representation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004079.png" /> is polynomial if, for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004080.png" />, the entries of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004081.png" /> are polynomials in the entries of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004082.png" />. The polynomial representations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004083.png" /> are indexed by the partitions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004084.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004085.png" /> non-negative parts. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004086.png" /> be the character of a polynomial representation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004087.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004088.png" /> have eigenvalues <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004089.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004090.png" /> is a polynomial function of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004091.png" /> (because this is true for diagonalizable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004092.png" /> and these are dense in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004093.png" />) and is symmetric (because <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004094.png" /> is a class function). In fact, more is true: The irreducible polynomial characters of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004095.png" /> are precisely the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004096.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004097.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004098.png" /> non-negative parts.
+
Now, consider the complex [[General linear group|general linear group]] $\operatorname{GL}_l$. A representation $\rho : \operatorname{GL} _ { l } \rightarrow \operatorname{GL} _ { m }$ is polynomial if, for every $X \in \operatorname {GL}_{l}$, the entries of $\rho ( X )$ are polynomials in the entries of $X$. The polynomial representations of $\operatorname{GL}_l$ are indexed by the partitions $\lambda$ with $l$ non-negative parts. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004086.png"/> be the character of a polynomial representation $\rho$ and let $X$ have eigenvalues $x _ { 1 } , \dots , x _ { l }$. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004090.png"/> is a polynomial function of the $x_{i}$ (because this is true for diagonalizable $X$ and these are dense in $\operatorname{GL}_l$) and is symmetric (because <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004094.png"/> is a class function). In fact, more is true: The irreducible polynomial characters of $\operatorname{GL}_l$ are precisely the $s_{ \lambda }$ for $\lambda$ with $l$ non-negative parts.
  
 
==Properties.==
 
==Properties.==
The connection with representations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s12004099.png" /> can be used to construct an isomorphism of algebras. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040100.png" /> denote the vector space of all class functions on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040101.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040102.png" />. The irreducible characters form a basis for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040103.png" />, and it can be endowed with a multiplication by induction of the tensor product. The characteristic or Frobenius mapping [[#References|[a1]]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040104.png" /> is defined on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040105.png" /> by
+
The connection with representations of $\mathcal{S} _ { n }$ can be used to construct an isomorphism of algebras. Let $R ^ { n }$ denote the vector space of all class functions on $\mathcal{S} _ { n }$ and let $R = \sum _ { n &gt; 0 } R ^ { n }$. The irreducible characters form a basis for $R$, and it can be endowed with a multiplication by induction of the tensor product. The characteristic or Frobenius mapping [[#References|[a1]]] $\operatorname{ch} : R \rightarrow \Lambda$ is defined on $\chi \in R ^ { x }$ by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040106.png" /></td> </tr></table>
+
\begin{equation*} \operatorname { ch } ( \chi ) = \frac { 1 } { n ! } \sum _ { | \mu | = n } k _ { \mu } \chi _ { \mu } p _ { \mu }, \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040107.png" /> is the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040108.png" /> on the class corresponding to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040109.png" />. The mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040110.png" /> is an isomorphism of algebras. In fact, there are natural inner products on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040111.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040112.png" /> that make <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040113.png" /> an isometry.
+
where $\chi _ { \mu }$ is the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040108.png"/> on the class corresponding to $\mu$. The mapping $\operatorname{ch} : R \rightarrow \Lambda$ is an isomorphism of algebras. In fact, there are natural inner products on $R$ and $\Lambda$ that make $\operatorname{ch}$ an isometry.
  
A number of identities involving Schur functions have interesting bijective proofs using the combinatorial definition. Among the most famous are the following, in which it is assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040114.png" /> is another set of variables.
+
A number of identities involving Schur functions have interesting bijective proofs using the combinatorial definition. Among the most famous are the following, in which it is assumed that $\mathbf{y} = \{ y _ { 1 } , \dots , y _ { l } \}$ is another set of variables.
  
 
The Cauchy identity and its dual are
 
The Cauchy identity and its dual are
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040115.png" /></td> </tr></table>
+
\begin{equation*} \sum _ { \lambda } s _ { \lambda } (  \mathbf{x} ) s _ { \lambda } (  \mathbf{y} ) = \prod _ { i , j = 1 } ^ { l } \frac { 1 } { 1 - x _ { i } y _ { j } } \end{equation*}
  
 
and
 
and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040116.png" /></td> </tr></table>
+
\begin{equation*} \sum _ { \lambda } s _ { \lambda } ( \mathbf x ) s _ { \lambda ^ { \prime } } ( \mathbf y ) = \prod _ { i , j = 1 } ^ { l } ( 1 + x _ { i } y _ { j } ). \end{equation*}
  
D. Knuth [[#References|[a4]]] has given algorithmic bijections between matrices and semi-standard Young tableaux that prove these identities. It is a generalization of a mapping of C. Schensted [[#References|[a10]]] for standard Young tableaux, i.e., semi- standard Young tableaux where the entries are precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040117.png" />.
+
D. Knuth [[#References|[a4]]] has given algorithmic bijections between matrices and semi-standard Young tableaux that prove these identities. It is a generalization of a mapping of C. Schensted [[#References|[a10]]] for standard Young tableaux, i.e., semi- standard Young tableaux where the entries are precisely $1 , \dots , | \lambda |$.
  
One can also describe the [[structure constant]]s for the algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040118.png" /> in the basis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040119.png" /> combinatorially. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040120.png" /> as Ferrers shapes, then one has a skew shape <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040121.png" /> consisting of all dots or cells that are in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040122.png" /> but not in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040123.png" />. Skew semi-standard Young tableaux are defined in the obvious way. The reverse row word for a semi-standard Young tableaux <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040124.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040125.png" />, is obtained by reading the entries in each row from right to left, starting with the top row and working down. For the example tableau, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040126.png" />. Also, a sequence of positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040127.png" /> is a lattice permutation or ballot sequence if, in every prefix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040128.png" />, the number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040129.png" />'s is at least as big as the number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040130.png" />'s for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040131.png" />. The Littlewood–Richardson rule [[#References|[a7]]] states that if
+
One can also describe the [[structure constant]]s for the algebra $\Lambda$ in the basis $s_{ \lambda }$ combinatorially. If $\mu \subseteq \lambda$ as Ferrers shapes, then one has a skew shape $\lambda / \mu$ consisting of all dots or cells that are in $\lambda$ but not in $\mu$. Skew semi-standard Young tableaux are defined in the obvious way. The reverse row word for a semi-standard Young tableaux $T$, $\pi_T$, is obtained by reading the entries in each row from right to left, starting with the top row and working down. For the example tableau, $\pi_T = 3111324$. Also, a sequence of positive integers $\pi = w _ { 1 } \dots w _ { n }$ is a lattice permutation or ballot sequence if, in every prefix $w _ { 1 } \ldots w _ { k }$, the number of $i$'s is at least as big as the number of $( i + 1 )$'s for all $i \geq 1$. The Littlewood–Richardson rule [[#References|[a7]]] states that if
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040132.png" /></td> </tr></table>
+
\begin{equation*} \lambda ^ { s _ { \mu } } = \sum _ { \nu } c _ { \lambda \mu } ^ { \nu } s _ { \nu }, \end{equation*}
  
then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040133.png" /> is equal to the number of semi-standard Young tableaux <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040134.png" /> of shape <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040135.png" /> and content <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040136.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040137.png" /> is a ballot sequence. Via the characteristic mapping, the Littlewood–Richardson coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040138.png" /> can also be viewed as giving the multiplicities of the character product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040139.png" /> when decomposed into irreducibles. Equivalently, one can consider the decomposition of the inner tensor product of two irreducible polynomial representations of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s120/s120040/s120040140.png" />.
+
then $c _ { \lambda \mu } ^ { \nu }$ is equal to the number of semi-standard Young tableaux $T$ of shape $\nu / \lambda$ and content $\mu$ such that $\pi_T$ is a ballot sequence. Via the characteristic mapping, the Littlewood–Richardson coefficients $c _ { \lambda \mu } ^ { \nu }$ can also be viewed as giving the multiplicities of the character product $\chi ^ { \lambda } \chi ^ { \mu }$ when decomposed into irreducibles. Equivalently, one can consider the decomposition of the inner tensor product of two irreducible polynomial representations of $\operatorname{GL}_l$.
  
 
There are many generalizations of Schur functions, one of the most notable being the Hall–Littlewood functions. See [[#References|[a8]]] for more information.
 
There are many generalizations of Schur functions, one of the most notable being the Hall–Littlewood functions. See [[#References|[a8]]] for more information.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F.G. Frobenius,  "Über die Charactere der symmetrischen Gruppe"  ''Sitz. K. Preuss. Akad. Wiss''  (1900)  pp. 516–534  (Also: Gesammelte Abh. 3 Springer, 1968, 148-166)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  C. Jacobi,  "De functionibus alternantibus earumque divisione per productum e differentiis elementorum conflatum"  ''J. Reine Angew. Math.'' , '''22'''  (1841)  pp. 360–371  (Also: Math. Werke 3, Chelsea, 1969, 439-452)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G.D. James,  A. Kerber,  "The representation theory of the symmetric group" , ''Encycl. Math. Appl.'' , '''16''' , Addison-Wesley  (1981)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D.E. Knuth,  "Permutations, matrices and generalized Young tableaux"  ''Pacific J. Math.'' , '''34'''  (1970)  pp. 709–727</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  C. Kostka,  "Über den Zusammenhang zwischen einigen Formen von symmetrischen Funktionen"  ''Crelle's J.'' , '''93'''  (1882)  pp. 89–123</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  D.E. Littlewood,  "The theory of group characters" , Oxford Univ. Press  (1950)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  D.E. Littlewood,  A.R. Richardson,  "Group characters and algebra"  ''Philos. Trans. R. Soc. London Ser. A'' , '''233'''  (1934)  pp. 99–142</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  I.G. Macdonald,  "Symmetric functions and Hall polynomials" , Oxford Univ. Press  (1995)  (Edition: Second)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  B.E. Sagan,  "The symmetric group: representations, combinatorial algorithms, and symmetric functions" , Wadsworth&amp;Brooks/Cole  (1991)  (Second ed.: Springer, to appear)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  C. Schensted,  "Longest increasing and decreasing subsequences"  ''Canad. J. Math.'' , '''13'''  (1961)  pp. 179–191</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  I. Schur,  "Über eine Klasse von Matrizen die sich einer gegeben Matrix zuordnen lassen"  ''Inaugural Diss. Berlin''  (1901)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  N. Trudi,  "Intorno un determinante piu generale di quello che suol dirsi determinante delle radici di una equazione, ed alle funzioni simmetriche complete di queste radici"  ''Rend. Accad. Sci. Fis. Mat. Napoli'' , '''3'''  (1864)  pp. 121–134  (Also: Giornale di Mat. 2 (1864), 152–158; 180–186)</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  F.G. Frobenius,  "Über die Charactere der symmetrischen Gruppe"  ''Sitz. K. Preuss. Akad. Wiss''  (1900)  pp. 516–534  (Also: Gesammelte Abh. 3 Springer, 1968, 148-166)</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  C. Jacobi,  "De functionibus alternantibus earumque divisione per productum e differentiis elementorum conflatum"  ''J. Reine Angew. Math.'' , '''22'''  (1841)  pp. 360–371  (Also: Math. Werke 3, Chelsea, 1969, 439-452)</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  G.D. James,  A. Kerber,  "The representation theory of the symmetric group" , ''Encycl. Math. Appl.'' , '''16''' , Addison-Wesley  (1981)</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  D.E. Knuth,  "Permutations, matrices and generalized Young tableaux"  ''Pacific J. Math.'' , '''34'''  (1970)  pp. 709–727</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  C. Kostka,  "Über den Zusammenhang zwischen einigen Formen von symmetrischen Funktionen"  ''Crelle's J.'' , '''93'''  (1882)  pp. 89–123</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  D.E. Littlewood,  "The theory of group characters" , Oxford Univ. Press  (1950)</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  D.E. Littlewood,  A.R. Richardson,  "Group characters and algebra"  ''Philos. Trans. R. Soc. London Ser. A'' , '''233'''  (1934)  pp. 99–142</td></tr><tr><td valign="top">[a8]</td> <td valign="top">  I.G. Macdonald,  "Symmetric functions and Hall polynomials" , Oxford Univ. Press  (1995)  (Edition: Second)</td></tr><tr><td valign="top">[a9]</td> <td valign="top">  B.E. Sagan,  "The symmetric group: representations, combinatorial algorithms, and symmetric functions" , Wadsworth&amp;Brooks/Cole  (1991)  (Second ed.: Springer, to appear)</td></tr><tr><td valign="top">[a10]</td> <td valign="top">  C. Schensted,  "Longest increasing and decreasing subsequences"  ''Canad. J. Math.'' , '''13'''  (1961)  pp. 179–191</td></tr><tr><td valign="top">[a11]</td> <td valign="top">  I. Schur,  "Über eine Klasse von Matrizen die sich einer gegeben Matrix zuordnen lassen"  ''Inaugural Diss. Berlin''  (1901)</td></tr><tr><td valign="top">[a12]</td> <td valign="top">  N. Trudi,  "Intorno un determinante piu generale di quello che suol dirsi determinante delle radici di una equazione, ed alle funzioni simmetriche complete di queste radici"  ''Rend. Accad. Sci. Fis. Mat. Napoli'' , '''3'''  (1864)  pp. 121–134  (Also: Giornale di Mat. 2 (1864), 152–158; 180–186)</td></tr></table>

Revision as of 15:30, 1 July 2020

The Schur functions $s_{ \lambda }$ are a special basis for the algebra of symmetric functions $\Lambda$. They are also intimately connected with representations of the symmetric and general linear groups (cf. also Representation of the symmetric groups). Standard references are [a3], [a6], [a8], [a9].

Definitions.

Let $\mathbf{x} = \{ x _ { 1 } , \dots , x _ { l } \}$ be a set of variables and let $\Lambda$ be the algebra of symmetric functions in $\mathbf{x}$. Bases for this algebra are indexed by partitions $\lambda = ( \lambda _ { 1 } , \dots , \lambda _ { l } )$, i.e., $\lambda$ is a weakly decreasing sequence of $l$ non-negative integers $\lambda _ { i }$ called parts. Associated with any partition is an alternant, which is the $l \times l$ determinant

\begin{equation*} a_\lambda = \operatorname { det } ( x _ { i } ^ { \lambda_j } ). \end{equation*}

In particular, for the partition $\delta = ( l - 1 , l - 2 , \ldots , 0 )$ one has the Vandermonde determinant $a _ { \delta } = \prod _ { i < j } ( x _ { i } - x _ { j } )$. In his thesis [a11], I. Schur defined the functions which bear his name as

\begin{equation*} s _ { \lambda } = \frac { a _ { \lambda + \delta} } { a _ { \delta } }, \end{equation*}

where addition of partitions is component-wise. It is clear from this equation that $s_{ \lambda }$ is a symmetric homogeneous polynomial of degree $| \lambda | = \Sigma _ { i } \lambda_i$.

There is a more combinatorial definition of a Schur function. A partition $\lambda$ can be viewed as a Ferrers shape, obtained by placing dots or cells in $l$ left-justified rows with $\lambda _ { i }$ boxes in row $i$. One obtains a semi-standard Young tableaux, $T$, of shape $\lambda$ by replacing each dot by a positive integer so that rows weakly increase and columns strictly increase (cf. also Young tableau). For example, if $\lambda = ( 4,2,1 )$, then its shape and a possible tableau are

Each tableau determines a monomial $x ^ { T } = \prod _ { i \in T } x _ { i }$, e.g., in the example above, $x ^ { T } = x _ { 1 } ^ { 3 } x _ { 2 } x _ { 3 } ^ { 2 } x _ { 4 }$. The second definition of the Schur function is then

\begin{equation*} s _ { \lambda } = \sum _ { T } \mathbf{x} ^ { T }, \end{equation*}

where the sum is over all semi-standard Young tableaux of shape $\lambda$ with entries between $1$ and $l$.

Change of basis.

The Schur functions can also be written in terms of the other standard bases for $\Lambda$. A monomial symmetric function $m _ { \lambda }$ is the sum of all monomials whose exponent sequence is some permutation of $\lambda$. Also, define the Kostka number [a5] $K _ { \lambda \mu }$ as the number of semi-standard Young tableaux $T$ of shape $\lambda$ and content $\mu = ( \mu _ { 1 } , \dots , \mu _ { l } )$, i.e., $T$ contains $\mu _ { i }$ entries equal to $i$ for $1 \leq i \leq l$. The combinatorial definition of $s_{ \lambda }$ immediately gives the following rule, known as Young's rule:

\begin{equation*} s _ { \lambda } = \sum _ { \mu } K _ { \lambda \mu } m _ { \mu }. \end{equation*}

Now consider the complete homogeneous symmetric functions $h_\lambda = h _ { \lambda _ { 1 } } \ldots h _ { \lambda _ { l } }$ and the elementary symmetric functions $\lambda = e _ { \lambda _ { 1 } } \cdots e _ { \lambda _ { l } }$, where $h _ { \lambda _ { i } }$ (respectively, $e _ { \lambda _ { i } }$) is the sum of all (respectively, all square-free) monomials of degree $\lambda _ { i }$. Also, let $\lambda ^ { \prime }$ denote the partition conjugate to $\lambda$, whose parts are the column lengths of $\lambda$'s shape. In the preceding example, $\lambda ^ { \prime } = ( 3,2,1,1 )$. For the two bases under consideration, the function $s_{ \lambda }$ can be described as a determinant (the Jacobi–Trudi identity [a2], [a12] and its dual):

\begin{equation*} s _ { \lambda } = \operatorname { det } ( h _ { \lambda _ { i } - i + j } ), \end{equation*}

\begin{equation*} s _ { \lambda ^ { \prime } } = \operatorname { det } ( e _ { \lambda _ { i } - i + j } ). \end{equation*}

Note that this identity immediately implies

\begin{equation*} s _{( l )} = h _ { l } \text { and } s _ { ( 1 ^ { l }) } = e_{ l}, \end{equation*}

where $( 1 ^ { l } )$ is the partition with $l$ parts all equal to $1$. These specializations also follow directly from the combinatorial definition of $s_{ \lambda }$.

Representations.

The description of $s_{ \lambda }$ in terms of the power sum symmetric functions brings in the representation theory of the symmetric group $\mathcal{S} _ { n }$. The irreducible representations of $\mathcal{S} _ { n }$ are indexed by partitions $\lambda$ such that $| \lambda | = n$. Given a conjugacy class of $\mathcal{S} _ { n }$ corresponding to a partition $\mu$, let $k _ { \mu }$ denote its size and let $\chi _ { \mu } ^ { \lambda }$ be the value of the $\lambda$th irreducible character on the class. Now consider the power sum symmetric function $p _ { \lambda } = p _ { \lambda _ { 1 } } \cdots p _ { \lambda _ { l } }$, where $p _ { \lambda _ { i } } = x _ { 1 } ^ { \lambda _ { i } } + \ldots + x _ { l } ^ { \lambda _ { i } }$.

The following now holds: If $| \lambda | = n$, then

\begin{equation*} s _ { \lambda } = \frac { 1 } { n ! } \sum _ { | \mu | = n } k _ { \mu } \chi _ { \mu } ^ { \lambda } p _ { \mu }. \end{equation*}

In other words, $s_{ \lambda }$ is the cycle-indicator generating function (in the sense of Polyá–Redfield enumeration) for the irreducible character of $\mathcal{S} _ { n }$ corresponding to $\lambda$.

Now, consider the complex general linear group $\operatorname{GL}_l$. A representation $\rho : \operatorname{GL} _ { l } \rightarrow \operatorname{GL} _ { m }$ is polynomial if, for every $X \in \operatorname {GL}_{l}$, the entries of $\rho ( X )$ are polynomials in the entries of $X$. The polynomial representations of $\operatorname{GL}_l$ are indexed by the partitions $\lambda$ with $l$ non-negative parts. Let be the character of a polynomial representation $\rho$ and let $X$ have eigenvalues $x _ { 1 } , \dots , x _ { l }$. Then is a polynomial function of the $x_{i}$ (because this is true for diagonalizable $X$ and these are dense in $\operatorname{GL}_l$) and is symmetric (because is a class function). In fact, more is true: The irreducible polynomial characters of $\operatorname{GL}_l$ are precisely the $s_{ \lambda }$ for $\lambda$ with $l$ non-negative parts.

Properties.

The connection with representations of $\mathcal{S} _ { n }$ can be used to construct an isomorphism of algebras. Let $R ^ { n }$ denote the vector space of all class functions on $\mathcal{S} _ { n }$ and let $R = \sum _ { n > 0 } R ^ { n }$. The irreducible characters form a basis for $R$, and it can be endowed with a multiplication by induction of the tensor product. The characteristic or Frobenius mapping [a1] $\operatorname{ch} : R \rightarrow \Lambda$ is defined on $\chi \in R ^ { x }$ by

\begin{equation*} \operatorname { ch } ( \chi ) = \frac { 1 } { n ! } \sum _ { | \mu | = n } k _ { \mu } \chi _ { \mu } p _ { \mu }, \end{equation*}

where $\chi _ { \mu }$ is the value of on the class corresponding to $\mu$. The mapping $\operatorname{ch} : R \rightarrow \Lambda$ is an isomorphism of algebras. In fact, there are natural inner products on $R$ and $\Lambda$ that make $\operatorname{ch}$ an isometry.

A number of identities involving Schur functions have interesting bijective proofs using the combinatorial definition. Among the most famous are the following, in which it is assumed that $\mathbf{y} = \{ y _ { 1 } , \dots , y _ { l } \}$ is another set of variables.

The Cauchy identity and its dual are

\begin{equation*} \sum _ { \lambda } s _ { \lambda } ( \mathbf{x} ) s _ { \lambda } ( \mathbf{y} ) = \prod _ { i , j = 1 } ^ { l } \frac { 1 } { 1 - x _ { i } y _ { j } } \end{equation*}

and

\begin{equation*} \sum _ { \lambda } s _ { \lambda } ( \mathbf x ) s _ { \lambda ^ { \prime } } ( \mathbf y ) = \prod _ { i , j = 1 } ^ { l } ( 1 + x _ { i } y _ { j } ). \end{equation*}

D. Knuth [a4] has given algorithmic bijections between matrices and semi-standard Young tableaux that prove these identities. It is a generalization of a mapping of C. Schensted [a10] for standard Young tableaux, i.e., semi- standard Young tableaux where the entries are precisely $1 , \dots , | \lambda |$.

One can also describe the structure constants for the algebra $\Lambda$ in the basis $s_{ \lambda }$ combinatorially. If $\mu \subseteq \lambda$ as Ferrers shapes, then one has a skew shape $\lambda / \mu$ consisting of all dots or cells that are in $\lambda$ but not in $\mu$. Skew semi-standard Young tableaux are defined in the obvious way. The reverse row word for a semi-standard Young tableaux $T$, $\pi_T$, is obtained by reading the entries in each row from right to left, starting with the top row and working down. For the example tableau, $\pi_T = 3111324$. Also, a sequence of positive integers $\pi = w _ { 1 } \dots w _ { n }$ is a lattice permutation or ballot sequence if, in every prefix $w _ { 1 } \ldots w _ { k }$, the number of $i$'s is at least as big as the number of $( i + 1 )$'s for all $i \geq 1$. The Littlewood–Richardson rule [a7] states that if

\begin{equation*} \lambda ^ { s _ { \mu } } = \sum _ { \nu } c _ { \lambda \mu } ^ { \nu } s _ { \nu }, \end{equation*}

then $c _ { \lambda \mu } ^ { \nu }$ is equal to the number of semi-standard Young tableaux $T$ of shape $\nu / \lambda$ and content $\mu$ such that $\pi_T$ is a ballot sequence. Via the characteristic mapping, the Littlewood–Richardson coefficients $c _ { \lambda \mu } ^ { \nu }$ can also be viewed as giving the multiplicities of the character product $\chi ^ { \lambda } \chi ^ { \mu }$ when decomposed into irreducibles. Equivalently, one can consider the decomposition of the inner tensor product of two irreducible polynomial representations of $\operatorname{GL}_l$.

There are many generalizations of Schur functions, one of the most notable being the Hall–Littlewood functions. See [a8] for more information.

References

[a1] F.G. Frobenius, "Über die Charactere der symmetrischen Gruppe" Sitz. K. Preuss. Akad. Wiss (1900) pp. 516–534 (Also: Gesammelte Abh. 3 Springer, 1968, 148-166)
[a2] C. Jacobi, "De functionibus alternantibus earumque divisione per productum e differentiis elementorum conflatum" J. Reine Angew. Math. , 22 (1841) pp. 360–371 (Also: Math. Werke 3, Chelsea, 1969, 439-452)
[a3] G.D. James, A. Kerber, "The representation theory of the symmetric group" , Encycl. Math. Appl. , 16 , Addison-Wesley (1981)
[a4] D.E. Knuth, "Permutations, matrices and generalized Young tableaux" Pacific J. Math. , 34 (1970) pp. 709–727
[a5] C. Kostka, "Über den Zusammenhang zwischen einigen Formen von symmetrischen Funktionen" Crelle's J. , 93 (1882) pp. 89–123
[a6] D.E. Littlewood, "The theory of group characters" , Oxford Univ. Press (1950)
[a7] D.E. Littlewood, A.R. Richardson, "Group characters and algebra" Philos. Trans. R. Soc. London Ser. A , 233 (1934) pp. 99–142
[a8] I.G. Macdonald, "Symmetric functions and Hall polynomials" , Oxford Univ. Press (1995) (Edition: Second)
[a9] B.E. Sagan, "The symmetric group: representations, combinatorial algorithms, and symmetric functions" , Wadsworth&Brooks/Cole (1991) (Second ed.: Springer, to appear)
[a10] C. Schensted, "Longest increasing and decreasing subsequences" Canad. J. Math. , 13 (1961) pp. 179–191
[a11] I. Schur, "Über eine Klasse von Matrizen die sich einer gegeben Matrix zuordnen lassen" Inaugural Diss. Berlin (1901)
[a12] N. Trudi, "Intorno un determinante piu generale di quello che suol dirsi determinante delle radici di una equazione, ed alle funzioni simmetriche complete di queste radici" Rend. Accad. Sci. Fis. Mat. Napoli , 3 (1864) pp. 121–134 (Also: Giornale di Mat. 2 (1864), 152–158; 180–186)
How to Cite This Entry:
Schur functions in algebraic combinatorics. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Schur_functions_in_algebraic_combinatorics&oldid=49900
This article was adapted from an original article by Bruce E. Sagan (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article