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


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 $$$$A:=A_s:=(|J\cap K|\colon J,K\in\J).$$$$ 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 $$$$P:=\tfrac1{\la_1}\,A$$$$ 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$$: $$$$pP^m-\pi=\nu^m\,pP_2.$$$$ 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 $$$$A=\la_1 P_1+\la_2 P_2$$$$ it also immediately follows that for any $$x=(x_J)\in\R^\J$$ $$$$\|Ax\|_2^2\ge\la_1^2\|P_1x\|_2^2=\la_1^2\Big(\sum_J x_J\Big)^2.$$$$ 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$$.

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.

• Wow, thank you for the references! I did not know that there is an entire theory here. However, I think that, using the representation of $|J\cap K|$ as the sum of products of indicators as in my answer, one may be able to deal somewhat similarly, in an elementary way, with natural powers (or, equivalently, with factorial products) of $|J\cap K|$, even though that may be significantly more difficult in the more general situation. – Iosif Pinelis Oct 23 '18 at 0:59

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

The first key observation in the proof of the theorem is that $$$$A=\sum_{k=1}^n A^{(k)},\quad\text{where}\quad A^{(k)}_{JK}:=\ii{k\in J}\ii{k\in K}$$$$ 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 $$$$(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,$$$$ as desired.

Next, let us show for any distinct $$i,j\in[n]$$ the vector $$d^{(i,j)}$$ defined by the formula $$$$d^{(i,j)}_J:=\ii{i\in J}-\ii{j\in J}$$$$ 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 $$$$\sum_{j=2}^n t_jd^{(1,j)}_J=0 \tag{1}$$$$ 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 $$$$t_s=\dots=t_n=0. \tag{2}$$$$ 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$$