MeatAxe
2.4
Programs for working with modular representations

Given a matrix representation and a seed vector v, the spinup algorithm calculates the submodule generated by the seed vector, i.e., the smallest subspace containing v which is invariant under the generators. SpinUp() can handle multiple seed vectors, search for cyclic vectors generating the whole space, and generate seed vectors as linear combinations of a given basis.
Spinup scripts When spinning up a seed vector, you can record the operations performed by the algorithm in a spinup script. This script can then be fed into SpinUpWithScript() to repeat the procedure with a different seed vector and different generators.
Standard basis Normally, the basis vectors computed during the spinup process are chosen randomly. However, the spinup algorithm can be used in "standard basis" mode. In this mode, the result is invariant under a change of basis. More precisely, if a given seed vector v and generators g_{1},...g_{n} produce the basis (b_{1},...b__{m}), and A is a nonsingular matrix, then vA and A^{1}g_{1}A,...A^{1}g_{n}A produce the basis (b_{1}A,...b_{m}A).
Splitting a representation If a proper invariant subspace U<V has been found for a matrix representation M, the restriction of M to U as well as the representation on V/U can be calculated. This is called splitting the representation. The basis for V/U is chosen randomly.
Data Structures  
class  SpinUpInfo_t 
Spinup Parameters. More...  
Functions  
Matrix_t *  QProjection (const Matrix_t *subspace, const Matrix_t *vectors) 
Projection on quotient. More...  
Matrix_t *  QAction (const Matrix_t *subspace, const Matrix_t *gen) 
Action on Quotient. More...  
Matrix_t *  SAction (const Matrix_t *subspace, const Matrix_t *gen) 
Action on a subspace. More...  
int  DoSpinup (const SpinUpInfo_t *info) 
Spin up. More...  
Matrix_t *  SpinUp (const Matrix_t *seed, const MatRep_t *rep, int flags, IntMatrix_t **script, SpinUpInfo_t *info) 
Spin up. More...  
Matrix_t *  SpinUpWithPermutations (const Matrix_t *seed, int ngen, const Perm_t **gen, int flags, IntMatrix_t **script, SpinUpInfo_t *info) 
Spin Up With Permutations. More...  
int  SpinUpInfoInit (SpinUpInfo_t *info) 
Initialize spinup parameters. More...  
Matrix_t *  SpinUpWithScript (const Matrix_t *seed, const MatRep_t *rep, const IntMatrix_t *script) 
Spinup with script. More...  
int  Split (Matrix_t *subspace, const MatRep_t *rep, MatRep_t **sub, MatRep_t **quot) 
Split a Representation. More...  
int DoSpinup  (  const SpinUpInfo_t *  info  ) 
Spin up.
Action on Quotient.
Given a subspace U≤F^{n} and a matrix A∊F^{n×n} that maps U into U, this function calculates the action of the matrix on the quotient F^{n}/U. As input, the function expects a basis of the subspace in subspace, which must be in echelon form, and the matrix operating on the subspace in gen. The result is a square matrix with ndim(U) rows describing the action of A on the quotient in a randomly chosen basis.
Before calculating the action, QAction() checks if the arguments are valid matrices, and if they are compatible. Both subspace and gen must be over the same field, have the same number of columns, and gen must be square.
subspace  Pointer to an invariant subspace. 
gen  Matrix operating on the subspace. 
Projection on quotient.
This function calculates the projection of a matrix onto the quotient by a subspace. The first matrix, subspace must be in echelon form, while the second argument can be any matrix. Of course both matrices must be over the same field and have the same number of columns. The return value is a pointer to a matrix containing the projections the vectors. This matrix is not in echelon form and may even contain null rows.
The projection depends on the basis for the subspace and is calculated as follows. Let V=F^{n×n} and (w_{1},...w_{s}) be a basis for the subspace W≤V. The basis, written as a matrix of row vectors, is assumed to be in semiechelon form. By looking at the pivot columns we can construct the vectors w_{s+1},...w_{n} by taking all vectors which have a exactly one 1 at any nonpivot position and are zero otherwise. Then, (w_{1},...,w_{s},w_{s+1},...,w_{n}) is a basis for V in semiechelon form and defines the decomposition of any vector into subspace and quotient part.
subspace  The invariant subspace. 
vectors  The vectors to project. 
Action on a subspace.
Given a subspace U≤F^{n} and a matrix A∊F^{n×n} that maps U into U, this function calculates the action of the matrix on the subspace. As input, the function expects a basis of the subspace in subspace, which must be in chelon form, and the matrix operating on the subspace in gen. The result is a square matrix with dim(U) rows containing the image of the basis vectors under A, expressed in the given basis.
Before calculating the action, SAction() checks if the arguments are valid matrices, and if they are compatible. Both subspace and gen must be over the same field, have the same number of columns, and gen must be square.
subspace  Pointer to an invariant subspace. 
gen  Matrix operating on the subspace. 
Matrix_t* SpinUp  (  const Matrix_t *  seed, 
const MatRep_t *  rep,  
int  flags,  
IntMatrix_t **  script,  
SpinUpInfo_t *  info  
) 
Spin up.
This function calculates the submodule generated by one or more "seed" vectors under the action of a set of matrices. seed must be a matrix with the same number of columns as the generators and any number of rows. Of course, all matrices, generators and seed, must be over the same field.
The spinup mode and various options are controlled by two arguments, flags and info. flags must be a combination of the following values:
SF_FIRST:
Only the first row of seed is taken as seed vector.SF_EACH:
Each row of seed is taken as seed vector.SF_MAKE:
One vector from each 1dimensional subspace of the row space of seed is taken as seed vector.SF_SUB:
Find a submodule: spin up seed vectors onebyone until a seed vector generates a proper submodule.SF_CYCLIC:
Find a cyclic vector: spin up vectors onebyone until a seed vector generates the whole space.SF_COMBINE:
Calculate the submodule generated by the set of all seed vectors. This ist typically used with SF_EACH
to calculate the submodule generate by the row space of seed.SF_STD:
Create the standard basis. This increases both computation time and memory usage.The seed modes, SF_FIRST
, SF_EACH
and SF_MAKE
, and the search modes, SF_SUB
, SF_CYCLIC
, SF_COMBINE
, are mutually exclusive. If, in mode SF_SUB
or SF_CYCLIC
, no seed vector generates a proper submodule or the whole space, respectively, this is not considered an error, and the return value is not NULL
. The rows of the matrix returned by SpinUp() always form a basis of an invariant subspace, but you must examine the number of rows of that matrix to find out if it is a proper subspace, or null, or the whole space.
The subspace returned by SpinUp() is always in echelon form, if SF_STD
is not used. With SF_STD
however, the subspace is not necessarily in echelon form.
SpinUp() can record the operations that led to the invariant subspace in a "spinup script". You can use the script as input to SpinUpWithScript() to repeat the spinup with a different seed vector. Typically, a spinup script is created together with SF_STD, and then used to reconstruct the standard basis in a different representation. In order to create a spinup script, script must point to a variable of type IntMatrix_t*. This variable must either be 0 or contain a valid pointer. In the second case, the buffer pointed to by script is first deallocated before a new script is created. After SpinUp() returns, the variable contains a pointer to the script. If no spinup script is needed, pass 0 as 4th parameter.
The format of the spinup script is a matrix with 2 columns and one row for each basis vector. A row (n,1) means that the corresponding basis vector is the nth seed vector. Seed vector numbers start from 1. An entry (n,g) with g≥0 means that the corresponding basis vector was obtained by multiplying the nth basis vector by the gth generator. Basis vector number and generator number start from 0.
Additional parameters can be passed via the info argument. To be compatible with future versions of SpinUpInfo_t, you should always initialize the parameter structure with SpinUpinfoInit().
seed  Matrix with seed vectors. 
rep  Pointer to a MatRep_t structure with generators. 
flags  Flags, a combination of SF_XXXX constants (see description). 
script  Pointer to a variable where the spinup script will be stored (see description). May be 0. 
info  Pointer to a data structure with additional parameters, or 0. 
int SpinUpInfoInit  (  SpinUpInfo_t *  info  ) 
Initialize spinup parameters.
info  Pointer to parameter structure. 
Matrix_t* SpinUpWithPermutations  (  const Matrix_t *  seed, 
int  ngen,  
const Perm_t **  gen,  
int  flags,  
IntMatrix_t **  script,  
SpinUpInfo_t *  info  
) 
Spin Up With Permutations.
This function works like Spinup() but expects permutations instead of matrices for the generators.
Matrix_t* SpinUpWithScript  (  const Matrix_t *  seed, 
const MatRep_t *  rep,  
const IntMatrix_t *  script  
) 
Spinup with script.
This function repeats a previous spinup with different seed vector and generators. To do so, the function needs a spinup script, which is generated by SpinUp(). The result is a matrix having as many rows as the script.
seed  Matrix with seed vectors. 
rep  Pointer to a MatRep_t structure with generators. 
script  Pointer to the spinup script. 
Split a Representation.
Given a matrix representation of an algebra A and an Ainvariant subspace U, this function calculates two new matrix representations corrsponding to the subspace and quotient, respectively.
subspace is a basis for the invariant subspace. This matrix must be in echelon form. rep is the representation to be split. sub and quot are pointers to variables, where the representation on subspace and quotient, respectively, will be stored. Both sub and quot can be 0 if the corresponding representation is not needed. If sub is not 0, *sub
must be 0 or a pointer to a valid matrix representation, which will be destroyed before the result is stored in *sub. The same remark applies to quot.
The function checks that the subspace is indeed invariant under the given representation. However, this check is carried out only when the subspace is calculated, i.e., if sub is not 0. The function also check if subspace and representation are compatible. If any of these checks fails, the return value is 1.
Internally, Split() uses SAction() and QAction() to calculate the action of the generators on the subspace and quotient.
The following example shows how to use SpinUp() to find an invariant subspace. If a proper subspace is found, the representation is split.
subspace  Pointer to an invariant subspace. 
rep  Matrix representation to split. 
sub  Matrix representation on the subspace. 
quot  Matrix representation on the quotient. 