\documentclass[12pt,final,notitlepage,onecolumn,german]{article}%
\usepackage[all,cmtip]{xy}
\usepackage{lscape}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{hyperref}
\usepackage{color}
\usepackage{amsmath}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{CSTFile=LaTeX article (bright).cst}
%TCIDATA{Created=Sat Mar 27 17:33:36 2004}
%TCIDATA{LastRevised=Thursday, December 05, 2013 01:17:01}
%TCIDATA{<META NAME="ViewSettings" CONTENT="0">}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\definecolor{violet}{RGB}{143,0,255}
\definecolor{forestgreen}{RGB}{34, 100, 34}
\voffset=-1.5cm
\hoffset=-1.5cm
\setlength\textheight{22cm}
\setlength\textwidth{14cm}
\begin{document}

\begin{center}
\textbf{A representation-theoretical solution to MathOverflow question
\#88399}

\textit{Darij Grinberg}

version 2 (4 December 2013)

\bigskip
\end{center}

Sorry for hasty writing. Please let me know about any mistakes or unclarities
(A@B.com with A=darijgrinberg and B=gmail).

\begin{center}
\textbf{\S 1. Statement of the problem}
\end{center}

Let $n\in\mathbb{N}$.

For every $w\in S_{n}$, let $\sigma\left(  w\right)  $ denote the number of
cycles in the cycle decomposition of the permutation $w$ (this includes cycles
consisting of one element).

We can consider the matrix $\left(  x^{\sigma\left(  gh^{-1}\right)  }\right)
_{g,h\in S_{n}}$; this is a matrix over the polynomial ring $\mathbb{Q}\left[
x\right]  $, whose rows and whose columns are indexed by the elements of
$S_{n}$. (So this is a matrix with $n!$ rows and $n!$ columns, although there
is no explicit ordering on the set of rows/columns given.)

The claim of
\href{http://mathoverflow.net/questions/88399/an-nxn-determinant}{MathOverflow
question \#88399} is:

\begin{quote}
\textbf{Theorem 1.} The polynomial
\[
\det\left(  \left(  x^{\sigma\left(  gh^{-1}\right)  }\right)  _{g,h\in S_{n}%
}\right)  \in\mathbb{Q}\left[  x\right]
\]
factors into linear factors of the form $x-\ell$ with $\ell\in\left\{
-n+1,-n+2,...,n-1\right\}  $.
\end{quote}

Before we head to the proof of this theorem, let us show some examples:

\textbf{Example.} If $n=1$, then the matrix $\left(  x^{\sigma\left(
gh^{-1}\right)  }\right)  _{g,h\in S_{n}}$ has only one row and one column,
and its only entry is $x$. Its determinant thus is $x$, which is in agreement
with Theorem 1.

If $n=2$, then the matrix $\left(  x^{\sigma\left(  gh^{-1}\right)  }\right)
_{g,h\in S_{n}}$ has two rows and two columns. Picking a reasonable ordering
on $S_{n}$, we can represent it as the $2\times2$-matrix $\left(
\begin{array}
[c]{cc}%
x^{2} & x\\
x & x^{2}%
\end{array}
\right)  $, which has determinant $x^{2}\left(  x-1\right)  \left(
x+1\right)  $.

If $n=3$, then the matrix $\left(  x^{\sigma\left(  gh^{-1}\right)  }\right)
_{g,h\in S_{n}}$ can be represented (by picking an ordering on $S_{n}$) by the
$6\times6$-matrix%
\[
\left(
\begin{array}
[c]{cccccc}%
x^{3} & x^{2} & x^{2} & x & x & x^{2}\\
x^{2} & x^{3} & x & x^{2} & x^{2} & x\\
x^{2} & x & x^{3} & x^{2} & x^{2} & x\\
x & x^{2} & x^{2} & x^{3} & x & x^{2}\\
x & x^{2} & x^{2} & x & x^{3} & x^{2}\\
x^{2} & x & x & x^{2} & x^{2} & x^{3}%
\end{array}
\right)  ,
\]
and thus has determinant $x^{6}\left(  x-2\right)  \left(  x+2\right)  \left(
x-1\right)  ^{5}\left(  x+1\right)  ^{5}$. This, again, matches the claim of
Theorem 1.

For $n=4$, we have \newline$\det\left(  \left(  x^{\sigma\left(
gh^{-1}\right)  }\right)  _{g,h\in S_{n}}\right)  =\left(  x-3\right)  \left(
x+3\right)  \left(  x-2\right)  ^{10}\left(  x+2\right)  ^{10}\left(
x-1\right)  ^{23}\left(  x+1\right)  ^{23}x^{28}$.

\begin{quote}
\textbf{Exercise 1.} Prove that the polynomial $\det\left(  \left(
x^{\sigma\left(  gh^{-1}\right)  }\right)  _{g,h\in S_{n}}\right)  $ is even
(that is, a polynomial in $x^{2}$) for every $n\geq2$. (See the end of this
note for a hint.)
\end{quote}

\begin{center}
\textbf{\S 2. Reduction to representation theory}
\end{center}

Let us first reduce Theorem 1 to a representation-theoretical statement:

For any finite group $G$, let $\operatorname*{Irrep}G$ denote a set of
representatives of all irreducible representations of $G$ over $\mathbb{C}$
modulo isomorphism.\footnote{\textit{Remark.} We are considering irreducible
representations over $\mathbb{C}$ here for simplicity, but actually the
argument works more generally: We can replace $\mathbb{C}$ by any field
$\mathbb{K}$ of characteristic $0$ such that the group algebra $\mathbb{K}%
\left[  G\right]  $ factors into a direct product of matrix rings over
$\mathbb{K}$. In particular, the algebraic closure of $\mathbb{Q}$ does the
trick. In the case $G=S_{n}$ (this is the case we are going to consider!), it
is known that \textbf{any} field of characteristic $0$ can be taken as
$\mathbb{K}$, because the Specht modules are defined over $\mathbb{Q}$ and
thus provide a factorization of the group algebra $\mathbb{K}\left[  G\right]
$ into a direct product of matrix rings over $\mathbb{K}$ for any field
$\mathbb{K}$ of characteristic $0$. See any good text on representation theory
of $S_{n}$ for details (the main reason for this to work is Corollary 4.38 of
[2]).}

From the theory of group determinants (more precisely, the results of [1], or
the proof of Theorem 4.7 in [2]), we know that if $G$ is a finite group, and
$X_{g}$ is an indeterminate\footnote{Distinct indeterminates are presumed to
commute.} for every $g\in G$, then the matrix $\left(  X_{gh^{-1}}\right)
_{g,h\in G}$ (both rows and columns of this matrix are indexed by elements of
$G$) has determinant%
\[
\det\left(  \left(  X_{gh^{-1}}\right)  _{g,h\in G}\right)  =\prod
\limits_{\rho\in\operatorname*{Irrep}G}\left(  \det\left(  \sum\limits_{g\in
G}\rho\left(  g\right)  X_{g}\right)  ^{\dim\rho}\right)  .
\]


Applying this to $G=S_{n}$ and evaluating this polynomial identity at
$X_{g}=x^{\sigma\left(  g\right)  }$, we obtain%
\begin{equation}
\det\left(  \left(  x^{\sigma\left(  gh^{-1}\right)  }\right)  _{g,h\in S_{n}%
}\right)  =\prod\limits_{\rho\in\operatorname*{Irrep}S_{n}}\left(  \det\left(
\sum\limits_{g\in S_{n}}\rho\left(  g\right)  x^{\sigma\left(  g\right)
}\right)  ^{\dim\rho}\right)  . \label{det.2}%
\end{equation}


Hence, in order to show that the polynomial $\det\left(  \left(
x^{\sigma\left(  gh^{-1}\right)  }\right)  _{g,h\in S_{n}}\right)
\in\mathbb{Q}\left[  x\right]  $ factors into linear factors of the form
$x-\ell$ with $\ell\in\left\{  -n+1,-n+2,...,n-1\right\}  $, it is enough to
prove that, for every irreducible representation $\rho$ of $S_{n}$ over
$\mathbb{C}$, the polynomial $\det\left(  \sum\limits_{g\in S_{n}}\rho\left(
g\right)  x^{\sigma\left(  g\right)  }\right)  $ factors into linear factors
of the form $x-\ell$ with $\ell\in\left\{  -n+1,-n+2,...,n-1\right\}  $.

We are going to show something better:

\begin{quote}
\textbf{Theorem 2.} Let $\lambda=\left(  \lambda_{1},\lambda_{2}%
,...,\lambda_{n}\right)  $ be a partition of $n$. Let $m_{\lambda}$ be the
number of nonzero parts of the partition $\lambda$. Let $\rho_{\lambda}$ be
the irreducible representation of $S_{n}$ over $\mathbb{C}$ corresponding to
the partition $\lambda$. Then,%
\begin{equation}
\sum\limits_{g\in S_{n}}\rho_{\lambda}\left(  g\right)  x^{\sigma\left(
g\right)  }=\dfrac{n!}{\dim\rho}\prod\limits_{1\leq i<j\leq m_{\lambda}}%
\dfrac{\lambda_{i}-\lambda_{j}+j-i}{j-i}\cdot\prod\limits_{i=1}^{m_{\lambda}%
}\dfrac{\dbinom{x+\lambda_{i}-i}{\lambda_{i}}}{\dbinom{\lambda_{i}+m_{\lambda
}-i}{m_{\lambda}-i}}\cdot\operatorname*{id}\nolimits_{\rho_{\lambda}}.
\label{2.eq}%
\end{equation}



\end{quote}

Let us first see how Theorem 1 follows from Theorem 2:

\textit{Proof of Theorem 1.} For every partition $\lambda$ of $n$, let us
denote by $\rho_{\lambda}$ the irreducible representation of $S_{n}$ over
$\mathbb{C}$ corresponding to $\lambda$, and let us denote by $m_{\lambda}$
the number of nonzero parts of the partition $\lambda$. It is known that the
isomorphism classes of irreducible representations of $S_{n}$ over
$\mathbb{C}$ are in 1-to-1 correspondence with the partitions of $n$, and this
correspondence sends every partition $\lambda$ to the representation
$\rho_{\lambda}$. Thus,
\begin{align*}
&  \prod\limits_{\rho\in\operatorname*{Irrep}S_{n}}\left(  \det\left(
\sum\limits_{g\in S_{n}}\rho\left(  g\right)  x^{\sigma\left(  g\right)
}\right)  ^{\dim\rho}\right) \\
&  =\prod\limits_{\lambda\text{ partition of }n}\left(  \det\left(
\sum\limits_{g\in S_{n}}\rho_{\lambda}\left(  g\right)  x^{\sigma\left(
g\right)  }\right)  ^{\dim\rho_{\lambda}}\right) \\
&  =\prod\limits_{\lambda\text{ partition of }n}\left(  \left(  \dfrac
{n!}{\dim\rho}\prod\limits_{1\leq i<j\leq m_{\lambda}}\dfrac{\lambda
_{i}-\lambda_{j}+j-i}{j-i}\cdot\prod\limits_{i=1}^{m_{\lambda}}\dfrac
{\dbinom{x+\lambda_{i}-i}{\lambda_{i}}}{\dbinom{\lambda_{i}+m_{\lambda}%
-i}{m_{\lambda}-i}}\cdot\operatorname*{id}\nolimits_{\rho_{\lambda}}\right)
^{\dim\rho_{\lambda}}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by (\ref{2.eq})}\right)  .
\end{align*}
Combined with (\ref{det.2}), this yields%
\begin{align*}
&  \det\left(  \left(  x^{\sigma\left(  gh^{-1}\right)  }\right)  _{g,h\in
S_{n}}\right) \\
&  =\prod\limits_{\lambda\text{ partition of }n}\left(  \left(  \dfrac
{n!}{\dim\rho}\prod\limits_{1\leq i<j\leq m_{\lambda}}\dfrac{\lambda
_{i}-\lambda_{j}+j-i}{j-i}\cdot\prod\limits_{i=1}^{m_{\lambda}}\dfrac
{\dbinom{x+\lambda_{i}-i}{\lambda_{i}}}{\dbinom{\lambda_{i}+m_{\lambda}%
-i}{m_{\lambda}-i}}\cdot\operatorname*{id}\nolimits_{\rho_{\lambda}}\right)
^{\dim\rho_{\lambda}}\right)  .
\end{align*}
Now, the right hand side of this equation is clearly a polynomial in $x$ which
factors into a product of a constant and linear factors. All of the linear
factors have the form $x+\lambda_{i}-i-\alpha$ for $\alpha\in\left\{
0,1,...,\lambda_{i}-1\right\}  $ for various partitions $\lambda$ of $n$ and
various $i\in\left\{  1,2,...,m_{\lambda}\right\}  $.\ \ \ \ \footnote{In
fact, the only place where $x$ occurs on the right hand side of this equation
is $\dbinom{x+\lambda_{i}-i}{\lambda_{i}}$, and this factors as $\dbinom
{x+\lambda_{i}-i}{\lambda_{i}}=\dfrac{\left(  x+\lambda_{i}-i\right)  \left(
x+\lambda_{i}-i-1\right)  ...\left(  x+\lambda_{i}-i-\left(  \lambda
_{i}-1\right)  \right)  }{\lambda_{i}!}$.} By very simple combinatorics, it is
easy to see that each of these factors has the form $x-\ell$ for some $\ell
\in\left\{  -n+1,-n+2,...,n-1\right\}  $. Thus, the polynomial $\det\left(
\left(  x^{\sigma\left(  gh^{-1}\right)  }\right)  _{g,h\in S_{n}}\right)
\in\mathbb{Q}\left[  x\right]  $ factors into a product of a constant and
linear factors of the form $x-\ell$ with $\ell\in\left\{
-n+1,-n+2,...,n-1\right\}  $. Moreover, the constant is $1$ because the
polynomial $\det\left(  \left(  x^{\sigma\left(  gh^{-1}\right)  }\right)
_{g,h\in S_{n}}\right)  $ is monic\footnote{\textit{Proof.} In order to see
this, it is enough to show that when the determinant $\det\left(  \left(
x^{\sigma\left(  gh^{-1}\right)  }\right)  _{g,h\in S_{n}}\right)  $ is
written as a sum over all permutations of the set $S_{n}$ (nota bene:
permutations of $S_{n}$, not permutations in $S_{n}$), the highest degree of
$x$ is contributed by the product of the main diagonal. But this is clear,
because the main diagonal of the matrix $\left(  x^{\sigma\left(
gh^{-1}\right)  }\right)  _{g,h\in S_{n}}$ is filled with $x^{\sigma\left(
\operatorname*{id}\right)  }=x^{n}$ terms, while all other entries of the
matrix are lower powers of $x$.}. Hence, the polynomial $\det\left(  \left(
x^{\sigma\left(  gh^{-1}\right)  }\right)  _{g,h\in S_{n}}\right)
\in\mathbb{Q}\left[  x\right]  $ factors into linear factors of the form
$x-\ell$ with $\ell\in\left\{  -n+1,-n+2,...,n-1\right\}  $. Thus, Theorem 1
is proven (using Theorem 2).

\begin{center}
\textbf{\S 3. Proof of Theorem 2}
\end{center}

\textit{Proof of Theorem 2.} First of all, (\ref{2.eq}) is a polynomial
identity in $x$. Hence, we can WLOG assume that $x$ is not a polynomial
indeterminate in $\mathbb{Q}\left[  x\right]  $, but an integer greater than
$n$ (because if a polynomial identity over $\mathbb{Q}$ holds for infinitely
many integers, then it must always hold). Assume this.

Since $x$ is an integer greater than $n$, we have $x\in\mathbb{N}$. This
allows us to find a $\mathbb{Q}$-vector space of dimension $x$. Let $V$ be
such a vector space.

For every $S_{n}$-module $P$, let $\chi_{P}$ denote the character of this
module $P$. Note that every $h\in S_{n}$ satisfies%
\begin{equation}
\chi_{V^{\otimes n}}\left(  h\right)  =x^{\sigma\left(  h\right)  }.
\label{2.pf.1}%
\end{equation}
\footnote{\textit{Proof.} Let $h\in S_{n}$. Denote the action of $h$ on
$V^{\otimes n}$ by $h\mid_{V^{\otimes n}}$. Then, by the definition of a
character, $\chi_{V^{\otimes n}}\left(  h\right)  =\operatorname*{Tr}\left(
h\mid_{V^{\otimes n}}\right)  $.
\par
Pick a basis $\left(  e_{1},e_{2},...,e_{x}\right)  $ of $V$. This basis
induces a basis $\left(  e_{i_{1}}\otimes e_{i_{2}}\otimes...\otimes e_{i_{n}%
}\right)  _{\left(  i_{1},i_{2},...,i_{n}\right)  \in\left\{
1,2,...,x\right\}  ^{n}}$ of $V^{\otimes n}$. By the definition of the action
of $S_{n}$ on $V^{\otimes n}$, every $\left(  i_{1},i_{2},...,i_{n}\right)
\in\left\{  1,2,...,x\right\}  ^{n}$ satisfies%
\[
h\left(  e_{i_{1}}\otimes e_{i_{2}}\otimes...\otimes e_{i_{n}}\right)
=e_{h^{-1}\left(  i_{1}\right)  }\otimes e_{h^{-1}\left(  i_{2}\right)
}\otimes...\otimes e_{h^{-1}\left(  i_{n}\right)  }.
\]
Thus, if $h^{\left(  \times n\right)  }$ denotes the permutation of the set
$\left\{  1,2,...,x\right\}  ^{n}$ which sends every $\left(  i_{1}%
,i_{2},...,i_{n}\right)  \in\left\{  1,2,...,x\right\}  ^{n}$ to $\left(
h^{-1}\left(  i_{1}\right)  ,h^{-1}\left(  i_{2}\right)  ,...,h^{-1}\left(
i_{n}\right)  \right)  $, then the linear map $h\mid_{V^{\otimes n}}$ is
represented by the permutation matrix of the permutation $h^{\left(  \times
n\right)  }$ with respect to the basis $\left(  e_{i_{1}}\otimes e_{i_{2}%
}\otimes...\otimes e_{i_{n}}\right)  _{\left(  i_{1},i_{2},...,i_{n}\right)
\in\left\{  1,2,...,x\right\}  ^{n}}$ of $V^{\otimes n}$. Hence,
\[
\operatorname*{Tr}\left(  h\mid_{V^{\otimes n}}\right)  =\operatorname*{Tr}%
\left(  \text{permutation matrix of the permutation }h^{\left(  \times
n\right)  }\right)  =\left(  \text{number of fixed points of }h^{\left(
\times n\right)  }\right)
\]
(because the trace of a permutation matrix always equals the number of fixed
points of the corresponding permutation). Now, let us count the fixed points
of $h^{\left(  \times n\right)  }$.
\par
Clearly, an $n$\text{-tuple }$\left(  i_{1},i_{2},...,i_{n}\right)
\in\left\{  1,2,...,x\right\}  ^{n}$ is a fixed point of $h^{\left(  \times
n\right)  }$ if and only if every $j\in\left\{  1,2,...,n\right\}  $ satisfies
$i_{j}=i_{h^{-1}\left(  j\right)  }$. In other words, an $n$-tuple $\left(
i_{1},i_{2},...,i_{n}\right)  \in\left\{  1,2,...,x\right\}  ^{n}$ is a fixed
point of $h^{\left(  \times n\right)  }$ if and only if each pair of elements
$j$ and $k$ of $\left\{  1,2,...,n\right\}  $ which lie in the same cycle of
$h$ satisfies $i_{j}=i_{k}$. Hence, if we want to choose a fixed point of
$h^{\left(  \times n\right)  }$, we need only to specify, for every cycle $c$
of $h$, the value of $i_{j}$ for some element $j$ of this cycle $c$ (which
element $j$ we choose doesn't matter). Thus, we have to choose one element of
the set $\left\{  1,2,...,x\right\}  $ for each cycle of $h$; these choices
are arbitrary and independent, but beside them we have no more freedom. Thus,
there is a total of $x^{\sigma\left(  h\right)  }$ ways to choose a fixed
point of $h^{\left(  \times n\right)  }$ (because there are $\sigma\left(
h\right)  $ cycles of $h$, and there are $x$ elements of the set $\left\{
1,2,...,x\right\}  $). In other words,%
\[
x^{\sigma\left(  h\right)  }=\left(  \text{number of fixed points of
}h^{\left(  \times n\right)  }\right)  =\operatorname*{Tr}\left(
h\mid_{V^{\otimes n}}\right)  =\chi_{V^{\otimes n}}\left(  h\right)  .
\]
This proves (\ref{2.pf.1}).}

Let $L_{\lambda}$ be the representation of $\operatorname*{GL}\left(
V\right)  $ corresponding to the partition $\lambda$ of $n$. In other words,
let $L_{\lambda}$ be the image of $V$ under the $\lambda$-th Schur functor.
Then, $L_{\lambda}=\operatorname*{Hom}\nolimits_{\mathbb{Q}\left[
S_{n}\right]  }\left(  \rho_{\lambda},V^{\otimes n}\right)  $ (by one of the
definitions of Schur functors), so that
\begin{align}
\dim L_{\lambda}  &  =\dim\left(  \operatorname*{Hom}\nolimits_{\mathbb{Q}%
\left[  S_{n}\right]  }\left(  \rho_{\lambda},V^{\otimes n}\right)  \right)
=\left\langle \chi_{V^{\otimes n}},\chi_{\rho_{\lambda}}\right\rangle
\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Theorem 3.8 of [2], applied to
}V=V^{\otimes n}\text{ and }W=\rho_{\lambda}\right) \nonumber\\
&  =\underbrace{\dfrac{1}{\left\vert S_{n}\right\vert }}_{=\dfrac{1}{n!}}%
\sum\limits_{g\in S_{n}}\underbrace{\chi_{\rho_{\lambda}}\left(  g\right)
}_{=\operatorname*{Tr}\left(  \rho_{\lambda}\left(  g\right)  \right)
}\underbrace{\chi_{V^{\otimes n}}\left(  g^{-1}\right)  }%
_{\substack{=x^{\sigma\left(  g^{-1}\right)  }\\\text{(by (\ref{2.pf.1}))}%
}}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by one of the definitions of the inner
product of characters}\right) \nonumber\\
&  =\dfrac{1}{n!}\sum\limits_{g\in S_{n}}\operatorname*{Tr}\left(
\rho_{\lambda}\left(  g\right)  \right)  x^{\sigma\left(  g^{-1}\right)
}=\dfrac{1}{n!}\operatorname*{Tr}\left(  \sum\limits_{g\in S_{n}}\rho
_{\lambda}\left(  g\right)  x^{\sigma\left(  g^{-1}\right)  }\right)
\nonumber\\
&  =\dfrac{1}{n!}\operatorname*{Tr}\left(  \sum\limits_{g\in S_{n}}%
\rho_{\lambda}\left(  g\right)  x^{\sigma\left(  g\right)  }\right)
\ \ \ \ \ \ \ \ \ \ \left(  \text{since every }g\in S_{n}\text{ satisfies
}\sigma\left(  g^{-1}\right)  =\sigma\left(  g\right)  \right)  .
\label{2.pf.4}%
\end{align}
On the other hand, Theorem 4.63 of [2] (the Weyl character formula) yields%
\begin{align*}
\dim L_{\lambda}  &  =\prod\limits_{1\leq i<j\leq x}\dfrac{\lambda_{i}%
-\lambda_{j}+j-i}{j-i}\ \ \ \ \ \ \ \ \ \ \left(  \text{where }\lambda_{\ell
}\text{ denotes }0\text{ for all }\ell>m_{\lambda}\right) \\
&  =\prod\limits_{1\leq i<j\leq m_{\lambda}}\dfrac{\lambda_{i}-\lambda
_{j}+j-i}{j-i}\cdot\underbrace{\prod\limits_{1\leq i\leq m_{\lambda}<j\leq x}%
}_{=\prod\limits_{i=1}^{m_{\lambda}}\prod\limits_{j=m_{\lambda}+1}^{x}%
}\underbrace{\dfrac{\lambda_{i}-\lambda_{j}+j-i}{j-i}}_{\substack{=\dfrac
{\lambda_{i}+j-i}{j-i}\\\text{(since }m_{\lambda}<j\text{ yields }\lambda
_{j}=0\text{)}}}\cdot\prod\limits_{m_{\lambda}\leq i<j\leq x}%
\underbrace{\dfrac{\lambda_{i}-\lambda_{j}+j-i}{j-i}}_{\substack{=1\text{
(since }m_{\lambda}\leq i<j\\\text{yields that both }\lambda_{i}\text{ and
}\lambda_{j}\text{ are }0\text{)}}}\\
&  =\prod\limits_{1\leq i<j\leq m_{\lambda}}\dfrac{\lambda_{i}-\lambda
_{j}+j-i}{j-i}\cdot\prod\limits_{i=1}^{m_{\lambda}}\underbrace{\prod
\limits_{j=m_{\lambda}+1}^{x}\dfrac{\lambda_{i}+j-i}{j-i}}_{\substack{=\dfrac
{\dbinom{x+\lambda_{i}-i}{\lambda_{i}}}{\dbinom{\lambda_{i}+m_{\lambda}%
-i}{m_{\lambda}-i}}\\\text{(this is straightforward to check)}}}\cdot
\underbrace{\prod\limits_{m_{\lambda}\leq i<j\leq x}1}_{=1}\\
&  =\prod\limits_{1\leq i<j\leq m_{\lambda}}\dfrac{\lambda_{i}-\lambda
_{j}+j-i}{j-i}\cdot\prod\limits_{i=1}^{m_{\lambda}}\dfrac{\dbinom
{x+\lambda_{i}-i}{\lambda_{i}}}{\dbinom{\lambda_{i}+m_{\lambda}-i}{m_{\lambda
}-i}}.
\end{align*}
Combined with (\ref{2.pf.4}), this yields%
\[
\dfrac{1}{n!}\operatorname*{Tr}\left(  \sum\limits_{g\in S_{n}}\rho_{\lambda
}\left(  g\right)  x^{\sigma\left(  g\right)  }\right)  =\prod\limits_{1\leq
i<j\leq m_{\lambda}}\dfrac{\lambda_{i}-\lambda_{j}+j-i}{j-i}\cdot
\prod\limits_{i=1}^{m_{\lambda}}\dfrac{\dbinom{x+\lambda_{i}-i}{\lambda_{i}}%
}{\dbinom{\lambda_{i}+m_{\lambda}-i}{m_{\lambda}-i}},
\]
so that%
\begin{equation}
\operatorname*{Tr}\left(  \sum\limits_{g\in S_{n}}\rho_{\lambda}\left(
g\right)  x^{\sigma\left(  g\right)  }\right)  =n!\prod\limits_{1\leq i<j\leq
m_{\lambda}}\dfrac{\lambda_{i}-\lambda_{j}+j-i}{j-i}\cdot\prod\limits_{i=1}%
^{m_{\lambda}}\dfrac{\dbinom{x+\lambda_{i}-i}{\lambda_{i}}}{\dbinom
{\lambda_{i}+m_{\lambda}-i}{m_{\lambda}-i}}. \label{2.pf.6}%
\end{equation}


But $\sum\limits_{g\in S_{n}}gx^{\sigma\left(  g\right)  }$ is a central
element of $\mathbb{Q}\left[  S_{n}\right]  $ (since the map $S_{n}%
\rightarrow\mathbb{Q}$, $g\mapsto\sigma\left(  g\right)  $ is a class
function), so that $\sum\limits_{g\in S_{n}}gx^{\sigma\left(  g\right)  }$
acts on any irreducible representation of $S_{n}$ as a scalar multiple of
$\operatorname*{id}$ (by Schur's lemma). In particular, this yields that
$\rho_{\lambda}\left(  \sum\limits_{g\in S_{n}}gx^{\sigma\left(  g\right)
}\right)  =\kappa\cdot\operatorname*{id}\nolimits_{\rho_{\lambda}}$ for some
$\kappa\in\mathbb{C}$ (since $\rho_{\lambda}$ is an irreducible representation
of $S_{n}$). Consider this $\kappa$. Then,%
\begin{equation}
\sum\limits_{g\in S_{n}}\rho_{\lambda}\left(  g\right)  x^{\sigma\left(
g\right)  }=\rho_{\lambda}\left(  \sum\limits_{g\in S_{n}}gx^{\sigma\left(
g\right)  }\right)  =\kappa\cdot\operatorname*{id}\nolimits_{\rho_{\lambda}%
},\label{2.pf.8}%
\end{equation}
so that
\[
\operatorname*{Tr}\left(  \sum\limits_{g\in S_{n}}\rho_{\lambda}\left(
g\right)  x^{\sigma\left(  g\right)  }\right)  =\operatorname*{Tr}\left(
\kappa\cdot\operatorname*{id}\nolimits_{\rho_{\lambda}}\right)  =\kappa
\cdot\dim\rho_{\lambda}.
\]
Combined with (\ref{2.pf.6}), this yields%
\[
\kappa\cdot\dim\rho_{\lambda}=n!\prod\limits_{1\leq i<j\leq m_{\lambda}}%
\dfrac{\lambda_{i}-\lambda_{j}+j-i}{j-i}\cdot\prod\limits_{i=1}^{m_{\lambda}%
}\dfrac{\dbinom{x+\lambda_{i}-i}{\lambda_{i}}}{\dbinom{\lambda_{i}+m_{\lambda
}-i}{m_{\lambda}-i}},
\]
so that%
\[
\kappa=\dfrac{n!}{\dim\rho}\prod\limits_{1\leq i<j\leq m_{\lambda}}%
\dfrac{\lambda_{i}-\lambda_{j}+j-i}{j-i}\cdot\prod\limits_{i=1}^{m_{\lambda}%
}\dfrac{\dbinom{x+\lambda_{i}-i}{\lambda_{i}}}{\dbinom{\lambda_{i}+m_{\lambda
}-i}{m_{\lambda}-i}}.
\]
Thus, (\ref{2.pf.8}) becomes%
\[
\sum\limits_{g\in S_{n}}\rho_{\lambda}\left(  g\right)  x^{\sigma\left(
g\right)  }=\dfrac{n!}{\dim\rho}\prod\limits_{1\leq i<j\leq m_{\lambda}}%
\dfrac{\lambda_{i}-\lambda_{j}+j-i}{j-i}\cdot\prod\limits_{i=1}^{m_{\lambda}%
}\dfrac{\dbinom{x+\lambda_{i}-i}{\lambda_{i}}}{\dbinom{\lambda_{i}+m_{\lambda
}-i}{m_{\lambda}-i}}\cdot\operatorname*{id}\nolimits_{\rho_{\lambda}}.
\]
This proves Theorem 2.

\begin{center}
\textbf{Hints to exercises}
\end{center}

\textit{Hint to exercise 1:} Let $n\geq2$. Expand $\det\left(  \left(
x^{\sigma\left(  gh^{-1}\right)  }\right)  _{g,h\in S_{n}}\right)  $ as a
product over all permutations of $S_{n}$ (a total of $\left(  n!\right)  !$
permutations, but you don't have to actually do the computations...). It is
clearly enough to show that every such permutation gives rise to a product
which simplifies to $x^{m}$ for some even $m$. To prove this, show that any
permutation $\alpha\in S_{n}$ satisfies $\operatorname*{sign}\alpha=\left(
-1\right)  ^{n-\sigma\left(  \alpha\right)  }$.

\begin{center}
\textbf{References}
\end{center}

[1] Keith Conrad, \textit{The Origin of Representation Theory}.\newline%
\texttt{\href{http://www.math.uconn.edu/~kconrad/articles/groupdet.pdf}{\texttt{http://www.math.uconn.edu/\symbol{126}%
kconrad/articles/groupdet.pdf}}}

[2] Pavel Etingof, Oleg Golberg, Sebastian Hensel, Tiankai Liu, Alex
Schwendner, Dmitry Vaintrob, Elena Yudovina, \textit{Introduction to
representation theory}, arXiv:0901.0827v5.\newline%
\texttt{\href{http://arxiv.org/abs/0901.0827v5}{\texttt{http://arxiv.org/abs/0901.0827v5}%
}}


\end{document}