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?
  • 1
    $\begingroup$ Keep in mind that the spectra of $BB^T$ and of $B^TB$ are related. ;) $\endgroup$ – darij grinberg Jul 31 '15 at 15:15
  • $\begingroup$ 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. $\endgroup$ – 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.

However, there are yet further questions in the original posting.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.