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:

  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.

  • $\begingroup$ What does it mean for n+1 to be equal to 1? $\endgroup$ – Qiaochu Yuan Aug 26 '10 at 21:47
  • $\begingroup$ Standard convention for writing down permutations sanely: When n=5, it means we talk about the adjacent transposition (1,2), (2,3), (3,4), (4,5), and (5,1). I think the "Coxeter diagram" for this is called A-tilde or something, and some combinatorialists like looking at this generating set. $\endgroup$ – Jack Schmidt Aug 26 '10 at 22:10
  • 1
    $\begingroup$ Anyway, your $\rho$ reminds me of the YJM elements in the Okounkov-Vershik construction (see bprim.org/vershik_okounkov-murli-new-aug07.pdf and front.math.ucdavis.edu/0503.5040 ), and as far as I remember, they consider the eigenvalues. At least that's some beginning. $\endgroup$ – darij grinberg Aug 31 '10 at 0:03
  • 1
    $\begingroup$ Thanks, so I did understand you right. Actually, I mentioned the Okounkov-Vershik paper because they consider very similar elements of $\mathbb C\left[S_n\right]$, namely $\left(1,i\right)+\left(2,i\right)+...+\left(i-1,i\right)$. $\endgroup$ – darij grinberg Aug 31 '10 at 11:36
  • 1
    $\begingroup$ That is indeed an interesting element. It might correspond to the top to random transposition card shuffling model, for which complete analysis in Markov chain theory is available using coupon collector phenomenon. $\endgroup$ – John Jiang Aug 31 '10 at 15:25

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.