markov chains - Diagonalizing some matrices arising from Fourier transform on $S_n$.

Consider the function $f$ on $S_n$ which equals $1/n$ on all adjacent transpositions $(i,i+1)$, where we let $n+1 = 1$, and $0$ otherwise, and its Fourier transform $hat{f}(rho)$ evaluated at the irreducible representations.

Recall the irreducible representations of $S_n$ are indexed by the set of partitions of $n$. Partitions here are written as a finite non-increasing sequence of positive integers that add up to $n$.

When $rho$ is the representation corresponding to the partition $(n)$, the matrix $hat{f}(rho)$ is simply the $1 times 1$ matrix $[1]$.

When $rho$ is the representation corresponding to the partition $(n-1,1)$, the resulting matrix $hat{f}(rho)$ can be explicitly diagonalized, since it can be extended into a cyclic matrix on $mathbb{R}^n$. The eigenvalues are simply $cos frac{2pi k}{n}$ where $k = 1, ldots n-1$. Therefore the spectral gap for that matrix (the smallest gap between $1$ and an eigenvalue not equal to $1$) is simply

$$1-cos frac{2 pi}{n} = 1-cos frac{2(n-1)pi}{n} = frac{2 pi^2}{n^2} + O(frac{1}{n^3})$$.

the following questions are in increasing levels of difficulty and are interesting to Markov chain theorists:

1. Is it true that all other eigenvalues of $hat{f}(rho)$ for some irreducible representation $rho$ are strictly less than $1-cos frac{2 pi}{n}$ in absolute value?

Denote by $e_{lambda,j}$, $j = 1, ldots, d_lambda$ the eigenvalues of $hat{f}(rho_lambda)$, where $rho_lambda$ is the representation associated with the partition $lambda$ and $d_lambda$ is the dimension of that representation.

1. For any fixed $k in mathbb{N}$, is it true that $ (1-max_j e_{lambda,j}) le (n-lambda_1) frac{2 pi^2}{n^2} + O(frac{1}{n^3})$, for $n-lambda_1 le k$? Here $lambda_1$ denotes the longest part of the partition $lambda$.




2. If $lambda > lambda'$ in the sense that one can move blocks in the Ferrers diagram of $lambda'$ in the up and right direction to obtain $lambda$, for instance $(n-1,1) > (n-2,1,1)$, is it true that the spectral gap of $hat{f}(rho_lambda)$ is smaller than that associated with $lambda'$?




3. Give an explicit formula for $e_{lambda,j}$. This is most likely not possible.

   
   
   

   This question shows how hard it can be to diagonalize matrices and to understand the representation theory of $S_n$ at a practical level.