$\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$?](https://mathoverflow.net/questions/313392/is-this-bound-uniform-in-n/313413#313413) ; however, his proof seems to be easy to extend to general $s$. 



Spectral decomposition of a combinatorial matrix/Random walks on $s$-sets
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](https://onlinelibrary.wiley.com/doi/full/10.1002/jcd.21308) 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)](https://www.sciencedirect.com/science/article/pii/0024379582900271), 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.


