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.

This query is inspired by this previous question.

Suppose $A$ is an $n \times n$ matrix whose entries are integers between $-s$ and $s$. Suppose further that $A^k=I$ and moreover $k$ is the smallest positive integer with this property. What sort of bounds can be derived on $k$ in terms of $n$ and $s$?

A related question is considered in the discussion to this answer. The question I am asking is slightly different because I am restricting the integers to lie between $-s$ and $s$.

share|improve this question
    
There are matrices, e.g. $$A=\begin{pmatrix} 0 & \cdots & 0\\ \vdots & \ddots & \vdots \\ 0 & \cdots & 0\end{pmatrix}$$ for which there is no such $k$. A slightly less trivial example you get when $s>0$ and $n>1$ is $$A=\begin{pmatrix} 1 & 1 & 0 & \cdots & 0\\ 1 & 0 & 0 & \cdots & 0\\ 0 & 0 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \cdots & 0\end{pmatrix}$$ –  Zev Chonoles Aug 26 '11 at 3:59
1  
Zev, the question assumed that there exists an integer $k$ with the property $A^k=I$. I don't understand your "slightly less trivial" example; the matrix has no powers which equals the identity, since it maps $e_n$ to zero. –  robinson Aug 26 '11 at 4:53
    
Anyway, the circular shift matrix $A$ satisfies $A^{n-1}=I$ and no smaller power works, so $k$ can be at least that large. I suspect that may be the point you were trying to make. –  robinson Aug 26 '11 at 4:54
    
Indeed, I meant a "slightly less trivial example of a matrix with no power equal to the identity". I didn't have any particular point, just thought I'd make the observation - I'm afraid I didn't have anything nearly as useful to say as "$k$ can be at least as large as $n-1$" :) –  Zev Chonoles Aug 26 '11 at 5:18

2 Answers 2

up vote 1 down vote accepted

I'm not sure the restriction on the entries makes much difference. If $p$ is prime, the polynomial for roots of unity of order $p^r$ has coefficients in $\lbrace\,-1,0,1\,\rbrace$, so the companion matrix for this polynomial has entries from that same set; then a block matrix built from such companion matrices for various primes will have order the product of the prime powers and entries integers between $-1$ and $1$.

share|improve this answer

Let $m(x)$ be the minimal polynomial of $A$, and let $\Phi_k(x)$ be the $k$th cyclotomic polynomial (the minimal polynomial in $\mathbb Z[x]$ for a primitive $k$th root of unity). We know that $\Phi_k(x)$ has degree $\phi(k)$. Since $A$ has integer entries, $m(x)$ has integer coefficients. Since $k$ is minimal, this implies that $\Phi_k(x)$ divides $m(x)$. Since $m(x)$ has degree at most $n$, we conclude $\phi(k) \le n$.

This gives a bound on $k$ depending on $n$ only. For example, using the bound $\phi(k) \ge \sqrt{k}$ (valid for $k>6$), we conclude $k \le \max(6, n^2)$. Using better lower bounds on $\phi(k)$, we can improve the bound.

EDIT: This doesn't quite work if $k$ is composite. See comments below.

share|improve this answer
    
I don't know if it is that easy. In fact, Gerry Myerson tried to use the same argument in this question to conclude $\phi(k)\leq n$; but see the discussion that followed. –  Arturo Magidin Aug 26 '11 at 4:54
    
Oops, I guess that was too easy. I was trying to generalize the argument for $n=2$ where I knew 6 was the biggest possible value. Still, as Gerry Myerson mentions in that discussion, given a fixed $n$, there are only finitely many possible $k$. –  Ted Aug 26 '11 at 5:16

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.