Finite fast tests for periodicity of certain matrices

Question

Let $M=- U^{-1} U^T$ be an $n times n$-integer matrix, where $U$ is an upper triangular 0-1-matrix where all diagonal entries are equal to one. $M$ is called periodic if $M^r=id$ for some $r geq 1$.
The question is about whether there is a fast finite test to check whether a matrix is periodic, so that one just has to look for "small" $r$. See Distributive lattices with periodic Coxeter matrix for a motivation.

Question 1: Given $n$, is there a good bound for the minimal number $a(n)$ such that if $M^r neq id$ for all $r=1,...,a(n)$, then $M$ is not periodic?

Question 2: Given $n$, is there a good bound for the minimal number $b(n)$ such that if $M$ has an entry of absolute value at least $b(n)$, then $M$ is not periodic?

Of course one might ask those questions also for integer matrices $M$ with more general properties. (there it does not work for question 2 as Gerry Myerson showed)

Gerry Myerson · Answer

For general integer matrices $M$, there is no $b(n)$. E.g., for $n=2$, if $a(a+1)+1=bc$, and $$M=pmatrix{a&-bcr c&-a-1cr}$$ then $M^3$ is the identity matrix.
EDIT: for general matrices, Theorem 2.7 of James Kuzmanovich and Andrey Pavlichenkov, Finite groups of matrices whose entries are integers, The American Mathematical Monthly Vol. 109, No. 2 (Feb., 2002), pp. 173-186 shows there's a bound on $a(n)$ in terms of $n$. Let $m=p_1^{e_1}p_2^{e_2}cdots p_t^{e_t}$ with $p_1<p_2<cdots<p_t$. Then there is an $ntimes n$ integer matrix with order $m$ if and only if

$sum_{i=1}^t(p_i-1)p_i^{e_i-1}-1le n$ for $p_1^{e_1}=2$, or

$sum_{i=1}^t(p_i-1)p_i^{e_i-1}le n$ otherwise.

Finite fast tests for periodicity of certain matrices

One Answer

Add your own answers!

Ask a Question