Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Bib Ind

### 5 Matrices over semirings

In this chapter we describe the functionality in Semigroups for creating matrices over semirings. We use the term to mean everywhere in this manual.

For reference, matrices over the following semirings are currently supported:

the Boolean semiring

the set {0, 1} where 0 + 0 = 0, 0 + 1 = 1 + 1 = 1 + 0 = 1, 1⋅ 0 = 0 ⋅ 0 = 0 ⋅ 1 = 0, and 1⋅ 1 = 1.

the max-plus semiring

the set of integers and negative infinity Z∪ {-∞} with operations max and plus.

the min-plus semiring

the set of integers and infinity Z∪ {∞} with operations min and plus;

tropical max-plus semirings

the set {-∞, 0, 1, ..., t} for some threshold t with operations max and plus;

tropical min-plus semirings

the set {0, 1, ..., t, ∞} for some threshold t with operations min and plus;

the semiring N_t,p

the semiring N_t,p = {0, 1, ..., t, t + 1, ..., t + p - 1} for some threshold t and period p under addition and multiplication modulo the congruence t = t + p;

the integers

the usual ring of integers;

finite fields

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 1.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.

#### 5.1 Creating matrices over semirings

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.

##### 5.1-1 IsMatrixOverSemiring
 ‣ 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).

##### 5.1-2 IsMatrixOverSemiringCollection
 ‣ 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.

##### 5.1-3 DimensionOfMatrixOverSemiring
 ‣ 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

##### 5.1-4 DimensionOfMatrixOverSemiringCollection
 ‣ 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

##### 5.1-5 Matrix
 ‣ 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.

filt

This must be one of the filters given in Section 5.1-8.

mat

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 -.

The supported semirings are fully described at the start of this chapter.

threshold

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.

period

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(IsIntegerMatrix, [[-1, -2, 0],
>                             [0, 3, -1],
>                             [1, 0, -3]]);
Matrix(IsIntegerMatrix, [[-1, -2, 0], [0, 3, -1], [1, 0, -3]])
gap> Matrix(Integers, [[-1, -2, 0],
>                      [0, 3, -1],
>                      [1, 0, -3]]);
Matrix(IsIntegerMatrix, [[-1, -2, 0], [0, 3, -1], [1, 0, -3]])


##### 5.1-6 AsMatrix
 ‣ 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;

• IsIntegerMatrix (5.1-8) and an ntp 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> AsMatrix(IsIntegerMatrix, mat);
Matrix(IsIntegerMatrix, [[1, 2, 2], [0, 2, 0], [1, 3, 0]])
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 := AsMatrix(IsIntegerMatrix, mat);
Matrix(IsIntegerMatrix, [[0, 1, 0], [1, 2, 1], [1, 0, 1]])
gap> AsMatrix(IsNTPMatrix, mat, 1, 2);
Matrix(IsNTPMatrix, [[0, 1, 0], [1, 2, 1], [1, 0, 1]], 1, 2)

##### 5.1-7 RandomMatrix
 ‣ 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.

filt

This must be one of the filters given in Section 5.1-8.

dim

This must be a positive integer.

threshold

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.

period

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(IsIntegerMatrix, 2);
Matrix(IsIntegerMatrix, [[1, 3], [0, 0]])
gap> RandomMatrix(Integers, 2);
Matrix(IsIntegerMatrix, [[-1, 0], [0, -1]])
gap> RandomMatrix(GF(5), 1);
Matrix(GF(5), [[Z(5)^0]])

##### 5.1-8 Matrix filters
 ‣ IsBooleanMat( obj ) ( category )
 ‣ IsMatrixOverFiniteField( obj ) ( category )
 ‣ IsMaxPlusMatrix( obj ) ( category )
 ‣ IsMinPlusMatrix( obj ) ( category )
 ‣ IsTropicalMatrix( obj ) ( category )
 ‣ IsTropicalMaxPlusMatrix( obj ) ( category )
 ‣ IsTropicalMinPlusMatrix( obj ) ( category )
 ‣ IsNTPMatrix( obj ) ( category )
 ‣ IsIntegerMatrix( 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.

##### 5.1-9 Matrix collection filters
 ‣ 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 )
 ‣ IsIntegerMatrixCollection( obj ) ( category )
 ‣ IsIntegerMatrixCollColl( 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.

##### 5.1-10 AsList
 ‣ 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(IsIntegerMatrix, [[0, 2],
>                                    [3, 5]]);
Matrix(IsIntegerMatrix, [[0, 2], [3, 5]])
gap> AsList(mat);
[ [ 0, 2 ], [ 3, 5 ] ]
gap> mat := Matrix(GF(7), [[Z(7) ^ 3, Z(7) ^ 2],
>                          [Z(7) ^ 4, Z(7)]]);
Matrix(GF(7), [[Z(7)^3, Z(7)^2], [Z(7)^4, Z(7)]])
gap> list := AsList(mat);
[ [ Z(7)^3, Z(7)^2 ], [ Z(7)^4, Z(7) ] ]
gap> IsMutable(list);
false
gap> IsMutable(list);
false
gap> list := AsMutableList(mat);
[ [ Z(7)^3, Z(7)^2 ], [ Z(7)^4, Z(7) ] ]
gap> IsMutable(list);
true
gap> IsMutable(list);
true
gap> mat = Matrix(BaseDomain(mat), AsList(mat));
true

##### 5.1-11 ThresholdTropicalMatrix
 ‣ 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

##### 5.1-12 ThresholdNTPMatrix
 ‣ ThresholdNTPMatrix( mat ) ( attribute )
 ‣ PeriodNTPMatrix( mat ) ( attribute )

Returns: A positive integer.

An is a matrix with entries in a semiring N_t,p = {0, 1, ..., t, t + 1, ..., 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

#### 5.2 Operators for matrices over semirings

mat1 * mat2

returns 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 < mat2

returns 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 = mat2

returns 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.

#### 5.3 Boolean matrices

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)

##### 5.3-1 BooleanMat
 ‣ 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:

a matrix with entries 0 and/or 1

the argument arg is list of n lists of length n consisting of the values 0 and 1;

a matrix with entries true and/or false

the argument arg is list of n lists of length n consisting of the values true and false;

successors

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, 2]]);
Matrix(IsBooleanMat, [[1, 0], [1, 1]])
gap> x = y;
true
gap> y = z;
true
gap> Display(x);
1 0
1 1

##### 5.3-2 AsBooleanMat
 ‣ 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:

permutations

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).

transformations

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.

partial permutations

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.

bipartitions

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.

pbrs

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, [])
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

##### 5.3-4 OnBlist
 ‣ 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 ]

##### 5.3-5 Successors
 ‣ 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 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 ] ]

##### 5.3-6 BooleanMatNumber
 ‣ 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

##### 5.3-7 BlistNumber
 ‣ 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], );
[ 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
]

##### 5.3-8 CanonicalBooleanMat
 ‣ 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

##### 5.3-9 IsRowTrimBooleanMat
 ‣ 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 if no subset induced by a row of mat is contained in the subset induced by any other row of mat. is defined analogously. A boolean matrix is 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

##### 5.3-10 IsSymmetricBooleanMat
 ‣ IsSymmetricBooleanMat( mat ) ( property )

Returns: true or false.

A boolean matrix is 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

##### 5.3-11 IsReflexiveBooleanMat
 ‣ IsReflexiveBooleanMat( mat ) ( property )

Returns: true or false.

A boolean matrix is 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

##### 5.3-12 IsTransitiveBooleanMat
 ‣ IsTransitiveBooleanMat( mat ) ( property )

Returns: true or false.

A boolean matrix is 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

##### 5.3-13 IsAntiSymmetricBooleanMat
 ‣ IsAntiSymmetricBooleanMat( mat ) ( property )

Returns: true or false.

A boolean matrix is 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

##### 5.3-14 IsTotalBooleanMat
 ‣ IsTotalBooleanMat( mat ) ( property )
 ‣ IsOntoBooleanMat( mat ) ( property )

Returns: true or false.

A boolean matrix is if there is at least one entry in every row is true. Similarly, a boolean matrix is 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

##### 5.3-15 IsPartialOrderBooleanMat
 ‣ IsPartialOrderBooleanMat( mat ) ( property )

Returns: true or false.

A boolean matrix is a if it is reflexive, transitive, and anti-symmetric.

gap> Number(FullBooleanMatMonoid(3), IsPartialOrderBooleanMat);
19

##### 5.3-16 IsEquivalenceBooleanMat
 ‣ IsEquivalenceBooleanMat( mat ) ( property )

Returns: true or false.

A boolean matrix is an if it is reflexive, transitive, and symmetric.

gap> Number(FullBooleanMatMonoid(3), IsEquivalenceBooleanMat);
5
gap> Bell(3);
5

##### 5.3-17 IsTransformationBooleanMat
 ‣ IsTransformationBooleanMat( mat ) ( property )

Returns: true or false.

A boolean matrix is a if every row contains precisely one true value.

gap> Number(FullBooleanMatMonoid(3), IsTransformationBooleanMat);
27

#### 5.4 Matrices over finite fields

In this section we describe the operations, properties, and attributes in Semigroups specifically for matrices over finite fields. These are in addition to those given elsewhere in this chapter for arbitrary matrices over semirings.

##### 5.4-1 NewMatrixOverFiniteField
 ‣ NewMatrixOverFiniteField( filt, F, rows ) ( operation )

Returns: a new matrix object.

Creates a new n-by-n matrix over the finite field F with constructing filter filt. The matrix itself is given by a list rows of rows. Currently the only possible value for filt is IsPlistMatrixOverFiniteFieldRep.

gap> x := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep,
>                                  GF(4),
>                                  Z(4) * [[1, 0], [0, 1]]);
Matrix(GF(2^2), [[Z(2^2), 0*Z(2)], [0*Z(2), Z(2^2)]])
gap> y := NewMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep,
>                                  GF(4),
>                                  []);
Matrix(GF(2^2), [])

##### 5.4-2 IdentityMatrixOverFiniteField
 ‣ IdentityMatrixOverFiniteField( F, n ) ( operation )
 ‣ IdentityMatrixOverFiniteField( mat, n ) ( operation )

Given a finite field F and a positive integer n, this operation returns an n-by-n identity matrix with entries in the finite field F. If instead the first argument is an n-by-n matrix mat whose BaseDomain (5.4-7) is a finite field F, then IdentityMatrixOverFiniteField(mat, n) returns the same as IdentityMatrixOverFiniteField(F, n).

gap> x := NewIdentityMatrixOverFiniteField(
>                   IsPlistMatrixOverFiniteFieldRep, GF(4), 2);
Matrix(GF(2^2), [[Z(2)^0, 0*Z(2)], [0*Z(2), Z(2)^0]])
gap> y := NewZeroMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep,
>                                      GF(4), 2);
Matrix(GF(2^2), [[0*Z(2), 0*Z(2)], [0*Z(2), 0*Z(2)]])

##### 5.4-3 NewIdentityMatrixOverFiniteField
 ‣ NewIdentityMatrixOverFiniteField( filt, F, n ) ( operation )
 ‣ NewZeroMatrixOverFiniteField( filt, F, n ) ( operation )

Creates a new n-by-n zero or identity matrix with entries in the finite field F.

gap> x := NewIdentityMatrixOverFiniteField(
>                   IsPlistMatrixOverFiniteFieldRep, GF(4), 2);
Matrix(GF(2^2), [[Z(2)^0, 0*Z(2)], [0*Z(2), Z(2)^0]])
gap> y := NewZeroMatrixOverFiniteField(IsPlistMatrixOverFiniteFieldRep,
>                                      GF(4), 2);
Matrix(GF(2^2), [[0*Z(2), 0*Z(2)], [0*Z(2), 0*Z(2)]])

##### 5.4-4 RowSpaceBasis
 ‣ RowSpaceBasis( m ) ( attribute )
 ‣ RowSpaceTransformation( m ) ( attribute )
 ‣ RowSpaceTransformationInv( m ) ( attribute )

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]]);
Matrix(GF(2^2), [[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 ] ]

##### 5.4-5 RowRank
 ‣ RowRank( m ) ( attribute )

Returns: Length of a basis of the row space of m.

gap> x := Matrix(GF(5), Z(5) ^ 0 * [[1, 1, 0], [0, 0, 0], [1, 1, 1]]);
Matrix(GF(5), [[Z(5)^0, Z(5)^0, 0*Z(5)], [0*Z(5), 0*Z(5), 0*Z(5)],
[Z(5)^0, Z(5)^0, Z(5)^0]])
gap> RowRank(x);
2

##### 5.4-6 RightInverse
 ‣ 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]]);
Matrix(GF(2^2), [[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);
Matrix(GF(2^2), [[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);
Z(2)^0 Z(2)^0 0*Z(2)
0*Z(2) 0*Z(2) 0*Z(2)
0*Z(2) 0*Z(2) Z(2)^0

##### 5.4-7 BaseDomain
 ‣ BaseDomain( mat ) ( attribute )

Returns: If mat is a matrix over a finite field (in the category IsMatrixOverSemiring (5.1-1)), then BaseDomain returns the finite field specified at the point that mat was created. Every entry in the matrix mat belongs to BaseDomain(mat).

gap> x := Matrix(GF(5), Z(5) ^ 0 * [[1, 1, 0], [0, 0, 0], [1, 1, 1]]);
Matrix(GF(5), [[Z(5)^0, Z(5)^0, 0*Z(5)], [0*Z(5), 0*Z(5), 0*Z(5)],
[Z(5)^0, Z(5)^0, Z(5)^0]])
gap> BaseDomain(x);
GF(5)

##### 5.4-8 TransposedMatImmutable
 ‣ TransposedMatImmutable( m ) ( attribute )

Returns: An immutable matrix.

This attribute contains an immutable copy of m. Note that matrices are immutable by default.

gap> x := Matrix(GF(5), Z(5) ^ 0 * [[1, 1, 0], [0, 0, 0], [1, 1, 1]]);
Matrix(GF(5), [[Z(5)^0, Z(5)^0, 0*Z(5)], [0*Z(5), 0*Z(5), 0*Z(5)],
[Z(5)^0, Z(5)^0, Z(5)^0]])
gap> TransposedMatImmutable(x);
Matrix(GF(5), [[Z(5)^0, 0*Z(5), Z(5)^0], [Z(5)^0, 0*Z(5), Z(5)^0],
[0*Z(5), 0*Z(5), Z(5)^0]])

#### 5.5 Integer Matrices

In this section we describe operations in Semigroups specifically for integer matrices. These are in addition to those given elsewhere in this chapter for arbitrary matrices over semirings. These include:

• InverseOp (5.5-1)

• IsTorsion (5.5-2)

• Order (5.5-3)

##### 5.5-1 InverseOp
 ‣ InverseOp( mat ) ( operation )

Returns: An integer matrix.

If mat is an integer matrix (i.e. belongs to the category IsIntegerMatrix (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(IsIntegerMatrix, [[0, 0, -1],
>                                    [0, 1, 0],
>                                    [1, 0, 0]]);;
gap> InverseOp(mat);
Matrix(IsIntegerMatrix, [[0, 0, 1], [0, 1, 0], [-1, 0, 0]])
gap> mat * InverseOp(mat) = One(mat);
true


##### 5.5-2 IsTorsion
 ‣ IsTorsion( mat ) ( attribute )

Returns: true or false

If mat is an integer matrix (i.e. belongs to the category IsIntegerMatrix (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(IsIntegerMatrix, [[0, 0, -1],
>                                    [0, 1, 0],
>                                    [1, 0, 0]]);;
gap> IsTorsion(mat);
true
gap> mat := Matrix(IsIntegerMatrix, [[0, 0, -1, 0],
>                                    [0, -1, 0, 0],
>                                    [4, 4, 2, -1],
>                                    [1, 1, 0, 3]]);;
gap> IsTorsion(mat);
false


##### 5.5-3 Order
 ‣ Order( mat ) ( attribute )

Returns: An integer or infinity.

If mat is an integer matrix (i.e. belongs to the category IsIntegerMatrix (5.1-8)), 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(IsIntegerMatrix, [[0, 0, -1, 0],
>                                    [0, -1, 0, 0],
>                                    [4, 4, 2, -1],
>                                    [1, 1, 0, 3]]);;
gap> Order(mat);
infinity
gap> mat := Matrix(IsIntegerMatrix, [[0, 0, -1],
>                                    [0, 1, 0],
>                                    [1, 0, 0]]);;
gap> Order(mat);
4


#### 5.6 Max-plus and min-plus matrices

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)

##### 5.6-1 InverseOp
 ‣ 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

##### 5.6-4 UnweightedPrecedenceDigraph
 ‣ 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>


#### 5.7 Matrix semigroups

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:

• IsXMatrixSemigroup (5.7-1)

• IsFinite (5.7-3)

• IsTorsion (5.7-4)

• NormalizeSemigroup (5.7-5)

Random matrix semigroups can be created by using the function RandomSemigroup (6.7-1). We can also create a matrix semigroup isomorphic to a given semigroup by using IsomorphismSemigroup (6.6-1) and AsSemigroup (6.6-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.7-1), IsomorphismMonoid (6.6-2), and AsMonoid (6.6-4). These can be used with the filters in Section 5.7-2.

##### 5.7-1 Matrix semigroup filters
 ‣ 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.

##### 5.7-2 Matrix monoid filters
 ‣ 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. For matrix semigroups over finite fields there is also IsMatrixOverFiniteFieldGroup (5.7-7).

##### 5.7-3 IsFinite
 ‣ 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


##### 5.7-4 IsTorsion
 ‣ 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


##### 5.7-5 NormalizeSemigroup
 ‣ 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>


##### 5.7-6 Matrix groups

For interfacing the semigroups code with GAP's library code for matrix groups, the Semigroups package implements matrix groups that delegate to the GAP library. These functions include:

• IsMatrixOverFiniteFieldGroup (5.7-7)

• \^ (5.7-8)

• IsomorphismMatrixGroup (5.7-9)

• AsMatrixGroup (5.7-10)

This type of group only applies to matrices over finite fields (see IsMatrixOverFiniteFieldSemigroup (5.7-1)).

##### 5.7-7 IsMatrixOverFiniteFieldGroup
 ‣ IsMatrixOverFiniteFieldGroup( G ) ( filter )

Returns: true or false.

A matrix group is simply a group of invertible matrices over a finite field. An object in Semigroups is a matrix group if it satisfies IsGroup (Reference: IsGroup) and IsMatrixOverFiniteFieldCollection (5.1-9).

gap> x := Matrix(GF(4), Z(4) ^ 0 * [[1, 1, 0], [0, 1, 0], [1, 1, 1]]);;
gap> G := Group(x);
<group of 3x3 matrices over GF(2^2) with 1 generator>
gap> IsMatrixOverFiniteFieldGroup(G);
true
gap> G := Group(Z(4) ^ 0 * [[1, 1, 0], [0, 1, 0], [1, 1, 1]]);
Group([ <an immutable 3x3 matrix over GF2> ])
gap> IsGroup(G);
true
gap> IsMatrixOverFiniteFieldGroup(G);
false

##### 5.7-8 \^
 ‣ \^( G, mat ) ( operation )

Returns: A matrix group over a finite field.

The arguments of this operation, G and mat, must be categories IsMatrixOverFiniteFieldGroup (5.7-7) and IsMatrixOverFiniteField (5.1-8). If G consists of d by d matrices over GF(q) and mat is a d by d matrix over GF(q), then G ^ mat returns the conjugate of G by mat inside GL(d, q).

gap> x := Matrix(GF(4), Z(4) ^ 0 * [[1, 1, 0], [0, 1, 0], [1, 1, 1]]);;
gap> y := Matrix(GF(4), Z(4) ^ 0 * [[1, 0, 0], [1, 0, 1], [1, 1, 1]]);;
gap> G := Group(x);
<group of 3x3 matrices over GF(2^2) with 1 generator>
gap> G ^ y;
<group of 3x3 matrices over GF(2^2) with 1 generator>

##### 5.7-9 IsomorphismMatrixGroup
 ‣ IsomorphismMatrixGroup( G ) ( attribute )

Returns: An isomorphism.

If G belongs to the category IsMatrixOverFiniteFieldGroup (5.7-7), then IsomorphismMatrixGroup returns an isomorphism from G into a group consisting of GAP library matrices.

gap> x := Matrix(GF(4), Z(4) ^ 0 * [[1, 1, 0], [0, 1, 0], [1, 1, 1]]);;
gap> G := Group(x);;
gap> iso := IsomorphismMatrixGroup(G);;
gap> Source(iso); Range(iso);
<group of 3x3 matrices over GF(2^2) with 1 generator>
Group(
[
[ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, 0*Z(2) ],
[ Z(2)^0, Z(2)^0, Z(2)^0 ] ] ])

##### 5.7-10 AsMatrixGroup
 ‣ AsMatrixGroup( G ) ( attribute )

Returns: A group of GAP library matrices over a finite field.

Returns the image of the isomorphism returned by 5.7-9.

gap> x := Matrix(GF(4), Z(4) ^ 0 * [[1, 1, 0], [0, 1, 0], [1, 1, 1]]);;
gap> G := Group(x);
<group of 3x3 matrices over GF(2^2) with 1 generator>
gap> AsMatrixGroup(G);
Group(
[
[ [ Z(2)^0, Z(2)^0, 0*Z(2) ], [ 0*Z(2), Z(2)^0, 0*Z(2) ],
[ Z(2)^0, Z(2)^0, Z(2)^0 ] ] ])
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Bib Ind

generated by GAPDoc2HTML