Orders of Invertible Matrices

The functions defined here apply to invertible square matrices. Magma can efficiently compute the order of an invertible matrix over a finite field, using the Cunningham database to factorize the numbers of the form pⁿ - 1 which arise. The algorithm employed is that described in [CLG97].

Magma also contains efficient algorithms for rigorously proving whether a matrix over the ring of integers Z, the rational field Q, an algebraic number field, a cyclotomic field or a quadratic field has finite order or not, and for determining the order if it is finite.

HasFiniteOrder(A) : Mtrx -> BoolElt

Given a square invertible matrix A over a ring R, return true iff A has finite order, i.e., iff there exists a positive integer n such that Aⁿ=1. The coefficient ring R is currently restricted to being either a finite field, the ring of integers Z, the rational field Q, an algebraic number field, a cyclotomic field or a quadratic field. For matrices over any of these rings, the function rigorously proves its result (over other rings, an error results).

Order(A) : AlgMatElt -> RngIntElt

    Proof: BoolElt                      Default: true

Given a square invertible matrix A over any commutative ring, return the order of A. If R is a ring for which a finite order proof exists (see HasFiniteOrder above), then an error results if A has infinite order. Over other rings, if A has infinite order then the function may loop indefinitely since it may not be able to prove the infinitude of the order.

FactoredOrder(A) : AlgMatElt -> [ <RngIntElt, RngIntElt> ]

    Proof: BoolElt                      Default: true

Given a square invertible matrix A over a finite field, return the order of A in factored form. This returns the same value as Factorization(Order(A)), but since the order computation must compute the factorization of the order anyway, it involves no more effort to have it return the factorization. The conditions on the ring are as for Order.

ProjectiveOrder(A) : AlgMatElt -> RngIntElt, RngElt

    Proof: BoolElt                      Default: true

Given a square invertible matrix A over a finite field K, return the projective order n of A and a scalar s∈K such that Aⁿ = sI. The projective order of A is the smallest n such that Aⁿ is a scalar matrix (not just the identity matrix), and it always divides the true order of A. The parameter Proof is as for Order.

FactoredProjectiveOrder(A) : AlgMatElt -> [ <RngIntElt, RngIntElt> ], RngElt

    Proof: BoolElt                      Default: true

Given a square invertible matrix A over a finite field K, return the projective order n of A in factored form and a scalar s∈K such that Aⁿ = sI. The parameter Proof is as for FactoredOrder.