# The matrix $J$(all of whose entries are 1) is a polynomial in the adjacency matrix $A$ of a graph $G$ …

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?

-
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