chap5.txt

  
  5 Matrices
  
  
  5.1 Matrices: Category and Representations
  
  5.1-1 IsHomalgMatrix
  
  IsHomalgMatrix( A )  Category
  Returns:  true or false
  
  The GAP category of homalg matrices.
  
    Code  
    DeclareCategory( "IsHomalgMatrix",
            IsMatrixObj and
            IsAttributeStoringRep );
  
  
  5.1-2 IsHomalgInternalMatrixRep
  
  IsHomalgInternalMatrixRep( A )  Representation
  Returns:  true or false
  
  The internal representation of homalg matrices.
  
  (It is a representation of the GAP category IsHomalgMatrix (5.1-1).)
  
  
  5.2 Matrices: Constructors
  
  5.2-1 HomalgInitialMatrix
  
  HomalgInitialMatrix( m, n, R )  function
  Returns:  a homalg matrix
  
  A mutable unevaluated initial m × n homalg matrix filled with zeros over the
  homalg  ring  R.  This  construction is useful in case one wants to define a
  matrix  by  assigning  its  nonzero  entries.  The  property IsInitialMatrix
  (5.3-26)  is  reset  as  soon  as  the  matrix  is  evaluated.  New computed
  properties  or attributes of the matrix won't be cached, until the matrix is
  explicitly    made    immutable   using   (-->   MakeImmutable   (Reference:
  MakeImmutable)).
  
    Example  
    gap> ZZ := HomalgRingOfIntegers( );
    Z
    gap> z := HomalgInitialMatrix( 2, 3, ZZ );
    <An initial 2 x 3 matrix over an internal ring>
    gap> HasIsZero( z );
    false
    gap> IsZero( z );
    true
    gap> z;
    <A 2 x 3 mutable matrix over an internal ring>
    gap> HasIsZero( z );
    false
  
  
    Example  
    gap> n := HomalgInitialMatrix( 2, 3, ZZ );
    <An initial 2 x 3 matrix over an internal ring>
    gap> SetMatElm( n, 1, 1, "1" );
    gap> SetMatElm( n, 2, 3, "1" );
    gap> MakeImmutable( n );
    <A 2 x 3 matrix over an internal ring>
    gap> Display( n );
    [ [  1,  0,  0 ],
      [  0,  0,  1 ] ]
    gap> IsZero( n );
    false
    gap> n;
    <A non-zero 2 x 3 matrix over an internal ring>
  
  
  5.2-2 HomalgInitialIdentityMatrix
  
  HomalgInitialIdentityMatrix( m, R )  function
  Returns:  a homalg matrix
  
  A mutable unevaluated initial m × m homalg quadratic matrix with ones on the
  diagonal  over  the  homalg  ring R. This construction is useful in case one
  wants  to  define an elementary matrix by assigning its off-diagonal nonzero
  entries.  The  property IsInitialIdentityMatrix (5.3-27) is reset as soon as
  the matrix is evaluated. New computed properties or attributes of the matrix
  won't  be  cached,  until the matrix is explicitly made immutable using (-->
  MakeImmutable (Reference: MakeImmutable)).
  
    Example  
    gap> ZZ := HomalgRingOfIntegers( );
    Z
    gap> id := HomalgInitialIdentityMatrix( 3, ZZ );
    <An initial identity 3 x 3 matrix over an internal ring>
    gap> HasIsOne( id );
    false
    gap> IsOne( id );
    true
    gap> id;
    <A 3 x 3 mutable matrix over an internal ring>
    gap> HasIsOne( id );
    false
  
  
    Example  
    gap> e := HomalgInitialIdentityMatrix( 3, ZZ );
    <An initial identity 3 x 3 matrix over an internal ring>
    gap> SetMatElm( e, 1, 2, "1" );
    gap> SetMatElm( e, 2, 1, "-1" );
    gap> MakeImmutable( e );
    <A 3 x 3 matrix over an internal ring>
    gap> Display( e );
    [ [   1,   1,   0 ],
      [  -1,   1,   0 ],
      [   0,   0,   1 ] ]
    gap> IsOne( e );
    false
    gap> e;
    <A 3 x 3 matrix over an internal ring>
  
  
  5.2-3 HomalgZeroMatrix
  
  HomalgZeroMatrix( m, n, R )  function
  Returns:  a homalg matrix
  
  An immutable unevaluated m × n homalg zero matrix over the homalg ring R.
  
    Example  
    gap> ZZ := HomalgRingOfIntegers( );
    Z
    gap> z := HomalgZeroMatrix( 2, 3, ZZ );
    <An unevaluated 2 x 3 zero matrix over an internal ring>
    gap> Display( z );
    [ [  0,  0,  0 ],
      [  0,  0,  0 ] ]
    gap> z;
    <A 2 x 3 zero matrix over an internal ring>
  
  
  5.2-4 HomalgIdentityMatrix
  
  HomalgIdentityMatrix( m, R )  function
  Returns:  a homalg matrix
  
  An  immutable  unevaluated m × m homalg identity matrix over the homalg ring
  R.
  
    Example  
    gap> ZZ := HomalgRingOfIntegers( );
    Z
    gap> id := HomalgIdentityMatrix( 3, ZZ );
    <An unevaluated 3 x 3 identity matrix over an internal ring>
    gap> Display( id );
    [ [  1,  0,  0 ],
      [  0,  1,  0 ],
      [  0,  0,  1 ] ]
    gap> id;
    <A 3 x 3 identity matrix over an internal ring>
  
  
  5.2-5 HomalgVoidMatrix
  
  HomalgVoidMatrix( [m, ][n, ]R )  function
  Returns:  a homalg matrix
  
  A void m × n homalg matrix.
  
  5.2-6 HomalgMatrix
  
  HomalgMatrix( llist, R )  function
  HomalgMatrix( list, m, n, R )  function
  HomalgMatrix( str_llist, R )  function
  HomalgMatrix( str_list, m, n, R )  function
  Returns:  a homalg matrix
  
  An immutable evaluated m × n homalg matrix over the homalg ring R.
  
    Example  
    gap> ZZ := HomalgRingOfIntegers( );
    Z
    gap> m := HomalgMatrix( [ [ 1, 2, 3 ], [ 4, 5, 6 ] ], ZZ );
    <A 2 x 3 matrix over an internal ring>
    gap> Display( m );
    [ [  1,  2,  3 ],
      [  4,  5,  6 ] ]
  
  
    Example  
    gap> m := HomalgMatrix( [ [ 1, 2, 3 ], [ 4, 5, 6 ] ], 2, 3, ZZ );
    <A 2 x 3 matrix over an internal ring>
    gap> Display( m );
    [ [  1,  2,  3 ],
      [  4,  5,  6 ] ]
  
  
    Example  
    gap> m := HomalgMatrix( [ 1, 2, 3,   4, 5, 6 ], 2, 3, ZZ );
    <A 2 x 3 matrix over an internal ring>
    gap> Display( m );
    [ [  1,  2,  3 ],
      [  4,  5,  6 ] ]
  
  
    Example  
    gap> m := HomalgMatrix( "[ [ 1, 2, 3 ], [ 4, 5, 6 ] ]", ZZ );
    <A 2 x 3 matrix over an internal ring>
    gap> Display( m );
    [ [  1,  2,  3 ],
      [  4,  5,  6 ] ]
  
  
    Example  
    gap> m := HomalgMatrix( "[ [ 1, 2, 3 ], [ 4, 5, 6 ] ]", 2, 3, ZZ );
    <A 2 x 3 matrix over an internal ring>
    gap> Display( m );
    [ [  1,  2,  3 ],
      [  4,  5,  6 ] ]
  
  
  It  is  nevertheless  recommended to use the following form to create homalg
  matrices.  This  form  can  also  be used to define external matrices. Since
  whitespaces  (-->  Reference:  Whitespaces) are ignored, they can be used as
  optical delimiters:
  
    Example  
    gap> m := HomalgMatrix( "[ 1, 2, 3,   4, 5, 6 ]", 2, 3, ZZ );
    <A 2 x 3 matrix over an internal ring>
    gap> Display( m );
    [ [  1,  2,  3 ],
      [  4,  5,  6 ] ]
  
  
  One  can  split  the  input  string  over  several lines using the backslash
  character '\' to end each line
  
    Example  
    gap> m := HomalgMatrix( "[ \
    > 1, 2, 3, \
    > 4, 5, 6  \
    > ]", 2, 3, ZZ );
    <A 2 x 3 matrix over an internal ring>
    gap> Display( m );
    [ [  1,  2,  3 ],
      [  4,  5,  6 ] ]
  
  
  5.2-7 HomalgDiagonalMatrix
  
  HomalgDiagonalMatrix( diag, R )  function
  Returns:  a homalg matrix
  
  An  immutable unevaluated diagonal homalg matrix over the homalg ring R. The
  diagonal consists of the entries of the list diag.
  
    Example  
    gap> ZZ := HomalgRingOfIntegers( );
    Z
    gap> d := HomalgDiagonalMatrix( [ 1, 2, 3 ], ZZ );
    <An unevaluated diagonal 3 x 3 matrix over an internal ring>
    gap> Display( d );
    [ [  1,  0,  0 ],
      [  0,  2,  0 ],
      [  0,  0,  3 ] ]
    gap> d;
    <A diagonal 3 x 3 matrix over an internal ring>
  
  
  5.2-8 \*
  
  \*( R, mat )  operation
  \*( mat, R )  operation
  Returns:  a homalg matrix
  
  An  immutable evaluated homalg matrix over the homalg ring R having the same
  entries as the matrix mat. Syntax: R * mat or mat * R
  
    Example  
    gap> ZZ := HomalgRingOfIntegers( );
    Z
    gap> Z4 := ZZ / 4;
    Z/( 4 )
    gap> Display( Z4 );
    <A residue class ring>
    gap> d := HomalgDiagonalMatrix( [ 2 .. 4 ], ZZ );
    <An unevaluated diagonal 3 x 3 matrix over an internal ring>
    gap> d2 := Z4 * d; ## or d2 := d * Z4;
    <A 3 x 3 matrix over a residue class ring>
    gap> Display( d2 );
    [ [  2,  0,  0 ],
      [  0,  3,  0 ],
      [  0,  0,  4 ] ]
    
    modulo [ 4 ]
    gap> d;
    <A diagonal 3 x 3 matrix over an internal ring>
    gap> ZeroRows( d );
    [  ]
    gap> ZeroRows( d2 );
    [ 3 ]
    gap> d;
    <A non-zero diagonal 3 x 3 matrix over an internal ring>
    gap> d2;
    <A non-zero 3 x 3 matrix over a residue class ring>
  
  
  
  5.3 Matrices: Properties
  
  5.3-1 IsZero
  
  IsZero( A )  property
  Returns:  true or false
  
  Check  if  the  homalg  matrix  A  is  a  zero  matrix, taking possible ring
  relations into account.
  
  (for the installed standard method see IsZeroMatrix (B.1-16))
  
    Example  
    gap> ZZ := HomalgRingOfIntegers( );
    Z
    gap> A := HomalgMatrix( "[ 2 ]", ZZ );
    <A 1 x 1 matrix over an internal ring>
    gap> Z2 := ZZ / 2;
    Z/( 2 )
    gap> A := Z2 * A;
    <A 1 x 1 matrix over a residue class ring>
    gap> Display( A );
    [ [  2 ] ]
    
    modulo [ 2 ]
    gap> IsZero( A );
    true
  
  
  5.3-2 IsOne
  
  IsOne( A )  property
  Returns:  true or false
  
  Check  if  the  homalg  matrix A is an identity matrix, taking possible ring
  relations into account.
  
  (for the installed standard method see IsIdentityMatrix (B.2-2))
  
  5.3-3 IsUnitFree
  
  IsUnitFree( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-4 IsPermutationMatrix
  
  IsPermutationMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-5 IsSpecialSubidentityMatrix
  
  IsSpecialSubidentityMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-6 IsSubidentityMatrix
  
  IsSubidentityMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-7 IsLeftRegular
  
  IsLeftRegular( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-8 IsRightRegular
  
  IsRightRegular( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-9 IsInvertibleMatrix
  
  IsInvertibleMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-10 IsLeftInvertibleMatrix
  
  IsLeftInvertibleMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-11 IsRightInvertibleMatrix
  
  IsRightInvertibleMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-12 IsEmptyMatrix
  
  IsEmptyMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-13 IsDiagonalMatrix
  
  IsDiagonalMatrix( A )  property
  Returns:  true or false
  
  Check  if  the  homalg  matrix A is an identity matrix, taking possible ring
  relations into account.
  
  (for the installed standard method see IsDiagonalMatrix (B.2-3))
  
  5.3-14 IsScalarlMatrix
  
  IsScalarlMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-15 IsUpperTriangularMatrix
  
  IsUpperTriangularMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-16 IsLowerTriangularMatrix
  
  IsLowerTriangularMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-17 IsStrictUpperTriangularMatrix
  
  IsStrictUpperTriangularMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-18 IsStrictLowerTriangularMatrix
  
  IsStrictLowerTriangularMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-19 IsUpperStairCaseMatrix
  
  IsUpperStairCaseMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-20 IsLowerStairCaseMatrix
  
  IsLowerStairCaseMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-21 IsTriangularMatrix
  
  IsTriangularMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-22 IsBasisOfRowsMatrix
  
  IsBasisOfRowsMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-23 IsBasisOfColumnsMatrix
  
  IsBasisOfColumnsMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-24 IsReducedBasisOfRowsMatrix
  
  IsReducedBasisOfRowsMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-25 IsReducedBasisOfColumnsMatrix
  
  IsReducedBasisOfColumnsMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-26 IsInitialMatrix
  
  IsInitialMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-27 IsInitialIdentityMatrix
  
  IsInitialIdentityMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  5.3-28 IsVoidMatrix
  
  IsVoidMatrix( A )  property
  Returns:  true or false
  
  A is a homalg matrix.
  
  
  5.4 Matrices: Attributes
  
  5.4-1 NrRows
  
  NrRows( A )  attribute
  Returns:  a nonnegative integer
  
  The number of rows of the matrix A.
  
  (for the installed standard method see NrRows (B.1-17))
  
  5.4-2 NrColumns
  
  NrColumns( A )  attribute
  Returns:  a nonnegative integer
  
  The number of columns of the matrix A.
  
  (for the installed standard method see NrColumns (B.1-18))
  
  5.4-3 DeterminantMat
  
  DeterminantMat( A )  attribute
  Returns:  a ring element
  
  The determinant of the quadratic matrix A.
  
  You can invoke it with Determinant( A ).
  
  (for the installed standard method see Determinant (B.1-19))
  
  5.4-4 ZeroRows
  
  ZeroRows( A )  attribute
  Returns:  a (possibly empty) list of positive integers
  
  The list of zero rows of the matrix A.
  
  (for the installed standard method see ZeroRows (B.2-4))
  
  5.4-5 ZeroColumns
  
  ZeroColumns( A )  attribute
  Returns:  a (possibly empty) list of positive integers
  
  The list of zero columns of the matrix A.
  
  (for the installed standard method see ZeroColumns (B.2-5))
  
  5.4-6 NonZeroRows
  
  NonZeroRows( A )  attribute
  Returns:  a (possibly empty) list of positive integers
  
  The list of nonzero rows of the matrix A.
  
  5.4-7 NonZeroColumns
  
  NonZeroColumns( A )  attribute
  Returns:  a (possibly empty) list of positive integers
  
  The list of nonzero columns of the matrix A.
  
  5.4-8 PositionOfFirstNonZeroEntryPerRow
  
  PositionOfFirstNonZeroEntryPerRow( A )  attribute
  Returns:  a list of nonnegative integers
  
  The  list  of  positions of the first nonzero entry per row of the matrix A,
  else zero.
  
  5.4-9 PositionOfFirstNonZeroEntryPerColumn
  
  PositionOfFirstNonZeroEntryPerColumn( A )  attribute
  Returns:  a list of nonnegative integers
  
  The list of positions of the first nonzero entry per column of the matrix A,
  else zero.
  
  5.4-10 RowRankOfMatrix
  
  RowRankOfMatrix( A )  attribute
  Returns:  a nonnegative integer
  
  The row rank of the matrix A.
  
  5.4-11 ColumnRankOfMatrix
  
  ColumnRankOfMatrix( A )  attribute
  Returns:  a nonnegative integer
  
  The column rank of the matrix A.
  
  5.4-12 LeftInverse
  
  LeftInverse( M )  attribute
  Returns:  a homalg matrix
  
  A  left  inverse  C of the matrix M. If no left inverse exists then false is
  returned. (--> RightDivide (5.5-45))
  
  (for the installed standard method see LeftInverse (5.5-2))
  
  5.4-13 RightInverse
  
  RightInverse( M )  attribute
  Returns:  a homalg matrix
  
  A  right inverse C of the matrix M. If no right inverse exists then false is
  returned. (--> LeftDivide (5.5-46))
  
  (for the installed standard method see RightInverse (5.5-3))
  
  5.4-14 CoefficientsOfUnreducedNumeratorOfHilbertPoincareSeries
  
  CoefficientsOfUnreducedNumeratorOfHilbertPoincareSeries( A )  attribute
  Returns:  a list of integers
  
  A is a homalg matrix (row convention).
  
  5.4-15 CoefficientsOfNumeratorOfHilbertPoincareSeries
  
  CoefficientsOfNumeratorOfHilbertPoincareSeries( A )  attribute
  Returns:  a list of integers
  
  A is a homalg matrix (row convention).
  
  5.4-16 UnreducedNumeratorOfHilbertPoincareSeries
  
  UnreducedNumeratorOfHilbertPoincareSeries( A )  attribute
  Returns:  a univariate polynomial with rational coefficients
  
  A is a homalg matrix (row convention).
  
  5.4-17 NumeratorOfHilbertPoincareSeries
  
  NumeratorOfHilbertPoincareSeries( A )  attribute
  Returns:  a univariate polynomial with rational coefficients
  
  A is a homalg matrix (row convention).
  
  5.4-18 HilbertPoincareSeries
  
  HilbertPoincareSeries( A )  attribute
  Returns:  a univariate rational function with rational coefficients
  
  A is a homalg matrix (row convention).
  
  5.4-19 HilbertPolynomial
  
  HilbertPolynomial( A )  attribute
  Returns:  a univariate polynomial with rational coefficients
  
  A is a homalg matrix (row convention).
  
  5.4-20 AffineDimension
  
  AffineDimension( A )  attribute
  Returns:  a nonnegative integer
  
  A is a homalg matrix (row convention).
  
  5.4-21 AffineDegree
  
  AffineDegree( A )  attribute
  Returns:  a nonnegative integer
  
  A is a homalg matrix (row convention).
  
  5.4-22 ProjectiveDegree
  
  ProjectiveDegree( A )  attribute
  Returns:  a nonnegative integer
  
  A is a homalg matrix (row convention).
  
  5.4-23 ConstantTermOfHilbertPolynomialn
  
  ConstantTermOfHilbertPolynomialn( A )  attribute
  Returns:  an integer
  
  A is a homalg matrix (row convention).
  
  5.4-24 MatrixOfSymbols
  
  MatrixOfSymbols( A )  attribute
  Returns:  an integer
  
  A is a homalg matrix.
  
  
  5.5 Matrices: Operations and Functions
  
  5.5-1 HomalgRing
  
  HomalgRing( mat )  operation
  Returns:  a homalg ring
  
  The homalg ring of the homalg matrix mat.
  
    Example  
    gap> ZZ := HomalgRingOfIntegers( );
    Z
    gap> d := HomalgDiagonalMatrix( [ 2 .. 4 ], ZZ );
    <An unevaluated diagonal 3 x 3 matrix over an internal ring>
    gap> R := HomalgRing( d );
    Z
    gap> IsIdenticalObj( R, ZZ );
    true
  
  
  5.5-2 LeftInverse
  
  LeftInverse( RI )  method
  Returns:  a homalg matrix or fail
  
  The  left  inverse  of  the matrix RI. The lazy version of this operation is
  LeftInverseLazy (5.5-4). (--> RightDivide (5.5-45))
  
    Code  
    InstallMethod( LeftInverse,
            "for homalg matrices",
            [ IsHomalgMatrix ],
            
      function( RI )
        local Id, LI;
        
        Id := HomalgIdentityMatrix( NrColumns( RI ), HomalgRing( RI ) );
        
        LI := RightDivide( Id, RI );	## ( cf. [BR08, Subsection 3.1.3] )
        
        ## CAUTION: for the following SetXXX RightDivide is assumed
        ## NOT to be lazy evaluated!!!
        
        SetIsLeftInvertibleMatrix( RI, IsHomalgMatrix( LI ) );
        
        if IsBool( LI ) then
            return fail;
        fi;
        
        if HasIsInvertibleMatrix( RI ) and IsInvertibleMatrix( RI ) then
            SetIsInvertibleMatrix( LI, true );
        else
            SetIsRightInvertibleMatrix( LI, true );
        fi;
        
        SetRightInverse( LI, RI );
        
        SetNrColumns( LI, NrRows( RI ) );
        
        if NrRows( RI ) = NrColumns( RI ) then
            ## a left inverse of a ring element is unique
            ## and coincides with the right inverse
            SetRightInverse( RI, LI );
            SetLeftInverse( LI, RI );
        fi;
        
        return LI;
        
    end );
  
  
  5.5-3 RightInverse
  
  RightInverse( LI )  method
  Returns:  a homalg matrix or fail
  
  The  right  inverse  of the matrix LI. The lazy version of this operation is
  RightInverseLazy (5.5-5). (--> LeftDivide (5.5-46))
  
    Code  
    InstallMethod( RightInverse,
            "for homalg matrices",
            [ IsHomalgMatrix ],
            
      function( LI )
        local Id, RI;
        
        Id := HomalgIdentityMatrix( NrRows( LI ), HomalgRing( LI ) );
        
        RI := LeftDivide( LI, Id );	## ( cf. [BR08, Subsection 3.1.3] )
        
        ## CAUTION: for the following SetXXX LeftDivide is assumed
        ## NOT to be lazy evaluated!!!
        
        SetIsRightInvertibleMatrix( LI, IsHomalgMatrix( RI ) );
        
        if IsBool( RI ) then
            return fail;
        fi;
        
        if HasIsInvertibleMatrix( LI ) and IsInvertibleMatrix( LI ) then
            SetIsInvertibleMatrix( RI, true );
        else
            SetIsLeftInvertibleMatrix( RI, true );
        fi;
        
        SetLeftInverse( RI, LI );
        
        SetNrRows( RI, NrColumns( LI ) );
        
        if NrRows( LI ) = NrColumns( LI ) then
            ## a right inverse of a ring element is unique
            ## and coincides with the left inverse
            SetLeftInverse( LI, RI );
            SetRightInverse( RI, LI );
        fi;
        
        return RI;
        
    end );
  
  
  5.5-4 LeftInverseLazy
  
  LeftInverseLazy( M )  operation
  Returns:  a homalg matrix
  
  A  lazy  evaluated left inverse C of the matrix M. If no left inverse exists
  then Eval( C ) will issue an error.
  
  (for the installed standard method see Eval (C.4-5))
  
  5.5-5 RightInverseLazy
  
  RightInverseLazy( M )  operation
  Returns:  a homalg matrix
  
  A lazy evaluated right inverse C of the matrix M. If no right inverse exists
  then Eval( C ) will issue an error.
  
  (for the installed standard method see Eval (C.4-6))
  
  5.5-6 Involution
  
  Involution( M )  method
  Returns:  a homalg matrix
  
  The twisted transpose of the homalg matrix M.
  
  (for the installed standard method see Eval (C.4-7))
  
  5.5-7 CertainRows
  
  CertainRows( M, plist )  method
  Returns:  a homalg matrix
  
  The  matrix  of  which  the i-th row is the k-th row of the homalg matrix M,
  where k=plist[i].
  
  (for the installed standard method see Eval (C.4-8))
  
  5.5-8 CertainColumns
  
  CertainColumns( M, plist )  method
  Returns:  a homalg matrix
  
  The  matrix of which the j-th column is the l-th column of the homalg matrix
  M, where l=plist[i].
  
  (for the installed standard method see Eval (C.4-9))
  
  5.5-9 UnionOfRows
  
  UnionOfRows( A, B )  method
  Returns:  a homalg matrix
  
  Stack the two homalg matrices A and B.
  
  (for the installed standard method see Eval (C.4-10))
  
  5.5-10 UnionOfColumns
  
  UnionOfColumns( A, B )  method
  Returns:  a homalg matrix
  
  Augment the two homalg matrices A and B.
  
  (for the installed standard method see Eval (C.4-11))
  
  5.5-11 DiagMat
  
  DiagMat( list )  method
  Returns:  a homalg matrix
  
  Build  the  block diagonal matrix out of the homalg matrices listed in list.
  An  error  is  issued  if  list is empty or if one of the arguments is not a
  homalg matrix.
  
  (for the installed standard method see Eval (C.4-12))
  
  5.5-12 KroneckerMat
  
  KroneckerMat( A, B )  method
  Returns:  a homalg matrix
  
  The Kronecker (or tensor) product of the two homalg matrices A and B.
  
  (for the installed standard method see Eval (C.4-13))
  
  5.5-13 \*
  
  \*( a, A )  method
  Returns:  a homalg matrix
  
  The product of the ring element a with the homalg matrix A (enter: a * A;).
  
  (for the installed standard method see Eval (C.4-14))
  
  5.5-14 \+
  
  \+( A, B )  method
  Returns:  a homalg matrix
  
  The sum of the two homalg matrices A and B (enter: A + B;).
  
  (for the installed standard method see Eval (C.4-15))
  
  5.5-15 \-
  
  \-( A, B )  method
  Returns:  a homalg matrix
  
  The difference of the two homalg matrices A and B (enter: A - B;).
  
  (for the installed standard method see Eval (C.4-16))
  
  5.5-16 \*
  
  \*( A, B )  method
  Returns:  a homalg matrix
  
  The matrix product of the two homalg matrices A and B (enter: A * B;).
  
  (for the installed standard method see Eval (C.4-17))
  
  5.5-17 \=
  
  \=( A, B )  operation
  Returns:  true or false
  
  Check  if  the  homalg  matrices  A  and B are equal (enter: A = B;), taking
  possible ring relations into account.
  
  (for the installed standard method see AreEqualMatrices (B.2-1))
  
    Example  
    gap> ZZ := HomalgRingOfIntegers( );
    Z
    gap> A := HomalgMatrix( "[ 1 ]", ZZ );
    <A 1 x 1 matrix over an internal ring>
    gap> B := HomalgMatrix( "[ 3 ]", ZZ );
    <A 1 x 1 matrix over an internal ring>
    gap> Z2 := ZZ / 2;
    Z/( 2 )
    gap> A := Z2 * A;
    <A 1 x 1 matrix over a residue class ring>
    gap> B := Z2 * B;
    <A 1 x 1 matrix over a residue class ring>
    gap> Display( A );
    [ [  1 ] ]
    
    modulo [ 2 ]
    gap> Display( B );
    [ [  3 ] ]
    
    modulo [ 2 ]
    gap> A = B;
    true
  
  
  5.5-18 GetColumnIndependentUnitPositions
  
  GetColumnIndependentUnitPositions( A, poslist )  operation
  Returns:  a (possibly empty) list of pairs of positive integers
  
  The  list  of column independet unit position of the matrix A. We say that a
  unit  A[i,k]  is column independet from the unit A[l,j] if i>l and A[l,k]=0.
  The  rows are scanned from top to bottom and within each row the columns are
  scanned  from right to left searching for new units, column independent from
  the preceding ones. If A[i,k] is a new column independent unit then [i,k] is
  added to the output list. If A has no units the empty list is returned.
  
  (for  the  installed  standard  method see GetColumnIndependentUnitPositions
  (B.2-6))
  
  5.5-19 GetRowIndependentUnitPositions
  
  GetRowIndependentUnitPositions( A, poslist )  operation
  Returns:  a (possibly empty) list of pairs of positive integers
  
  The list of row independet unit position of the matrix A. We say that a unit
  A[k,j]  is  row  independet  from  the  unit A[i,l] if j>l and A[k,l]=0. The
  columns  are  scanned from left to right and within each column the rows are
  scanned from bottom to top searching for new units, row independent from the
  preceding  ones.  If  A[k,j]  is  a new row independent unit then [j,k] (yes
  [j,k])  is  added  to  the  output list. If A has no units the empty list is
  returned.
  
  (for   the  installed  standard  method  see  GetRowIndependentUnitPositions
  (B.2-7))
  
  5.5-20 GetUnitPosition
  
  GetUnitPosition( A, poslist )  operation
  Returns:  a (possibly empty) list of pairs of positive integers
  
  The  position [i,j] of the first unit A[i,j] in the matrix A, where the rows
  are  scanned  from top to bottom and within each row the columns are scanned
  from  left  to  right.  If A[i,j] is the first occurrence of a unit then the
  position pair [i,j] is returned. Otherwise fail is returned.
  
  (for the installed standard method see GetUnitPosition (B.2-8))
  
  5.5-21 Eliminate
  
  Eliminate( rel, indets )  operation
  Returns:  a homalg matrix
  
  Eliminate the independents indets from the matrix (or list of ring elements)
  rel,  i.e. compute a generating set of the ideal defined as the intersection
  of  the  ideal  generated  by  the  entries of the list rel with the subring
  generated  by  all  indeterminates  except  those  in indets. by the list of
  indeterminates indets.
  
  5.5-22 BasisOfRowModule
  
  BasisOfRowModule( M )  operation
  Returns:  a homalg matrix
  
  Let  R be the ring over which M is defined (R:=HomalgRing( M )) and S be the
  row  span  of M, i.e. the R-submodule of the free module R^(1 × NrColumns( M
  ))  spanned by the rows of M. A solution to the submodule membership problem
  is  an  algorithm which can decide if an element m in R^(1 × NrColumns( M ))
  is  contained  in  S  or  not. And exactly like the Gaussian (resp. Hermite)
  normal  form when R is a field (resp. principal ideal ring), the row span of
  the  resulting  matrix B coincides with the row span S of M, and computing B
  is typically the first step of such an algorithm. (--> Appendix A)
  
  5.5-23 BasisOfColumnModule
  
  BasisOfColumnModule( M )  operation
  Returns:  a homalg matrix
  
  Let  R be the ring over which M is defined (R:=HomalgRing( M )) and S be the
  column  span  of M, i.e. the R-submodule of the free module R^(NrRows( M ) ×
  1)  spanned  by  the  columns  of  M. A solution to the submodule membership
  problem is an algorithm which can decide if an element m in R^(NrRows( M ) ×
  1)  is  contained in S or not. And exactly like the Gaussian (resp. Hermite)
  normal  form when R is a field (resp. principal ideal ring), the column span
  of  the  resulting  matrix  B  coincides  with  the  column span S of M, and
  computing  B is typically the first step of such an algorithm. (--> Appendix
  A)
  
  5.5-24 DecideZeroRows
  
  DecideZeroRows( A, B )  operation
  Returns:  a homalg matrix
  
  Let  A  and B be matrices having the same number of columns and defined over
  the  same  ring  R  (:=HomalgRing( A )) and S be the row span of B, i.e. the
  R-submodule of the free module R^(1 × NrColumns( B )) spanned by the rows of
  B.  The  result is a matrix C having the same shape as A, for which the i-th
  row  C^i is equivalent to the i-th row A^i of A modulo S, i.e. C^i-A^i is an
  element  of  the row span S of B. Moreover, the row C^i is zero, if and only
  if the row A^i is an element of S. So DecideZeroRows decides which rows of A
  are zero modulo the rows of B. (--> Appendix A)
  
  5.5-25 DecideZeroColumns
  
  DecideZeroColumns( A, B )  operation
  Returns:  a homalg matrix
  
  Let  A and B be matrices having the same number of rows and defined over the
  same  ring  R  (:=HomalgRing(  A  )) and S be the column span of B, i.e. the
  R-submodule of the free module R^(NrRows( B ) × 1) spanned by the columns of
  B.  The  result is a matrix C having the same shape as A, for which the i-th
  column  C_i is equivalent to the i-th column A_i of A modulo S, i.e. C_i-A_i
  is  an  element of the column span S of B. Moreover, the column C_i is zero,
  if  and  only  if  the  column  A_i is an element of S. So DecideZeroColumns
  decides  which  columns of A are zero modulo the columns of B. (--> Appendix
  A)
  
  5.5-26 SyzygiesGeneratorsOfRows
  
  SyzygiesGeneratorsOfRows( M )  operation
  Returns:  a homalg matrix
  
  Let  R  be the ring over which M is defined (R:=HomalgRing( M )). The matrix
  of  row  syzygies  SyzygiesGeneratorsOfRows( M ) is a matrix whose rows span
  the left kernel of M, i.e. the R-submodule of the free module R^(1 × NrRows(
  M )) consisting of all rows X satisfying XM=0. (--> Appendix A)
  
  5.5-27 SyzygiesGeneratorsOfColumns
  
  SyzygiesGeneratorsOfColumns( M )  operation
  Returns:  a homalg matrix
  
  Let  R  be the ring over which M is defined (R:=HomalgRing( M )). The matrix
  of  column  syzygies  SyzygiesGeneratorsOfColumns(  M  )  is  a matrix whose
  columns  span the right kernel of M, i.e. the R-submodule of the free module
  R^(NrColumns(  M  )  ×  1) consisting of all columns X satisfying MX=0. (-->
  Appendix A)
  
  5.5-28 SyzygiesGeneratorsOfRows
  
  SyzygiesGeneratorsOfRows( M, M2 )  operation
  Returns:  a homalg matrix
  
  Let  R  be the ring over which M is defined (R:=HomalgRing( M )). The matrix
  of relative row syzygies SyzygiesGeneratorsOfRows( M, M2 ) is a matrix whose
  rows  span  the left kernel of M modulo M2, i.e. the R-submodule of the free
  module  R^(1 × NrRows( M )) consisting of all rows X satisfying XM+YM2=0 for
  some row Y ∈ R^(1 × NrRows( M2 )). (--> Appendix A)
  
  5.5-29 SyzygiesGeneratorsOfColumns
  
  SyzygiesGeneratorsOfColumns( M, M2 )  operation
  Returns:  a homalg matrix
  
  Let  R  be the ring over which M is defined (R:=HomalgRing( M )). The matrix
  of relative column syzygies SyzygiesGeneratorsOfColumns( M, M2 ) is a matrix
  whose  columns span the right kernel of M modulo M2, i.e. the R-submodule of
  the  free  module  R^(NrColumns(  M  )  ×  1)  consisting  of  all columns X
  satisfying  MX+M2Y=0  for  some  column  Y  ∈  R^(NrColumns( M2 ) × 1). (-->
  Appendix A)
  
  5.5-30 ReducedBasisOfRowModule
  
  ReducedBasisOfRowModule( M )  operation
  Returns:  a homalg matrix
  
  Like  BasisOfRowModule(  M  ) but where the matrix SyzygiesGeneratorsOfRows(
  ReducedBasisOfRowModule(  M  )  )  contains  no  units.  This  can easily be
  achieved    starting    from    B:=BasisOfRowModule(    M   )   (and   using
  GetColumnIndependentUnitPositions  (5.5-18)  applied  to  the  matrix of row
  syzygies of B, etc). (--> Appendix A)
  
  5.5-31 ReducedBasisOfColumnModule
  
  ReducedBasisOfColumnModule( M )  operation
  Returns:  a homalg matrix
  
  Like     BasisOfColumnModule(     M     )     but     where    the    matrix
  SyzygiesGeneratorsOfColumns(  ReducedBasisOfColumnModule(  M ) ) contains no
  units. This can easily be achieved starting from B:=BasisOfColumnModule( M )
  (and  using GetRowIndependentUnitPositions (5.5-19) applied to the matrix of
  column syzygies of B, etc.). (--> Appendix A)
  
  5.5-32 ReducedSyzygiesGeneratorsOfRows
  
  ReducedSyzygiesGeneratorsOfRows( M )  operation
  Returns:  a homalg matrix
  
  Like    SyzygiesGeneratorsOfRows(    M    )    but    where    the    matrix
  SyzygiesGeneratorsOfRows( ReducedSyzygiesGeneratorsOfRows( M ) ) contains no
  units.     This     can     easily     be     achieved     starting     from
  C:=SyzygiesGeneratorsOfRows(          M         )         (and         using
  GetColumnIndependentUnitPositions  (5.5-18)  applied  to  the  matrix of row
  syzygies of C, etc.). (--> Appendix A)
  
  5.5-33 ReducedSyzygiesGeneratorsOfColumns
  
  ReducedSyzygiesGeneratorsOfColumns( M )  operation
  Returns:  a homalg matrix
  
  Like    SyzygiesGeneratorsOfColumns(    M    )    but   where   the   matrix
  SyzygiesGeneratorsOfColumns(   ReducedSyzygiesGeneratorsOfColumns(   M  )  )
  contains   no   units.   This   can   easily   be   achieved  starting  from
  C:=SyzygiesGeneratorsOfColumns(         M         )        (and        using
  GetRowIndependentUnitPositions  (5.5-19)  applied  to  the  matrix of column
  syzygies of C, etc.). (--> Appendix A)
  
  5.5-34 BasisOfRowsCoeff
  
  BasisOfRowsCoeff( M, T )  operation
  Returns:  a homalg matrix
  
  Returns  B:=BasisOfRowModule(  M  )  and  assigns  the  void  matrix  T (-->
  HomalgVoidMatrix (5.2-5)) such that B = T M. (--> Appendix A)
  
  5.5-35 BasisOfColumnsCoeff
  
  BasisOfColumnsCoeff( M, T )  operation
  Returns:  a homalg matrix
  
  Returns  B:=BasisOfRowModule(  M  )  and  assigns  the  void  matrix  T (-->
  HomalgVoidMatrix (5.2-5)) such that B = M T. (--> Appendix A)
  
  5.5-36 DecideZeroRowsEffectively
  
  DecideZeroRowsEffectively( A, B, T )  operation
  Returns:  a homalg matrix
  
  Returns  M:=DecideZeroRows(  A,  B  )  and  assigns  the  void matrix T (-->
  HomalgVoidMatrix (5.2-5)) such that M = A + TB. (--> Appendix A)
  
  5.5-37 DecideZeroColumnsEffectively
  
  DecideZeroColumnsEffectively( A, B, T )  operation
  Returns:  a homalg matrix
  
  Returns  M:=DecideZeroColumns(  A,  B  )  and assigns the void matrix T (-->
  HomalgVoidMatrix (5.2-5)) such that M = A + BT. (--> Appendix A)
  
  5.5-38 BasisOfRows
  
  BasisOfRows( M )  operation
  BasisOfRows( M, T )  operation
  Returns:  a homalg matrix
  
  With  one  argument  it  is a synonym of BasisOfRowModule (5.5-22). with two
  arguments it is a synonym of BasisOfRowsCoeff (5.5-34).
  
  5.5-39 BasisOfColumns
  
  BasisOfColumns( M )  operation
  BasisOfColumns( M, T )  operation
  Returns:  a homalg matrix
  
  With  one argument it is a synonym of BasisOfColumnModule (5.5-23). with two
  arguments it is a synonym of BasisOfColumnsCoeff (5.5-35).
  
  5.5-40 DecideZero
  
  DecideZero( mat, rel )  operation
  Returns:  a homalg matrix
  
    Code  
    InstallMethod( DecideZero,
            "for sets of ring relations",
            [ IsHomalgMatrix, IsHomalgRingRelations ],
            
      function( mat, rel )
        
        return DecideZero( mat,  MatrixOfRelations( rel ) );
        
    end );
  
  
  5.5-41 SyzygiesOfRows
  
  SyzygiesOfRows( M )  operation
  SyzygiesOfRows( M, M2 )  operation
  Returns:  a homalg matrix
  
  With one argument it is a synonym of SyzygiesGeneratorsOfRows (5.5-26). with
  two arguments it is a synonym of SyzygiesGeneratorsOfRows (5.5-28).
  
  5.5-42 SyzygiesOfColumns
  
  SyzygiesOfColumns( M )  operation
  SyzygiesOfColumns( M, M2 )  operation
  Returns:  a homalg matrix
  
  With  one  argument it is a synonym of SyzygiesGeneratorsOfColumns (5.5-27).
  with two arguments it is a synonym of SyzygiesGeneratorsOfColumns (5.5-29).
  
  5.5-43 ReducedSyzygiesOfRows
  
  ReducedSyzygiesOfRows( M )  operation
  ReducedSyzygiesOfRows( M, M2 )  operation
  Returns:  a homalg matrix
  
  With  one  argument  it  is  a  synonym  of  ReducedSyzygiesGeneratorsOfRows
  (5.5-32).    With    two   arguments   it   calls   ReducedBasisOfRowModule(
  SyzygiesGeneratorsOfRows(  M,  M2 ) ). (--> ReducedBasisOfRowModule (5.5-30)
  and SyzygiesGeneratorsOfRows (5.5-28))
  
  5.5-44 ReducedSyzygiesOfColumns
  
  ReducedSyzygiesOfColumns( M )  operation
  ReducedSyzygiesOfColumns( M, M2 )  operation
  Returns:  a homalg matrix
  
  With  one  argument  it  is  a synonym of ReducedSyzygiesGeneratorsOfColumns
  (5.5-33).   With   two   arguments   it   calls  ReducedBasisOfColumnModule(
  SyzygiesGeneratorsOfColumns(  M,  M2  )  ).  (--> ReducedBasisOfColumnModule
  (5.5-31) and SyzygiesGeneratorsOfColumns (5.5-29))
  
  5.5-45 RightDivide
  
  RightDivide( B, A )  operation
  Returns:  a homalg matrix or fail
  
  Let  B  and A be matrices having the same number of columns and defined over
  the  same  ring.  The matrix RightDivide( B, A ) is a particular solution of
  the  inhomogeneous (one sided) linear system of equations XA=B in case it is
  solvable. Otherwise fail is returned. The name RightDivide suggests X=BA^-1.
  This  generalizes  LeftInverse  (5.5-2)  for  which  B  becomes the identity
  matrix. (--> SyzygiesGeneratorsOfRows (5.5-26))
  
  5.5-46 LeftDivide
  
  LeftDivide( A, B )  operation
  Returns:  a homalg matrix or fail
  
  Let  A and B be matrices having the same number of rows and defined over the
  same  ring.  The  matrix  LeftDivide( A, B ) is a particular solution of the
  inhomogeneous  (one  sided)  linear  system  of equations AX=B in case it is
  solvable.  Otherwise fail is returned. The name LeftDivide suggests X=A^-1B.
  This  generalizes  RightInverse  (5.5-3)  for  which  B becomes the identity
  matrix. (--> SyzygiesGeneratorsOfColumns (5.5-27))
  
  5.5-47 RightDivide
  
  RightDivide( B, A, L )  operation
  Returns:  a homalg matrix or fail
  
  Let  B,  A  and  L be matrices having the same number of columns and defined
  over  the  same  ring.  The  matrix  RightDivide(  B, A, L ) is a particular
  solution of the inhomogeneous (one sided) linear system of equations XA+YL=B
  in  case  it  is solvable (for some Y which is forgotten). Otherwise fail is
  returned.  The  name  RightDivide  suggests  X=BA^-1  modulo  L. (Cf. [BR08,
  Subsection 3.1.1])
  
    Code  
    InstallMethod( RightDivide,
            "for homalg matrices",
            [ IsHomalgMatrix, IsHomalgMatrix, IsHomalgMatrix ],
            
      function( B, A, L )	## CAUTION: Do not use lazy evaluation here!!!
        local R, BL, ZA, AL, CA, IAL, ZB, CB, NF, X;
        
        R := HomalgRing( B );
        
        BL := BasisOfRows( L );
        
        ## first reduce A modulo L
        ZA := DecideZeroRows( A, BL );
        
        AL := UnionOfRows( ZA, BL );
        
        ## CA * AL = IAL
        CA := HomalgVoidMatrix( R );
        IAL := BasisOfRows( AL, CA );
        
        ## also reduce B modulo L
        ZB := DecideZeroRows( B, BL );
        
        ## knowing this will avoid computations
        IsOne( IAL );
        
        ## IsSpecialSubidentityMatrix( IAL );	## does not increase performance
        
        ## NF = ZB + CB * IAL
        CB := HomalgVoidMatrix( R );
        NF := DecideZeroRowsEffectively( ZB, IAL, CB );
        
        ## NF <> 0
        if not IsZero( NF ) then
            return fail;
        fi;
        
        ## CD = -CB * CA => CD * A = B
        X := -CB * CertainColumns( CA, [ 1 .. NrRows( A ) ] );
        
        ## check assertion
        Assert( 5, IsZero( DecideZeroRows( X * A - B, BL ) ) );
        
        return X;
        
        ## technical: -CB * CA := (-CB) * CA and COLEM should take over
        ## since CB := -matrix
        
    end );
  
  
  5.5-48 LeftDivide
  
  LeftDivide( A, B, L )  operation
  Returns:  a homalg matrix or fail
  
  Let  A,  B  and  L be matrices having the same number of columns and defined
  over  the  same  ring.  The  matrix  LeftDivide(  A,  B, L ) is a particular
  solution of the inhomogeneous (one sided) linear system of equations AX+LY=B
  in  case  it  is solvable (for some Y which is forgotten). Otherwise fail is
  returned.  The  name  LeftDivide  suggests  X=A^-1B  modulo  L.  (Cf. [BR08,
  Subsection 3.1.1])
  
    Code  
    InstallMethod( LeftDivide,
            "for homalg matrices",
            [ IsHomalgMatrix, IsHomalgMatrix, IsHomalgMatrix ],
            
      function( A, B, L )	## CAUTION: Do not use lazy evaluation here!!!
        local R, BL, ZA, AL, CA, IAL, ZB, CB, NF, X;
        
        R := HomalgRing( B );
        
        BL := BasisOfColumns( L );
        
        ## first reduce A modulo L
        ZA := DecideZeroColumns( A, BL );
        
        AL := UnionOfColumns( ZA, BL );
        
        ## AL * CA = IAL
        CA := HomalgVoidMatrix( R );
        IAL := BasisOfColumns( AL, CA );
        
        ## also reduce B modulo L
        ZB := DecideZeroColumns( B, BL );
        
        ## knowing this will avoid computations
        IsOne( IAL );
        
        ## IsSpecialSubidentityMatrix( IAL );	## does not increase performance
        
        ## NF = ZB + IAL * CB
        CB := HomalgVoidMatrix( R );
        NF := DecideZeroColumnsEffectively( ZB, IAL, CB );
        
        ## NF <> 0
        if not IsZero( NF ) then
            return fail;
        fi;
        
        ## CD = CA * -CB => A * CD = B
        X := CertainRows( CA, [ 1 .. NrColumns( A ) ] ) * -CB;
        
        ## check assertion
        Assert( 5, IsZero( DecideZeroColumns( A * X - B, BL ) ) );
        
        return X;
        
        ## technical: CA * -CB := CA * (-CB) and COLEM should take over since
        ## CB := -matrix
        
    end );
  
  
  5.5-49 GenerateSameRowModule
  
  GenerateSameRowModule( M, N )  operation
  Returns:  true or false
  
  Check  if  the  row span of M and of N are identical or not (--> RightDivide
  (5.5-45)).
  
  5.5-50 GenerateSameColumnModule
  
  GenerateSameColumnModule( M, N )  operation
  Returns:  true or false
  
  Check  if the column span of M and of N are identical or not (--> LeftDivide
  (5.5-46)).