Equitable partitions in the undirected graph

100 Views Asked by At

Let $G$ be an undirected simple graph with the adjacency matrix $A$. Let $P_{\pi}$ be the characteristic matrix for an equitable partition $\pi$, such that $A P_{\pi} = P_{\pi} B_{\pi}$, i.e., $B_{\pi}$ is the quotient matrix for the partition $\pi$. We know that for any eigen-pair $(\lambda,v)$ of $B_{\pi}$ we have an eigen-pair $(\lambda, P_{\pi} v)$ for $A$. On the other hand $A$ is diagonalizable, since it is real symmetric.

Now, my intuition is that for any $\pi$, $B_{\pi}$ is always diagonalizable, but, how to prove / disprove it?

1

There are 1 best solutions below

0
On

Prove that the minimal polynomial of $B$ divides that of $A$ (which follows from $AP=PB$) and then use the fact that a matrix is diagonalizable if and only if its minimal polynomial has no repeated factors.