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 );  gap> HasIsZero( z ); false gap> IsZero( z ); true gap> z;  gap> HasIsZero( z ); false   Example  gap> n := HomalgInitialMatrix( 2, 3, ZZ );  gap> SetMatElm( n, 1, 1, "1" ); gap> SetMatElm( n, 2, 3, "1" ); gap> MakeImmutable( n );  gap> Display( n ); [ [ 1, 0, 0 ],  [ 0, 0, 1 ] ] gap> IsZero( n ); false gap> n;   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 );  gap> HasIsOne( id ); false gap> IsOne( id ); true gap> id;  gap> HasIsOne( id ); false   Example  gap> e := HomalgInitialIdentityMatrix( 3, ZZ );  gap> SetMatElm( e, 1, 2, "1" ); gap> SetMatElm( e, 2, 1, "-1" ); gap> MakeImmutable( e );  gap> Display( e ); [ [ 1, 1, 0 ],  [ -1, 1, 0 ],  [ 0, 0, 1 ] ] gap> IsOne( e ); false gap> e;   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 );  gap> Display( z ); [ [ 0, 0, 0 ],  [ 0, 0, 0 ] ] gap> z;   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 );  gap> Display( id ); [ [ 1, 0, 0 ],  [ 0, 1, 0 ],  [ 0, 0, 1 ] ] gap> id;   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 );  gap> Display( m ); [ [ 1, 2, 3 ],  [ 4, 5, 6 ] ]   Example  gap> m := HomalgMatrix( [ [ 1, 2, 3 ], [ 4, 5, 6 ] ], 2, 3, ZZ );  gap> Display( m ); [ [ 1, 2, 3 ],  [ 4, 5, 6 ] ]   Example  gap> m := HomalgMatrix( [ 1, 2, 3, 4, 5, 6 ], 2, 3, ZZ );  gap> Display( m ); [ [ 1, 2, 3 ],  [ 4, 5, 6 ] ]   Example  gap> m := HomalgMatrix( "[ [ 1, 2, 3 ], [ 4, 5, 6 ] ]", ZZ );  gap> Display( m ); [ [ 1, 2, 3 ],  [ 4, 5, 6 ] ]   Example  gap> m := HomalgMatrix( "[ [ 1, 2, 3 ], [ 4, 5, 6 ] ]", 2, 3, ZZ );  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 );  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 );  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 );  gap> Display( d ); [ [ 1, 0, 0 ],  [ 0, 2, 0 ],  [ 0, 0, 3 ] ] gap> d;   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 );  gap> d := HomalgDiagonalMatrix( [ 2 .. 4 ], ZZ );  gap> d2 := Z4 * d; ## or d2 := d * Z4;  gap> Display( d2 ); [ [ 2, 0, 0 ],  [ 0, 3, 0 ],  [ 0, 0, 4 ] ]  modulo [ 4 ] gap> d;  gap> ZeroRows( d ); [ ] gap> ZeroRows( d2 ); [ 3 ] gap> d;  gap> d2;   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 );  gap> Z2 := ZZ / 2; Z/( 2 ) gap> A := Z2 * A;  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 );  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 );  gap> B := HomalgMatrix( "[ 3 ]", ZZ );  gap> Z2 := ZZ / 2; Z/( 2 ) gap> A := Z2 * A;  gap> B := Z2 * B;  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)).