41
$\begingroup$

Given an $n\times n$-matrix $A$ with integer entries, I would like to decide whether there is some $m\in\mathbb N$ such that $A^m$ is the identity matrix.

I can solve this by regarding $A$ as a complex matrix and computing its Jordan normal form; equivalently, I can compute the eigenvalues and check whether they are roots of $1$ and whether their geometric and algebraic multiplicities coincide.

Are there other ways to solve this problem, perhaps exploiting the fact that $A$ has integer entries? Edit: I am interested in conditions which are easy to verify for families of matrices in a proof.

Edit: Thanks to everyone for this wealth of answers. It will take me some time to read all of them carefully.

$\endgroup$
10
  • 2
    $\begingroup$ Dear Rasmus, I was wondering if you couldn't be more precise about your motivations and the kind of answer you expect. For instance, to which extent is it a numerical computation question? $\endgroup$ Aug 25, 2011 at 10:24
  • $\begingroup$ If the answer to the above is "none at all": How do you check whether the eigenvalues are roots of 1? $\endgroup$
    – user57159
    Aug 25, 2011 at 10:34
  • 4
    $\begingroup$ @Rasmus: what does "easily testable" mean if you aren't interested in computational aspects? $\endgroup$ Aug 25, 2011 at 16:50
  • 1
    $\begingroup$ @Qiaochu: I may have underestimated the broadness of the notion of computational aspects. To give an analogy: A matrix over a field is invertible iff its determinant is non-zero. I would consider this condition easily testable. I admit that I need to compute the determinant for this, though. But I am not interested in how to program a computer to do this for me. $\endgroup$
    – Rasmus
    Aug 25, 2011 at 20:19
  • 1
    $\begingroup$ ... Linear algebra over a ring which is not a field seems much harder than over a field. Can we exploit the fact that $A$ has rational entries? Not really, because two matrices with rational entries are conjugate over $\mathbb Q$ if they are conjugate over $\mathbb C$. (See this question.) So, I'd say the short answer to (3) is: "no". $\endgroup$ Aug 26, 2011 at 14:32

7 Answers 7

15
$\begingroup$

The following conditions on an $n$ by $n$ integer matrix $A$ are equivalent:

(1) $A$ is invertible and of finite order.

(2) The minimal polynomial of $A$ is a product of distinct cyclotomic polynomials.

(3) The elementary divisors of $A$ are cyclotomic polynomials.

$\endgroup$
5
  • 2
    $\begingroup$ I forgot to mention explicitly that the elementary divisors are computed in $\mathbb Q[X]$. I think it's clear enough from the context. [I've already made so many edits that I don't want to make one more just for that. - The elementary divisors are always powers of irreducible elements of the underlying PID. So, the statement in the answer is correct over any field on which it makes sense - the most natural such field being of course $\mathbb Q$.] $\endgroup$ Aug 26, 2011 at 1:50
  • $\begingroup$ I was reading this wikipedia article to find out what an elementary divisor of a rational matrix is. The article seems to say that it is a rational number rather than a polynomial. What am I missing? $\endgroup$
    – Rasmus
    Aug 29, 2011 at 21:05
  • 1
    $\begingroup$ @Rasmus: Let $K$ be a field, $V$ a finite dimensional $K$-vector space and $\phi$ an endomorphism of $V$. We can form the PID $K[X]$ (where $X$ is an indeterminate) and endow $V$ with the $K[X]$-module structure given by $fv:=f(\phi)v$ (with $f\in K[X]$, $v\in V$). [We could also view $V$ as a module over the PID $K$, but this wouldn't take $\phi$ into account.] If $V=K^n$, then $\phi$ can be viewed as a matrix (like your matrix $A$); in this case, the matrix $A$ of the Wikipedia entry is the "characteristic matrix" $X-\phi$... $\endgroup$ Aug 29, 2011 at 21:57
  • $\begingroup$ ... My favorite reference for this is Bourbaki, Algèbre, Chap. 7, but there are others, like Jacobson's Basic Algebra, vol. 1, Birkhoff-Mac Lane, A Survey of Modern Algebra, probably Lang's Algebra. (I wrote this answer and this one.) $\endgroup$ Aug 29, 2011 at 22:00
  • $\begingroup$ Thank you very much for this explanation and also for your interesting comments under the question! $\endgroup$
    – Rasmus
    Aug 29, 2011 at 23:10
10
$\begingroup$

Answer amended in view of Rasmus's comment:

I'm not sure how useful it is, but here's a remark. If $A$ has finite order, clearly $\{\|A^{m}\|: m \in \mathbb{N} \}$ is bounded (any matrix norm you care to choose will do).

On the other hand, if the semisimple part (in its Jordan decomposition as a complex matrix) of $A$ does not have finite order, at least one of its eigenvalues has absolute value greater than $1$, so $\{ \|A^{m}\| :m \in \mathbb{N} \}$ is unbounded.

(I am using the fact that all eigenvalues of $A$ are algebraic integers, and they are closed under algebraic conjugation: it is a very old theorem (and fun to prove) that if all algebraic conjugates of an algebraic integer $\alpha$ are of absolute value $1$, then $\alpha$ is a root of unity).

On the other hand, if the semi-simple part of $A$ has finite order, but $A$ itself does not, then (a conjugate of) some power of $A,$ say $A^h$, (as a complex matrix) has a Jordan block of size greater than $1$ associated to the eigenvalue $1$. Then the entries of the powers of $A^h$ become arbitrarily large, and $\{ \| A^{m} \|: m \in \mathbb{N} \}$ is still unbounded.

$\endgroup$
4
  • $\begingroup$ Could you please define when a matrix has finite order? $\endgroup$
    – Rasmus
    Aug 25, 2011 at 11:49
  • $\begingroup$ To say that a matrix $A$ has finite order means just that $A^{m} = I$ for some positive integer $m.$ Hence my answer says that either some power of $A$ is the identity matrix, or else (some of ) the matrix entries in the powers of $A$ will get arbitrarily large in absolute value as the power increases. $\endgroup$ Aug 25, 2011 at 12:02
  • 2
    $\begingroup$ The matrix $\begin{pmatrix}1&1\\0&1\end{pmatrix}$ has the only eigenvalue $1$ but is not of finite order. Am I missing something? $\endgroup$
    – Rasmus
    Aug 25, 2011 at 20:28
  • $\begingroup$ Dear Geoff, thanks for clarifying. $\endgroup$
    – Rasmus
    Aug 25, 2011 at 21:47
7
$\begingroup$

If $A$ is an $n\times n$ integer matrix, and $A^m=1$, then $\phi(m)\le n$, where $\phi$ is Euler's phi-function (because $\phi(m)$ is the degree of the minimal polynomial for the $m$th roots of unity, and $n$ is the degree of the characteristic polynomial of $A$). Given $n$, there are only finitely many $m$ with $\phi(m)\le n$, and a little elementary number theory lets you find the biggest such $m$. So all you have to do is calculate $A^j$ for all $j$ up to that biggest $m$; if you don't get the identity matrix by then, you never will.

This may take less calculation than finding the eigenvalues, Jordan form, etc.

EDIT: Jyrki notes in the comments that it's not so easy. It still may be salvageable.

FURTHER EDIT: A very nice paper which considers, among other things, the question of the maximal order of an $n\times n$ matrix with integer entries is James Kuzmanovich and Andrey Pavlichenkov, Finite groups of matrices whose entries are integers, The American Mathematical Monthly Vol. 109, No. 2, Feb., 2002, pages 173-186. With regard to Geoff Robinson's comment, "It is larger than Landau's function, but not by much," the authors find that the ratio between the two functions is less than 51 for $n\lt100,000$ (the maximum in that range being 50.978, first achieved at $n=22434$), and they admit to not knowing whether the ratio is unbounded.

$\endgroup$
9
  • 1
    $\begingroup$ A nice idea, but are you sure it works exactly like this? Say, we find a 2x2 matrix of order 3, and a 4x4 matrix of order 5. Putting these together as diagonal blocks we get a 6x6 matrix of order 15. Yet $\phi(15)=8>6$. IOW there need not be any eigenvalues that are primitive roots of order $m$. $\endgroup$ Aug 25, 2011 at 12:59
  • $\begingroup$ @Jyrki, oops. I knew I was forgetting something. Well, it's still true that, given $n$, $m$ is bounded, and I'm sure the bounds are well-studied and readily available. Perhaps someone will find a reference. $\endgroup$ Aug 25, 2011 at 13:17
  • 1
    $\begingroup$ @Jyrki: This is Landau's function, given at oeis.org/A000793 which grows like $\exp(\sqrt{n \log n})$ $\endgroup$ Aug 25, 2011 at 13:26
  • $\begingroup$ @Gerry: Yes, your approach gives a bound on the prime power factors of $m$. If $p^\ell$ divides $m$ then one of the eigenvalues must be of order $p^\ell$, and consequently your argument goes thru, and we get the inequality $\phi(p^\ell)=p^{\ell-1}(p-1)\le n$. Probably a bit more can be said? $\endgroup$ Aug 25, 2011 at 13:29
  • 1
    $\begingroup$ @all above: I think the maximal order of a matrix of finite order in ${\rm GL}(n,\mathbb{Z})$ can be explicitly determined. It is larger than Landau's function, but not by much. First note that the maximum is achieved when the min poly is a product of cyclotomics from powers of different primes. $\endgroup$ Aug 25, 2011 at 15:03
4
$\begingroup$

There are these so-called Pascal matrices. These special matrices are suitable to work with for this problem and also a direct subclass of your solution set.

But notice that if there is a such matrix then there is a property that is related to @Pierre-Yves' answer and that is $A^{m-1}A=A^{m-2}A^2=\ldots = I$ hence the inverse of $A^p$ is $A^{m-p}$. So if there is such $A$ then $A^{-1}$ first it must be integer valued and further it must be some power of $A$ i.e. checking whether $A^{-1}=A^{m-1}$ should be sufficient. And this can be done with a relatively fast computation on any machine.

EDIT 1: As Geoff and Yuval commented below, the matrix inverse and its relatively low order powers already encode a lot of information that can be checked with ease.

EDIT 2: Bah, of course the obvious numerical solution is to check whether $A = A^{m+1}$ which involves only matrix multiplication with a few lines of code in any environment :)

$\endgroup$
7
  • 3
    $\begingroup$ The fact that $A$ and $A^{-1}$ should have the same characteristic polyomial should be fairly easily checkable and computable, even before starting to worry about powers. $\endgroup$ Aug 25, 2011 at 15:29
  • $\begingroup$ @Geoff: Oops, that was stupid of me, thanks :) $\endgroup$
    – user13838
    Aug 25, 2011 at 15:54
  • 1
    $\begingroup$ :no,not at all. $\endgroup$ Aug 25, 2011 at 16:09
  • $\begingroup$ You could use a "meet-in-the-middle" approach to drive the running time down by roughly a square root factor. Instead of trying all possible exponents in sequence, "guess" the order of magnitude of $m$, and look for $A^x = A^{-y}$ where $x,y$ are both taken from domains whose sizes are the square root of the original order of magnitude. Instead of "guessing", you can enumerate (this only affects the running time by a constant). $\endgroup$ Aug 25, 2011 at 17:15
  • 1
    $\begingroup$ Regarding EDIT 2, how is the equation $A=A^{m+1}$ any better than $A^m=1$? $\endgroup$
    – Rasmus
    Aug 25, 2011 at 20:36
4
$\begingroup$

we have the classification of such matrix in general case,

here is the paper:

Reginald Koo, A Classification of Matrices of Finite Order over $\mathbb{C, R}$ and $\mathbb{Q}$, Mathematics Magazine, Vol. $76$, No. $2$ (Apr., $2003$), pp. $143-148$.

$\endgroup$
3
  • $\begingroup$ HINT - don't answer thusly. $\endgroup$ Nov 7, 2011 at 3:49
  • $\begingroup$ Dear Jay, thank you for the reference. Could you please expand your answer a little? In particular, could you formulate the classification theorem in the paper you mention? $\endgroup$
    – Rasmus
    Nov 7, 2011 at 9:27
  • 1
    $\begingroup$ @Rasmus: Here's a link to the paper. It looks nice and useful, but it seems that some work is needed to extract something on matrices with integer entries. $\endgroup$
    – t.b.
    Nov 7, 2011 at 12:33
2
$\begingroup$

Depending on your actual situation you might want to use crude necessary criteria to weed out candidates.

For example, the trace of the matrix is the sum of $n$ roots of unity and cannot have large absolute value.

The same criteria can be repeatedly checked while computing powers.

$\endgroup$
0
$\begingroup$

If we were to know that $A$ is normal, then we could use spectral calculus to conclude from $A^m=1$ that the norm fulfills $||A||=1$. But since $A$ has only integer entries, we know that the rows $Ae_i$ must be unit vectors, otherwise the norm of the matrix would be equal or larger than $\sqrt{2}$. After all,

$$||Ae_i|| = ||\sum_j a_{ij} e_j|| = \sqrt{\sum_j a_{ij}^2} \geq \sqrt{2} \quad \text{ if more than one } a_{ij} \geq 1 .$$

This means that $A$ must be a permutation matrix.

I don't know what happens when the matrix is not normal, i.e. when it does not commute with its transpose.

$\endgroup$
2
  • 2
    $\begingroup$ Please check your argument. The matrix $$A=\left(\begin{array}{rr}0&1\\-1&-1\end{array}\right)$$ satisfies the equation $A^3=1$ and its Jordan form has no off-diagonal entries. I think that your mistake is in that the matrix norm is only invariant up to unitary equivalence - not up to a more general similarity transformation. $\endgroup$ Aug 25, 2011 at 17:22
  • $\begingroup$ @Jyrki Lahtonen: Oops, indeed, thanks. Having a diagonal Jordan form doesn't mean that the matrix is normal. $\endgroup$ Aug 26, 2011 at 7:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .