Finite fast tests for periodicity of certain matrices

MathOverflow Asked on January 12, 2021

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)

One 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

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

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

Answered by Gerry Myerson on January 12, 2021

Add your own answers!

Related Questions

Open problems in matroid theory

2  Asked on January 6, 2021 by logictheorist


Discrete logarithm for polynomials

1  Asked on January 4, 2021 by adam-p-goucher


Does the lemma remain valid in b-metric space?

0  Asked on January 4, 2021 by seddik-merdaci


A determinant identity

1  Asked on January 4, 2021 by vassilis-papanicolaou


Anti-concentration of Gaussian quadratic form

3  Asked on January 1, 2021 by mitch


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir