Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
If $J$ is a polynomial in $A$ then $AJ=JA$. All entries in a row of $AJ$ are equal,... –  Chris Godsil Nov 15 '12 at 19:16
    
Thank you. I have edited my question according to your hint. Though I still need to prove the other implication. –  Montez Nov 15 '12 at 23:26
    
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". –  Chris Godsil Nov 17 '12 at 0:49
    
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? –  draks ... Nov 28 '12 at 22:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.