Goto Chapter: Top 1 2 3 4 A Bib Ind

4 Gaussian Algorithms

4.1 A list of the available algorithms

As decribed earlier, the main functions of Gauss are EchelonMat (4.2-1) and EchelonMatTransformation (4.2-2), ReduceMat (4.2-3) and ReduceMatTransformation (4.2-4), KernelMat (4.2-5) and, additionally Rank (4.2-6). These are all documented in the next section, but of course rely on specific algorithms depending on the base ring of the matrix. These are not fully documented but it should be very easy to find out how they work based on the documentation of the main functions.

 EchelonMat Field: EchelonMatDestructive Ring: HermiteMatDestructive EchelonMatTransformation Field: EchelonMatTransformationDestructive Ring: HermiteMatTransformationDestructive ReduceMat Field: ReduceMatWithEchelonMat Ring: ReduceMatWithHermiteMat ReduceMatTransformation Field: ReduceMatWithEchelonMatTransformation Ring: ReduceMatWithHermiteMatTransformation KernelMat Field: KernelEchelonMatDestructive Ring: KernelHermiteMatDestructive Rank Field (dense): Rank (GAP method) Field (sparse): RankDestructive GF(2) (sparse): RankOfIndicesListList Ring: n.a.

4.2 Methods and Functions for Gaussian algorithms

4.2-1 EchelonMat
 ‣ EchelonMat( mat ) ( method )

Returns: a record that contains information about an echelonized form of the matrix mat.

The components of this record are

vectors'

the reduced row echelon / hermite form of the matrix mat without zero rows.

list that contains at position <i>, if nonzero, the number of the row for that the pivot element is in column <i>.

computes the reduced row echelon form RREF of a dense or sparse matrix mat over a field, or the hermite form of a sparse matrix mat over $$ℤ / < p^n >$$.

gap> M := [[0,0,0,1,0],[0,1,1,1,1],[1,1,1,1,0]] * One( GF(2) );;
gap> Display(M);
. . . 1 .
. 1 1 1 1
1 1 1 1 .
gap> EchelonMat(M);
rec( heads := [ 1, 2, 0, 3, 0 ],
vectors := [ <an immutable GF2 vector of length 5>,
<an immutable GF2 vector of length 5>,
<an immutable GF2 vector of length 5> ] )
gap> Display( last.vectors );
1 . . . 1
. 1 1 . 1
. . . 1 .
gap> SM := SparseMatrix( M );
<a 3 x 5 sparse matrix over GF(2)>
gap> EchelonMat( SM );
rec( heads := [ 1, 2, 0, 3, 0 ], vectors := <a 3 x 5 sparse matrix over GF(
2)> )
gap> Display(last.vectors);
1 . . . 1
. 1 1 . 1
. . . 1 .
gap> SM := SparseMatrix( [[7,4,5],[0,0,6],[0,4,4]] * One( Integers mod 8 ) );
<a 3 x 3 sparse matrix over (Integers mod 8)>
gap> Display( SM );
7 4 5
. . 6
. 4 4
gap> EchelonMat( SM );
rec( heads := [ 1, 2, 3 ],
vectors := <a 3 x 3 sparse matrix over (Integers mod 8)> )
gap> Display( last.vectors );
1 . 1
. 4 .
. . 2


4.2-2 EchelonMatTransformation
 ‣ EchelonMatTransformation( mat ) ( method )

Returns: a record that contains information about an echelonized form of the matrix mat.

The components of this record are

vectors'

the reduced row echelon / hermite form of the matrix mat without zero rows.

list that contains at position <i>, if nonzero, the number of the row for that the pivot element is in column <i>.

coeffs'

the transformation matrix needed to obtain the RREF from mat.

relations'

the kernel of the matrix mat if RingOfDefinition(mat) is a field. Otherwise these are only the obvious row relations of mat, there might be more kernel vectors - --> KernelMat (4.2-5).

computes the reduced row echelon form RREF of a dense or sparse matrix mat over a field, or the hermite form of a sparse matrix mat over $$ℤ / < p^n >$$. In either case, the transformation matrix $$T$$ is calculated as the row union of coeffs' and relations'.

gap> M := [[1,0,1],[1,1,0],[1,0,1],[1,1,0],[1,1,1]] * One( GF(2) );;
gap> EchelonMatTransformation( M );
rec(
coeffs := [ <an immutable GF2 vector of length 5>,
<an immutable GF2 vector of length 5>,
<an immutable GF2 vector of length 5> ], heads := [ 1, 2, 3 ],
relations :=
[ <an immutable GF2 vector of length 5>,
<an immutable GF2 vector of length 5> ],
vectors := [ <an immutable GF2 vector of length 3>,
<an immutable GF2 vector of length 3>,
<an immutable GF2 vector of length 3> ] )
gap> Display(last.vectors);
1 . .
. 1 .
. . 1
gap> Display(last.coeffs);
1 1 . . 1
1 . . . 1
. 1 . . 1
gap> Display(last.relations);
1 . 1 . .
. 1 . 1 .
gap> Display( Concatenation( last.coeffs, last.relations ) * M );
1 . .
. 1 .
. . 1
. . .
. . .
gap> SM := SparseMatrix( M );
<a 5 x 3 sparse matrix over GF(2)>
gap> EchelonMatTransformation( SM );
rec( coeffs := <a 3 x 5 sparse matrix over GF(2)>,
heads := [ 1, 2, 3 ],
relations := <a 2 x 5 sparse matrix over GF(2)>,
vectors := <a 3 x 3 sparse matrix over GF(2)> )
gap> Display(last.vectors);
1 . .
. 1 .
. . 1
gap> Display(last.coeffs);
1 1 . . 1
1 . . . 1
. 1 . . 1
gap> Display(last.relations);
1 . 1 . .
. 1 . 1 .
gap> Display( UnionOfRows( last.coeffs, last.relations ) * SM );
1 . .
. 1 .
. . 1
. . .
. . .


4.2-3 ReduceMat
 ‣ ReduceMat( A, B ) ( method )

Returns: a record with a single component reduced_matrix' := M. M is created by reducing A with B, where B must be in Echelon/Hermite form. M will have the same dimensions as A.

gap> M := [[0,0,0,1,0],[0,1,1,1,1],[1,1,1,1,0]] * One( GF(2) );;
gap> Display(M);
. . . 1 .
. 1 1 1 1
1 1 1 1 .
gap> N := [[1,1,0,0,0],[0,0,1,0,1]] * One( GF(2) );;
gap> Display(N);
1 1 . . .
. . 1 . 1
gap> ReduceMat(M,N);
rec(
reduced_matrix := [ <a GF2 vector of length 5>, <a GF2 vector of length 5>,
<a GF2 vector of length 5> ] )
gap> Display(last.reduced_matrix);
. . . 1 .
. 1 . 1 .
. . . 1 1
gap> SM := SparseMatrix(M); SN := SparseMatrix(N);
<a 3 x 5 sparse matrix over GF(2)>
<a 2 x 5 sparse matrix over GF(2)>
gap> ReduceMat(SM,SN);
rec( reduced_matrix := <a 3 x 5 sparse matrix over GF(2)> )
gap> Display(last.reduced_matrix);
. . . 1 .
. 1 . 1 .
. . . 1 1


4.2-4 ReduceMatTransformation
 ‣ ReduceMatTransformation( A, B ) ( method )

Returns: a record with a component reduced_matrix' := M. M is created by reducing A with B, where B must be in Echelon/Hermite form. M will have the same dimensions as A. In addition to the (identical) output as ReduceMat this record also includes the component transformation', which stores the row operations that were needed to reduce A with B. This differs from "normal" transformation matrices because only rows of B had to be moved. Therefore, the transformation matrix solves M = A + T * B.

gap> M := [[0,0,0,1,0],[0,1,1,1,1],[1,1,1,1,0]] * One( GF(2) );;
gap> Display(M);
. . . 1 .
. 1 1 1 1
1 1 1 1 .
gap> N := [[1,1,0,0,0],[0,0,1,0,1]] * One( GF(2) );;
gap> Display(N);
1 1 . . .
. . 1 . 1
gap> ReduceMatTransformation(M,N);
rec(
reduced_matrix :=
[ <a GF2 vector of length 5>, <a GF2 vector of length 5>,
<a GF2 vector of length 5> ],
transformation := [ <a GF2 vector of length 2>,
<a GF2 vector of length 2>, <a GF2 vector of length 2> ] )
gap> Display(last.reduced_matrix);
. . . 1 .
. 1 . 1 .
. . . 1 1
gap> Display(last.transformation);
. .
. 1
1 1
gap> Display( M + last.transformation * N );
. . . 1 .
. 1 . 1 .
. . . 1 1
gap> SM := SparseMatrix(M); SN := SparseMatrix(N);
<a 3 x 5 sparse matrix over GF(2)>
<a 2 x 5 sparse matrix over GF(2)>
gap> ReduceMatTransformation(SM,SN);
rec( reduced_matrix := <a 3 x 5 sparse matrix over GF(2)>,
transformation := <a 3 x 2 sparse matrix over GF(2)> )
gap> Display(last.reduced_matrix);
. . . 1 .
. 1 . 1 .
. . . 1 1
gap> Display(last.transformation);
. .
. 1
1 1
gap> Display( SM + last.transformation * SN );
. . . 1 .
. 1 . 1 .
. . . 1 1


4.2-5 KernelMat
 ‣ KernelMat( M ) ( function )

Returns: a record with a single component relations'.

If M is a matrix over a field this is the same output as EchelonMatTransformation (4.2-2) provides in the relations' component, but with less memory and CPU usage. If the base ring of M is a non-field, the Kernel might have additional generators, which are added to the output.

gap> M := [[2,1],[0,2]];
[ [ 2, 1 ], [ 0, 2 ] ]
gap> SM := SparseMatrix( M * One( GF(3) ) );
<a 2 x 2 sparse matrix over GF(3)>
gap> KernelMat(SM);
rec( relations := <a 0 x 2 sparse matrix over GF(3)> )
gap> SN := SparseMatrix( M * One( Integers mod 4 ) );
<a 2 x 2 sparse matrix over (Integers mod 4)>
gap> KernelMat(SN);
rec( relations := <a 1 x 2 sparse matrix over (Integers mod 4)> )
gap> Display(last.relations);
2 1


4.2-6 Rank
 ‣ Rank( sm[, boundary] ) ( method )

Returns: the rank of the sparse matrix sm. Only works for fields.

Computes the rank of a sparse matrix. If the optional argument boundary is provided, some algorithms take into account the fact that Rank(sm) <= boundary, thus possibly terminating earlier.

gap> M := SparseDiagMat( ListWithIdenticalEntries( 10,
>         SparseMatrix( [[1,1],[1,1]] * One( GF(5) ) ) ) );
<a 20 x 20 sparse matrix over GF(5)>
gap> Display(M);
1 1 . . . . . . . . . . . . . . . . . .
1 1 . . . . . . . . . . . . . . . . . .
. . 1 1 . . . . . . . . . . . . . . . .
. . 1 1 . . . . . . . . . . . . . . . .
. . . . 1 1 . . . . . . . . . . . . . .
. . . . 1 1 . . . . . . . . . . . . . .
. . . . . . 1 1 . . . . . . . . . . . .
. . . . . . 1 1 . . . . . . . . . . . .
. . . . . . . . 1 1 . . . . . . . . . .
. . . . . . . . 1 1 . . . . . . . . . .
. . . . . . . . . . 1 1 . . . . . . . .
. . . . . . . . . . 1 1 . . . . . . . .
. . . . . . . . . . . . 1 1 . . . . . .
. . . . . . . . . . . . 1 1 . . . . . .
. . . . . . . . . . . . . . 1 1 . . . .
. . . . . . . . . . . . . . 1 1 . . . .
. . . . . . . . . . . . . . . . 1 1 . .
. . . . . . . . . . . . . . . . 1 1 . .
. . . . . . . . . . . . . . . . . . 1 1
. . . . . . . . . . . . . . . . . . 1 1
gap> Rank(M);
10
`
Goto Chapter: Top 1 2 3 4 A Bib Ind

generated by GAPDoc2HTML