MeatAxe
2.4
Programs for working with modular representations

In the MeatAxe, a matrix over a finite field is represented by a Matrix_t structure. Matrices can be created in many ways, for example
Matrices that no longer needed must be deleted by calling MatFree(). Matrices can consume large amounts of memory, so it always a good idea to delete a matrix as early as possible.
As with row vectors, row and column indexs are zerobased. For example, in a 3 by 5 matrix the row index runs from 0 to 2 and the column index runs from 0 to 4.
A matrix A with entries (a_{ij}) is said to be in echelon form if the following conditions are satisfied:
If a matrix is in echelon form, the column indexes of its pivot elements are called the pivot columns of the matrix. The list of all pivot columns is called the pivot table of the matrix. For a matrix in echelon form the number of rows, Nor
, is always less than or equal to the number of columns, Noc
. When different from 0, the PivotTable
field is a pointer to an array of integers containing first the pivot columns and then the nonpivot columns. This means, the size of the array is always Noc:
the first Nor
elements contain the pivot columns and the remaining Noc
contain the nonpivot columns in arbitrary order. Nor
elements
Data Structures  
class  Matrix_t 
A matrix over a finite field. More...  
Functions  
Matrix_t *  MatAddMul (Matrix_t *dest, const Matrix_t *src, FEL coeff) 
Add a multiple of a matrix. More...  
Matrix_t *  MatAdd (Matrix_t *dest, const Matrix_t *src) 
Sum of two matrices. More...  
int  MatClean (Matrix_t *mat, const Matrix_t *sub) 
Clean a matrix. More...  
int  MatCompare (const Matrix_t *a, const Matrix_t *b) 
Compare two matrices If the matrices are equal, the return value is 0. More...  
int  MatCopyRegion (Matrix_t *dest, int destrow, int destcol, const Matrix_t *src, int row1, int col1, int nrows, int ncols) 
Copy a rectangular region of a matrix This function copies a rectangular region of src tp dest. More...  
int  MatIsValid (const Matrix_t *mat) 
Check if the matrix is valid. More...  
Matrix_t *  MatAlloc (int field, int nor, int noc) 
Create a new matrix. More...  
PTR  MatGetPtr (const Matrix_t *mat, int row) 
Pointer to a row of a matrix. More...  
void  Mat_DeletePivotTable (Matrix_t *mat) 
Delete the pivot table of a matrix. More...  
int  MatFree (Matrix_t *mat) 
Delete a matrix. More...  
Matrix_t *  MatCut (const Matrix_t *src, int row1, int col1, int nrows, int ncols) 
Cut a rectangle out of a matrix. More...  
Matrix_t *  MatCutRows (const Matrix_t *src, int row1, int nrows) 
Copy a range of rows of a matrix. More...  
Matrix_t *  MatDup (const Matrix_t *src) 
Duplicate a matrix This function creates a copy of an existing matrix. More...  
int  MatEchelonize (Matrix_t *mat) 
Reduce to echelon form This function performs a Gaussian elimination on the matrix mat. More...  
long  MatNullity (const Matrix_t *mat) 
Nullity of a matrix. More...  
long  MatNullity__ (Matrix_t *mat) 
Nullity of a matrix. More...  
Matrix_t *  MatId (int fl, int nor) 
Identity matrix This function creates an identity matrix with nor nows over GF(fl). More...  
Matrix_t *  MatInsert_ (Matrix_t *mat, const Poly_t *pol) 
Insert a matrix into a polynomial Given a square matrix A and a polynomial p over the same field, this functions calculates p(A). More...  
Matrix_t *  MatInsert (const Matrix_t *mat, const Poly_t *pol) 
Insert a matrix into a polynomial Given a square matrix A and a polynomial p over the same field, this functions calculates p(A). More...  
Matrix_t *  MatInverse (const Matrix_t *mat) 
Inverse of a matrix This function calculates the inverse of a matrix. More...  
Matrix_t *  MatMul (Matrix_t *dest, const Matrix_t *src) 
Multiply matrices This function multiplies dest from the right by src. More...  
Matrix_t *  MatNullSpace_ (Matrix_t *mat, int flags) 
Nullspace of a matrix This function calculates the nullspace of a matrix. More...  
Matrix_t *  MatNullSpace (const Matrix_t *mat) 
Nullspace of a matrix This function calculates the nullspace of a matrix. More...  
Matrix_t *  MatNullSpace__ (Matrix_t *mat) 
Nullspace of a matrix This function calculates the nullspace of a matrix and deletes the original matrix. More...  
int  MatOrder (const Matrix_t *mat) 
Order of a matrix. More...  
int  MatPivotize (Matrix_t *mat) 
Reduce to echelon form. More...  
void  MatPrint (const char *name, const Matrix_t *m) 
Print a matrix on stdout. More...  
Matrix_t *  MatPower (const Matrix_t *mat, long n) 
Power of a matrix. More...  
Matrix_t *  MatRead (FILE *f) 
Read a matrix from a file. More...  
Matrix_t *  MatLoad (const char *fn) 
Read a matrix from a file. More...  
Matrix_t *  MatTransposed (const Matrix_t *src) 
Transpose a matrix. More...  
FEL  MatTrace (const Matrix_t *mat) 
Trace of a Matrix. More...  
int  MatWrite (const Matrix_t *mat, FILE *f) 
Write a matrix to a file. More...  
int  MatSave (const Matrix_t *mat, const char *fn) 
Write a matrix to a file. More...  
Matrix_t *  MatMulScalar (Matrix_t *dest, FEL coeff) 
Multiply a Matrix by a Constant. More...  
int  StablePower_ (Matrix_t *mat, int *pwr, Matrix_t **ker) 
Stable power of a matrix. More...  
int  StablePower (const Matrix_t *mat, int *pwr, Matrix_t **ker) 
Stable power of a matrix. More...  
void Mat_DeletePivotTable  (  Matrix_t *  mat  ) 
Delete the pivot table of a matrix.
This function deletes the pivot table associated with a matrix. It is used internally, applications should never call this function directly.
mat  Pointer to the matrix. 
Sum of two matrices.
This function adds src to dest, overwriteing the previos value in dest. The matrices must be over the same field and have the same dimensions.
Add a multiple of a matrix.
This function adds a multiple of a matrix to another matrix. The matrices must be compatible for addition. MatAddMul() handles special cases (coeff equals 0 or 1) in an intelligent way, so there is no need for the caller to do this.
dest  Matrix to add to. 
src  Matrix to add. 
coeff  Coefficient. 
Matrix_t* MatAlloc  (  int  field, 
int  nor,  
int  noc  
) 
Clean a matrix.
This function "cleans" a matrix with a space, i.e., it adds suitable linear combinations of the rows in sub to the rows of mat such that all pivot columns in mat are zero. Both matrices must be over the same field and have the same number of colums. The second matrix, sub, must be in echelon form. The cleaned matrix is reduced to echelon form.
Compare two matrices If the matrices are equal, the return value is 0.
Otherwise the return value is positive, if a is "greater" than b and negative, if a is "less" than b. The ordering matrices is defined as follows:
In case an error occurs, the return value is 1. But note that a return value of 1 does not necessarily mean that an error has occured.
a  First matrix. 
b  Second matrix. 
int MatCopyRegion  (  Matrix_t *  dest, 
int  destrow,  
int  destcol,  
const Matrix_t *  src,  
int  row1,  
int  col1,  
int  nrows,  
int  ncols  
) 
Copy a rectangular region of a matrix This function copies a rectangular region of src tp dest.
The source region is defined by its upper left corner and dimensions, the destination region is specified by its upper left corner and has the same dimensions. Both nrows and ncols can be given as 1. In this case the region extends up to the last row or last column, respectively. The two matrices must be over the same field. Both source and destination region must not exceed the matrices' dimensions. In particular, it is not possible to extend the destination matrix by using MatCopyRegion().
dest  Pointer to the destination matrix. 
destrow  Destination row. 
destcol  Destination column. 
src  Pointer to the source matrix. 
row1  First row in region. 
col1  First column in region. 
nrows  Number of rows to copy. 1 means as many rows as possible. 
ncols  Number of columns to copy. 1 means as many columns as possible. 
Cut a rectangle out of a matrix.
This function creates a new matrix containing a copy of a rectangular region of the source matrix. The region, defined by row1, col1, nrows and ncols, must not exceed the matrix. However, both nrows and ncols may be 1. In this case the region extends up to the last row or last column, respectivly. For example, to extract the first 10 rows from a matrix independently of the number of columns, you could say
src  Pointer to the matrix. 
row1  First row in region. 
col1  First column in region. 
nrows  Number of rows to cut. 1 means as many rows as possible. 
ncols  Number of columns to cut. 1 means as many columns as possible. 
Copy a range of rows of a matrix.
This function creates a new matrix containing a range of consecutive rows of the source matrix. The range must now exceed the matrix's dimensions. However, nrows may be given as 1, meaning "up to the last row".
src  Pointer to the matrix. 
row1  First row in region. 
nrows  Number of rows to cut. 1 means as many rows as possible. 
Duplicate a matrix This function creates a copy of an existing matrix.
The caller is responsible for destroying the copy with MatFree() when it is no longer needed.
int MatEchelonize  (  Matrix_t *  mat  ) 
Reduce to echelon form This function performs a Gaussian elimination on the matrix mat.
On return, mat is in semi echelon form and a pivot table has been attatched to the matrix. If the rank of mat was smaller than the number of rows, some rows are removed during the process. This function can also be used to rebuild the pivot table after the matrix has been modified.
mat  Pointer to the matrix. 
int MatFree  (  Matrix_t *  mat  ) 
Delete a matrix.
This function frees a matrix which has beed created by MatAlloc(). Freeing includes the internal data buffers as well as the Matrix_t structure itself.
mat  Pointer to the matrix. 
Pointer to a row of a matrix.
This function returns a pointer to the specified row of a matrix. Row numbers start from 0. The current row size is not changed.
mat  Pointer to the matrix. 
row  Row index. 
Matrix_t* MatId  (  int  fl, 
int  nor  
) 
Identity matrix This function creates an identity matrix with nor nows over GF(fl).
fl  Field order. 
nor  Number of rows. 
Insert a matrix into a polynomial Given a square matrix A and a polynomial p over the same field, this functions calculates p(A).
Unlike MatInsert_() this function returns a new matrix and does not modify the original matrix.
mat  Pointer to the matrix. 
pol  Pointer to the polynomial. 
Insert a matrix into a polynomial Given a square matrix A and a polynomial p over the same field, this functions calculates p(A).
Unlike MatInsert() this function is destructive. The result is stored in the original matrix and the old value is lost.
mat  Pointer to the matrix. 
pol  Pointer to the polynomial. 
Inverse of a matrix This function calculates the inverse of a matrix.
mat must be a nonsingular square matrix. The inverse matrix is returned in a newly allocated Matrix_t structure, and the original matrix remains unchanged.
mat  Pointer to the matrix. 
int MatIsValid  (  const Matrix_t *  mat  ) 
Check if the matrix is valid.
This function checks if the argument is a pointer to a valid matrix. If the matrix is o.k., the function returns 1. Otherwise, an error is signalled and, if the error handler does not terminate the program, the function returns 0.
mat  Matrix to check. 
Matrix_t* MatLoad  (  const char *  fn  ) 
Read a matrix from a file.
This function opens a file, reads a single matrix, and closes the file. To read more than one matrix from a file, use MatRead().
fn  File name. 
Multiply matrices This function multiplies dest from the right by src.
The matrices must be compatible for multiplication, i.e. they must be over the same field, and the number of columns of dest must be equal to the number of rows of src. The result of the multiplication is stored in dest, overwriting the original contents.
dest  Left factor and result. 
src  Right factor. 
Multiply a Matrix by a Constant.
dest  Pointer to the matrix. 
coeff  Value to multiply with. 
long MatNullity  (  const Matrix_t *  mat  ) 
Nullity of a matrix.
This function calculates the dimension of the nullspace of a matrix. Unlike MatNullity__() this function does not modify the matrix.
mat  Pointer to the matrix. 
long MatNullity__  (  Matrix_t *  mat  ) 
Nullity of a matrix.
This function calculates the dimension of the nullspace of a matrix and deletes the matrix.
mat  Pointer to the matrix. 
Nullspace of a matrix This function calculates the nullspace of a matrix.
Unlike MatNullSpace_() and MatNullSpace__(), this function does not change the original matrix, but it allocates a temporary copy of the matrix and thus needs more memory.
mat  Pointer to the matrix. 
Nullspace of a matrix This function calculates the nullspace of a matrix.
Unlike MatNullSpace(), this function modifies the orginal matrix, but uses less memory since no temporary workspace is allocated. The result is in echelon form.
mat  Pointer to the matrix. 
flags  If nonzero, the nullspace is not reduced to echelon form. 
Nullspace of a matrix This function calculates the nullspace of a matrix and deletes the original matrix.
mat  Pointer to the matrix. 
int MatOrder  (  const Matrix_t *  mat  ) 
Order of a matrix.
This function calculates the order of a matrix. mat must be a nonsingular, square matrix. Even if mat is nonsingular, the function may fail. This happens if the order is greater than 1000000, or if the order on any cyclic subspace is greater than 1000.
mat  Pointer to the matrix. 
int MatPivotize  (  Matrix_t *  mat  ) 
Reduce to echelon form.
This function builds the pivot table of a matrix. Unlike MatEchelonize() this function assumes that mat is already in echelon form.
mat  Pointer to the matrix. 
Power of a matrix.
This function calculates the nth power of a matrix, using the binary method. This method is generally faster than multiplying the matrix $n$ times by itself. On the other hand, a third matrix is temporarily created in addition to the original matrix and the result matrix. The cases n=0 and n=1 are handled separately, avoiding unnecessary memory allocation and calculation.
Negative exponents are not allowed. To calculate a negative power, you must first invert the matrix with MatInverse() and then call MatPower() with the inverted matrix and a positive exponent.
mat  Pointer to the matrix. 
n  Exponent. 
void MatPrint  (  const char *  name, 
const Matrix_t *  m  
) 
Print a matrix on stdout.
This function prints a matrix on the standard output in readable form. If name is not 0, the name followed by an equal sign is printed before the matrix.
name  Name to print before the matrix, or 0. 
m  Pointer to the matrix. 
Matrix_t* MatRead  (  FILE *  f  ) 
Read a matrix from a file.
f  File to read from. 
int MatSave  (  const Matrix_t *  mat, 
const char *  fn  
) 
Write a matrix to a file.
This function opens a file, writes a matrix to the file, and closes the file. If a file with the specified name already exists, the old contents of the file are destroyd. To write more than one matrix to a file, use MatWrite().
mat  Pointer to the matrix. 
fn  File name. 
Trace of a Matrix.
This function calculates the sum of all diagonal elements of a matrix. Note that the matrix need not be square.
mat  Pointer to the matrix. 
FF_ZERO
on error. Transpose a matrix.
src  Pointer to the matrix. 
int MatWrite  (  const Matrix_t *  mat, 
FILE *  f  
) 
Write a matrix to a file.
mat  Pointer to the matrix. 
f  Pointer to the file. 
Stable power of a matrix.
This function works like StablePower_(), but it does not modify the matrix in mat. This means, of course, that a temporary copy of the matrix is created.
mat  The matrix. 
pwr  Stable power. 
ker  Kernel of the stable power. 
Stable power of a matrix.
This function takes a square matrix M and finds an integer n>0 such that ker(M^{n}) = ker(M^{n+1}). ker must be a pointer to a variable of type Matrix_t*, where the stable kernel will be stored. Both pwr and ker may be NULL if the corresponding information is not needed.
Note that the number $n$ found by StablePower_() is not guararanteed to be minimal. In fact, n will always be a power of two since the function only examines matrices of the form M^{2k}.
This function modifies the matrix. To avoid this, use StablePower().
mat  The matrix. 
pwr  Stable power. 
ker  Kernel of the stable power. 