|
SharedMeatAxe
1.0
|
chop [Options] [-Gi] [-g NGen] [-s Word] [-n MaxNul] [-d MaxDeg] Name
This program calculates the irreducible constituents of a given matrix representation. The representing matrices of the generators are read from input files, see "input Files" above. Unless a different number of generators has been specified with -g, two generators are expected. However, if the "-i" option is used, and the file Name.cfinfo exists, chop takes the number of generators from this file and ignores the "-g" option.
For each composition factor chop writes the action of the generators to CFName.1, CFName.2, ... CFName is the name of the composition factor, which is constructed by appending the dimension and a letter to the module name. For example, "X10a.1" is the action of the first generator on the first composition factor of dimension 10 of the module X. If a second, inequivalent composition factor of dimension 10 was found, it would be named `X10b' and so on. chop also creates the file Name.cfinfo' containing a list of all composition factors. This file is used by subsequent programs such as pwkond.
chop repeatedly splits a module into submodule and quotient until it arrives at the irreducible constituents. Thus, it finds a composition series. The program assumes that the algebra generated by the input matrices contains the unit matrix.
In order to split a given module or to prove its irreducibility the algorithm needs an element of the algebra with a non-trivial but low-dimensional kernel. Such elements are searched by taking linear combinations of certain products of the generators ("words"). See the description of the zmw program for more details on the word generator. By default, chop tries all words in the order defined by the word generator. The "-s" option may be used to make chop start with a word different from 1.
For each word A generated in this way, the program calculates its characteristic polynomial and examines the irreducible factors. If p(x) is an irreducible factor, p(A) has a non-trivial kernel. Then, one vector of the kernel is chosen and the smallest submodule containing this vector is calculated. If the vector spans a proper submodule, the action of the generators on this submodule as well as on the quotient are calculated and the same procedure is applied recursively to both submodule and quotient.
To avoid expensive matrix multiplications in the calculation of p(A), there is a limit on the degree of p(x). This limit can be set with the "-d" option and defaults to 5.
If a module cannot be split by the program, it may be irreducible. In order to prove this, chop uses Norton's criterion. This requires, however, to find an algebra element with a small kernel, because up to scalar multiples each vector in the kernel must be examined to see whether it spins up to the whole module. For this reason a "nullity threshold" m is maintained by the program. Initially, m is set to 3 or to the value given in the "-n" option. Each algebra element that has a nullity less then or equal to m is used for the Norton test.
In some cases the algorithm described is not able to split the module although it is reducible. These exceptional cases are treated with an alternative strategy described in [LI98].
Algebra elements with trivial kernel are useless for the algorithm, so an attempt is made to avoid unnecessary computation of such elements. Once an element is known to have a trivial kernel on a given module M, the program will mark it as invertible and ignore it for all constituents of M.
If a constituent is irreducible but not absolutely irreducible, the nullity of any element in the algebra will be a multiple of [E:F], where F is the ground field and E the splitting field. This situation is recognized by calculating the greatest common divisor d of all nullities which occur during the search. In order to prove that the splitting field degree is equal to d, the following method is used: Take a word with nullity d and two vectors v1, v2 in its null-space. Use these vectors as seeds for a standard basis algorithm. If the resulting representations are different, [E:F] is less than d, and the word is discarded. Otherwise, the linear map which transforms one standard basis into the other is an endomorphism e of the module. If v1, under the action of e, spins up to the whole null space, then [E:F]=d. Otherwise, take a third vector not in the span and repeat the procedure above. Again, this yields an endomorphism, or it turns out that [E:F]<d. These steps are repeated until a word with nullity [E:F] is found.