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.

  • $\begingroup$ 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? $\endgroup$ – Jernej Feb 7 '15 at 19:56
  • $\begingroup$ @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. $\endgroup$ – Chris Godsil Feb 7 '15 at 20:10
  • $\begingroup$ Hm.. that makes sense, thanks! $\endgroup$ – Jernej Feb 7 '15 at 20:19

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.