MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am interested in eigenvalues of the following association scheme, which somewhat resembles the Johnson scheme.

Let $n$ and $k\leq n$ be positive integers. The $n!/(n-k)!$ vertices of the scheme are the $k$-tuples in $\{1,\ldots,n\}^k$ having unique elements (one can think of these tuples as ordered $k$-subsets of $\{1,\ldots,n\}$). For $i\in\{0,\ldots,k\}$, let two such tuples $\alpha$ and $\beta$ be $i$-related if they have exactly $k-i$ common elements and every common element has the same index in both $\alpha$ and $\beta$.

Let $A_i$ be $01$-matrix such that $(A_i)_{\alpha,\beta}=1$ if and only if $\alpha$ and $\beta$ are $i$-related. The matrices $A_0,A_1,\ldots,A_k$ together with some other matrices (which I do not care about) form an association scheme. The eigenvalues of $A_i$ correspond to irreducible representations of the direct product of symmetric groups $S_n$ and $S_k$.

Are the eigenvalues of $A_0,A_1,\ldots,A_k$ known?

I was only able to show that the eigenvalue of $A_i$ corresponding to an irreducible representation $\lambda\times\sigma$ of $S_n\times S_k$ is $0$ whenever the Young diagram corresponding to $\sigma$ has less than $i$ columns. My motivation comes from trying to show that, for $k\in O(n^{1/3})$, the eigenvalue of the operator $\sum_{i=0}^{k}\frac{(n-k-i)!}{(n-2k)!}A_i$ corresponding to an irreducible representation $\lambda\times\sigma$ is approximately equal to $n^k2^{k+\lambda_1-n}$, where $\lambda_1$ is the number of columns of the Young diagram corresponding to $\lambda$.

Even more particularly, I want to show that, when $k\in O(n^{1/3})$ and $\lambda_1=n-k+1$ (i.e. the Young diagram corresponding to $\lambda$ has $k-1$ boxes bellow the first row), we get that the eigenvalue of $B=\sum_{i=0}^k\frac{(n-k-i)!}{(n-2k)!}A_i$ corresponding to $\lambda\times\sigma$ is in $O(n^kk)$. Numerical results for small $k$ suggest that this eigenvalue is approximately $2n^k$, but I do not need so tight upper bound.

From the way I construct $B$, I know that it is positive semi-definite. If $\lambda_1=n-k$, then I can prove that the eigenvalue corresponding to $\lambda\times\sigma$ is at most $n^k(1+O(n^{-1/3}))$ as follows. First of all, in this case, we can rather easily relate dimensions of $\lambda$ and $\sigma$ using the hook length formula, because, if we think of $\lambda$ and $\sigma$ as Young diagrams, then, due the the Littlewood-Richardson rule, the part of $\lambda$ below the first row must be exactly equal to $\sigma$. Then I consider the trace of the projection $B\sum_{\lambda'}\Pi_{\lambda',\sigma}$, where $\Pi_{\lambda',\sigma}$ is the projector to the eigenspace corresponding to $\lambda'\times\sigma$. This trace is easy to calculate, since we do not need to consider the group $S_n$ for it, and only the term $\frac{(n-k)!}{(n-2k)!}A_0$ of $B$ contributes to it. And then I use the facts that $B\geq0$ and $\sum_{\lambda'}Tr(\Pi_{\lambda',\sigma})\approx Tr(\Pi_{\lambda,\sigma}) =\dim\lambda\cdot \dim \sigma$. But this argument does not seem to help when $\lambda_1=n-k+1$.

When $\sigma=[k]$ (the trivial representation) and $\sigma=[1^k]$ (the sign representation), I can calculate eigenvalues of $B$ corresponding to $\lambda\times\sigma$ exactly. For the former, by using the Johnson scheme. And, for the latter, by using the fact that only $A_0$ and $A_1$ have non-zero eigenvalues corresponding to $\lambda\times[1^k]$ and we have to consider only $\lambda=[n-k+1,1^{k-1}]$ and $\lambda=[n-k,1^k]$. Numerics for small $k$ suggest that, when $\lambda_1=n-k+1$, the eigenvalue of $B$ corresponding to $\lambda\times\sigma$ is between the eigenvalues corresponding to $[n-k+1,k-1]\times[k]$ and $[n-k+1,1^k]$. Proving that this indeed always holds would be enough for me.

I think that it could also be helpful if one could prove that, if we fix $k$, $\sigma$, and the part of the Young diagram corresponding to $\lambda$ below the first row---let us call it $\theta$, thus $\lambda=[n-|\theta|,\theta]$---then the eigenvalue of $A_i$ corresponding to $\lambda\times\sigma$ is a polynomial in $n$ with degree at most $\min\{i,k-|\theta|\}$. This seems to be true.

share|cite|improve this question
Try contacting Bill Martin at Worcester, if anyone knows he will. – Chris Godsil Mar 4 '13 at 12:34
This is a pretty old thread, and I don't follow some of what you say, but I may have some half-baked ideas that might work for showing your bound. For one thing, you can use the fact that your eigenvalues corresponding to high-dimensional irreducibles have proportionately high multiplicity, which actually bounds their magnitudes. Bounding the low multiplicity eigenvalues might be a challenge, but there has been some success in bounding eigenvalues of graphs arising from similar association schemes. If you're still located in Waterloo, we could even chat about it face to face. – Nathan Lindzey Jun 20 at 23:22

Your Answer


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

Browse other questions tagged or ask your own question.