MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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.