# how prove the following statment for this matrix.

Let $A:=[a_{ij}]_{n×n}$ , $a_{ij}=0$ or $a_{ij}=1$ and $\exists m \in\mathbb N$ such that $A^m=J-I$, where $I$ is the identity matrix and $J=[1]_{n×n}$ (each entry is $1$). How to prove:

1. $\exists a \in\mathbb N$ such that $n=a^m+1$, and
2. $m$ is odd.

-
Let's collaborate :) I am thinking; $\det(A^m) = \det(J-I)$. Luckily, $\det(J-I) = n-1$, when $n$ is odd and $\det(J-I) = -(n-1)$ when $n$ is even. Then, since $\det(A^m) = [\det(A)]^m$, the equation holds with $a = \det(A)$ (not sure yet as to why $m$ should be odd). –  Anon Jan 29 '13 at 20:35
@Anon, your comment is practically an answer. –  DonAntonio Jan 29 '13 at 20:45
its better to write $detA^m=(-1)^n(n-1)$ then $n=\frac{{detA}^m}{(-1)^n}+1$ –  Maisam Hedyelloo Jan 29 '13 at 20:47
Theorem 1 in C. W. H. Lam, J. H. van Lint, Directed Graphs with Unique Paths of Fixed Length, Journal of Combinatorial Theory B, vol. 24, No. 3, 1978, alexandria.tue.nl/repository/freearticles/593457.pdf . –  darij grinberg Jan 29 '13 at 21:02
@darijgrinberg aww, I just myself took the square-root $J-I$ and saw that it was imaginary :) –  Anon Jan 29 '13 at 21:05
(The problem statement is false when $n=1$, but we will ignore this degenerate case.) We have at least three proofs.
Proof 1 (adapted from the proof by Anon; see his/her comment). We have $$\det (A)^m=\det (A^m)=\det(J-I)=(-1)^{n-1}(n-1)$$ and therefore $n=|\det(A)|^m+1$.
Proof 2 (adapted from Theorem 1 of C. W. H. Lam, J. H. van Lint, Directed Graphs with Unique Paths of Fixed Length, Journal of Combinatorial Theory B, vol. 24, No. 3, 1978; thanks to @darij_grinberg for the information): $A^m=J−I$ implies that $AJ−A=A^{m+1}=JA−A$. Hence $AJ=JA$, i.e. all row sums and column sums of $A$ are equal to some natural integer $c$. Thus $AJ=JA=cJ$ and in turn $A^mJ=c^mJ$. But by property of $A$, we also have $A^mJ=(J−I)J=(n−1)J$. Therefore $c^m=n−1$.
Proof 3: As $2 = 1^m+1$, we may assume that $n\ge3$. Since $A$ is an entrywise nonnegative, by Perron-Frobenius theorem, the spectral radius $\rho(A)$ of $A$ is a maximal eigenvalue of $A$. Hence $\rho(A)^m$ a maximal eigenvalue of $A^m$. But when $n\ge3$, the maximal eigenvalue of $A^m=J-I$ is unique, namely $n-1$. Hence $\rho(A)^m=n-1$, or $n=\rho(A)^m+1$. Finally, as the eigenvalues of $A^m=J-I$ are $n-1$ (simple eigenvalue) and $-1$ (with multiplicity $n-1$), the eigenvalues of $A$ are $\rho(A)=(n-1)^{1/m}$ and a number of $m$-th roots of $-1$. Hence $\rho(A)=|\det(A)|$ and in turn $\rho(A)$ is an integer.