zor man page
zor — calculate the order of a matrix or permutation
Synopsis
zor [Options] <File>
Description
This program reads a file, containing either permutations, or a square matrix, and calculates the order(s) and prints the message:
ORDER IS xxxx
There are two options to reduce the run time of the program. Using the -m option you can specify a maximal expected order. If, during the algorithm described below, the order reaches this limit, the program will stop and print an appropriate message. The second option, -q, makes zor stop if the dimension of W (see below) reaches 1/10 of the dimension of the whole space. In this case, the message is
ORDER IS A MULTIPLE OF NNN
Note: The -q and -m options have no effect for permutations.
Options
- -Q
Quiet, no messages.
- -V
Verbose, more messages.
- -T <MaxTime>
Set CPU time limit
- -m <MaxOrder>
Set an upper limit for the order of cyclic subspaces.
- -q
Quick mode: find a lower bound for the order.
- -G
Produce output in GAP format.
Implementation Details
If the input is a matrix, the order is found by calculating the orders on cyclic subspaces and taking the least common multiple. The algorithm works as follows:
- Let A be the given matrix and V the space A acts upon. Set W:={0} (the trivial subspace) and o:=1.
- (NEXT) Choose a vector v not in W. Calculate the cyclic subspace C generated by v and the order o' of A on C.
- Set o:=lcm(o,o')
- W:=W + C. If W=V, o is the order of A and the program terminates. Otherwise, continue with (NEXT).
Gaussian elimination is used to maintain a basis of W in echelon form. In order to avoid infinite loops, there is a limit on o'. If the vector does not return after 1000 multiplications the order is assumed to be infinite and the program stops with an error message. This happens also if the value of o exceeds 100000.
If the input file contains permutations, each one is read in and its order is calculated as the least common multiple of the orbit sizes. The result is printed in the format
ELEMENT nn HAS ORDER nnn
The whole matrix plus a second matrix of the same size must fit into memory. In the case of permutations, there must be enough memory for one permutation.