If $A$ is an adjacency matrix of the connected graph $G$ and $B_\pi$ is its quotient matrix corresponding to an equitable partition $\pi={C_1,C_2,...,C_m}$. Since this quotient matrix is diagonally similar to a symmetric matrix. So if we take any $k\times k$ principal submatrix that is, $B_k$, of the $B_\pi$.
Can by the use Cauchy's interlacing theorem we say this:
$\lambda_i(B_\pi) \geq \lambda_i(B_k)\geq \lambda_{m-k+i}(B_\pi)$? for any $i=1...k$.
P.s: As Cauch's interlacing theorem is for Hermitian matrix.
Asked
Active
Viewed 486 times
1
Bernard
- 175,478
-
@Mahmoud I think I'm missing something. Does $B_\pi$ ever fail to be symmetric? Could you give me an example of a graph/partition for which this occurs? – Ben Grossmann Jul 05 '18 at 12:26
-
@Omnomnomnom, Considering the distance partition in Petersen graph the quotient matrix is not symmeteric. – محمد عتیق طا ہر Jul 05 '18 at 12:54
1 Answers
1
Let $C$ be the symmetric matrix diagonally similar to $B$. Then each prinicipal submatrix of $B$ is diagonally similar to the corresponding principal submatrix of $C$, and so they have the same eigenvalues. Since interlacing holds for $C$, it must hold for $B$.
Chris Godsil
- 13,703