chap4.txt

  
  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.
  
            `heads'
  
            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 >.
  
    Example  
    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.
  
            `heads'
  
            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'.
  
    Example  
    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.
  
    Example  
    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.
  
    Example  
    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.
  
    Example  
    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.
  
    Example  
    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