The smallest power of a matrix which equals the identity 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$. 
 A: 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$. 
A: 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.
