5.3-3 \in
In this chapter we describe the functionality in Semigroups for creating matrices over semirings. Only square matrices are currently supported. We use the term matrix to mean square matrix everywhere in this manual.
For reference, matrices over the following semirings are currently supported:
the set \(\{0, 1\}\) where \(0 + 0 = 0\), \(0 + 1 = 1 + 1 = 1 + 0 = 1\), \(1\cdot 0 = 0 \cdot 0 = 0 \cdot 1 = 0\), and \(1\cdot 1 = 1\).
the set of integers and negative infinity \(\mathbb{Z}\cup \{-\infty\}\) with operations max and plus.
the set of integers and infinity \(\mathbb{Z}\cup \{\infty\}\) with operations min and plus;
the set \(\{-\infty, 0, 1, \ldots, t\}\) for some threshold \(t\) with operations max and plus;
the set \(\{0, 1, \ldots, t, \infty\}\) for some threshold \(t\) with operations min and plus;
the semiring \(\mathbb{N}_{t,p} = \{0, 1, \ldots, t, t + 1, \ldots, t + p - 1\}\) for some threshold \(t\) and period \(p\) under addition and multiplication modulo the congruence \(t = t + p\);
the usual ring of integers;
the finite fields GF(q^d) for prime q and some positive integer d.
With the exception of matrices of finite fields, semigroups of matrices in Semigroups are of the second type described in Section 6.1. In other words, a version of the Froidure-Pin Algorithm [FP97] is used to compute semigroups of these types, i.e it is possible that all of the elements of such a semigroup are enumerated and stored in the memory of your computer.
In this section we describe the two main operations for creating matrices over semirings in Semigroups, and the categories, attributes, and operations which apply to every matrix over one of the semirings given at the start of this chapter.
There are several special methods for boolean matrices, which can be found in Section 5.3. There are also several special methods for finite fields, which can be found in section 5.4.
‣ IsMatrixOverSemiring( obj ) | ( category ) |
Returns: true or false.
Every matrix over a semiring in Semigroups is a member of the category IsMatrixOverSemiring, which is a subcategory of IsMultiplicativeElementWithOne (Reference: IsMultiplicativeElementWithOne), IsAssociativeElement (Reference: IsAssociativeElement), and IsPositionalObjectRep; see Reference: Representation.
Every matrix over a semiring in Semigroups is a square matrix.
Basic operations for matrices over semirings are: DimensionOfMatrixOverSemiring (5.1-3), TransposedMat (Reference: TransposedMat), and One (Reference: One).
‣ IsMatrixOverSemiringCollection( obj ) | ( category ) |
‣ IsMatrixOverSemiringCollColl( obj ) | ( category ) |
Returns: true or false.
Every collection of matrices over the same semiring belongs to the category IsMatrixOverSemiringCollection. For example, semigroups of matrices over a semiring belong to IsMatrixOverSemiringCollection.
Every collection of collections of matrices over the same semiring belongs to the category IsMatrixOverSemiringCollColl. For example, a list of semigroups of matrices over semirings belongs to IsMatrixOverSemiringCollColl.
‣ DimensionOfMatrixOverSemiring( mat ) | ( attribute ) |
Returns: A positive integer.
If mat is a matrix over a semiring (i.e. belongs to the category IsMatrixOverSemiring (5.1-1)), then mat is a square n by n matrix. DimensionOfMatrixOverSemiring returns the dimension n of mat.
gap> x := BooleanMat([[1, 0, 0, 1], > [0, 1, 1, 0], > [1, 0, 1, 1], > [0, 0, 0, 1]]); Matrix(IsBooleanMat, [[1, 0, 0, 1], [0, 1, 1, 0], [1, 0, 1, 1], [0, 0, 0, 1]]) gap> DimensionOfMatrixOverSemiring(x); 4
‣ DimensionOfMatrixOverSemiringCollection( coll ) | ( attribute ) |
Returns: A positive integer.
If coll is a collection of matrices over a semiring (i.e. belongs to the category IsMatrixOverSemiringCollection (5.1-2)), then the elements of coll are square n by n matrices. DimensionOfMatrixOverSemiringCollection returns the dimension n of these matrices.
gap> x := BooleanMat([[1, 0, 0, 1], > [0, 1, 1, 0], > [1, 0, 1, 1], > [0, 0, 0, 1]]); Matrix(IsBooleanMat, [[1, 0, 0, 1], [0, 1, 1, 0], [1, 0, 1, 1], [0, 0, 0, 1]]) gap> DimensionOfMatrixOverSemiringCollection(Semigroup(x)); 4
‣ Matrix( filt, mat[, threshold[, period]] ) | ( operation ) |
‣ Matrix( semiring, mat ) | ( operation ) |
Returns: A matrix over semiring.
This operation can be used to construct a matrix over a semiring in Semigroups.
In its first form, the first argument filt specifies the filter to be used to create the matrix, the second argument mat is a GAP matrix (i.e. a list of lists) compatible with filt, the third and fourth arguments threshold and period (if required) must be positive integers.
This must be one of the filters given in Section 5.1-8.
This must be a list of n lists each of length n (i.e. a square matrix), consisting of elements belonging to the underlying semiring described by filt, and threshold and period if present. An error is given if mat is not compatible with the other arguments.
For example, if filt is IsMaxPlusMatrix, then the entries of mat must belong to the max-plus semiring, i.e. they must be integers or -\(\infty\).
The supported semirings are fully described at the start of this chapter.
If filt is any of IsTropicalMaxPlusMatrix (5.1-8), IsTropicalMinPlusMatrix (5.1-8), or IsNTPMatrix (5.1-8), then this argument specifies the threshold of the underlying semiring of the matrix being created.
If filt is IsNTPMatrix (5.1-8), then this argument specifies the period of the underlying semiring of the matrix being created.
In its second form, the arguments should be a semiring semiring and matrix mat with entries in semiring. Currently, the only supported semirings are finite fields of prime order, and the integers Integers (Reference: Integers).
The function BooleanMat (5.3-1) is provided for specifically creating boolean matrices.
gap> Matrix(IsBooleanMat, [[1, 0, 0, 0], > [0, 0, 0, 0], > [1, 1, 1, 1], > [1, 0, 1, 1]]); Matrix(IsBooleanMat, [[1, 0, 0, 0], [0, 0, 0, 0], [1, 1, 1, 1], [1, 0, 1, 1]]) gap> Matrix(IsMaxPlusMatrix, [[4, 0, -2], > [1, -3, 0], > [5, -1, -4]]); Matrix(IsMaxPlusMatrix, [[4, 0, -2], [1, -3, 0], [5, -1, -4]]) gap> Matrix(IsMinPlusMatrix, [[-1, infinity], > [1, -1]]); Matrix(IsMinPlusMatrix, [[-1, infinity], [1, -1]]) gap> Matrix(IsTropicalMaxPlusMatrix, [[3, 2, 4], > [3, 1, 1], > [-infinity, 1, 1]], > 9); Matrix(IsTropicalMaxPlusMatrix, [[3, 2, 4], [3, 1, 1], [-infinity, 1, 1]], 9) gap> Matrix(IsTropicalMinPlusMatrix, [[1, 1, 1], > [0, 3, 0], > [1, 1, 3]], > 9); Matrix(IsTropicalMinPlusMatrix, [[1, 1, 1], [0, 3, 0], [1, 1, 3]], 9) gap> Matrix(IsNTPMatrix, [[0, 0, 0], > [2, 0, 1], > [2, 2, 2]], > 2, 1); Matrix(IsNTPMatrix, [[0, 0, 0], [2, 0, 1], [2, 2, 2]], 2, 1) gap> Matrix(Integers, [[-1, -2, 0], > [0, 3, -1], > [1, 0, -3]]); <3x3-matrix over Integers> gap> Matrix(Integers, [[-1, -2, 0], > [0, 3, -1], > [1, 0, -3]]); <3x3-matrix over Integers>
‣ AsMatrix( filt, mat ) | ( operation ) |
‣ AsMatrix( filt, mat, threshold ) | ( operation ) |
‣ AsMatrix( filt, mat, threshold, period ) | ( operation ) |
Returns: A matrix.
This operation can be used to change the representation of certain matrices over semirings. If mat is a matrix over a semiring (in the category IsMatrixOverSemiring (5.1-1)), then AsMatrix returns a new matrix corresponding to mat of the type specified by the filter filt, and if applicable the arguments threshold and period. The dimension of the matrix mat is not changed by this operation.
The version of the operation with arguments filt and mat can be applied to:
IsMinPlusMatrix (5.1-8) and a tropical min-plus matrix (i.e. convert a tropical min-plus matrix to a (non-tropical) min-plus matrix);
IsMaxPlusMatrix (5.1-8) and a tropical max-plus matrix;
The version of the operation with arguments filt, mat, and threshold can be applied to:
IsTropicalMinPlusMatrix (5.1-8), a tropical min-plus or min-plus matrix, and a value for the threshold of the resulting matrix.
IsTropicalMaxPlusMatrix (5.1-8) and a tropical max-plus, or max-plus matrix, and a value for the threshold of the resulting matrix.
The version of the operation with arguments filt, mat, threshold, and period can be applied to IsNTPMatrix (5.1-8) and an ntp matrix, or integer matrix.
When converting matrices with negative entries to an ntp, tropical max-plus, or tropical min-plus matrix, the entry is replaced with its absolute value.
When converting non-tropical matrices to tropical matrices entries higher than the specified threshold are reduced to the threshold.
gap> mat := Matrix(IsTropicalMinPlusMatrix, [[0, 1, 3], > [1, 1, 6], > [0, 4, 2]], 10);; gap> AsMatrix(IsMinPlusMatrix, mat); Matrix(IsMinPlusMatrix, [[0, 1, 3], [1, 1, 6], [0, 4, 2]]) gap> mat := Matrix(IsTropicalMaxPlusMatrix, [[-infinity, -infinity, 3], > [0, 1, 3], > [4, 1, 0]], 10);; gap> AsMatrix(IsMaxPlusMatrix, mat); Matrix(IsMaxPlusMatrix, [[-infinity, -infinity, 3], [0, 1, 3], [4, 1, 0]]) gap> mat := Matrix(IsNTPMatrix, [[1, 2, 2], > [0, 2, 0], > [1, 3, 0]], 4, 5);; gap> Matrix(Integers, mat); <3x3-matrix over Integers> gap> mat := Matrix(IsMinPlusMatrix, [[0, 1, 3], [1, 1, 6], [0, 4, 2]]);; gap> mat := AsMatrix(IsTropicalMinPlusMatrix, mat, 2); Matrix(IsTropicalMinPlusMatrix, [[0, 1, 2], [1, 1, 2], [0, 2, 2]], 2) gap> mat := AsMatrix(IsTropicalMinPlusMatrix, mat, 1); Matrix(IsTropicalMinPlusMatrix, [[0, 1, 1], [1, 1, 1], [0, 1, 1]], 1) gap> mat := Matrix(IsTropicalMaxPlusMatrix, [[-infinity, -infinity, 3], > [0, 1, 3], > [4, 1, 0]], 10);; gap> AsMatrix(IsTropicalMaxPlusMatrix, mat, 4); Matrix(IsTropicalMaxPlusMatrix, [[-infinity, -infinity, 3], [0, 1, 3], [4, 1, 0]], 4) gap> mat := Matrix(IsMaxPlusMatrix, [[-infinity, -infinity, 3], > [0, 1, 3], > [4, 1, 0]]);; gap> AsMatrix(IsTropicalMaxPlusMatrix, mat, 10); Matrix(IsTropicalMaxPlusMatrix, [[-infinity, -infinity, 3], [0, 1, 3], [4, 1, 0]], 10) gap> mat := Matrix(IsNTPMatrix, [[0, 1, 0], > [1, 3, 1], > [1, 0, 1]], 10, 10);; gap> mat := AsMatrix(IsNTPMatrix, mat, 5, 6); Matrix(IsNTPMatrix, [[0, 1, 0], [1, 3, 1], [1, 0, 1]], 5, 6) gap> mat := AsMatrix(IsNTPMatrix, mat, 2, 6); Matrix(IsNTPMatrix, [[0, 1, 0], [1, 3, 1], [1, 0, 1]], 2, 6) gap> mat := AsMatrix(IsNTPMatrix, mat, 2, 1); Matrix(IsNTPMatrix, [[0, 1, 0], [1, 2, 1], [1, 0, 1]], 2, 1) gap> mat := Matrix(Integers, mat); <3x3-matrix over Integers> gap> AsMatrix(IsNTPMatrix, mat, 1, 2); Matrix(IsNTPMatrix, [[0, 1, 0], [1, 2, 1], [1, 0, 1]], 1, 2)
‣ RandomMatrix( filt, dim[, threshold[, period]] ) | ( function ) |
‣ RandomMatrix( semiring, dim ) | ( function ) |
Returns: A matrix over semiring.
This operation can be used to construct a random matrix over a semiring in Semigroups. The usage of RandomMatrix is similar to that of Matrix (5.1-5).
In its first form, the first argument filt specifies the filter to be used to create the matrix, the second argument dim is dimension of the matrix, the third and fourth arguments threshold and period (if required) must be positive integers.
This must be one of the filters given in Section 5.1-8.
This must be a positive integer.
If filt is any of IsTropicalMaxPlusMatrix (5.1-8), IsTropicalMinPlusMatrix (5.1-8), or IsNTPMatrix (5.1-8), then this argument specifies the threshold of the underlying semiring of the matrix being created.
If filt is IsNTPMatrix (5.1-8), then this argument specifies the period of the underlying semiring of the matrix being created.
In its second form, the arguments should be a semiring semiring and dimension dim. Currently, the only supported semirings are finite fields of prime order and the integers Integers (Reference: Integers).
gap> RandomMatrix(IsBooleanMat, 3); Matrix(IsBooleanMat, [[1, 0, 0], [1, 0, 1], [1, 0, 1]]) gap> RandomMatrix(IsMaxPlusMatrix, 2); Matrix(IsMaxPlusMatrix, [[1, -infinity], [1, 0]]) gap> RandomMatrix(IsMinPlusMatrix, 3); Matrix(IsMinPlusMatrix, [[infinity, 2, infinity], [4, 0, -2], [1, -3, 0]]) gap> RandomMatrix(IsTropicalMaxPlusMatrix, 3, 5); Matrix(IsTropicalMaxPlusMatrix, [[5, 1, 4], [1, -infinity, 1], [1, 0, 2]], 5) gap> RandomMatrix(IsTropicalMinPlusMatrix, 3, 2); Matrix(IsTropicalMinPlusMatrix, [[1, -infinity, -infinity], [1, 1, 1], [2, 2, 1]], 2) gap> RandomMatrix(IsNTPMatrix, 3, 2, 5); Matrix(IsNTPMatrix, [[1, 1, 1], [1, 1, 0], [3, 0, 1]], 2, 5) gap> RandomMatrix(Integers, 2); Matrix(Integers, [[1, 3], [0, 0]]) gap> RandomMatrix(Integers, 2); Matrix(Integers, [[-1, 0], [0, -1]]) gap> RandomMatrix(GF(5), 1); Matrix(GF(5), [[Z(5)^0]])
‣ IsBooleanMat( obj ) | ( category ) |
‣ IsMatrixOverFiniteField( obj ) | ( category ) |
‣ IsMaxPlusMatrix( obj ) | ( category ) |
‣ IsMinPlusMatrix( obj ) | ( category ) |
‣ IsTropicalMatrix( obj ) | ( category ) |
‣ IsTropicalMaxPlusMatrix( obj ) | ( category ) |
‣ IsTropicalMinPlusMatrix( obj ) | ( category ) |
‣ IsNTPMatrix( obj ) | ( category ) |
‣ Integers( obj ) | ( category ) |
Returns: true or false.
Every matrix over a semiring in Semigroups is a member of one of these categories, which are subcategory of IsMatrixOverSemiring (5.1-1).
IsTropicalMatrix is a supercategory of IsTropicalMaxPlusMatrix and IsTropicalMinPlusMatrix.
Basic operations for matrices over semirings include: multiplication via \*, DimensionOfMatrixOverSemiring (5.1-3), One (Reference: One), the underlying list of lists used to create the matrix can be accessed using AsList (5.1-10), the rows of mat can be accessed using mat[i] where i is between 1 and the dimension of the matrix, it also possible to loop over the rows of a matrix; for tropical matrices ThresholdTropicalMatrix (5.1-11); for ntp matrices ThresholdNTPMatrix (5.1-12) and PeriodNTPMatrix (5.1-12).
For matrices over finite fields see Section 5.4; for Boolean matrices more details can be found in Section 5.3.
‣ IsBooleanMatCollection( obj ) | ( category ) |
‣ IsBooleanMatCollColl( obj ) | ( category ) |
‣ IsMatrixOverFiniteFieldCollection( obj ) | ( category ) |
‣ IsMatrixOverFiniteFieldCollColl( obj ) | ( category ) |
‣ IsMaxPlusMatrixCollection( obj ) | ( category ) |
‣ IsMaxPlusMatrixCollColl( obj ) | ( category ) |
‣ IsMinPlusMatrixCollection( obj ) | ( category ) |
‣ IsMinPlusMatrixCollColl( obj ) | ( category ) |
‣ IsTropicalMatrixCollection( obj ) | ( category ) |
‣ IsTropicalMaxPlusMatrixCollection( obj ) | ( category ) |
‣ IsTropicalMaxPlusMatrixCollColl( obj ) | ( category ) |
‣ IsTropicalMinPlusMatrixCollection( obj ) | ( category ) |
‣ IsTropicalMinPlusMatrixCollColl( obj ) | ( category ) |
‣ IsNTPMatrixCollection( obj ) | ( category ) |
‣ IsNTPMatrixCollColl( obj ) | ( category ) |
Returns: true or false.
Every collection of matrices over the same semiring in Semigroups belongs to one of the categories above. For example, semigroups of boolean matrices belong to IsBooleanMatCollection.
Similarly, every collection of collections of matrices over the same semiring in Semigroups belongs to one of the categories above.
‣ AsList( mat ) | ( attribute ) |
‣ AsMutableList( mat ) | ( operation ) |
Returns: A list of lists.
If mat is a matrix over a semiring (in the category IsMatrixOverSemiring (5.1-1)), then AsList returns the underlying list of lists of semiring elements corresponding to mat. In this case, the returned list and all of its entries are immutable.
The operation AsMutableList returns a mutable copy of the underlying list of lists of the matrix over semiring mat.
gap> mat := Matrix(IsNTPMatrix, > [[0, 1, 0], [1, 3, 1], [1, 0, 1]], 5, 6); Matrix(IsNTPMatrix, [[0, 1, 0], [1, 3, 1], [1, 0, 1]], 5, 6) gap> list := AsList(mat); [ [ 0, 1, 0 ], [ 1, 3, 1 ], [ 1, 0, 1 ] ] gap> IsMutable(list); false gap> IsMutable(list[1]); false gap> list := AsMutableList(mat); [ [ 0, 1, 0 ], [ 1, 3, 1 ], [ 1, 0, 1 ] ] gap> IsMutable(list); true gap> IsMutable(list[1]); true gap> mat = Matrix(IsNTPMatrix, AsList(mat), 5, 6); true
‣ ThresholdTropicalMatrix( mat ) | ( attribute ) |
Returns: A positive integer.
If mat is a tropical matrix (i.e. belongs to the category IsTropicalMatrix (5.1-8)), then ThresholdTropicalMatrix returns the threshold (i.e. the largest integer) of the underlying semiring.
gap> mat := Matrix(IsTropicalMaxPlusMatrix, > [[0, 3, 0, 2], > [1, 1, 1, 0], > [-infinity, 1, -infinity, 1], > [0, -infinity, 2, -infinity]], 10); Matrix(IsTropicalMaxPlusMatrix, [[0, 3, 0, 2], [1, 1, 1, 0], [-infinity, 1, -infinity, 1], [0, -infinity, 2, -infinity]], 10) gap> ThresholdTropicalMatrix(mat); 10 gap> mat := Matrix(IsTropicalMaxPlusMatrix, > [[0, 3, 0, 2], > [1, 1, 1, 0], > [-infinity, 1, -infinity, 1], > [0, -infinity, 2, -infinity]], 3); Matrix(IsTropicalMaxPlusMatrix, [[0, 3, 0, 2], [1, 1, 1, 0], [-infinity, 1, -infinity, 1], [0, -infinity, 2, -infinity]], 3) gap> ThresholdTropicalMatrix(mat); 3
‣ ThresholdNTPMatrix( mat ) | ( attribute ) |
‣ PeriodNTPMatrix( mat ) | ( attribute ) |
Returns: A positive integer.
An ntp matrix is a matrix with entries in a semiring \(\mathbb{N}_{t,p} = \{0, 1, \ldots, t, t + 1, \ldots, t + p - 1\}\) for some threshold \(t\) and period \(p\) under addition and multiplication modulo the congruence \(t = t + p\).
If mat is a ntp matrix (i.e. belongs to the category IsNTPMatrix (5.1-8)), then ThresholdNTPMatrix and PeriodNTPMatrix return the threshold and period of the underlying semiring, respectively.
gap> mat := Matrix(IsNTPMatrix, [[1, 1, 0], > [2, 1, 0], > [0, 1, 1]], > 1, 2); Matrix(IsNTPMatrix, [[1, 1, 0], [2, 1, 0], [0, 1, 1]], 1, 2) gap> ThresholdNTPMatrix(mat); 1 gap> PeriodNTPMatrix(mat); 2 gap> mat := Matrix(IsNTPMatrix, [[2, 1, 3], > [0, 5, 1], > [4, 1, 0]], > 3, 4); Matrix(IsNTPMatrix, [[2, 1, 3], [0, 5, 1], [4, 1, 0]], 3, 4) gap> ThresholdNTPMatrix(mat); 3 gap> PeriodNTPMatrix(mat); 4
mat1 * mat2returns the product of the matrices mat1 and mat2 of equal dimension over the same semiring using the usual matrix multiplication with the operations + and * from the underlying semiring.
mat1 < mat2returns true if when considered as a list of rows, the matrix mat1 is short-lex less than the matrix mat2, and false if this is not the case. This means that a matrix of lower dimension is less than a matrix of higher dimension.
mat1 = mat2returns true if the matrix mat1 equals the matrix mat2 (i.e. the entries are equal and the underlying semirings are equal) and returns false if it does not.
In this section we describe the operations, properties, and attributes in Semigroups specifically for Boolean matrices. These include:
NumberBooleanMat (5.3-6)
Successors (5.3-5)
IsRowTrimBooleanMat (5.3-9), IsColTrimBooleanMat (5.3-9), and IsTrimBooleanMat (5.3-9),
CanonicalBooleanMat (5.3-8)
IsSymmetricBooleanMat (5.3-10)
IsAntiSymmetricBooleanMat (5.3-13)
IsTransitiveBooleanMat (5.3-12)
IsReflexiveBooleanMat (5.3-11)
IsTotalBooleanMat (5.3-14)
IsOntoBooleanMat (5.3-14)
IsPartialOrderBooleanMat (5.3-15)
IsEquivalenceBooleanMat (5.3-16)
‣ BooleanMat( arg ) | ( function ) |
Returns: A boolean matrix.
BooleanMat returns the boolean matrix mat defined by its argument. The argument can be any of the following:
0 and/or 1the argument arg is list of n lists of length n consisting of the values 0 and 1;
true and/or falsethe argument arg is list of n lists of length n consisting of the values true and false;
the argument arg is list of n sublists of consisting of positive integers not greater than n. In this case, the entry j in the sublist in position i of arg indicates that the entry in position (i, j) of the created boolean matrix is true.
BooleanMat returns an error if the argument is not one of the above types.
gap> x := BooleanMat([[true, false], [true, true]]); Matrix(IsBooleanMat, [[1, 0], [1, 1]]) gap> y := BooleanMat([[1, 0], [1, 1]]); Matrix(IsBooleanMat, [[1, 0], [1, 1]]) gap> z := BooleanMat([[1], [1, 2]]); Matrix(IsBooleanMat, [[1, 0], [1, 1]]) gap> x = y; true gap> y = z; true gap> Display(x); 1 0 1 1
‣ AsBooleanMat( x[, n] ) | ( operation ) |
Returns: A boolean matrix.
AsBooleanMat returns the pbr, bipartition, permutation, transformation, or partial permutation x, as a boolean matrix of dimension n.
There are several possible arguments for AsBooleanMat:
If x is a permutation and n is a positive integer, then AsBooleanMat(x, n) returns the boolean matrix mat of dimension n such that mat[i][j] = true if and only if j = i ^ x.
If no positive integer n is specified, then the largest moved point of x is used as the value for n; see LargestMovedPoint (Reference: LargestMovedPoint for a permutation).
If x is a transformation and n is a positive integer such that x is a transformation of [1 .. n], then AsTransformation returns the boolean matrix mat of dimension n such that mat[i][j] = true if and only if j = i ^ x.
If the positive integer n is not specified, then the degree of f is used as the value for n.
If x is a partial permutation and n is a positive integer such that i ^ x <= n for all i in [1 .. n], then AsBooleanMat returns the boolean matrix mat of dimension n such that mat[i][j] = true if and only if j = i ^ x.
If the optional argument n is not present, then the default value of the maximum of degree and the codegree of x is used.
If x is a bipartition and n is any non-negative integer, then AsBooleanMat returns the boolean matrix mat of dimension n such that mat[i][j] = true if and only if i and j belong to the same block of x.
If the optional argument n is not present, then twice the degree of x is used by default.
If x is a pbr and n is any non-negative integer, then AsBooleanMat returns the boolean matrix mat of dimension n such that mat[i][j] = true if and only if i and j are related in x.
If the optional argument n is not present, then twice the degree of x is used by default.
gap> Display(AsBooleanMat((1, 2), 5)); 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 gap> Display(AsBooleanMat((1, 2))); 0 1 1 0 gap> x := Transformation([1, 3, 4, 1, 3]);; gap> Display(AsBooleanMat(x)); 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 gap> Display(AsBooleanMat(x, 4)); 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 gap> x := PartialPerm([1, 2, 3, 6, 8, 10], > [2, 6, 7, 9, 1, 5]); [3,7][8,1,2,6,9][10,5] gap> Display(AsBooleanMat(x)); 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 gap> x := Bipartition([[1, 4, -2, -3], [2, 3, 5, -5], [-1, -4]]); <bipartition: [ 1, 4, -2, -3 ], [ 2, 3, 5, -5 ], [ -1, -4 ]> gap> y := AsBooleanMat(x); <10x10 boolean matrix> gap> Display(y); 1 0 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 1 gap> IsEquivalenceBooleanMat(y); true gap> AsBooleanMat(x, 1); Matrix(IsBooleanMat, [[1]]) gap> Display(AsBooleanMat(x, 1)); 1 gap> Display(AsBooleanMat(x, 2)); 1 0 0 1 gap> Display(AsBooleanMat(x, 3)); 1 0 0 0 1 1 0 1 1 gap> Display(AsBooleanMat(x, 11)); 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 gap> x := PBR( > [[-1, 1], [2, 3], [-3, 2, 3]], > [[-1, 1, 2], [-3, -1, 1, 3], [-3, -1, 1, 2, 3]]);; gap> AsBooleanMat(x); Matrix(IsBooleanMat, [[1, 0, 0, 1, 0, 0], [0, 1, 1, 0, 0, 0], [0, 1, 1, 0, 0, 1], [1, 1, 0, 1, 0, 0], [1, 0, 1, 1, 0, 1], [1, 1, 1, 1, 0, 1]]) gap> Display(AsBooleanMat(x)); 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 1 0 1
5.3-3 \in‣ \in( mat1, mat2 ) | ( operation ) |
Returns: true or false.
If mat1 and mat2 are boolean matrices, then mat1 in mat2 returns true if the binary relation defined by mat1 is a subset of that defined by mat2.
gap> x := BooleanMat([[1, 0, 0, 1], [0, 0, 0, 0], > [1, 0, 1, 1], [0, 1, 1, 1]]);; gap> y := BooleanMat([[1, 0, 1, 0], [1, 1, 1, 0], > [0, 1, 1, 0], [1, 1, 1, 1]]);; gap> x in y; false gap> y in y; true
‣ OnBlist( blist, mat ) | ( function ) |
Returns: A boolean list.
If blist is a boolean list of length n and mat is boolean matrices of dimension n, then OnBlist returns the product of blist (thought of as a row vector over the boolean semiring) and mat.
gap> mat := BooleanMat([[1, 0, 0, 1], > [0, 0, 0, 0], > [1, 0, 1, 1], > [0, 1, 1, 1]]);; gap> blist := BlistList([1 .. 4], [1, 2]); [ true, true, false, false ] gap> OnBlist(blist, mat); [ true, false, false, true ]
‣ Successors( mat ) | ( attribute ) |
Returns: A list of lists of positive integers.
A row of a boolean matrix of dimension n can be thought of of as the characteristic function of a subset S of [1 .. n], i.e. i in S if and only if the ith component of the row equals \(1\). We refer to the subset S as the successors of the row.
If mat is a boolean matrix, then Successors returns the list of successors of the rows of mat.
gap> mat := BooleanMat([[1, 0, 1, 1], > [1, 0, 0, 0], > [0, 0, 1, 0], > [1, 1, 0, 0]]);; gap> Successors(mat); [ [ 1, 3, 4 ], [ 1 ], [ 3 ], [ 1, 2 ] ]
‣ BooleanMatNumber( m, n ) | ( operation ) |
‣ NumberBooleanMat( mat ) | ( operation ) |
Returns: A boolean matrix, or a positive integer.
These functions implement a bijection from the set of all boolean matrices of dimension n and the numbers [1 .. 2 ^ (n ^ 2)].
More precisely, if m and n are positive integers such that m is at most 2 ^ (n ^ 2), then BooleanMatNumber returns the mth n by n boolean matrix.
If mat is an n by n boolean matrix, then NumberBooleanMat returns the number in [1 .. 2 ^ (n ^ 2)] that corresponds to mat.
gap> mat := BooleanMat([[0, 1, 1, 0], > [1, 0, 1, 1], > [1, 1, 0, 1], > [0, 1, 0, 1]]);; gap> NumberBooleanMat(mat); 27606 gap> Display(BooleanMatNumber(27606, 4)); 0 1 1 0 1 0 1 1 1 1 0 1 0 1 0 1
‣ BlistNumber( m, n ) | ( function ) |
‣ NumberBlist( blist ) | ( function ) |
Returns: A boolean list, or a positive integer.
These functions implement a bijection from the set of all boolean lists of length n and the numbers [1 .. 2 ^ n].
More precisely, if m and n are positive integers such that m is at most 2 ^ n, then BlistNumber returns the mth boolean list of length n.
If blist is a boolean list of length n, then NumberBlist returns the number in [1 .. 2 ^ n] that corresponds to blist.
gap> blist := BlistList([1 .. 10], []); [ false, false, false, false, false, false, false, false, false, false ] gap> NumberBlist(blist); 1 gap> blist := BlistList([1 .. 10], [10]); [ false, false, false, false, false, false, false, false, false, true ] gap> NumberBlist(blist); 2 gap> BlistNumber(1, 10); [ false, false, false, false, false, false, false, false, false, false ] gap> BlistNumber(2, 10); [ false, false, false, false, false, false, false, false, false, true ]
‣ CanonicalBooleanMat( G, H, mat ) | ( operation ) |
‣ CanonicalBooleanMat( G, mat ) | ( operation ) |
‣ CanonicalBooleanMat( mat ) | ( attribute ) |
Returns: A boolean matrix.
This operation returns a fixed representative of the orbit of the boolean matrix mat under the action of the permutation group G on its rows and the permutation group H on its columns.
In its second form, when only a single permutation group G is specified, G acts on the rows and columns of mat independently.
In its third form, when only a boolean matrix is specified, CanonicalBooleanMat returns a fixed representative of the orbit of mat under the action of the symmetric group on its rows, and, independently, on its columns. In other words, CanonicalBooleanMat returns a canonical boolean matrix equivalent to mat up to rearranging rows and columns. This version of CanonicalBooleanMat uses Digraphs and its interface with the bliss library for computing automorphism groups and canonical forms of graphs [JK07]. As a consequence, CanonicalBooleanMat with a single argument is significantly faster than the versions with 2 or 3 arguments.
gap> mat := BooleanMat([[1, 1, 1, 0, 0, 0], > [0, 0, 0, 1, 0, 1], > [1, 0, 0, 1, 0, 1], > [0, 0, 0, 0, 0, 0], > [0, 1, 1, 1, 1, 1], > [0, 1, 1, 0, 1, 0]]); Matrix(IsBooleanMat, [[1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 0, 1], [1, 0, 0, 1, 0, 1], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 0, 1, 0]]) gap> CanonicalBooleanMat(mat); Matrix(IsBooleanMat, [[0, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0], [0, 0, 1, 1, 1, 0], [1, 1, 0, 0, 1, 0], [0, 0, 1, 1, 0, 1], [1, 1, 1, 1, 0, 1]]) gap> Display(CanonicalBooleanMat(mat)); 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 1 1 0 1 gap> Display(CanonicalBooleanMat(Group((1, 3)), mat)); 0 1 1 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 1 1 0 gap> Display(CanonicalBooleanMat(Group((1, 3)), Group(()), mat)); 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 0 1 0
‣ IsRowTrimBooleanMat( mat ) | ( property ) |
‣ IsColTrimBooleanMat( mat ) | ( property ) |
‣ IsTrimBooleanMat( mat ) | ( property ) |
Returns: true or false.
A row or column of a boolean matrix of dimension n can be thought of of as the characteristic function of a subset S of [1 .. n], i.e. i in S if and only if the ith component of the row or column equals 1.
A boolean matrix is row trim if no subset induced by a row of mat is contained in the subset induced by any other row of mat. Column trim is defined analogously. A boolean matrix is trim if it is both row and column trim.
gap> mat := BooleanMat([[0, 0, 1, 1], > [1, 0, 1, 0], > [1, 1, 0, 0], > [0, 1, 0, 1]]);; gap> IsTrimBooleanMat(mat); true gap> mat := BooleanMat([[0, 1, 1, 0], > [0, 0, 1, 0], > [1, 0, 0, 1], > [1, 0, 1, 0]]);; gap> IsRowTrimBooleanMat(mat); false gap> IsColTrimBooleanMat(mat); false
‣ IsSymmetricBooleanMat( mat ) | ( property ) |
Returns: true or false.
A boolean matrix is symmetric if it is symmetric about the main diagonal, i.e. mat[i][j] = mat[j][i] for all i, j in the range [1 .. n] where n is the dimension of mat.
gap> mat := BooleanMat([[0, 1, 1, 0], > [1, 0, 1, 1], > [1, 1, 0, 1], > [0, 1, 0, 1]]); Matrix(IsBooleanMat, [[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 0, 1]]) gap> IsSymmetricBooleanMat(mat); false gap> mat := BooleanMat([[0, 1, 1, 0], > [1, 0, 1, 1], > [1, 1, 0, 1], > [0, 1, 1, 1]]); Matrix(IsBooleanMat, [[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 1]]) gap> IsSymmetricBooleanMat(mat); true
‣ IsReflexiveBooleanMat( mat ) | ( property ) |
Returns: true or false.
A boolean matrix is reflexive if every entry in the main diagonal is true, i.e. mat[i][i] = true for all i in the range [1 .. n] where n is the dimension of mat.
gap> mat := BooleanMat([[1, 0, 0, 0], > [1, 1, 0, 0], > [0, 1, 0, 1], > [1, 1, 1, 1]]); Matrix(IsBooleanMat, [[1, 0, 0, 0], [1, 1, 0, 0], [0, 1, 0, 1], [1, 1, 1, 1]]) gap> IsReflexiveBooleanMat(mat); false gap> mat := BooleanMat([[1, 1, 1, 0], > [1, 1, 1, 1], > [1, 1, 1, 1], > [0, 1, 1, 1]]); Matrix(IsBooleanMat, [[1, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 1], [0, 1, 1, 1]]) gap> IsReflexiveBooleanMat(mat); true
‣ IsTransitiveBooleanMat( mat ) | ( property ) |
Returns: true or false.
A boolean matrix is transitive if whenever mat[i][j] = true and mat[j][k] = true then mat[i][k] = true.
gap> x := BooleanMat([[1, 0, 0, 1], > [1, 0, 1, 1], > [1, 1, 1, 0], > [0, 1, 1, 0]]); Matrix(IsBooleanMat, [[1, 0, 0, 1], [1, 0, 1, 1], [1, 1, 1, 0], [0, 1, 1, 0]]) gap> IsTransitiveBooleanMat(x); false gap> x := BooleanMat([[1, 1, 1, 1], > [1, 1, 1, 1], > [1, 1, 1, 1], > [1, 1, 1, 1]]); Matrix(IsBooleanMat, [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]) gap> IsTransitiveBooleanMat(x); true
‣ IsAntiSymmetricBooleanMat( mat ) | ( property ) |
Returns: true or false.
A boolean matrix is anti-symmetric if whenever mat[i][j] = true and mat[j][i] = true then i = j.
gap> x := BooleanMat([[1, 0, 0, 1], > [1, 0, 1, 1], > [1, 1, 1, 0], > [0, 1, 1, 0]]); Matrix(IsBooleanMat, [[1, 0, 0, 1], [1, 0, 1, 1], [1, 1, 1, 0], [0, 1, 1, 0]]) gap> IsAntiSymmetricBooleanMat(x); false gap> x := BooleanMat([[1, 0, 0, 1], > [1, 0, 1, 0], > [1, 0, 1, 0], > [0, 1, 1, 0]]); Matrix(IsBooleanMat, [[1, 0, 0, 1], [1, 0, 1, 0], [1, 0, 1, 0], [0, 1, 1, 0]]) gap> IsAntiSymmetricBooleanMat(x); true
‣ IsTotalBooleanMat( mat ) | ( property ) |
‣ IsOntoBooleanMat( mat ) | ( property ) |
Returns: true or false.
A boolean matrix is total if there is at least one entry in every row is true. Similarly, a boolean matrix is onto if at least one entry in every column is true.
gap> x := BooleanMat([[1, 0, 0, 1], > [1, 0, 1, 1], > [1, 1, 1, 0], > [0, 1, 1, 0]]); Matrix(IsBooleanMat, [[1, 0, 0, 1], [1, 0, 1, 1], [1, 1, 1, 0], [0, 1, 1, 0]]) gap> IsTotalBooleanMat(x); true gap> IsOntoBooleanMat(x); true gap> x := BooleanMat([[1, 0, 0, 1], > [1, 0, 1, 0], > [0, 0, 0, 0], > [0, 1, 1, 0]]); Matrix(IsBooleanMat, [[1, 0, 0, 1], [1, 0, 1, 0], [0, 0, 0, 0], [0, 1, 1, 0]]) gap> IsTotalBooleanMat(x); false gap> IsOntoBooleanMat(x); true
‣ IsPartialOrderBooleanMat( mat ) | ( property ) |
Returns: true or false.
A boolean matrix is a partial order if it is reflexive, transitive, and anti-symmetric.
gap> Number(FullBooleanMatMonoid(3), IsPartialOrderBooleanMat); 19
‣ IsEquivalenceBooleanMat( mat ) | ( property ) |
Returns: true or false.
A boolean matrix is an equivalence if it is reflexive, transitive, and symmetric.
gap> Number(FullBooleanMatMonoid(3), IsEquivalenceBooleanMat); 5 gap> Bell(3); 5
‣ IsTransformationBooleanMat( mat ) | ( property ) |
Returns: true or false.
A boolean matrix is a transformation if every row contains precisely one true value.
gap> Number(FullBooleanMatMonoid(3), IsTransformationBooleanMat); 27
In this section we describe some operations in Semigroups for matrices over finite fields that are required for such matrices to form semigroups satisfying IsActingSemigroup (6.1-2).
From v5.0.0, Semigroups uses the GAP library implementation of matrices over finite fields belonging to the category IsMatrixObj (Reference: IsMatrixObj) rather than the previous implementation in the Semigroups package. This means that from v5.0.0, matrices over a finite field no longer belong to the category IsMatrixOverSemiring (5.1-1).
The following methods are implemented in Semigroups for matrix objects over finite fields.
‣ RowSpaceBasis( m ) | ( attribute ) |
‣ RowSpaceTransformation( m ) | ( attribute ) |
‣ RowSpaceTransformationInv( m ) | ( attribute ) |
If m is a matrix object over a finite field, then to compute the value of any of the above attributes, a canonical basis for the row space of m is computed along with an invertible matrix RowSpaceTransformation such that m * RowSpaceTransformation(m) = RowSpaceBasis(m). RowSpaceTransformationInv(m) is the inverse of RowSpaceTransformation(m).
gap> x := Matrix(GF(4), Z(4) ^ 0 * [[1, 1, 0], [0, 1, 1], [1, 1, 1]]); [ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, Z(2)^0 ], [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] gap> RowSpaceBasis(x); <rowbasis of rank 3 over GF(2^2)> gap> RowSpaceTransformation(x); [ [ 0*Z(2), Z(2)^0, Z(2)^0 ], [ Z(2)^0, Z(2)^0, Z(2)^0 ], [ Z(2)^0, 0*Z(2), Z(2)^0 ] ]
‣ RightInverse( m ) | ( attribute ) |
‣ LeftInverse( m ) | ( attribute ) |
Returns: A matrix over a finite field.
These attributes contain a semigroup left-inverse, and a semigroup right-inverse of the matrix m respectively.
gap> x := Matrix(GF(4), Z(4) ^ 0 * [[1, 1, 0], [0, 0, 0], [1, 1, 1]]); [ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), 0*Z(2), 0*Z(2) ], [ Z(2)^0, Z(2)^0, Z(2)^0 ] ] gap> LeftInverse(x); [ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), 0*Z(2), 0*Z(2) ], [ Z(2)^0, 0*Z(2), Z(2)^0 ] ] gap> Display(LeftInverse(x) * x); 1 1 . . . . . . 1
In this section we describe operations in Semigroups specifically for integer matrices.
From v5.0.0, Semigroups uses the GAP library implementation of matrices over the integers belonging to the category IsMatrixObj (Reference: IsMatrixObj) rather than the previous implementation in the Semigroups package. This means that from v5.0.0, matrices over the integers no longer belong to the category IsMatrixOverSemiring (5.1-1).
The following methods are implemented in Semigroups for matrix objects over the integers.
‣ InverseOp( mat ) | ( operation ) |
Returns: An integer matrix.
If mat is an integer matrix (i.e. belongs to the category Integers (5.1-8)) whose inverse (if it exists) is also an integer matrix, then InverseOp returns the inverse of mat.
An integer matrix has an integer matrix inverse if and only if it has determinant one.
gap> mat := Matrix(Integers, [[0, 0, -1], > [0, 1, 0], > [1, 0, 0]]); <3x3-matrix over Integers> gap> InverseOp(mat); <3x3-matrix over Integers> gap> mat * InverseOp(mat) = One(mat); true
‣ IsTorsion( mat ) | ( attribute ) |
Returns: true or false
If mat is an integer matrix (i.e. belongs to the category Integers (5.1-8)), then IsTorsion returns true if mat is torsion and false otherwise.
An integer matrix mat is torsion if and only if there exists an integer n such that mat to the power of n is equal to the identity matrix.
gap> mat := Matrix(Integers, [[0, 0, -1], > [0, 1, 0], > [1, 0, 0]]); <3x3-matrix over Integers> gap> IsTorsion(mat); true gap> mat := Matrix(Integers, [[0, 0, -1, 0], > [0, -1, 0, 0], > [4, 4, 2, -1], > [1, 1, 0, 3]]); <4x4-matrix over Integers> gap> IsTorsion(mat); false
‣ Order( mat ) | ( attribute ) |
Returns: An integer or infinity.
If mat is an integer matrix, then InverseOp returns the order of mat. The order of mat is the smallest integer power of mat equal to the identity. If no such integer exists, the order is equal to infinity.
gap> mat := Matrix(Integers, [[0, 0, -1, 0], > [0, -1, 0, 0], > [4, 4, 2, -1], > [1, 1, 0, 3]]);; gap> Order(mat); infinity gap> mat := Matrix(Integers, [[0, 0, -1], > [0, 1, 0], > [1, 0, 0]]);; gap> Order(mat); 4
In this section we describe operations in Semigroups specifically for max-plus and min-plus matrices. These are in addition to those given elsewhere in this chapter for arbitrary matrices over semirings. These include:
InverseOp (5.6-1)
RadialEigenvector (5.6-2)
SpectralRadius (5.6-3)
UnweightedPrecedenceDigraph (5.6-4)
‣ InverseOp( mat ) | ( operation ) |
Returns: A max-plus matrix.
If mat is an invertible max-plus matrix (i.e. belongs to the category IsMaxPlusMatrix (5.1-8) and is a row permutation applied to the identity), then InverseOp returns the inverse of mat. This method is described in [Far09].
gap> InverseOp(Matrix(IsMaxPlusMatrix, [[-infinity, -infinity, 0], > [0, -infinity, -infinity], > [-infinity, 0, -infinity]])); Matrix(IsMaxPlusMatrix, [[-infinity, 0, -infinity], [-infinity, -infinity, 0], [0, -infinity, -infinity]])
‣ RadialEigenvector( mat ) | ( operation ) |
Returns: A vector.
If mat is a n by n max-plus matrix (i.e. belongs to the category IsMaxPlusMatrix (5.1-8)), then RadialEigenvector returns an eigenvector corresponding to the eigenvalue equal to the spectral radius of mat. This method is described in [Far09].
gap> RadialEigenvector(Matrix(IsMaxPlusMatrix, [[0, -3], [-2, -10]])); [ 0, -2 ]
‣ SpectralRadius( mat ) | ( operation ) |
Returns: A rational number.
If mat is a max-plus matrix (i.e. belongs to the category IsMaxPlusMatrix (5.1-8)), then SpectralRadius returns the supremum of the set of eigenvalues of mat. This method is described in [BFCGOGJ92].
gap> SpectralRadius(Matrix(IsMaxPlusMatrix, [[-infinity, 1, -4], > [2, -infinity, 0], > [0, 1, 1]])); 3/2
‣ UnweightedPrecedenceDigraph( mat ) | ( operation ) |
Returns: A digraph.
If mat is a max-plus matrix (i.e. belongs to the category IsMaxPlusMatrix (5.1-8)), then UnweightedPrecedenceDigraph returns the unweighted precedence digraph corresponding to mat.
For an n by n matrix mat, the unweighted precedence digraph is defined as the digraph with n vertices where vertex i is adjacent to vertex j if and only if mat[i][j] is not equal to -infinity.
gap> UnweightedPrecedenceDigraph(Matrix(IsMaxPlusMatrix, [[2, -2, 0], > [-infinity, 10, -2], [-infinity, 2, 1]])); <immutable digraph with 3 vertices, 7 edges>
In this section we describe operations and attributes in Semigroups specifically for matrix semigroups. These are in addition to those given elsewhere in this chapter for arbitrary matrices over semirings. These include:
Random matrix semigroups can be created by using the function RandomSemigroup (6.6-1). We can also create a matrix semigroup isomorphic to a given semigroup by using IsomorphismSemigroup (6.5-1) and AsSemigroup (6.5-3). These functions require a filter, and accept any of the filters in Section 5.7-1.
There are corresponding functions which can be used for matrix monoids: RandomMonoid (6.6-1), IsomorphismMonoid (6.5-2), and AsMonoid (6.5-4). These can be used with the filters in Section 5.7-2.
‣ IsMatrixOverSemiringSemigroup( obj ) | ( category ) |
‣ IsBooleanMatSemigroup( obj ) | ( category ) |
‣ IsMatrixOverFiniteFieldSemigroup( obj ) | ( category ) |
‣ IsMaxPlusMatrixSemigroup( obj ) | ( category ) |
‣ IsMinPlusMatrixSemigroup( obj ) | ( category ) |
‣ IsTropicalMatrixSemigroup( obj ) | ( category ) |
‣ IsTropicalMaxPlusMatrixSemigroup( obj ) | ( category ) |
‣ IsTropicalMinPlusMatrixSemigroup( obj ) | ( category ) |
‣ IsNTPMatrixSemigroup( obj ) | ( category ) |
‣ IsIntegerMatrixSemigroup( obj ) | ( category ) |
Returns: true or false.
The above are the currently supported types of matrix semigroups. For monoids see Section 5.7-2.
‣ IsMatrixOverSemiringMonoid( obj ) | ( category ) |
‣ IsBooleanMatMonoid( obj ) | ( category ) |
‣ IsMatrixOverFiniteFieldMonoid( obj ) | ( category ) |
‣ IsMaxPlusMatrixMonoid( obj ) | ( category ) |
‣ IsMinPlusMatrixMonoid( obj ) | ( category ) |
‣ IsTropicalMatrixMonoid( obj ) | ( category ) |
‣ IsTropicalMaxPlusMatrixMonoid( obj ) | ( category ) |
‣ IsTropicalMinPlusMatrixMonoid( obj ) | ( category ) |
‣ IsNTPMatrixMonoid( obj ) | ( category ) |
‣ IsIntegerMatrixMonoid( obj ) | ( category ) |
Returns: true or false.
The above are the currently supported types of matrix monoids. They correspond to the matrix semigroup types in Section 5.7-1.
‣ IsFinite( S ) | ( property ) |
Returns: true or false.
If S is a max-plus or min-plus matrix semigroup (i.e. belongs to the category IsMaxPlusMatrixSemigroup (5.7-1)), then IsFinite returns true if S is finite and false otherwise. This method is based on [Gau96] (max-plus) and [Sim78] (min-plus). For min-plus matrix semigroups, this method is only valid if each min-plus matrix in the semigroup contains only non-negative integers. Note, this method is terminating and does not involve enumerating semigroups.
gap> IsFinite(Semigroup(Matrix(IsMaxPlusMatrix, > [[0, -3], > [-2, -10]]))); true gap> IsFinite(Semigroup(Matrix(IsMaxPlusMatrix, > [[1, -infinity, 2], > [-2, 4, -infinity], > [1, 0, 3]]))); false gap> IsFinite(Semigroup(Matrix(IsMinPlusMatrix, > [[infinity, 0], > [5, 4]]))); false gap> IsFinite(Semigroup(Matrix(IsMinPlusMatrix, > [[1, 0], > [0, infinity]]))); true
‣ IsTorsion( S ) | ( attribute ) |
Returns: true or false.
If S is a max-plus matrix semigroup (i.e. belongs to the category IsMaxPlusMatrixSemigroup (5.7-1)), then IsTorsion returns true if S is torsion and false otherwise. This method is based on [Gau96] and draws on [Bur16], [BFCGOGJ92] and [Far09].
gap> IsTorsion(Semigroup(Matrix(IsMaxPlusMatrix, > [[0, -3], > [-2, -10]]))); true gap> IsTorsion(Semigroup(Matrix(IsMaxPlusMatrix, > [[1, -infinity, 2], > [-2, 4, -infinity], > [1, 0, 3]]))); false
‣ NormalizeSemigroup( S ) | ( operation ) |
Returns: A semigroup.
This method applies to max-plus matrix semigroups (i.e. those belonging to the category IsMaxPlusMatrixSemigroup (5.7-1)) that are finitely generated, such that the spectral radius of the matrix equal to the sum of the generators (with respect to the max-plus semiring) is zero. NormalizeSemigroup returns a semigroup of matrices all with strictly non-positive entries. Note that the output is isomorphic to a min-plus matrix semigroup. This method is based on [Gau96] and [Bur16].
gap> NormalizeSemigroup(Semigroup(Matrix(IsMaxPlusMatrix, > [[0, -3], > [-2, -10]]))); <commutative semigroup of 2x2 max-plus matrices with 1 generator>
generated by GAPDoc2HTML