%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % This file is part of the C Meat-Axe. % % Written by Michael Ringe % % (C) Copyright 1992: Lehrstuhl D fuer Mathematik % % RWTH Aachen % % Aachen, Germany % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \chapter{Programs} \label{chap:progs} %================= \def\myparagraph#1{\subsubsection*{\sc #1}} \def\Syntax{\myparagraph{Usage}} \def\Description{\myparagraph{Description}} \def\Examples{\myparagraph{Examples}} \def\Bugs{\myparagraph{Bugs}} \def\Limits{\myparagraph{Limits}} \def\Messages{\myparagraph{Messages}} \def\SeeAlso{\myparagraph{See Also}} \def\Typeout#1{} %\def\Typeout#1{\typeout{#1}} \section{General Features} %========================= The following options are used throughout the whole {\MeatAxe} system. Not every program supports all of these options, but the meaning is always the same. \begin{list}{}{\leftmargin 1cm\labelwidth 5mm\labelsep 2mm} \item[{\tt -help}\hfill] Print a help screen. \item[{\tt -g}\hfill] Set the number of generators. This option must be followed by a positive integer. \item[{\tt -G}\hfill] Generate output in GAP format. \item[{\tt -Q}\hfill] Quiet, do not print any message except errors and results. \item[{\tt -V}\hfill] Verbose, print more messages. Repeat this option (e.g., {\tt -VVV}) to see more detailed information. \item[{\tt -T}\hfill] Time limit. This option must be followed by a positive integer specifying the maximal CPU time which may be used. \end{list} \section{Utility Programs} %========================= \subsection{MAKETAB and BIGMKTAB} \label{sec:maketab}\Typeout{MAKETAB} %---- ---------------------------- \Syntax \msg{maketab {\it fieldorder}\\bigmktab {\it fieldorder}} \Description These programs generate lookup tables for fast field arithmetic. Tables are stored in a file (one file for each field) which is loaded by the ZZZ module at run-time. {\it fieldorder} must be a positive integer (a prime power, actually) less than or equal to 256 for MAKETAB, or 65536 for BIGMKTAB. MAKETAB creates tables for the small field version, up to GF(256). The output file is named {\tt pXXX.zzz}, where XXX is the field order. The size of this file is approximately 130 KBytes and does not depend on the field order. BIGMKTAB creates tables for the large field version. The output file is named {\tt pXXXXX.zzz}, where XXXXX is the field order. This file is usually (i.e., for comparable field orders) much smaller than the `zzz' file, but its size increases linearly with $q$. The table file is needed whenever a program performs finite field operations, i.e., when working with matrices. The programs look for the table file first in the current directory and then, if it is not there, in the library directory (see section \ref{sec:libdir}). Thus, table files for the most commonly used fields can be kept in the library, and additional table files can be created in the current directory when they are needed. Usually, the name of the library directory is defined at compile-time, but this may be changed at any time by defining the environment variable {\tt MTXLIB}. \subsection{CONV: Convert Binary Files}\Typeout{CONV} %----------------------------------- \Syntax \msg{conv {\it File} \ldots} \Description This program is used to convert {\MeatAxe} (binary) data files which have been created on a different machine or with an old version of the {\MeatAxe}. {\it File}\ldots\ is a list of files to be converted. Binary data files are in general not compatible between different machines because they depend on the machines word size and on the way integers are stored (`little-endian' or `big-endian'). Data files from previous releases of the {\MeatAxe} may also be unreadable because the file format has changed.\footnote{For a description of data and file formats see section \ref{sec:intdata}}. This program provides a way to exchange data files in such cases without having to convert to text format using ZPR/ZCV. The input may be any file. CONV will detect automatically if an input file is a {\MeatAxe} data file, perform the necessary operations, and replace the input file with the converted file. Non-{\MeatAxe} files remain unchanged. For each input file a message is printed giving the file name and a short descriptin of what was done to the file. \Bugs CONV cannot convert for a different `target machine'. There is no backup of the original file. \section{File Conversion and Manipulation} %========================================= \subsection{ZCF: Change Format}\label{sec:zcf} %----------------------------- \Typeout{ZCF} \Syntax \msg{zcf {\it NewField} [{\it Input} {\it Result}]} \Description This program converts between various data types. Currently there are two kinds of conversions available: \begin{enumerate} \item If {\it Input} is a matrix, the field is changed to {\it NewField}. The result is a matrix of the same size over GF({\it NewField}). \item If {\it Input} is a permutation of degree $n$, it is converted into the corresponding ($n\times n$) permutation matrix over GF({\it NewField}). \end{enumerate} The result is written to {\it Result}. Default file names are G1 for input and P2 for output. If {\it Input} is a matrix it can be restricted to a subfield or embedded into a larger field. In the first case, of course, the entries must already be in the subfield. The conversion is done in two steps. First, all entries of the matrix are converted to integers. Then, they are mapped to the new field and reassembled into rows. The result is written out row by row. At the end the user is informed with a message \msg{EMBEDED INTO GF({\it NewField})} or \msg{RESTRICTED TO GF({\it NewField})} In case of permutations the output matrix is generated row by row by inserting ones at the positions specified by the permutation. At the end a message saying \msg{CONVERTED TO GF({\it newfield})} is printed. \Limits If the input is a matrix, the whole matrix must fit into memory. Additionally, the program needs $n\cdot m\cdot s$ bytes of memory, where $m$ and $n$ are the dimensions of the input matrix and $s=1$ for the small arithmetic version and $s=2$ for the big version. In case of permutations, the input permutation and one row of the output file must fit into memory. \subsection{ZCV: Convert a Matrix or Permutation}\label{sec:zcv} %--------------------------------------------- \Typeout{ZCV} \Syntax \msg{zcv [$\left\{\mbox{\begin{tabular}{@{}c@{}}{\it Textfile}\\=\end{tabular}}\right\}$[{\it BinFile}]]} \Description This program reads a text file, and outputs a matrix or permutation in internal format depending on the input to {\it BinFile} (default: P2). If the input file name is '=', input is read from stdin. If no arguments are given, T1 is used as input file and output goes to P2. Here are some examples: \begin{center} \begin{tabular}{|l|l|} \hline Command & Conversion \\ \hline \tt zcv & T1 $\rightarrow$ P2 \\ \tt zcv txt & Txt $\rightarrow$ P2 \\ \tt zcv txt z1 & Txt $\rightarrow$ z1 \\ \tt zcv = z1 & standard input $\rightarrow$ z1 \\ \hline \end{tabular} \end{center} To convert text from a file called `{\tt =}' you must use input redirection: \msg{zcv = binfile < =} \paragraph{Text file format} %- - - - - - - - - - - - - - The first row of the input file is a header consisting of 4 integers, namely the mode ({\tt MM}), the field parameter ({\tt FFFFFF}), the number of rows ({\tt RRRRRR}) and the number of columns ({\tt CCCCCC}). They can be in fixed format, \msg{MMFFFFFFRRRRRRCCCCCC} or in free format with at least one separating between the numbers. For example, the following headers are equivalent \begin{verbatim} 0100002000024000024 1 2 24 24 1 2 24 24 \end{verbatim} The exact meaning of the 4 integers depends on the value of the `mode', as does the format of the rest of the file. \begin{center} \small \begin{tabular}{|c|c|c|c|p{0.32\linewidth}|} \hline Mode &\tt FFFFFF &\tt RRRRRR&\tt CCCCCC & Rest of file \\ \hline 1 & field size & rows & columns & 80I1 -- a matrix \\ 2 & " & " & " & A permutation (to be converted to matrix form)\\ 5 & " & " & " & An integer matrix (to be reduced mod $p$) \\ 6 & " & " & " & A matrix \\ 12 & 1 & no.\ of points & no.\ of perms.& One or more permutations\\ \hline \end{tabular} \end{center} In mode 1 the input format is fixed. There must be at most 80 characters per line, lines must be filled as much as possible, and each row of the matrix starts with a new input line. There are no blanks allowed to separate numbers. This format can be used for fields up to GF(9). In all other modes, the input consists of a sequence of integers in free format, separated by any combination of blanks, tabs, or newlines. Empty lines and any characters following a `\#' are ignored, even in mode 1. Here are some examples: \begin{center} \begin{tabular}{@{}|l|l|@{}} \hline \multicolumn{1}{|c|}{Input} & \multicolumn{1}{c|}{Result} \\ \hline \begin{tabular}{@{}l@{}} \verb:01000005000005000003:\\ \verb:114:\\ \verb:210:\\ \verb:011:\\ \verb:131:\\ \verb:411:\\ \end{tabular} & Matrix over GF(5): $\left(\begin{array}{ccc}1&1&4\\2&1&0\\0&1&1\\1&3&1\\4&1&1\end{array} \right)$ \\ \hline \begin{tabular}{@{}l@{}} \verb:02000005000003000006:\\ \verb: 4:\\ \verb: 6:\\ \verb: 1:\\ \end{tabular} & Matrix over GF(5): $\left(\begin{array}{cccccc} 0&0&0&1&0&0\\0&0&0&0&0&1\\1&0&0&0&0&0 \end{array}\right)$ \\ \hline \begin{tabular}{l} \verb:12 1 3 2:\\ \verb: 1 3 2:\\ \verb: 2 3 1:\\ \end{tabular} & 2 Permutations: (23) and (123) \\ \hline \begin{tabular}{@{}l@{}} \verb: 5 7 3 3:\\ \verb: 4 -1 0:\\ \verb: 6 2 -1:\\ \verb: 1 1 9:\\ \end{tabular} & Matrix over GF(7): $\left(\begin{array}{ccc} 4&6&0\\6&2&6\\1&1&2 \end{array}\right)$ \\ \hline \end{tabular} \end{center} Another use of this program is, together with ZPR, to convert between various types of object. See the documentation of ZPR for examples. \subsection{ZPR: Print a Matrix or Permutation}\label{sec:zpr} %------------------------------------------- \Typeout{ZPR} \Syntax \msg{zpr [-Gs] [-r {\em Range}] [{\it Datafile} [{\it Textfile}]]} \Description This program reads a matrix or permutation(s) from {\it Datafile} (G1 by default), and outputs the object(s) therein to {\it Textfile} in a format suitable for reading by a human, or by the ZCV program. If {\it Datafile} but no {\em Textfile} is specified, output is written to the standard output by default. However, if ZPR is invoked without any arguments input is read from G1 and output is written to T1. This is for compatibility with the FORTRAN {\MeatAxe}. There are several options to change the output format: \begin{list}{}{} \item[\tt-G] GAP output. \item[\tt-s] Print only a summary (file header fields). \item[\tt-r] Select an output range i.e., a range of rows within a matrix or a range of permutations if the input file is a list of permutations. By default ZPR prints all rows of a matrix or all permutations in a file, respectively. {\it Range} may be a single number or an interval in the form {\it First}{\tt-}{\it Last} as in the following examples: \begin{list}{}{} \item\begin{tabular}{|l|l|l|} \hline Option&\multicolumn{2}{c|}{Meaning for}\\ & Matrices & Permutations \\ \hline \tt -r5& Row 5 & 5th Permutation \\ \hline \tt -r5-10&Rows 5--10 & 5th -- 10th Permutation\\ \hline \end{tabular}\end{list} \end{list} If neither {\tt-c} nor {\tt-G} is specified, ZPR uses the standard output format described below. The program starts by inspecting the input file to see what sort of thing it is, and a suitable output format is chosen as described in the table below. The next step is to write out a `header' record. This has 4 integers in it. The first integer (2 digits) describes which format is in use. The other 3 (6 digits each) describe the object. For a matrix, they are field size, number of rows, number of columns. For a permutation they are `1', number of points, and number of permutations. \begin{center} \begin{tabular}{|l|c|c|c|c|} \hline Description of object &mode& FL & NOR & NOC \\ \hline Matrix over $GF(q),q<10$ &01& field &no.\ of rows&no.\ of columns\\ Matrix, 10$<$q$<$100 &03& field &no.\ of rows&no.\ columns\\ Matrix, 100$<$q$<10^6$ &04& field &no.\ of rows&no.\ of columns\\ Permutation &12& 1 &no.\ points&no.\ of permutations\\ \hline \end{tabular} \end{center} This format exactly matches the input format of the ZCV program. Hence these programs can be used freely to convert between internal and readable formats, and it is recommended that archive material be kept in the readable format, since this is more likely to be readable in a few years time. Another use of this pair of programs is, with a little use of an editor, to convert between various types of objects. For example, to convert a permutation to a matrix, use ZPR and then edit the type from 12 to 2. You may also convert between the `small' and `big' arithmetic versions. In order to do this, you need two versions of both ZPR and ZCV, one compiled with the big and one with the small ZZZ module. Let these programs be called {\tt bigzpr}, {\tt smallzpr}, {\tt bigzcv} and {\tt smallzcv}. Then, conversion from small to big version is done with \msg{smallzpr matrix.small | bigzcv - matrix.big} and from big to small version with \msg{bigzpr matrix.big | smallzcv - matrix.small} \SeeAlso ZCV \subsection{ZCT: Cut}\Typeout{ZCT} %-------------------- \Syntax \msg{zct {\it Rows}[:{\it Columns}] [{\it Input} [{\it Result}]]} \Description This program cuts a piece, specified by {\it Rows} and {\it Columns}, out of the file {\it Input}, and writes the piece to {\it Result}. {\it Input} may be a matrix or a set of permutations. If no file names are specified, input is read from G1 and the result goes out to P2. If only {\it Result} is omitted, the output file name is formed by appending "1" to {\it Input}. Both {\it Rows} and {\it Columns} are lists of positive integers or ranges (e.g., `13-25') separated by commas. If {\it Input} is a matrix, the corresponding rows and columns are cut, and the resulting rectangular pieces are combined to one rectangular matrix which is written to {\it Result}. If the {\it Columns} list is omitted, all columns of the selected rows are cut. Here are some examples. Let {\it Input} be the 5 by 10 matrix \begin{center} \begin{tabular}{l} \verb:1 2 3 4 5 6 7 8 9 0:\\ \verb:0 1 2 3 4 5 6 7 8 9:\\ \verb:0 0 1 2 3 4 5 6 7 8:\\ \verb:0 0 0 0 0 0 0 0 0 0:\\ \verb:9 8 7 6 5 4 3 2 1 0: \end{tabular} \end{center} Then, ZCT would produce the output shown below for several {\it Rows}:{\it Columns} lists: \begin{center} \begin{tabular}{|c|c|} \hline {\it Rows}:{\it Columns} & {\it Result} \\ \hline {\tt 1,4-5} & \begin{tabular}{l} \verb:1 2 3 4 5 6 7 8 9 0:\\ \verb:0 0 0 0 0 0 0 0 0 0:\\ \verb:9 8 7 6 5 4 3 2 1 0: \end{tabular} \\ \hline {\tt 1-3:8-10} & \begin{tabular}{l} \verb:8 9 0:\\ \verb:7 8 9:\\ \verb:6 7 8: \end{tabular} \\ \hline {\tt 1-2:2,5-7,9} & \begin{tabular}{l} \verb:2 5 6 7 9:\\ \verb:1 4 5 6 8: \end{tabular} \\ \hline {\tt 1-2,5:1-3,9-10} & \begin{tabular}{l} \verb:1 2 3 9 0:\\ \verb:0 1 2 8 9:\\ \verb:9 8 7 1 0: \end{tabular} \\ \hline \end{tabular} \end{center} The rows and columns which select the piece need not occur in ascending order, but the output depends on the ordering. For example, {\tt zct~1,2} and {\tt zct~2,1} both extract the first two rows of a matrix, but the second form will also permute the rows. Another example: \msg{zct 3-4,1-2:3-4,1-2 inp out} would perform the following operation on a 4 by 4 matrix: \begin{center} \begin{tabular}{cc} {\tt inp} & {\tt out} \\ \begin{tabular}{l} \verb:1 1 2 2:\\ \verb:1 1 2 2:\\ \verb:3 3 4 4:\\ \verb:3 3 4 4: \end{tabular} & \begin{tabular}{l} \verb:4 4 3 3:\\ \verb:4 4 3 3:\\ \verb:2 2 1 1:\\ \verb:2 2 1 1: \end{tabular} \end{tabular} \end{center} With permutations the program works in the same way as with matrices. Each permutation is treated as a row. The {\it Columns} list must be empty in this case, because ZCT can cut only entire permutations. \Limits The number of entries in the {\it Rows} and {\it Columns} list must not be greater than 10. One row (or permutation, respectively) of the input file and the whole result of the cut must fit into memory. \SeeAlso ZPT \subsection{ZPT: Paste}\Typeout{ZPT} %---------------------- \Syntax \msg{zpt [-\Big\{\begin{tabular}{@{}c@{}}r\\ R\end{tabular}\Big\} {\it \#Rows}] [-\Big\{\begin{tabular}{@{}c@{}}c\\ C\end{tabular}\Big\} {\it \#Cols}] {\it Out} {\it Inp}\ldots} \Description This program reads matrices or permutations from {\it Inp}, pastes them together, and writes the result to {\it Out}. The way in which the pieces are pasted together is controlled by two parameters, {\it \#Rows} and {\it \#Cols}. For example, \msg{zpt -r 2 -c 3 x aa ab ac ba bb bc} would paste together 6 matrices ({\tt aa}\ldots{\tt bc}) in two rows and three columns like this: \begin{center} \begin{tabular}{|c|c|c|} \hline {\tt aa} & {\tt ab} & {\tt ac} \\ \hline {\tt ba} & {\tt bb} & {\tt bc} \\ \hline \end{tabular} \end{center} The file name `{\tt -}' is treated specially: No file is read in, and the corresponding piece of the output matrix is left empty. This can be used to calculate the direct sum of two representations. For example, \msg{zpt -r 2 -c 2 A+B A - - B} creates the following matrix in block diagonal form: \begin{center} {\tt A+B}$=$\begin{tabular}{|c|c|} \hline {\tt A} & 0 \\ \hline 0 & {\tt B} \\ \hline \end{tabular} \end{center} If {\tt -R} and {\tt -C} are used instead of {\tt -r} and {\tt -c}, ZPT will take {\it Inp} as `base name'. This means, the actual input file names are formed by appending one or two numbers to the base name. Thus, the following commands are equivalent: \msg{zpt -r 2 -c 2 x x11 x12 x21 x22\\ zpt -r 2 -C 2 x x1 x2\\ zpt -R 2 -C 2 x x} However, \msg{zpt -R 2 -c 2 x x1 x2} is different, because {\tt x1} and {\tt x2} are now interpreted as base names of columns rather than rows. The latter command would paste together the same matrices as before, but with {\tt x12} and {\tt x21} exchanged. With permutations the program works in the same way, but {\it \#Cols} must be equal to 1. That means, permutations can only be concatenated. If only one of {\it \#Rows} and {\it \#Cols} is specified, the other parameter is assumed to be one. If both parameters are omitted, {\it \#Cols} is assumed to be one and {\it \#Rows} is determined by th number of {\it Inp} arguments. This is useful, for example, to concatenate several files with permutations without having to count the number of files: \msg{zpt Out File1 xxs test re233.1 re233.2 z1 z2} or for vectors: \msg{zpt List Vector*} Together with ZMU, ZPT can be used to perform a piecewise multiplication of two matrices (see section \ref{sec:zmu}). \Limits Permutations are read and written one by one, so only one permutation must fit into memory. In the case of matrices, the memory requirement depends on the sizes of the pieces. \Bugs Using {\tt -R} and {\tt -C} simultaneously with arguments greater than 10 will cause trouble because, for example, a file name like {\tt file111} is ambiguous. \SeeAlso ZCT, ZMU \section{Main Programs} %====================== \subsection{ZAD: Add Two Matrices} %--------------------------------- \Syntax \msg{zad [{\em Mat1} {\em Mat2} {\em Result}]} \Description This program reads two matrices from {\em Mat1} and {\em Mat2} (G1 and G2 by default) and outputs their sum to {\em Result} (default: P3). Both input files must be matrices over the same field with equal number of rows and columns. The matrices need not be square. The program reads one row at a time of each matrix, adds them together, and writes out the result. \Limits Two rows must fit into memory. \subsection{ZBL: Bottom Left (Clear Above Main Diagonal)} %------------------------------------------------------- \Syntax \msg{zbl [{\em Matrix} {\em Result}]} \Description This program reads in a matrix, zeroizes all entries above the main diagonal, and writes out the result. If file names are omitted, the matrix is read from G1 and output goes to P2. The input matrix is read row by row, and all entries above the main diagonal are replaced by zero. All entries on or below the main diagonal remain unchanged, and the resulting matrix, row by row, is written out. As an example, the following conversion would take place: \begin{center} \begin{verbatim} G1 P2 12100201201212212122 10000000000000000000 21000000000000001111 21000000000000000000 12212120101201201201 12200000000000000000 01020010020102012012 01020000000000000000 12100012101201012012 12100000000000000000 12120212121012012012 12120200000000000000 \end{verbatim} \end{center} Notice that the input matrix need not be square, and the output matrix has always the same shape and size as the input matrix. The purpose of this program is to enable the {\MeatAxe} to check if an irreducible representation in characteristic 2 fixes a quadratic form. This job is not particularly simple --- in many ways it is just a bodge, but it is possible: \begin{enumerate} \item Put the representation into standard basis using ZSB \item Find the symplectic form fixed by using ZSB to make the matrix that conjugates the representation to its dual. \item Quadratic forms can be represented by lower triangular matrices. Since the representation is in standard basis (so all the basis vectors are images of the first under the group) the diagonal entries of any fixed quadratic form must all be equal, so try each field entry in turn by adding that scalar matrix to the bottom half of the symplectic form. \item For each quadratic form made as in 3, test if it is fixed by forming $G^{tr}QG$ for each generator $G$, and checking that the diagonal is still the same as it was before (the symplectic form should have been checked before starting). The check can be done by adding the form to the result, then doing ZBL, ZTR and ZBL again --- the result will be the zero matrix (use ZNU) iff the form was fixed (given that the symplectic one was). \end{enumerate} \Limits One row of the matrix must fit into memory. \subsection{ZCL: `Clean' a Matrix by a Space}\Typeout{ZCL} %----------------------------------------- \Syntax \msg{zcl [{\it Space} {\it Matrix} {\it CleanedMat} {\it RowOps}]} \Description This program reads in two matrices from {\it Space} and {\it Matrix}, and `cleans' {\it Matrix} with {\it Space}. It puts out two matrices to {\it CleanedMat} and {\it RowOps} such that \[ {\it Matrix} = {\it RowOps}\cdot{\it Space}+{\it CleanedMat} \] and {\it CleanedMat} has as many zero columns as possible. Default file names are G1, G2, P3 and P4. The two input matrices must be over the same field and have the same number of columns. Also, {\it Space} must be in echelon form. The first matrix is read in, and pointers to the significant columns (pivots) are calculated. The second matrix ({\it Matrix}) is then processed a row at a time. Row operations are performed to clear out the pivot points of the input row using the rows of the first input matrix. A row describing what was done is written out to {\it RowOps}, and the remnant (clean) row is output to {\it CleanedMat}. One use of this program is to calculate the action of a generator on an invariant subspace: Take the subspace in echelon form (as it is on output from ZSP), multiply it by a generator. Feed the original echelon form into {\it Space} and the result of the multiplication into {\it Matrix}. {\it CleanedMat} should be zero, and {\it RowOps} is the action of the generator on the invariant subspace. The action on the quotient of a given subspace can be calculated with the ZQT program (see section \ref{sec:zqd}). \Limits The entire first matrix and one row of the second matrix must fit into memory. \Bugs The program does not perform a full check that {\it Space} is in echelon form. \subsection{ZCP: Characteristic Polynomial of a Matrix} %----------------------------------------------------- \Syntax \msg{zcp [-Gf] [{\it Matrix}]} \Description This program reads in a matrix, and prints out its characteristic polynomial in partially factorized form. The default input file is G1. Output is always written to the standard output. After the matrix has been read, the same algorithm as described with the ZOR program is used to calculate a decomposition of the space into cyclic subspaces. The algorithm finds, for each cyclic subspace, a basis of the form \[ (v,vA,vA^2,vA^3,\ldots,vA^{n-1}) \] Thus the characteristic polynomial of $A$ on that subspace is found easily by applying $A$ to the last vector and expressing the result as a linear combination of the basis vectors. The characteristic polynomial of $A$ is the product of the polynomials on all cyclic subspaces in the decomposition. Of course the factors obtained in this way are not necessarily irreducible. If no options are used, the output is in text format. Each line of output contains one factor (as defined above) of the characteristic polynomial. The {\tt -G} option may be used to generate output which is readable by the GAP computer program. The output, then, is a sequence of sequences of finite field elements, representing the coefficients of the factors in ascending order. If {\tt -f} option is used, the characteristic polynomial is decomposed into irreducible factors, and these factors are written out. \Limits There must be enough memory to hold the input matrix and two more matrices of the same size. \subsection{ZEF: Reduce to (Semi) Echelon Form}\Typeout{ZEF} %------------------------------------------- \Syntax \msg{zef [-GQV] {\it Matrix} {\it Result}} \Description This program reads in a matrix, performs a Gaussian elimination to put the matrix into semi-echelon form, and writes out the result. A matrix is in semi-echelon form, if the first non-zero entry in each row entry is a 1, and all entries exactly below that 1 are zero. Here is an example: \begin{center} \begin{verbatim} 000112312312342412123 012012312312231231233 000000001345121223233 102012330332333312212 001021230333323123123 000001230311212112121 \end{verbatim} \end{center} A matrix is in (full) echelon form if the rows are further permuted so that the first non-zero entry in each row is later than the first non-zero entry in all previous rows. There is no real need to do this row permutation in the {\MeatAxe} system, and the permutation is not done by this program. At the end, the matrix may have fewer rows than it started with, since the rows may have been linearly dependent. The rows of the output matrix are always linearly independent and span the same space as the rows of the input matrix. A message \msg{RANK nnn} is printed at the end of the run to notify the operator of the size of the output matrix. This program may be used to find the rank of matrix, being faster than the null-space program. There is no need for the input matrix to be square, and the output may also not be square. \Limits The entire input matrix and the pivot table (4 bytes for each row) must fit into memory. \subsection{ZEV: Eigenvalues}\Typeout{ZEV} %------------------------- \Syntax \msg{zev [-G] [{\it Matrix} [{\it Poly} [{\it Group}]]]} \Description This program reads a matrix from {\it Matrix} and a list of polynomials from {\it Poly}. For each input polynomial, it evaluates that function of the input matrix, calculates the nullity, and puts out this nullity, divided by the degree, along with a text from the input. By default, the matrix is read from G1, and polynomials from the standard input. The {\tt -G} option produces output in GAP format. The program was specifically designed to assist in the calculation of the Brauer characters of diagonalizable matrices, with the text giving the complex number which is the Brauer character of the companion matrix for that polynomial. Usually the polynomials have been prepared in a separate data file and are fed into ZEV by giving the file name or by redirecting its input. The preparation of the input polynomials is generally a time-consuming task if it is done by hand, but there are data files available for the most commonly used fields. These files should be located in the library directory (see section \ref{sec:libdir}). They are distributed with this release of the C {\MeatAxe}. If the user is familiar with the computer program system GAP, he will find it easy to create his own data files. If the nullity is not a multiple of the degree, ZEV prints a warning message. \paragraph{Polynomial file format} %- - - - - - - - - - - - - - - - - The data file contains the polynomials in text form. Several polynomials can be comprised in a `group', and the data file can contain any number of groups of polynomials. This allows several sets of polynomials to be kept in one data file (for example, all polynomials for a given field), the appropriate polynomials being selected trough the {\it Group} argument on the command line. The file is read and interpreted line by line. There are three types of lines: \begin{enumerate} \item Comment lines, beginning with a `{\tt \#}'. These lines are simply ignored by ZEV, as are empty lines. \item Group headers. Each line beginning with a non-space character is interpreted as the beginning of a new group of polynomials. Such lines contain only one text field, the name of the group (up to 1023 characters). \item Lines beginning with a space are interpreted as polynomials. The format is \msg{[space]{\it Name} {\it Coefficients}} where {\it Name} is any text (up to 1023 characters), and {\it Coefficients} are the coefficients of the polynomial (in free format). Note that the first character must be an ordinary space charcter, a TAB is not allowed! The coefficients must use the names as specified by the arithmetic --- usually $0,1,\ldots q-1$. The one exception is $-1$, which the program treats specially as `0'-`1' so that the cyclotomic polynomials can be used over {\em all} fields. The coefficients are in decreasing degree, starting with the coefficient of the highest power of x and continuing, ending up with the constant term. \end{enumerate} Here is an example: \begin{verbatim} # Sample input file for ZEV # Some polynomials over GF(5) # p11b11 1 1 4 b11 1 4 4 1 3 4 -1-b11 1 2 4 1 1 4 p13c13 1 1 4 c13 1 3 0 3 1 c13*3 1 1 4 1 1 c13*9 1 2 1 2 1 \end{verbatim} This file contains 7 polynomials in two groups. The polynomial `b11' in group `p11b11' is $f(x)=x^5+4x^4+4x^3+x^2+3x+4$. \paragraph{Output format} % - - - - - - - - - - - - There are two output formats. By default the nullities are printed in tabular form giving group, name, degree and multiplicity (i.e., nullity divided by degree) for each polynomial. If the {\tt -G} option is given, ZEV prints an algebraic expression which can be read from GAP. Here is an example with an 8 by 8 matrix over GF(3), polynomials being read from {\tt poly3} ({\tt \$} is the shell prompt): \begin{verbatim} $ zev mat poly3 p8i2 p8i2 1 1 1 p8i2 -1 1 4 p8i2 0 2 2 p8i2 i2 2 0 p8i2 -i2 2 1 $ zev -G mat poly3 p8i2 MeatAxe.BrauerChar := 1*(1) + 4*(-1) + 2*(0) + 1*(-i2); \end{verbatim} Note that {\tt i2} does not appear in the expression because its coefficient is zero. \Limits There must be enough memory to hold the input matrix and two more matrices of the same size. Lines in the polynomial input file must not be longer than 1023 characters. Group and polynomial names must be shorter than 1023 characters. \Bugs It is not checked that the input file is a matrix. TAB characters at the beginning of a line are not interpreted as space. \subsection{ZFR: Frobenius Automorphism}\Typeout{ZFR} %------------------------------------ \Syntax \msg{zfr [{\it Matrix} {\it Result}]} \Description This program reads a matrix, applies the Frobenius automorphism $x\mapsto x^p$, where $p$ is the characteristic of the field, to each entry and writes out the result. Default file names are G1 for input and P2 for output. The program first calculates the characteristic by repeatedly adding 1 to itself until zero is reached. A message of the form \msg{CHARACTERISTIC IS {\it p}} is printed to inform the user which $p$ was used. Then the matrix is read row by row, the Frobenius automorphism is applied to each entry, and the resulting row is written out. \Limits One row of the matrix must fit into memory. \subsection{ZIV: Invert a Matrix or Permutation}\Typeout{ZIV} %-------------------------------------------- \Syntax \msg{ziv [{\it Input} {\it Result}]} \Description This program reads a matrix or a permutation from {\it Input} and writes its inverse out to {\it Result}. If no file names are specified, input is read from G1 and output goes to P2. First the input file is inspected. If it is a matrix, it is read in and an identity matrix is made in memory. Inversion proceeds by row operations as follows: The original matrix is reduced to the identity matrix, and the same operations are done to the other matrix that started as the identity matrix. At the end of this process, the second matrix is the inverse of the original matrix, so is written out as the answer. If the input file contains a permutation it is read in and its inverse is calculated point by point. I.e., if the input permutation maps $i$ to $k$, the inverse permutation is set up to map $k$ to $i$. The inverse permutation is then written out. If the input file contains more than one permutation, only the first one is inverted and written out. A message saying \msg{ZIV WARNING - ONLY 1 OF {\em n} PERMUTATIONS WILL BE INVERTED} is printed in this case. \Limits There must be enough memory to hold two matrices or two permutations, respectively. \subsection{ZKD: Kondense a Permutation} %--------------------------------------- \Syntax \msg{zkd {\it Field} {\it OrbSz} {\it Perm} {\em Result}} \Description This program reads an orbit sizes file ({\it OrbSz}) and a permutation from {\it Perm}. It outputs the kondensed form, i.e., a matrix over GF({\it Field}) to {\it Result}. The field must be specified on the command line because the other input data is is all to do with permutations and the program would otherwise not know which field was intended. The orbit sizes are read from {\it OrbSz}. This file is in permutation format, where the number of points gives the number of orbits, and the entries are the orbit sizes. Normally this file would be produced by the ZMO (make orbits) program. The second input file, {\it Perm}, must be one, or more, permutations. Notice that only the first permutation is read in and kondensed. If there are more than one permutation, the others are ignored. It is assumed, that the orbits are contiguous, i.e., if $l_1,l_2,\ldots,l_r$ are the orbit sizes, then the orbits are given by \begin{eqnarray*} O_i & = & \{s_i,s_i+1,\ldots,s_i+l_i-1\}\hspace{1cm} (1\leq i \leq r)\\ \mbox{where } s_i & =& 1+\sum_{k=1}^{i-1}l_k \end{eqnarray*} This is normally achieved by conjugating the original group generators by the permutation that comes out of ZMO (see the ZMO description). The next step is to calculate the largest power ($m$) of the characteristic that divides any of the orbit sizes. ZKD assumes that this is the order of the Sylow-$p$ subgroup of the kondensation subgroup, but it prints out its findings with the message \msg{p-part taken has order {\it n}} so the user can check it. If this is not the order of the Sylow-$p$ subgroup of the kondensation group, the program will not `know', so will continue. Normally, however, the kondensation subgroup $K$ will have trivial Sylow-$p$ subgroup, or at any rate the Sylow subgroup will have a regular orbit, and in this case at least the kondensation is legitimate. The output is a square matrix with one row and one column for each orbit of $K$. Abstractly, the kondensation can be described as follows. Let $G$ be a permutation group of degree $n$, $F$ a field of characteristic $p$ and $K\leq G$ a $p'$-subgroup. Then, there is an idempotent \[ e = \frac{1}{|K|} \sum_{h\in K} h \in FG \] associated to $K$. Now, let $V$ be a $FG$-module, for example (as in this program) the natural permutation module $V=F^n$, where $G$ acts by permuting the entries of vectors. Then, $Ve$ is an $e(FG)e$-module, and for any $\pi\in G$, the kondensed form is $e\pi e$, regarded as a linear map on $Ve$. To calculate the action of $e\pi e$, let $(v_1,\ldots,v_n)$ be the standard basis such that $v_i\pi=v_{i\pi}$ for $\pi\in G$. As explained above, the $K$-orbits are assumed to be contiguous. Thus, a basis of $Ve$ is given by the orbit sums \[ w_i = v_{s_i}+\ldots v_{s_i+l_i-1}\hspace{1cm}(1\leq i\leq r) \] and with respect to this basis we have \[ w_i (e\pi e) = \sum_k \frac{1}{l_{[i\pi]}} w_{[i\pi]} \] where $[m]$ denotes the orbit to which point $m$ belongs (i.e., $s_{[m]}\leq l