2
$\begingroup$

if and only if $G$ is connected and regular.

To prove the "only if", assume $J$ is a polynomial in $A$. Then $JA=AJ$. The entries in the $i$th row of $AJ$ are all equal to the sum of the entries in the $i$th row of $A$. The entries in the $i$th column of $JA$ are all equal to the sum of the entries in the $i$th column of $A$. Therefore, the sums of entries in a row of $A$ is constant. This shows that $G$ is regular. Also $G$ must be connected, for otherwise $i$ and $j$ is not connected and the $ij$th entry of $A^n$ is always zero and $J$ cannot be a polynomial in $A$.

But how can I show the other implication?

  • 0
    If $J$ is a polynomial in $A$ then $AJ=JA$. All entries in a row of $AJ$ are equal,...2012-11-15
  • 0
    Thank you. I have edited my question according to your hint. Though I still need to prove the other implication.2012-11-15
  • 0
    For the other direction I would use spectral decomposition, and the fact that the degree is a simple eigenvalue of $A$. (Sorry to be cryptic but I am short of time right now.) I think this is all proved in Biggs "Algebraic Graph Theory".2012-11-17
  • 0
    Let $B$ be a random real $n\times n$ matrix and $K=\sum_k c_k B^k$ be a polynomial, then $BK=KB$, because $[B^k,B]=0$. But $B$ is not regular. Where is the difference to your setup?2012-11-28

0 Answers 0