\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{}
%TCIDATA{}
%TCIDATA{}
%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 im_{\lambda}\right) \\
& =\prod\limits_{1\leq i