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{2\pi 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:


*

*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.


*

*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$.

*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'$?

*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.
 A: The partition $\lambda = (1, 1, \ldots, 1)$ answers your first and third questions in the negative direction.
For the irreducible representation corresponding to this partition,
$$
 \rho(g) = \begin{cases}  1 &\text{ if $g$ is an even permutation} \\
                         -1 &\text{ if $g$ is an odd permutation.}
           \end{cases}
$$
Then since $f$ is the mean of a set of odd partitions, $\hat{f}(\rho) = -1$.
This answers your first question since it has absolute value $1 > 1 - \cos \frac{2 \pi}{n}$, for sufficiently large $n$.
$(n - 1, 1) > \lambda$, so it also answers your third question as the spectral gap associated with $\lambda$ is zero, assuming the two-sided definition of spectral gap.
A: Consider the normal subgroup $A_n$ of $S_n$. It has index two.
The adjacent transpositions are odd permutations and lie in the coset of odd permutations. 
Let $\nu$ be a probability on $S_n$ concentrated on this coset. Let $\xi$ be the random walk on $S_n$ driven by $\nu$. Let $\xi_k$ be its position after $k$ transitions.
As the subgroup is normal, the random walk is concentrated on $A_n$ for $k$ even and the other coset for $k$ odd.
Therefore the convolution powers of $\nu$ do not converge to the uniform distribution and the random walk is periodic.
This means that there is more than one eigenvalue of absolute value one.
Your function $f$ is such a probability.
In fact the random walk driven by $f$ is reversible and so the stochastic operator is self-adjoint and so $-1$ is an eigenvalue.
This doesn't happen with the standard random transposition shuffle because that is a lazy random walk. If the laziness was taken out it would not converge either.
