Detailed Description

Spin-Up: Given a matrix representation and a seed vector v, the spin-up 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.

Spin-up Scripts: When spinning up a seed vector, you can record the operations performed by the algorithm in a spin-up 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 spin-up process are chosen randomly. However, the spin-up 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₁,...g_n produce the basis (b₁,...b__m), and A is a nonsingular matrix, then vA and A^-1g₁A,...A^-1g_nA produce the basis (b₁A,...b_mA).

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. Note that the representation on V/U depends on a randomly chosen basis.

Data Structures
class	SpinUpInfo_t
	Spin-up 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...

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 spin-up parameters. More...

Matrix_t *	SpinUpWithScript (const Matrix_t seed, const MatRep_t rep, const IntMatrix_t *script)
	Spin-up with script. More...

int	Split (Matrix_t subspace, const MatRep_t rep, MatRep_t sub, MatRep_t quot)
	Split a Representation. More...

Function Documentation

Matrix_t* QAction	(	const Matrix_t *	subspace,
		const Matrix_t *	gen
	)

Action on Quotient.

Given a subspace U≤Fⁿ and a matrix A∊F^n×n that maps U into U, this function calculates the action of the matrix on the quotient Fⁿ/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 n-dim(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.

Parameters

subspace	Pointer to an invariant subspace.
gen	Matrix operating on the subspace.

Returns: Action of the generator on the quotient, or 0 on error.

Matrix_t* QProjection	(	const Matrix_t *	subspace,
		const Matrix_t *	vectors
	)

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₁,...w_s) be a basis for the subspace W≤V. The basis, written as a matrix of row vectors, is assumed to be in semi-echelon 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 non-pivot position and are zero otherwise. Then, (w₁,...,w_s,w_s+1,...,w_n) is a basis for V in semi-echelon form and defines the decomposition of any vector into subspace and quotient part.

Parameters

subspace	The invariant subspace.
vectors	The vectors to project.

Returns: Projection of vectors on the quotient by subspace, or 0 on error.

Matrix_t* SAction	(	const Matrix_t *	subspace,
		const Matrix_t *	gen
	)

Action on a subspace.

Given a subspace U≤Fⁿ 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.

Parameters

subspace	Pointer to an invariant subspace.
gen	Matrix operating on the subspace.

Returns: Action of the generator on the subspace, or 0 on error.

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 1-dimensional subspace of the row space of seed is taken as seed vector.
SF_SUB: Find a submodule: spin up seed vectors one-by-one until a seed vector generates a proper submodule.
SF_CYCLIC: Find a cyclic vector: spin up vectors one-by-one 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 "spin-up script". You can use the script as input to SpinUpWithScript() to repeat the spin-up with a different seed vector. Typically, a spin-up script is created together with SF_STD, and then used to reconstruct the standard basis in a different representation. In order to create a spin-up 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 n-th 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 n-th basis vector by the g-th 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().

Parameters

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.

Returns: Span of the seed vector(s) under the action of the generators, or 0 on error.

int SpinUpInfoInit ( SpinUpInfo_t * info )

Initialize spin-up parameters.

Parameters

info	Pointer to parameter structure.

Returns: 0 on success, -1 on error.

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
	)

Spin-up with script.

This function repeats a previous spin-up with different seed vector and generators. Todo so, the functino needs a spin-up script, which is generated by SpinUp(). The result is a matrix having as many rows as the script.

Parameters

seed	Matrix with seed vectors.
rep	Pointer to a MatRep_t structure with generators.
script	Pointer to the spinup script.

Returns: Span of the seed vector(s) under the action of the generators, or 0 on error.

int Split	(	Matrix_t *	subspace,
		const MatRep_t *	rep,
		MatRep_t **	sub,
		MatRep_t **	quot
	)

Split a Representation.

Given a matrix representation of an algebra A and an A-invariant 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 examples shows how to use SpinUp() to find an invariant subspace. If a proper subspace is found, the representation is split using Split():

 MatRep_t *Rep;
 Matrix_t *seed;
 Matrix_t *subspace;
 ...
 subspace = SpinUp(seed,Rep,SF_FIRST|SF_SUB);
 if (subspace->Nor > 0 && subspace->Nor < subspace->Noc)
 {
     MatRep_t *Sub = NULL, *Quot = NULL;
     printf("Split!\n");
     Split(subspace,Rep,&Sub,&Quot);
 }

See also: SpinUp QAction SAction

Parameters

subspace	Pointer to an invariant subspace.
rep	Matrix representation to split.
sub	Matrix representation on the subspace.
quot	Matrix representation on the quotient.

Returns: 0 on success, -1 on error.

Detailed Description

Data Structures

Functions

Function Documentation