1chop(1)                          User Commands                         chop(1)
2
3
4

NAME

6       chop - find irreducible constituents of a matrix
7

SYNOPSIS

9       chop [OPTIONS] <Name>
10

DESCRIPTION

12       This  program calculates the irreducible constituents of a given matrix
13       representation.  The representing matrices of the generators  are  read
14       from  input  files, see "INPUT FILES" below.  Unless a different number
15       of generators has been specified with -g, two generators are  expected.
16       However,  if  the  -i  option is used, and the file Name.cfinfo exists,
17       chop takes the number of generators from this file and ignores  the  -g
18       option.
19
20       For each composition factor chop writes the action of the generators to
21       CFName.1, CFName.2, ....  CFName is the name of the composition factor,
22       which  is  constructed  by  appending the dimension and a letter to the
23       module name.  For example, "X10a.1" is the action of the first  genera‐
24       tor  on  the  first composition factor of dimension 10 of the module X.
25       If a second, inequivalent composition factor of dimension 10 was found,
26       it  would  be  named  "X10b"  and  so  on.   Chop also creates the file
27       Name.cfinfo containing a list of all composition factors.  This file is
28       used by subsequent programs such as pwkond(1).
29

OPTIONS

31       -Q     Quiet, no messages.
32
33       -V     Verbose, more messages.
34
35       -T <MaxTime>
36              Set CPU time limit
37
38       -G, --gap
39              Produce output in GAP format.  This option implies -Q.
40
41       -g <NGen>
42              Set the number of generators.  Default: 2.
43
44       -s <Word>
45              Start with word number Word.  Default: 1.
46
47       -n <MaxNul>
48              Set limit on nullity.  Default: 3.
49
50       -d <MaxDeg>
51              Set limit on degrees of polynomials.  Default: 5.
52
53       -i, --read-cfinfo
54              Read Name.cfinfo, if it exists
55

IMPLEMENTATION DETAILS

57       Chop  repeatedly  splits  a module into submodule and quotient until it
58       arrives at the irreducible constituents.  Thus, it finds a  composition
59       series.   The  program  assumes that the algebra generated by the input
60       matrices contains the unit matrix.
61
62       In order to split a given module or to  prove  its  irreducibility  the
63       algorithm  needs  an  element of the algebra with a nontrivial but low-
64       dimensional kernel.  Such elements are searched by taking linear combi‐
65       nations  of  certain products of the generators ("words").  By default,
66       chop tries all words in the order defined by the word  generator.   The
67       -s option may be used to make chop start with a word different from 1.
68
69       For each word A generated in this way, the program calculates its char‐
70       acteristic polynomial and examines the irreducible factors.  If p(x) is
71       an  irreducible factor, p(A) has a nontrivial kernel.  Then, one vector
72       of the kernel is chosen and the smallest submodule containing this vec‐
73       tor  is calculated.  If the vector spans a proper submodule, the action
74       of the generators on this submodule as well as on the quotient are cal‐
75       culated and the same procedure is applied recursively to both submodule
76       and quotient.
77
78       To avoid expensive matrix multiplications in the calculation  of  p(A),
79       there is a limit on the degree of p(x).  This limit can be set with the
80       -d option and defaults to 5.
81
82       If a module cannot be split by the program, it may be irreducible.   In
83       order to prove this, chop uses Norton's criterion.  This requires, how‐
84       ever, to find an algebra element with a small  kernel,  because  up  to
85       scalar  multiples  each  vector  in  the kernel must be examined to see
86       whether it spins up to the whole module.  For this  reason  a  "nullity
87       threshold" m is maintained by the program.  Initially, m is set to 3 or
88       to the value given in the -n option.  Each algebra element that  has  a
89       nullity less then or equal to m is used for the Norton test.
90
91       In  some  cases the algorithm described is not able to split the module
92       although it is reducible.  These exceptional cases are treated with  an
93       alternative strategy described in Lux and Ivanyos, "Treating the excep‐
94       tional cases of the Meataxe", 19 Feb 1998 (unpublished).
95
96       Algebra elements with trivial kernel are useless for the algorithm,  so
97       an  attempt  is made to avoid unnecessary computation of such elements.
98       Once an element is known to have a trivial kernel on a given module  M,
99       the  program  will  mark  it  as  invertible and ignore it for all con‐
100       stituents of M.
101
102       If a constituent is irreducible but  not  absolutely  irreducible,  the
103       nullity  of  any  element  in  the algebra will be a multiple of [E:F],
104       where F is the ground field and E the splitting field.  This  situation
105       is  recognized by calculating the greatest common divisor d of all nul‐
106       lities which occur during the search.   In  order  to  prove  that  the
107       splitting  field  degree  is  equal to d, the following method is used:
108       Take a word with nullity d and two vectors v1, v2  in  its  null-space.
109       Use  these  vectors  as  seeds  for a standard basis algorithm.  If the
110       resulting representations are different, [E:F] is less than d, and  the
111       word  is  discarded.   Otherwise,  the  linear map which transforms one
112       standard basis into the other is an endomorphism e of the  module.   If
113       v1,  under  the  action  of  e,  spins up to the whole null space, then
114       [E:F]=d.  Otherwise, take a third vector not in the span and repeat the
115       procedure  above.   Again, this yields an endomorphism, or it turns out
116       that [E:F]<d.  These steps are repeated until a word with nullity [E:F]
117       is found.
118

INPUT FILES

120       Name.{1,2,...}
121              Generators.
122

OUTPUT FILES

124       Name.cfinfo
125              Constituent info file
126
127       CFName.{1,2,...}
128              Generators on the constituents.
129

SEE ALSO

131       cfcomp(1), pseudochop(q), pwkond(1)
132
133
134
135MeatAxe                             2.4.24                             chop(1)
Impressum