Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
What does it mean for n+1 to be equal to 1? –  Qiaochu Yuan Aug 26 '10 at 21:47
    
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. –  Jack Schmidt Aug 26 '10 at 22:10
    
I added two words. Hopefully that's a bit clearer now. –  John Jiang Aug 26 '10 at 22:20
    
What do you mean by "Fourier transform"? (I know about the relation between Fourier transform and irreducible representations, but I don't exactly know what it means in this context.) Does your $\hat{f}\left(\rho\right)$ just mean the action of $\rho$ on the irreducible representation? –  darij grinberg Aug 31 '10 at 0:01
1  
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. –  darij grinberg Aug 31 '10 at 0:03
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.