GAP (Gauss) - Chapter 4: Gaussian 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

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

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

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

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

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( SparseUnionOfRows( [ last.coeffs, last.relations ] ) * SM );
 1 . .
 . 1 .
 . . 1
 . . .
 . . .

4.2-3 ReduceMat

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

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

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

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

4 Gaussian Algorithms