# Diagonalizing a matrix arising in a simple combinatorial situation

Maybe I'll return to this question a few hours from now and possibly even post an answer then. This concerns a matrix that I described in this answer.

Start with a $\dbinom n2\times n$ matrix $B$ with one row for each unordered pair $\{i,j\}\subseteq\{1,\ldots,n\}$. The entries in columns $i$ and $j$ of row $\{i,j\}$ are $1$; all other entries are $0$.

Then the matrix $C=B B^T$ is an $\dbinom n 2\times\dbinom n 2$ matrix of rank $n$. Its entry in row $\{i,j\}$ and column $\{k,\ell\}$ is $|\{i,j\}\cap\{k,\ell\}|$, the diagonal entries are $2$ and the majority of the off-diagonal entries are $0$ if $n$ is not too small, and many of the off-diagonal entries are $1$.

I wildly conjecture that the largest eigenvalue of $C=BB^T$ is $2(n-1)$ and the next $n-1$ eigenvalues are $n-2$. All the rest are clearly $0$.

My questions are:

• Is this guess about the eigenvalues right?
• Is there are nice geometric argument for this guess?
• Maybe a nice algebraic argument too?
• What interesting geometry is going on here?
• Or even algebra?
• Can things of interest be said about the orthogonal matrices that diagonalize this? Or in the singular-value decomposition of the $\dbinom n 2\times n$ matrix $b$, the other, smaller, $n\times n$ orthogonal matrix on the right?
• Keep in mind that the spectra of $BB^T$ and of $B^TB$ are related. ;) – darij grinberg Jul 31 '15 at 15:15
• ok, looking at this some hours later I see that it's easy to find the eigenvalues, and the geometry in $\mathbb R^n$ is clear. What's going on in $\mathbb R^{\binom n 2}$ I don't know yet, but maybe when I look at this three hours from now it will be obvious. – Michael Hardy Jul 31 '15 at 17:41

Alright, $BB^T$ is a matrix with $2$ in every diagonal entry and $0$s and $1$s off the diagonal. As darij grinberg points out $B^T B$ has $n-1$ in every diagonal entry and $1$ in every off-diagonal entry. If all diagonal entries are equal to each other and all off-diagonal entries are equal to each other, then the matrix is a linear combination of the $n\times n$ matrix $P$ in which every entry is $1/n$, and $Q=I-P$. These matrices enjoy the properties that $P^2=P^T=P$ and $Q^2=Q^T=Q$ and $PQ=QP=0$. Consequently \begin{align} (aP+bQ)(cP+dQ) & = acP^2 + ad PQ + bc QP + bd Q^2 \\[10pt] & = ac P + db Q, \end{align} so it's easy to multiply these. We have $$B^T B = 2(n-1) P + (n-2)Q. \tag 1$$ Since $P$ has rank $1$ and $Q$ has rank $n-1$, we can diagonalize the matrix $(1)$, getting $2(n-1)$ as the first diagonal entry and $n-2$ as the next $n-1$ diagonal entries. This confirms the guess.