# A question about the interlacing of symmetric matrices (graph interlacing)

Reading the paper of Haemers on graph interlacing I came across the following question.

Let $A$ be a real symmetric matrix partitioned into $m \times m$ blocks and suppose $B$ is a $m \times m$ matrix whose $(i,j)'$th entry is the average row sum of the $(i,j)'th$ block of $A.$

According to corollary 2.3 in the linked paper, the eigenvalues of $B$ interlace the eigenvalues of $A.$

Now $B$ need not be symmetric and it can happen that it has complex eigenvalues. Hence my question is

What is happening if $B$ has complex eigenvalues ? Are they just ignored?

As a side note, given that $m \leq n$ we say that a sequence $\lambda_1 \geq \cdots \lambda_n$ is interlaced by $\mu_1 \geq \cdots \geq \mu_m$ if $$\lambda_i \geq \mu_i \geq \lambda_{n-m+i} \quad \mbox{for all } i=1,\ldots,m$$

Although $B$ is not symmetric, it is diagonally similar to a symmetric matrix.
Let $P$ be the matrix whose columns are the characteristic vectors of your partition and let $Q$ be $P$ with columns scaled so they are unit vectors. So $Q=PD^{-1/2}$ where $D=P^TP$ (and is diagonal). Your matrix $B$ is $D^{-1}P^TAP$, which is not symmetric in general. But $D^{1/2} B D^{-1/2} = D^{1/2} D^{-1}P^TAP D^{-1/2} = Q^TAQ.$ So $B$ is diagonally similar to $Q^TAQ$, which is symmetric.
• Chris, do you happen to see a (efficient) way to use this relation in order to compute the eigenvalues of $B$ given that the eigenvalues of $A$ are known? – Jernej Feb 7 '15 at 19:56
• @Jernej:Not really. Take the disjoint union of $n$ disparate graphs on $n$ vertices, then add some edges to make the result connected. I find it very hard to see how use spectral information on the big graph to get information on the spectrum of (say) the third $n$-vertex graph. Also the standard general-purpose eigenvalue routines are so fast, there tends to be no reward for being clever. – Chris Godsil Feb 7 '15 at 20:10