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.

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.

Thanks in advance.

share|improve this question
5  
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
2  
@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
2  
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
1  
@darijgrinberg aww, I just myself took the square-root $J-I$ and saw that it was imaginary :) –  Anon Jan 29 '13 at 21:05

1 Answer 1

up vote 3 down vote accepted

(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.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.