Spectral decomposition of a combinatorial matrix/Random walks on $s$-sets

Question

$\newcommand{\Z}{\mathbb{Z}} \newcommand{\J}{\mathcal{J}} \newcommand{\la}{\lambda} \newcommand{\1}{\mathbf{1}} \newcommand{\R}{\mathbb{R}}$

Take any $n\in[3;\infty]$. Here and in what follows, $[k;\ell]:=[k,\ell]\cap\Z$. Take then any $s\in[2;n-1]$. Let $\J:=\J_s:=\binom{[n]}s$, the set of all $s$-sets in $[n]:=[1;n]$, that is, the set of all subsets of the set $[n]$ of size (cardinality) $s$. Let $N:=N_s:=|\J_s|=\binom ns$, the cardinality of the set $\J$. Consider the $N\times N$ matrix \begin{equation} A:=A_s:=(|J\cap K|\colon J,K\in\J). \end{equation} The problem is to prove

Theorem:$\quad$ The eigenvalues of the matrix $A$ are $\la_1:=s\binom{n-1}{s-1}$ (of multiplicity $1$), $\la_2:=\binom{n-2}{s-1}$ (of multiplicity $n-1$), and $\la_3:=0$ (of multiplicity $N-n$).

---

Comments: It is easy to see that the symmetric matrix \begin{equation} P:=\tfrac1{\la_1}\,A \end{equation} is double stochastic, which implies that $\la_1$ is indeed an eigenvalue of $A$, with a corresponding eigenvector $\1:=(1\colon J\in\J)$. That is, the vector $\pi:=\frac1N\,\1$ is the stationary distribution of the random walk/Markov chain on the set $\J_s$ of the $s$-sets with the transition probability matrix $P$. The eigenvalues of the matrix $P$ are $1$ (of multiplicity $1$), $\nu:=\la_2/\la_1:=\frac{n-s}{s(n-1)}\le\frac{n-2}{2(n-1)}\in(0,1/2)$ (of multiplicity $n-1$), and $0$ (of multiplicity $N-n$). So, $P=P_1+\nu P_2$, where $P_1$ and $P_2$ are the orthoprojectors onto the eigenspaces belonging to the respective eigenvalues $1$ and $\nu$. Take now any initial distribution $p$ on $\J$. Then for all natural $m$ we have $pP^m=pP_1+\nu^m pP_2=\pi+\nu^m pP_2$, so that we have the exponential convergence of the distribution $pP^m$ of the chain at time $m$ to the stationary distribution $\pi$: \begin{equation} pP^m-\pi=\nu^m\,pP_2. \end{equation} The difference $1-\nu$ between the two largest distinct eigenvalues of $P$ is called its spectral gap, which determines the rate of the exponential convergence.

From the spectral decomposition \begin{equation} A=\la_1 P_1+\la_2 P_2 \end{equation} it also immediately follows that for any $x=(x_J)\in\R^\J$ \begin{equation} \|Ax\|_2^2\ge\la_1^2\|P_1x\|_2^2=\la_1^2\Big(\sum_J x_J\Big)^2. \end{equation} For $s=2$, the latter inequality was proved by Fedor Petrov at Is this bound uniform in $N$? ; however, his proof seems to be easy to extend to general $s$.

Answer 1

Various variants of the matrix $$A_{J,K} = |J\cap K|$$ were studied, and the spectrum was computed. A one-parameter variant is given by $$A^{(i)}_{J,K} = \binom{|J\cap K|}{i}$$ for some fixed $i$, and your problem corresponds to $i=1$. In total, six variants are given in Section 3 of this friendly paper by Ghareghani, Ghorbani and Mohammad‐Noori. In particular, the spectrum of $A^{(i)}$ is described in Lemma 9. The lemma is attributed to R. M. Wilson (1982), who uses somewhat different notation and terminology. The case $i=1$ recovers your theorem, and in general the non-zero eigenvalues are given by $$\lambda_j=\binom{s-j}{i-j}\binom{n-i-j}{s-i}, \qquad j=0,1,2,\ldots,i,$$ with $\lambda_j$ having multiplicity $\binom{n}{j}-\binom{n}{j-1}$ (note that $\binom{n}{-1}:=0$). The eigenvalue 0 has multiplicity equal to the remaining dimension, i.e. $N-\binom{n}{i}$.

Other useful references, including to additional works of R. M. Wilson, appear in the bibliography of the G-G-MN paper.

Answer 2

$\newcommand{\ii}[1]{\operatorname{\mathsf I}\{#1\}}$

The first key observation in the proof of the theorem is that \begin{equation} A=\sum_{k=1}^n A^{(k)},\quad\text{where}\quad A^{(k)}_{JK}:=\ii{k\in J}\ii{k\in K} \end{equation} for $J,K$ in $\J$, where $\ii\cdot$ denotes the indicator. Clearly, the rank of $A^{(k)}$ is $\le1$ for each $k$, and so, the rank of $A$ is $\le n$. So, it suffices to exhibit an eigenvector belonging to $\la_1$ and $n-1$ linearly independent eigenvectors belonging to $\la_2$.

Concerning $\la_1$, for all $J\in\J$ we have \begin{equation} (A\1)_J=\sum_K A_{JK}=\sum_K\sum_{k=1}^n A^{(k)}_{JK} =\sum_{k=1}^n \ii{k\in J}\sum_K \ii{k\in K} =\sum_{k=1}^n \ii{k\in J}\binom{n-1}{s-1}=s\binom{n-1}{s-1}=\la_1, \end{equation} as desired.

Next, let us show for any distinct $i,j\in[n]$ the vector $d^{(i,j)}$ defined by the formula \begin{equation} d^{(i,j)}_J:=\ii{i\in J}-\ii{j\in J} \end{equation} for $J\in\J$ is a $\la_2$-eigenvector of $A$. Indeed, \begin{multline} (Ad^{(i,j)})_J=\sum_K A_{JK}d^{(i,j)}_K =\sum_{k=1}^n\ii{k\in J}\sum_K\ii{k\in K}(\ii{i\in K}-\ii{j\in K}) \\ =\sum_{k=1}^n\ii{k\in J}\sum_K(\ii{\{i,k\}\subseteq K}-\ii{\{j,k\}\subseteq K}) \\ =\sum_{k=1}^n\ii{k\in J}\Big(\ii{k=i}\binom{n-1}{s-1} +\ii{k\ne i}\binom{n-2}{s-2} \\ -\ii{k=j}\binom{n-1}{s-1}-\ii{k\ne j}\binom{n-2}{s-2}\Big) \\ =\sum_{k=1}^n\ii{k\in J}\binom{n-2}{s-1}(\ii{k=i}-\ii{k=j}) \\ =\binom{n-2}{s-1}(\ii{i\in J}-\ii{j\in J}) =\la_2d^{(i,j)}_J, \end{multline} as desired.

It remains to show that the $\la_2$-eigenvectors $d^{(1,2)},\dots,d^{(1,n)}$ are linearly independent. To do this, take any real $t_2,\dots,t_n$ such that \begin{equation} \sum_{j=2}^n t_jd^{(1,j)}_J=0 \tag{1} \end{equation} for all $J\in\J_s$. We need to show that $t_j=0$ for $j\in[2;n]$. First here, take $J=[1;s-1]\cup\{k\}$ for any $k\in[s;n]$. Then (1) yields \begin{multline} 0=\sum_{j=2}^n t_j(\ii{1\in[1;s-1]\cup\{k\}}-\ii{j\in[1;s-1]\cup\{k\}}) \\ =\sum_{j=2}^n t_j-\sum_{j=2}^{s-1} t_j-t_k=\sum_{j=s}^n t_j-t_k \end{multline} for all $k\in[s;n]$, so that $t_k=t$ for some real $t$ and all $k\in[s;n]$, whence $(n-s)t=0$ and $t=0$, so that \begin{equation} t_s=\dots=t_n=0. \tag{2} \end{equation} Next, take $J=[1;r-1]\cup\{k\}\cup[n-s+r+1,n]$ for any $r\in[2;s-1]$ and any $k\in[r;n-s+r]$. Then (1) yields \begin{multline} 0=\sum_{j=2}^n t_j(\ii{1\in[1;r-1]\cup\{k\}\cup[n-s+r+1,n]} \\ -\ii{j\in[1;r-1]\cup\{k\}\cup[n-s+r+1,n]}) \\ =\sum_{j=2}^n t_j-\sum_{j=2}^{r-1} t_j-t_k-\sum_{j=n-s+r+1}^n t_j, \end{multline} so that $t_k$ is constant for $k\in[r;n-s+r]$. In particular, $t_r=t_{r+1}$, for all $r\in[2;s-1]$, since $s\le n-1$. That is, $t_2=\dots=t_s$. It remains to recall (2). $\Box$