Command Line

zor Options [-q] [-m MaxOrder] Input

Options: Standard options, see Standard Command Line Options

-q: Quick mode (see description).

-m MaxOrder: Set upper limit for the oder of cyclic subspaces (see description).

Input: Input file.

Input Files

Input: Matrix or permutation.

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.

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) Chose 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.