In GAP, Matrices can be represented by lists of row vectors, see 23. (For a more general way to represent vectors and matrices, see Chapter 26). The row vectors must all have the same length, and their elements must lie in a common ring. However, since checking rectangularness can be expensive functions and methods of operations for matrices often will not give an error message for non-rectangular lists of lists –in such cases the result is undefined.
Because matrices are just a special case of lists, all operations and functions for lists are applicable to matrices also (see chapter 21). This especially includes accessing elements of a matrix (see 21.3), changing elements of a matrix (see 21.4), and comparing matrices (see 21.10).
Note that, since a matrix is a list of lists, the behaviour of ShallowCopy (12.7-1) for matrices is just a special case of ShallowCopy (12.7-1) for lists (see 21.7); called with an immutable matrix mat, ShallowCopy (12.7-1) returns a mutable matrix whose rows are identical to the rows of mat. In particular the rows are still immutable. To get a matrix whose rows are mutable, one can use List( mat, ShallowCopy ).
‣ InfoMatrix | ( info class ) |
The info class for matrix operations is InfoMatrix.
‣ IsMatrix( obj ) | ( category ) |
By convention matrix is a list of lists of equal length whose entries lie in a common ring.
For technical reasons laid out at the top of Chapter 24, the filter IsMatrix is a synonym for a table of ring elements, (see IsTable (21.1-4) and IsRingElement (31.14-16)). This means that IsMatrix returns true for tables such as [[1,2],[3]]. If necessary, IsRectangularTable (21.1-5) can be used to test whether an object is a list of homogeneous lists of equal lengths manually.
Note that matrices may have different multiplications, besides the usual matrix product there is for example the Lie product. So there are categories such as IsOrdinaryMatrix (24.2-2) and IsLieMatrix (24.2-3) that describe the matrix multiplication. One can form the product of two matrices only if they support the same multiplication.
gap> mat:=[[1,2,3],[4,5,6],[7,8,9]]; [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] gap> IsMatrix(mat); true gap> mat:=[[1,2],[3]]; [ [ 1, 2 ], [ 3 ] ] gap> IsMatrix(mat); true gap> IsRectangularTable(mat); false
Note that the empty list [] and more complex empty
structures such as [[]] are not matrices, although special methods allow them be used in place of matrices in some situations. See EmptyMatrix (24.5-3) below.
gap> [[0]]*[[]]; [ [ ] ] gap> IsMatrix([[]]); false
‣ IsOrdinaryMatrix( obj ) | ( category ) |
An ordinary matrix is a matrix whose multiplication is the ordinary matrix multiplication.
Each matrix in internal representation is in the category IsOrdinaryMatrix, and arithmetic operations with objects in IsOrdinaryMatrix produce again matrices in IsOrdinaryMatrix.
Note that we want that Lie matrices shall be matrices that behave in the same way as ordinary matrices, except that they have a different multiplication. So we must distinguish the different matrix multiplications, in order to be able to describe the applicability of multiplication, and also in order to form a matrix of the appropriate type as the sum, difference etc. of two matrices which have the same multiplication.
‣ IsLieMatrix( mat ) | ( category ) |
A Lie matrix is a matrix whose multiplication is given by the Lie bracket. (Note that a matrix with ordinary matrix multiplication is in the category IsOrdinaryMatrix (24.2-2).)
Each matrix created by LieObject (64.1-1) is in the category IsLieMatrix, and arithmetic operations with objects in IsLieMatrix produce again matrices in IsLieMatrix.
The rules for arithmetic operations involving matrices are in fact special cases of those for the arithmetic of lists, given in Section 21.11 and the following sections, here we reiterate that definition, in the language of vectors and matrices.
Note that the additive behaviour sketched below is defined only for lists in the category IsGeneralizedRowVector (21.12-1), and the multiplicative behaviour is defined only for lists in the category IsMultiplicativeGeneralizedRowVector (21.12-2) (see 21.12).
mat1 + mat2
returns the sum of the two matrices mat1 and mat2, Probably the most usual situation is that mat1 and mat2 have the same dimensions and are defined over a common field; in this case the sum is a new matrix over the same field where each entry is the sum of the corresponding entries of the matrices.
In more general situations, the sum of two matrices need not be a matrix, for example adding an integer matrix mat1 and a matrix mat2 over a finite field yields the table of pointwise sums, which will be a mixture of finite field elements and integers if mat1 has bigger dimensions than mat2.
scalar + mat
mat + scalar
returns the sum of the scalar scalar and the matrix mat. Probably the most usual situation is that the entries of mat lie in a common field with scalar; in this case the sum is a new matrix over the same field where each entry is the sum of the scalar and the corresponding entry of the matrix.
More general situations are for example the sum of an integer scalar and a matrix over a finite field, or the sum of a finite field element and an integer matrix.
mat1 - mat2
scalar - mat
mat - scalar
Subtracting a matrix or scalar is defined as adding its additive inverse, so the statements for the addition hold likewise.
scalar * mat
mat * scalar
returns the product of the scalar scalar and the matrix mat. Probably the most usual situation is that the elements of mat lie in a common field with scalar; in this case the product is a new matrix over the same field where each entry is the product of the scalar and the corresponding entry of the matrix.
More general situations are for example the product of an integer scalar and a matrix over a finite field, or the product of a finite field element and an integer matrix.
vec * mat
returns the product of the row vector vec and the matrix mat. Probably the most usual situation is that vec and mat have the same lengths and are defined over a common field, and that all rows of mat have some common length \(m\); in this case the product is a new row vector of length \(m\) over the same field which is the sum of the scalar multiples of the rows of mat with the corresponding entries of vec.
More general situations are for example the product of an integer vector and a matrix over a finite field, or the product of a vector over a finite field and an integer matrix.
mat * vec
returns the product of the matrix mat and the row vector vec. (This is the standard product of a matrix with a column vector.) Probably the most usual situation is that the length of vec and of all rows of mat are equal, and that the elements of mat and vec lie in a common field; in this case the product is a new row vector of the same length as mat and over the same field which is the sum of the scalar multiples of the columns of mat with the corresponding entries of vec.
More general situations are for example the product of an integer matrix and a vector over a finite field, or the product of a matrix over a finite field and an integer vector.
mat1 * mat2
This form evaluates to the (Cauchy) product of the two matrices mat1 and mat2. Probably the most usual situation is that the number of columns of mat1 equals the number of rows of mat2, and that the elements of mat and vec lie in a common field; if mat1 is a matrix with \(m\) rows and \(n\) columns and mat2 is a matrix with \(n\) rows and \(o\) columns, the result is a new matrix with \(m\) rows and \(o\) columns. The element in row \(i\) at position \(j\) of the product is the sum of \(\textit{mat1}[i][l] * \textit{mat2}[l][j]\), with \(l\) running from \(1\) to \(n\).
Inverse( mat )
returns the inverse of the matrix mat, which must be an invertible square matrix. If mat is not invertible then fail is returned.
mat1 / mat2
scalar / mat
mat / scalar
vec / mat
In general, left / right is defined as left * right^-1. Thus in the above forms the right operand must always be invertible.
mat ^ int
mat1 ^ mat2
vec ^ mat
Powering a square matrix mat by an integer int yields the int-th power of mat; if int is negative then mat must be invertible, if int is 0 then the result is the identity matrix One( mat ), even if mat is not invertible.
Powering a square matrix mat1 by an invertible square matrix mat2 of the same dimensions yields the conjugate of mat1 by mat2, i.e., the matrix mat2^-1 * mat1 * mat2.
Powering a row vector vec by a matrix mat is in every respect equivalent to vec * mat. This operations reflects the fact that matrices act naturally on row vectors by multiplication from the right, and that the powering operator is GAP's standard for group actions.
Comm( mat1, mat2 )
returns the commutator of the square invertible matrices mat1 and mat2 of the same dimensions and over a common field, which is the matrix mat1^-1 * mat2^-1 * mat1 * mat2.
The following cases are still special cases of the general list arithmetic defined in 21.11.
scalar + matlist
matlist + scalar
scalar - matlist
matlist - scalar
scalar * matlist
matlist * scalar
matlist / scalar
A scalar scalar may also be added, subtracted, multiplied with, or divided into a list matlist of matrices. The result is a new list of matrices where each matrix is the result of performing the operation with the corresponding matrix in matlist.
mat * matlist
matlist * mat
A matrix mat may also be multiplied with a list matlist of matrices. The result is a new list of matrices, where each entry is the product of mat and the corresponding entry in matlist.
matlist / mat
Dividing a list matlist of matrices by an invertible matrix mat evaluates to matlist * mat^-1.
vec * matlist
returns the product of the vector vec and the list of matrices mat. The lengths l of vec and matlist must be equal. All matrices in matlist must have the same dimensions. The elements of vec and the elements of the matrices in matlist must lie in a common ring. The product is the sum over vec[i] * matlist[i] with i running from 1 to l.
For the mutability of results of arithmetic operations, see 12.6.
‣ DimensionsMat( mat ) | ( attribute ) |
is a list of length 2, the first being the number of rows, the second being the number of columns of the matrix mat. If mat is malformed, that is, it is not a IsRectangularTable (21.1-5), returns fail.
gap> DimensionsMat([[1,2,3],[4,5,6]]); [ 2, 3 ] gap> DimensionsMat([[1,2,3],[4,5]]); fail
‣ DefaultFieldOfMatrix( mat ) | ( attribute ) |
For a matrix mat, DefaultFieldOfMatrix returns either a field (not necessarily the smallest one) containing all entries of mat, or fail.
If mat is a matrix of finite field elements or a matrix of cyclotomics, DefaultFieldOfMatrix returns the default field generated by the matrix entries (see 59.3 and 18.1).
gap> DefaultFieldOfMatrix([[Z(4),Z(8)]]); GF(2^6)
‣ TraceMatrix( mat ) | ( attribute ) |
‣ TraceMat( mat ) | ( attribute ) |
‣ Trace( mat ) | ( attribute ) |
The trace of a square matrix is the sum of its diagonal entries.
gap> TraceMatrix([[1,2,3],[4,5,6],[7,8,9]]); 15
‣ DeterminantMatrix( mat ) | ( attribute ) |
‣ DeterminantMat( mat ) | ( attribute ) |
‣ Determinant( mat ) | ( operation ) |
returns the determinant of the square matrix mat.
These methods assume implicitly that mat is defined over an integral domain whose quotient field is implemented in GAP. For matrices defined over an arbitrary commutative ring with one see DeterminantMatDivFree (24.4-6).
‣ DeterminantMatrixDestructive( mat ) | ( operation ) |
‣ DeterminantMatDestructive( mat ) | ( operation ) |
Does the same as DeterminantMatrix (24.4-4), with the difference that it may destroy its argument. The matrix mat must be mutable.
gap> DeterminantMatrix([[1,2],[2,1]]); -3 gap> mm:= [[1,2],[2,1]];; gap> DeterminantMatrixDestructive( mm ); -3 gap> mm; [ [ 1, 2 ], [ 0, -3 ] ]
‣ DeterminantMatrixDivFree( mat ) | ( operation ) |
‣ DeterminantMatDivFree( mat ) | ( operation ) |
return the determinant of a square matrix mat over an arbitrary commutative ring with one using the division free method of Mahajan and Vinay [MV97].
‣ IsEmptyMatrix( M ) | ( property ) |
Returns: A boolean
Is true if the matrix object M either has zero columns or zero rows, and false otherwise. In other words, a matrix object is empty if it has no entries.
‣ IsMonomialMatrix( mat ) | ( property ) |
A matrix is monomial if and only if it has exactly one nonzero entry in every row and every column.
gap> IsMonomialMatrix([[0,1],[1,0]]); true
‣ IsDiagonalMatrix( mat ) | ( property ) |
‣ IsDiagonalMat( mat ) | ( property ) |
return true if the matrix mat has only zero entries off the main diagonal, and false otherwise.
gap> IsDiagonalMatrix( [ [ 1 ] ] ); true gap> IsDiagonalMatrix( [ [ 1, 0, 0 ], [ 0, 1, 0 ] ] ); true gap> IsDiagonalMatrix( [ [ 0, 1 ], [ 1, 0 ] ] ); false
‣ IsUpperTriangularMatrix( mat ) | ( property ) |
‣ IsUpperTriangularMat( mat ) | ( property ) |
return true if the matrix mat has only zero entries below the main diagonal, and false otherwise.
gap> IsUpperTriangularMatrix( [ [ 1 ] ] ); true gap> IsUpperTriangularMatrix( [ [ 1, 2, 3 ], [ 0, 5, 6 ] ] ); true gap> IsUpperTriangularMatrix( [ [ 0, 1 ], [ 1, 0 ] ] ); false
‣ IsLowerTriangularMatrix( mat ) | ( property ) |
‣ IsLowerTriangularMat( mat ) | ( property ) |
return true if the matrix mat has only zero entries above the main diagonal, and false otherwise.
gap> IsLowerTriangularMatrix( [ [ 1 ] ] ); true gap> IsLowerTriangularMatrix( [ [ 1, 0, 0 ], [ 2, 3, 0 ] ] ); true gap> IsLowerTriangularMatrix( [ [ 0, 1 ], [ 1, 0 ] ] ); false
‣ IdentityMat( m[, R] ) | ( function ) |
returns a (mutable) m\(\times\)m identity matrix over the ring given by R. Here, R can be either a ring, or an element of a ring. By default, an integer matrix is created.
gap> IdentityMat(3); [ [ 1, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 1 ] ] gap> IdentityMat(2,Integers mod 15); [ [ ZmodnZObj( 1, 15 ), ZmodnZObj( 0, 15 ) ], [ ZmodnZObj( 0, 15 ), ZmodnZObj( 1, 15 ) ] ] gap> IdentityMat(2,Z(3)); [ [ Z(3)^0, 0*Z(3) ], [ 0*Z(3), Z(3)^0 ] ]
‣ NullMat( m, n[, R] ) | ( function ) |
returns a (mutable) m\(\times\)n null matrix over the ring given by by R. Here, R can be either a ring, or an element of a ring. By default, an integer matrix is created.
gap> NullMat(3,2); [ [ 0, 0 ], [ 0, 0 ], [ 0, 0 ] ] gap> NullMat(2,2,Integers mod 15); [ [ ZmodnZObj( 0, 15 ), ZmodnZObj( 0, 15 ) ], [ ZmodnZObj( 0, 15 ), ZmodnZObj( 0, 15 ) ] ] gap> NullMat(3,2,Z(3)); [ [ 0*Z(3), 0*Z(3) ], [ 0*Z(3), 0*Z(3) ], [ 0*Z(3), 0*Z(3) ] ]
‣ EmptyMatrix( char ) | ( function ) |
is an empty (ordinary) matrix in characteristic char that can be added to or multiplied with empty lists (representing zero-dimensional row vectors). It also acts (via the operation \^ (31.12-1)) on empty lists.
gap> EmptyMatrix(5); EmptyMatrix( 5 ) gap> AsList(last); [ ]
‣ DiagonalMat( vector ) | ( function ) |
returns a diagonal matrix mat with the diagonal entries given by vector.
gap> DiagonalMat([1,2,3]); [ [ 1, 0, 0 ], [ 0, 2, 0 ], [ 0, 0, 3 ] ]
‣ DiagonalMatrix( [filt, ]R, vector ) | ( operation ) |
‣ DiagonalMatrix( vector[, M] ) | ( operation ) |
Returns: a square matrix or matrix object with column number equal to the length of the dense list vector, whose diagonal entries are given by the entries of vector, and whose off-diagonal entries are zero.
If a semiring R is given then it will be the base domain (see BaseDomain (26.3-1)) of the returned matrix. In this case, a filter filt can be specified that defines the internal representation of the result (see ConstructingFilter (26.3-2)). The default value for filt is determined from R.
If a matrix object M is given then the returned matrix will have the same internal representation and the same base domain as M.
If only vector is given then it is used to compute a default for R.
If the ConstructingFilter (26.3-2) value of the result implies IsCopyable (12.6-1) then the result is fully mutable.
gap> d1:= DiagonalMatrix( GF(9), [ 1, 2 ] * Z(3)^0 ); [ [ Z(3)^0, 0*Z(3) ], [ 0*Z(3), Z(3) ] ] gap> Is8BitMatrixRep( d1 ); true gap> d2:= DiagonalMatrix( IsPlistMatrixRep, GF(9), [ 1, 2 ] * Z(3)^0 ); <2x2-matrix over GF(3^2)> gap> IsPlistMatrixRep( d2 ); true gap> DiagonalMatrix( [ 1, 2 ] ); <2x2-matrix over Rationals> gap> DiagonalMatrix( [ 1, 2 ], Matrix( Integers, [ [ 1 ] ], 1 ) ); <2x2-matrix over Integers> gap> DiagonalMatrix( [ 1, 2 ], [ [ 1 ] ] ); [ [ 1, 0 ], [ 0, 2 ] ]
‣ PermutationMat( perm, dim[, F] ) | ( function ) |
returns a matrix in dimension dim over the field given by F (i.e. the smallest field containing the element F or F itself if it is a field) that represents the permutation perm acting by permuting the basis vectors as it permutes points.
gap> PermutationMat((1,2,3),4,1); [ [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 1, 0, 0, 0 ], [ 0, 0, 0, 1 ] ]
‣ TransposedMatImmutable( mat ) | ( attribute ) |
‣ TransposedMat( mat ) | ( attribute ) |
‣ TransposedMatMutable( mat ) | ( operation ) |
‣ TransposedMatOp( mat ) | ( operation ) |
These functions all return the transposed of the matrix object mat, i.e., a matrix object \(trans\) such that \(trans[i,k] = \textit{mat}[k,i]\) holds.
They differ only w.r.t. the mutability of the result.
TransposedMat is an attribute and hence returns an immutable result. TransposedMatMutable is guaranteed to return a new mutable matrix.
TransposedMatImmutable is a synonym of TransposedMat, and TransposedMatOp is a synonym of TransposedMatMutable, in analogy to operations such as Zero (31.10-3).
‣ TransposedMatDestructive( mat ) | ( operation ) |
If mat is a mutable matrix, then the transposed is computed by swapping the entries in mat. In this way mat gets changed. In all other cases the transposed is computed by TransposedMat (24.5-7).
gap> TransposedMat([[1,2,3],[4,5,6],[7,8,9]]); [ [ 1, 4, 7 ], [ 2, 5, 8 ], [ 3, 6, 9 ] ] gap> mm:= [[1,2,3],[4,5,6],[7,8,9]];; gap> TransposedMatDestructive( mm ); [ [ 1, 4, 7 ], [ 2, 5, 8 ], [ 3, 6, 9 ] ] gap> mm; [ [ 1, 4, 7 ], [ 2, 5, 8 ], [ 3, 6, 9 ] ]
‣ KroneckerProduct( mat1, mat2 ) | ( operation ) |
The Kronecker product of two matrices is the matrix obtained when replacing each entry a of mat1 by the product a*mat2 in one matrix.
gap> KroneckerProduct([[1,2]],[[5,7],[9,2]]); [ [ 5, 7, 10, 14 ], [ 9, 2, 18, 4 ] ]
‣ ReflectionMat( coeffs[, conj][, root] ) | ( function ) |
Let coeffs be a row vector. ReflectionMat returns the matrix of the reflection in this vector.
More precisely, if coeffs is the coefficients list of a vector \(v\) w.r.t. a basis \(B\) (see Basis (61.5-2)) then the returned matrix describes the reflection in \(v\) w.r.t. \(B\) as a map on a row space, with action from the right.
The optional argument root is a root of unity that determines the order of the reflection. The default is a reflection of order 2. For triflections one should choose a third root of unity etc. (see E (18.1-1)).
conj is a function of one argument that conjugates a ring element. The default is ComplexConjugate (18.5-2).
The matrix of the reflection in \(v\) is defined as
\[ M = I_n + \overline{{v^{tr}}} \cdot (w-1) / ( v \overline{{v^{tr}}} ) \cdot v \]
where \(w\) equals root, \(n\) is the length of the coefficient list, and \(\overline{{\vphantom{x}}}\) denotes the conjugation.
So \(v\) is mapped to \(w v\), with default \(-v\), and any vector \(x\) with the property \(x \overline{{v^{tr}}} = 0\) is fixed by the reflection.
‣ PrintArray( array ) | ( function ) |
pretty-prints the array array.
‣ RandomMat( [rs, ]m, n[, R] ) | ( function ) |
RandomMat returns a new mutable random matrix with m rows and n columns with elements taken from the ring R, which defaults to Integers (14). Optionally, a random source rs can be supplied.
gap> RandomMat(2,3,GF(3)); [ [ Z(3), Z(3), 0*Z(3) ], [ Z(3), Z(3)^0, Z(3) ] ]
‣ RandomInvertibleMat( [rs, ]m[, R] ) | ( function ) |
RandomInvertibleMat returns a new mutable invertible random matrix with m rows and columns with elements taken from the ring R, which defaults to Integers (14). Optionally, a random source rs can be supplied.
gap> m := RandomInvertibleMat(4); [ [ -4, 1, 0, -1 ], [ -1, -1, 1, -1 ], [ 1, -2, -1, -2 ], [ 0, -1, 2, -2 ] ] gap> m^-1; [ [ -1/8, -11/24, 1/24, 1/4 ], [ 1/4, -13/12, -1/12, 1/2 ], [ -1/8, 5/24, -7/24, 1/4 ], [ -1/4, 3/4, -1/4, -1/2 ] ]
‣ RandomUnimodularMat( [rs, ]m ) | ( function ) |
returns a new random mutable m\(\times\)m matrix with integer entries that is invertible over the integers. Optionally, a random source rs can be supplied. If the option domain is given, random selection is made from domain, otherwise from Integers
gap> m := RandomUnimodularMat(3); [ [ -5, 1, 0 ], [ 12, -2, -1 ], [ -14, 3, 0 ] ] gap> m^-1; [ [ -3, 0, 1 ], [ -14, 0, 5 ], [ -8, -1, 2 ] ] gap> RandomUnimodularMat(3:domain:=[-1000..1000]); [ [ 312330173, 15560030349, -125721926670 ], [ -307290, -15309014, 123693281 ], [ -684293792, -34090949551, 275448039848 ] ]
‣ RankMatrix( mat ) | ( attribute ) |
‣ RankMat( mat ) | ( attribute ) |
If mat is a matrix object representing a matrix whose rows span a free module over the ring generated by the matrix entries and their inverses then RankMatrix returns the dimension of this free module. Otherwise fail is returned.
Note that RankMatrix may perform a Gaussian elimination. For large rational matrices this may take very long, because the entries may become very large.
gap> mat:=[[1,2,3],[4,5,6],[7,8,9]];; gap> RankMatrix( mat ); 2
‣ TriangulizedMat( mat ) | ( operation ) |
‣ RREF( mat ) | ( operation ) |
Computes an upper triangular form of the matrix mat via the Gaussian Algorithm. It returns a mutable matrix in upper triangular form. This is sometimes also called Hermite normal form
or Reduced Row Echelon Form
. RREF is a synonym for TriangulizedMat.
‣ TriangulizeMat( mat ) | ( operation ) |
Applies the Gaussian Algorithm to the mutable matrix mat and changes mat such that it is in upper triangular normal form (sometimes called Hermite normal form
or Reduced Row Echelon Form
).
gap> m:=TransposedMatMutable(mat); [ [ 1, 4, 7 ], [ 2, 5, 8 ], [ 3, 6, 9 ] ] gap> TriangulizeMat(m);m; [ [ 1, 0, -1 ], [ 0, 1, 2 ], [ 0, 0, 0 ] ] gap> m:=TransposedMatMutable(mat); [ [ 1, 4, 7 ], [ 2, 5, 8 ], [ 3, 6, 9 ] ] gap> TriangulizedMat(m);m; [ [ 1, 0, -1 ], [ 0, 1, 2 ], [ 0, 0, 0 ] ] [ [ 1, 4, 7 ], [ 2, 5, 8 ], [ 3, 6, 9 ] ]
‣ NullspaceMat( mat ) | ( attribute ) |
‣ TriangulizedNullspaceMat( mat ) | ( attribute ) |
returns a list of row vectors that form a basis of the vector space of solutions to the equation vec*mat=0. The result is an immutable matrix. This basis is not guaranteed to be in any specific form.
The variant TriangulizedNullspaceMat returns a basis of the nullspace in triangulized form as is often needed for algorithms.
‣ NullspaceMatDestructive( mat ) | ( operation ) |
‣ TriangulizedNullspaceMatDestructive( mat ) | ( operation ) |
This function does the same as NullspaceMat (24.7-4). However, the latter function makes a copy of mat to avoid having to change it. This function does not do that; it returns the nullspace and may destroy mat; this saves a lot of memory in case mat is big. The matrix mat must be mutable.
The variant TriangulizedNullspaceMatDestructive returns a basis of the nullspace in triangulized form. It may destroy the matrix mat.
gap> mat:=[[1,2,3],[4,5,6],[7,8,9]];; gap> NullspaceMat(mat); [ [ 1, -2, 1 ] ] gap> mm:=[[1,2,3],[4,5,6],[7,8,9]];; gap> NullspaceMatDestructive( mm ); [ [ 1, -2, 1 ] ] gap> mm; [ [ 1, 2, 3 ], [ 0, -3, -6 ], [ 0, 0, 0 ] ]
‣ SolutionMat( mat, vec ) | ( operation ) |
returns a row vector x that is a solution of the equation x * mat = vec. It returns fail if no such vector exists.
‣ SolutionMatDestructive( mat, vec ) | ( operation ) |
Does the same as SolutionMat( mat, vec ) except that it may destroy the matrix mat and the vector vec. The matrix mat must be mutable.
gap> mat:=[[1,2,3],[4,5,6],[7,8,9]];; gap> SolutionMat(mat,[3,5,7]); [ 5/3, 1/3, 0 ] gap> mm:= [[1,2,3],[4,5,6],[7,8,9]];; gap> v:= [3,5,7];; gap> SolutionMatDestructive( mm, v ); [ 5/3, 1/3, 0 ] gap> mm; [ [ 1, 2, 3 ], [ 0, -3, -6 ], [ 0, 0, 0 ] ] gap> v; [ 0, 0, 0 ]
‣ BaseFixedSpace( mats ) | ( function ) |
BaseFixedSpace returns a list of row vectors that form a base of the vector space \(V\) such that \(v M = v\) for all \(v\) in \(V\) and all matrices \(M\) in the list mats. (This is the common eigenspace of all matrices in mats for the eigenvalue 1.)
gap> BaseFixedSpace([[[1,2],[0,1]]]); [ [ 0, 1 ] ]
‣ GeneralisedEigenvalues( F, A ) | ( operation ) |
‣ GeneralizedEigenvalues( F, A ) | ( operation ) |
The generalised eigenvalues of the matrix A over the field F.
‣ GeneralisedEigenspaces( F, A ) | ( operation ) |
‣ GeneralizedEigenspaces( F, A ) | ( operation ) |
The generalised eigenspaces of the matrix A over the field F.
‣ Eigenvalues( F, A ) | ( operation ) |
The eigenvalues of the matrix A over the field F.
‣ Eigenspaces( F, A ) | ( operation ) |
The eigenspaces of the matrix A over the field F.
‣ Eigenvectors( F, A ) | ( operation ) |
The eigenvectors of the matrix A over the field F.
See also chapter 25.
‣ ElementaryDivisorsMat( [ring, ]mat ) | ( operation ) |
‣ ElementaryDivisorsMatDestructive( ring, mat ) | ( function ) |
returns a list of the elementary divisors, i.e., the unique \(d\) with \(d[i]\) divides \(d[i+1]\) and mat is equivalent to a diagonal matrix with the elements \(d[i]\) on the diagonal. The operations are performed over the euclidean ring ring, which must contain all matrix entries. For compatibility reasons it can be omitted and defaults to the DefaultRing (56.1-3) of the matrix entries.
The function ElementaryDivisorsMatDestructive produces the same result but in the process may destroy the contents of mat.
gap> mat:=[[1,2,3],[4,5,6],[7,8,9]];; gap> ElementaryDivisorsMat(mat); [ 1, 3, 0 ] gap> x:=Indeterminate(Rationals,"x");; gap> mat:=mat*One(x)-x*mat^0; [ [ -x+1, 2, 3 ], [ 4, -x+5, 6 ], [ 7, 8, -x+9 ] ] gap> ElementaryDivisorsMat(PolynomialRing(Rationals,1),mat); [ 1, 1, x^3-15*x^2-18*x ] gap> mat:=KroneckerProduct(CompanionMat((x-1)^2), > CompanionMat((x^3-1)*(x-1)));; gap> mat:=mat*One(x)-x*mat^0; [ [ -x, 0, 0, 0, 0, 0, 0, 1 ], [ 0, -x, 0, 0, -1, 0, 0, -1 ], [ 0, 0, -x, 0, 0, -1, 0, 0 ], [ 0, 0, 0, -x, 0, 0, -1, -1 ], [ 0, 0, 0, -1, -x, 0, 0, -2 ], [ 1, 0, 0, 1, 2, -x, 0, 2 ], [ 0, 1, 0, 0, 0, 2, -x, 0 ], [ 0, 0, 1, 1, 0, 0, 2, -x+2 ] ] gap> ElementaryDivisorsMat(PolynomialRing(Rationals,1),mat); [ 1, 1, 1, 1, 1, 1, x-1, x^7-x^6-2*x^4+2*x^3+x-1 ]
‣ ElementaryDivisorsTransformationsMat( [ring, ]mat ) | ( operation ) |
‣ ElementaryDivisorsTransformationsMatDestructive( ring, mat ) | ( function ) |
ElementaryDivisorsTransformations, in addition to the tasks done by ElementaryDivisorsMat, also calculates transforming matrices. It returns a record with components normal (a matrix \(S\)), rowtrans (a matrix \(P\)), and coltrans (a matrix \(Q\)) such that \(P A Q = S\). The operations are performed over the euclidean ring ring, which must contain all matrix entries. For compatibility reasons it can be omitted and defaults to the DefaultRing (56.1-3) of the matrix entries.
The function ElementaryDivisorsTransformationsMatDestructive produces the same result but in the process destroys the contents of mat.
gap> mat:=KroneckerProduct(CompanionMat((x-1)^2),CompanionMat((x^3-1)*(x-1)));; gap> mat:=mat*One(x)-x*mat^0; [ [ -x, 0, 0, 0, 0, 0, 0, 1 ], [ 0, -x, 0, 0, -1, 0, 0, -1 ], [ 0, 0, -x, 0, 0, -1, 0, 0 ], [ 0, 0, 0, -x, 0, 0, -1, -1 ], [ 0, 0, 0, -1, -x, 0, 0, -2 ], [ 1, 0, 0, 1, 2, -x, 0, 2 ], [ 0, 1, 0, 0, 0, 2, -x, 0 ], [ 0, 0, 1, 1, 0, 0, 2, -x+2 ] ] gap> t:=ElementaryDivisorsTransformationsMat(PolynomialRing(Rationals,1),mat); rec( coltrans := [ [ 0, 0, 0, 0, 0, 0, 1/6*x^2-7/9*x-1/18, -3*x^3-x^2-x-1 ], [ 0, 0, 0, 0, 0, 0, -1/6*x^2+x-1, 3*x^3-3*x^2 ], [ 0, 0, 0, 0, 0, 1, -1/18*x^4+1/3*x^3-1/3*x^2-1/9*x, x^5-x^4+2*x^2-2*x ], [ 0, 0, 0, 0, -1, 0, -1/9*x^3+1/2*x^2+1/9*x, 2*x^4+x^3+x^2+2*x ], [ 0, -1, 0, 0, 0, 0, -2/9*x^2+19/18*x, 4*x^3+x^2+x ], [ 0, 0, -1, 0, 0, -x, 1/18*x^5-1/3*x^4+1/3*x^3+1/9*x^2, -x^6+x^5-2*x^3+2*x^2 ], [ 0, 0, 0, -1, x, 0, 1/9*x^4-2/3*x^3+2/3*x^2+1/18*x, -2*x^5+2*x^4-x^2+x ], [ 1, 0, 0, 0, 0, 0, 1/6*x^3-7/9*x^2-1/18*x, -3*x^4-x^3-x^2-x ] ], normal := [ [ 1, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 0, x-1, 0 ], [ 0, 0, 0, 0, 0, 0, 0, x^7-x^6-2*x^4+2*x^3+x-1 ] ], rowtrans := [ [ 1, 0, 0, 0, 0, 0, 0, 0 ], [ 1, 1, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0, 0 ], [ 1, 0, 0, 1, 0, 0, 0, 0 ], [ -x+2, -x, 0, 0, 1, 0, 0, 0 ], [ 2*x^2-4*x+2, 2*x^2-x, 0, 2, -2*x+1, 0, 0, 1 ], [ 3*x^3-6*x^2+3*x, 3*x^3-2*x^2, 2, 3*x, -3*x^2+2*x, 0, 1, 2*x ], [ 1/6*x^8-7/6*x^7+2*x^6-4/3*x^5+7/3*x^4-4*x^3+13/6*x^2-7/6*x+2, 1/6*x^8-17/18*x^7+13/18*x^6-5/18*x^5+35/18*x^4-31/18*x^3+1/9*x^2-x+\ 2, 1/9*x^5-5/9*x^4+1/9*x^3-1/9*x^2+14/9*x-1/9, 1/6*x^6-5/6*x^5+1/6*x^4-1/6*x^3+11/6*x^2-1/6*x, -1/6*x^7+17/18*x^6-13/18*x^5+5/18*x^4-35/18*x^3+31/18*x^2-1/9*x+1, 1, 1/18*x^5-5/18*x^4+1/18*x^3-1/18*x^2+23/18*x-1/18, 1/9*x^6-5/9*x^5+1/9*x^4-1/9*x^3+14/9*x^2-1/9*x ] ] ) gap> t.rowtrans*mat*t.coltrans; [ [ 1, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 0, x-1, 0 ], [ 0, 0, 0, 0, 0, 0, 0, x^7-x^6-2*x^4+2*x^3+x-1 ] ]
‣ DiagonalizeMat( ring, mat ) | ( operation ) |
brings the mutable matrix mat, considered as a matrix over ring, into diagonal form by elementary row and column operations.
gap> m:=[[1,2],[2,1]];; gap> DiagonalizeMat(Integers,m);m; [ [ 1, 0 ], [ 0, 3 ] ]
‣ SemiEchelonMat( mat ) | ( attribute ) |
A matrix over a field \(F\) is in semi-echelon form if the first nonzero element in each row is the identity of \(F\), and all values exactly below these pivots are the zero of \(F\).
SemiEchelonMat returns a record that contains information about a semi-echelonized form of the matrix mat.
The components of this record are
vectorslist of row vectors, each with pivot element the identity of \(F\),
headslist that contains at position i, if nonzero, the number of the row for that the pivot element is in column i.
‣ SemiEchelonMatDestructive( mat ) | ( operation ) |
This does the same as SemiEchelonMat( mat ), except that it may (and probably will) destroy the matrix mat.
gap> mm:=[[1,2,3],[4,5,6],[7,8,9]];; gap> SemiEchelonMatDestructive( mm ); rec( heads := [ 1, 2, 0 ], vectors := [ [ 1, 2, 3 ], [ 0, 1, 2 ] ] ) gap> mm; [ [ 1, 2, 3 ], [ 0, 1, 2 ], [ 0, 0, 0 ] ]
‣ SemiEchelonMatTransformation( mat ) | ( attribute ) |
does the same as SemiEchelonMat (24.10-1) but additionally stores the linear transformation \(T\) performed on the matrix. The additional components of the result are
coeffsa list of coefficients vectors of the vectors component, with respect to the rows of mat, that is, coeffs * mat is the vectors component.
relationsa list of basis vectors for the (left) null space of mat.
gap> SemiEchelonMatTransformation([[1,2,3],[0,0,1]]); rec( coeffs := [ [ 1, 0 ], [ 0, 1 ] ], heads := [ 1, 0, 2 ], relations := [ ], vectors := [ [ 1, 2, 3 ], [ 0, 0, 1 ] ] )
‣ SemiEchelonMats( mats ) | ( operation ) |
A list of matrices over a field \(F\) is in semi-echelon form if the list of row vectors obtained on concatenating the rows of each matrix is a semi-echelonized matrix (see SemiEchelonMat (24.10-1)).
SemiEchelonMats returns a record that contains information about a semi-echelonized form of the list mats of matrices.
The components of this record are
vectorslist of matrices, each with pivot element the identity of \(F\),
headsmatrix that contains at position [i,j], if nonzero, the number of the matrix that has the pivot element in this position
‣ SemiEchelonMatsDestructive( mats ) | ( operation ) |
Does the same as SemiEchelonMats (24.10-4), except that it may destroy its argument. Therefore the argument must be a list of matrices that are mutable.
See also chapter 25
‣ BaseMat( mat ) | ( attribute ) |
returns a basis for the row space generated by the rows of mat in the form of an immutable matrix.
‣ BaseMatDestructive( mat ) | ( operation ) |
Does the same as BaseMat (24.11-1), with the difference that it may destroy the matrix mat. The matrix mat must be mutable.
gap> mat:=[[1,2,3],[4,5,6],[7,8,9]];; gap> BaseMat(mat); [ [ 1, 2, 3 ], [ 0, 1, 2 ] ] gap> mm:= [[1,2,3],[4,5,6],[5,7,9]];; gap> BaseMatDestructive( mm ); [ [ 1, 2, 3 ], [ 0, 1, 2 ] ] gap> mm; [ [ 1, 2, 3 ], [ 0, 1, 2 ], [ 0, 0, 0 ] ]
‣ BaseOrthogonalSpaceMat( mat ) | ( attribute ) |
Let \(V\) be the row space generated by the rows of mat (over any field that contains all entries of mat). BaseOrthogonalSpaceMat( mat ) computes a base of the orthogonal space of \(V\).
The rows of mat need not be linearly independent.
‣ SumIntersectionMat( M1, M2 ) | ( operation ) |
performs Zassenhaus' algorithm to compute bases for the sum and the intersection of spaces generated by the rows of the matrices M1, M2.
returns a list of length 2, at first position a base of the sum, at second position a base of the intersection. Both bases are in semi-echelon form (see 24.10).
gap> SumIntersectionMat(mat,[[2,7,6],[5,9,4]]); [ [ [ 1, 2, 3 ], [ 0, 1, 2 ], [ 0, 0, 1 ] ], [ [ 1, -3/4, -5/2 ] ] ]
‣ BaseSteinitzVectors( bas, mat ) | ( function ) |
find vectors extending mat to a basis spanning the span of bas. Both bas and mat must be matrices of full (row) rank. It returns a record with the following components:
subspaces a basis of the space spanned by mat in upper triangular form with leading ones at all echelon steps and zeroes above these ones.
factorspaceis a list of extending vectors in upper triangular form.
factorzerois a zero vector.
headsis a list of integers which can be used to decompose vectors in the basis vectors. The ith entry indicating the vector that gives an echelon step at position i. A negative number indicates an echelon step in the subspace, a positive number an echelon step in the complement, the absolute value gives the position of the vector in the lists subspace and factorspace.
gap> BaseSteinitzVectors(IdentityMat(3,1),[[11,13,15]]); rec( factorspace := [ [ 0, 1, 15/13 ], [ 0, 0, 1 ] ], factorzero := [ 0, 0, 0 ], heads := [ -1, 1, 2 ], subspace := [ [ 1, 13/11, 15/11 ] ] )
‣ DiagonalOfMatrix( mat ) | ( function ) |
‣ DiagonalOfMat( mat ) | ( function ) |
return the diagonal of the matrix mat. If mat is not a square matrix, then the result has the same length as the rows of mat, and is padded with zeros if mat has fewer rows than columns.
gap> DiagonalOfMatrix( [ [ 1, 2, 3 ], [ 4, 5, 6 ] ] ); [ 1, 5, 0 ]
‣ UpperSubdiagonal( mat, pos ) | ( operation ) |
returns a mutable list containing the entries of the posth upper subdiagonal of the matrix mat.
gap> UpperSubdiagonal( [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ], 1 ); [ 2, 6 ] gap> UpperSubdiagonal( [ [ 1, 2 ], [ 3, 4 ], [ 5, 6 ] ], 1 ); [ 2 ] gap> UpperSubdiagonal( [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ] ], 1 ); [ 2, 7 ]
‣ DepthOfUpperTriangularMatrix( mat ) | ( attribute ) |
If mat is an upper triangular matrix this attribute returns the index of the first nonzero diagonal.
gap> DepthOfUpperTriangularMatrix([[0,1,2],[0,0,1],[0,0,0]]); 1 gap> DepthOfUpperTriangularMatrix([[0,0,2],[0,0,0],[0,0,0]]); 2
‣ CharacteristicPolynomial( [F, E, ]mat[, ind] ) | ( attribute ) |
For a square matrix mat, CharacteristicPolynomial returns the characteristic polynomial of mat, that is, the StandardAssociate (56.5-5) of the determinant of the matrix \(\textit{mat} - X \cdot I\), where \(X\) is an indeterminate and \(I\) is the appropriate identity matrix.
If fields F and E are given, then F must be a subfield of E, and mat must have entries in E. Then CharacteristicPolynomial returns the characteristic polynomial of the F-linear mapping induced by mat on the underlying E-vector space of mat. In this case, the characteristic polynomial is computed using BlownUpMat (24.13-4) for the field extension of \(E/F\) generated by the default field. Thus, if \(F = E\), the result is the same as for the one argument version.
The returned polynomials are expressed in the indeterminate number ind. If ind is not given, it defaults to \(1\).
CharacteristicPolynomial(F, E, mat) is a multiple of the minimal polynomial MinimalPolynomial(F, mat) (see MinimalPolynomial (66.8-1)).
Note that, up to GAP version 4.4.6, CharacteristicPolynomial only allowed to specify one field (corresponding to F) as an argument. That usage has been disabled because its definition turned out to be ambiguous and may have lead to unexpected results. (To ensure backward compatibility, it is still possible to use the old form if F contains the default field of the matrix, see DefaultFieldOfMatrix (24.4-2), but this feature will disappear in future versions of GAP.)
gap> CharacteristicPolynomial( [ [ 1, 1 ], [ 0, 1 ] ] ); x^2-2*x+1 gap> mat := [[0,1],[E(4)-1,E(4)]];; gap> CharacteristicPolynomial( mat ); x^2+(-E(4))*x+(1-E(4)) gap> CharacteristicPolynomial( Rationals, CF(4), mat ); x^4+3*x^2+2*x+2 gap> mat:= [ [ E(4), 1 ], [ 0, -E(4) ] ];; gap> CharacteristicPolynomial( mat ); x^2+1 gap> CharacteristicPolynomial( Rationals, CF(4), mat ); x^4+2*x^2+1
‣ RationalCanonicalFormTransform( mat ) | ( function ) |
For a matrix A, return a matrix P such that \(A^{P}\) is in rational canonical form (also called Frobenius normal form). The algorithm used is the basic textbook version and thus not of optimal complexity.
gap> aa:=[[0,-8,12,40,-36,4,0,59,15,-9],[-2,-2,-2,6,-11,1,-1,10,1,0], > [1,5,0,-6,12,-2,0,-12,-4,2],[0,0,0,2,0,0,0,7,0,0], > [0,2,-3,-7,8,-1,0,-7,-3,2],[-5,-4,-6,18,-30,2,-2,35,5,-1], > [-1,-6,6,20,-28,3,0,24,10,-6],[0,0,0,-1,0,0,0,-3,0,0], > [0,0,-1,-2,-2,0,-1,-7,0,0],[0,-8,9,21,-36,4,-2,12,12,-8]];; gap> t:=RationalCanonicalFormTransform(aa);; gap> aa^t; [ [ 0, 0, 0, 1, 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, 1, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ], [ 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 ], [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 1 ], [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 1, 0, -1 ], [ 0, 0, 0, 0, 0, 0, 0, 0, 1, -1 ] ]
‣ JordanDecomposition( mat ) | ( attribute ) |
JordanDecomposition( mat ) returns a list [S,N] such that S is a semisimple matrix and N is nilpotent. Furthermore, S and N commute and mat=S+N.
gap> mat:=[[1,2,3],[4,5,6],[7,8,9]];; gap> JordanDecomposition(mat); [ [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ], [ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ] ]
‣ BlownUpMat( B, mat ) | ( function ) |
Let B be a basis of a field extension \(F / K\), and mat a matrix whose entries are all in \(F\). (This is not checked.) BlownUpMat returns a matrix over \(K\) that is obtained by replacing each entry of mat by its regular representation w.r.t. B.
More precisely, regard mat as the matrix of a linear transformation on the row space \(F^n\) w.r.t. the \(F\)-basis with vectors \((v_1, \ldots, v_n)\) and suppose that the basis B consists of the vectors \((b_1, \ldots, b_m)\); then the returned matrix is the matrix of the linear transformation on the row space \(K^{mn}\) w.r.t. the \(K\)-basis whose vectors are \((b_1 v_1, \ldots b_m v_1, \ldots, b_m v_n)\).
Note that the linear transformations act on row vectors, i.e., each row of the matrix is a concatenation of vectors of B-coefficients.
‣ BlownUpVector( B, vector ) | ( function ) |
Let B be a basis of a field extension \(F / K\), and vector a row vector whose entries are all in \(F\). BlownUpVector returns a row vector over \(K\) that is obtained by replacing each entry of vector by its coefficients w.r.t. B.
So BlownUpVector and BlownUpMat (24.13-4) are compatible in the sense that for a matrix mat over \(F\), BlownUpVector( B, mat * vector ) is equal to BlownUpMat( B, mat ) * BlownUpVector( B, vector ).
gap> B:= Basis( CF(4), [ 1, E(4) ] );; gap> mat:= [ [ 1, E(4) ], [ 0, 1 ] ];; vec:= [ 1, E(4) ];; gap> bmat:= BlownUpMat( B, mat );; bvec:= BlownUpVector( B, vec );; gap> Display( bmat ); bvec; [ [ 1, 0, 0, 1 ], [ 0, 1, -1, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ] [ 1, 0, 0, 1 ] gap> bvec * bmat = BlownUpVector( B, vec * mat ); true
‣ CompanionMatrix( poly ) | ( operation ) |
‣ CompanionMat( poly ) | ( operation ) |
Return a fully mutable matrix that is the companion matrix of the polynomial poly. The negatives of the coefficients of poly appear in the last column of the result.
The companion matrix of poly has poly as its minimal polynomial (see MinimalPolynomial (66.8-1)) and as its characteristic polynomial (see CharacteristicPolynomial (24.13-1)).
gap> x:= X( Rationals );; pol:= x^3 + x^2 + 2*x + 3;; gap> M:= CompanionMatrix( pol );; gap> Display( M ); [ [ 0, 0, -3 ], [ 1, 0, -2 ], [ 0, 1, -1 ] ] gap> MinimalPolynomial( M ) = pol; true
Just as for row vectors, (see section 23.3), GAP has a special representation for matrices over small finite fields.
To be eligible to be represented in this way, each row of a matrix must be able to be represented as a compact row vector of the same length over the same finite field.
gap> v := Z(2)*[1,0,0,1,1]; [ Z(2)^0, 0*Z(2), 0*Z(2), Z(2)^0, Z(2)^0 ] gap> ConvertToVectorRep(v,2); 2 gap> v; <a GF2 vector of length 5> gap> m := [v];; ConvertToMatrixRep(m,GF(2));; m; <a 1x5 matrix over GF2> gap> m := [v,v];; ConvertToMatrixRep(m,GF(2));; m; <a 2x5 matrix over GF2> gap> m := [v,v,v];; ConvertToMatrixRep(m,GF(2));; m; <a 3x5 matrix over GF2> gap> v := Z(3)*[1..8]; [ Z(3), Z(3)^0, 0*Z(3), Z(3), Z(3)^0, 0*Z(3), Z(3), Z(3)^0 ] gap> ConvertToVectorRep(v); 3 gap> m := [v];; ConvertToMatrixRep(m,GF(3));; m; [ [ Z(3), Z(3)^0, 0*Z(3), Z(3), Z(3)^0, 0*Z(3), Z(3), Z(3)^0 ] ] gap> RepresentationsOfObject(m); [ "IsPositionalObjectRep", "Is8BitMatrixRep" ] gap> m := [v,v,v,v];; ConvertToMatrixRep(m,GF(3));; m; < mutable compressed matrix 4x8 over GF(3) >
All compressed matrices over GF(2) are viewed as <a nxm matrix over GF2>, while over fields GF(q) for q between 3 and 256, matrices with 25 or more entries are viewed in this way, and smaller ones as lists of lists.
Matrices can be converted to this special representation via the following functions.
Note that the main advantage of this special representation of matrices is in low dimensions, where various overheads can be reduced. In higher dimensions, a list of compressed vectors will be almost as fast. Note also that list access and assignment will be somewhat slower for compressed matrices than for plain lists.
In order to form a row of a compressed matrix a vector must accept certain restrictions. Specifically, it cannot change its length or change the field over which it is compressed. The main consequences of this are: that only elements of the appropriate field can be assigned to entries of the vector, and only to positions between 1 and the original length; that the vector cannot be shared between two matrices compressed over different fields.
This is enforced by the filter IsLockedRepresentationVector. When a vector becomes part of a compressed matrix, this filter is set for it. Assignment, Unbind (21.5-3), ConvertToVectorRep (23.3-1) and ConvertToMatrixRep (24.14-2) are all prevented from altering a vector with this filter.
gap> v := [Z(2),Z(2)];; ConvertToVectorRep(v,GF(2));; v; <a GF2 vector of length 2> gap> m := [v,v]; [ <a GF2 vector of length 2>, <a GF2 vector of length 2> ] gap> ConvertToMatrixRep(m,GF(2)); 2 gap> m2 := [m[1], [Z(4),Z(4)]]; # now try and mix in some GF(4) [ <a GF2 vector of length 2>, [ Z(2^2), Z(2^2) ] ] gap> ConvertToMatrixRep(m2); # but m2[1] is locked #I ConvertToVectorRep: locked vector not converted to different field fail gap> m2 := [ShallowCopy(m[1]), [Z(4),Z(4)]]; # a fresh copy of row 1 [ <a GF2 vector of length 2>, [ Z(2^2), Z(2^2) ] ] gap> ConvertToMatrixRep(m2); # now it works 4 gap> m2; [ [ Z(2)^0, Z(2)^0 ], [ Z(2^2), Z(2^2) ] ] gap> RepresentationsOfObject(m2); [ "IsPositionalObjectRep", "Is8BitMatrixRep" ]
Arithmetic operations (see 21.11 and the following sections) preserve the compression status of matrices in the sense that if all arguments are compressed matrices written over the same field and the result is a matrix then also the result is a compressed matrix written over this field.
There are also two operations that are only available for matrices written over finite fields.
‣ ImmutableMatrix( field, matrix[, change] ) | ( operation ) |
Let matrix be an object for which either IsMatrix (24.2-1) or IsMatrixObj (26.2-2) returns true. In the former case, matrix is a list of lists, and ImmutableMatrix returns an immutable object for which IsMatrix (24.2-1) returns true (in particular again a list of lists), which is equal to matrix, and which is in the optimal (concerning space and runtime) representation for matrices defined over field, provided that the entries of matrix lie in field. In the latter case, ImmutableMatrix returns an immutable object that is equal to the result of ChangedBaseDomain (26.6-3) when this is called with matrix and field.
This means that matrices obtained by several calls of ImmutableMatrix for the same field are compatible for fast arithmetic without need for field conversion.
If the input matrix matrix is in IsMatrix (24.2-1) then it or its rows might change their representation as a side effect of this function. However, one cannot rely on this side effect. Also, if matrix is already immutable and the result of ImmutableMatrix has the same internal representation as matrix, the result is not necessarily identical to matrix.
If change is true, matrix or its rows (if there are subobjects that represent rows) may be changed to become immutable; otherwise the rows of matrix are copied first.
‣ ConvertToMatrixRep( list[, field] ) | ( function ) |
‣ ConvertToMatrixRep( list[, fieldsize] ) | ( function ) |
‣ ConvertToMatrixRepNC( list[, field] ) | ( function ) |
‣ ConvertToMatrixRepNC( list[, fieldsize] ) | ( function ) |
This function is more technical version of ImmutableMatrix (24.14-1), which will never copy a matrix (or any rows of it) but may fail if it encounters rows locked in the wrong representation, or various other more technical problems. Most users should use ImmutableMatrix (24.14-1) instead. The NC versions of the function do less checking of the argument and may cause unpredictable results or crashes if given unsuitable arguments. Called with one argument list, ConvertToMatrixRep converts list to an internal matrix representation if possible.
Called with a list list and a finite field field, ConvertToMatrixRep converts list to an internal matrix representation appropriate for a matrix over field.
Instead of a field also its size fieldsize may be given.
It is forbidden to call this function unless all elements of list are row vectors with entries in the field field. Violation of this condition can lead to unpredictable behaviour or a system crash. (Setting the assertion level to at least 2 might catch some violations before a crash, see SetAssertionLevel (7.5-1).)
list may already be a compressed matrix. In this case, if no field or fieldsize is given, then nothing happens.
The return value is the size of the field over which the matrix ends up written, if it is written in a compressed representation.
‣ ProjectiveOrder( mat ) | ( attribute ) |
Returns an integer n and a finite field element e such that A^n = eI. mat must be a matrix defined over a finite field.
gap> ProjectiveOrder([[1,4],[5,2]]*Z(11)^0); [ 5, Z(11)^5 ]
‣ SimultaneousEigenvalues( matlist, expo ) | ( function ) |
The matrices in matlist must be matrices over GF(q) for some prime q. Together, they must generate an abelian p-group of exponent expo. Then the eigenvalues of mat in the splitting field GF(q^r) for some r are powers of an element \(\xi\) in the splitting field, which is of order expo. SimultaneousEigenvalues returns a matrix of integers mod expo \((a_{{i,j}})\), such that the power \(\xi^{{a_{{i,j}}}}\) is an eigenvalue of the i-th matrix in matlist and the eigenspaces of the different matrices to the eigenvalues \(\xi^{{a_{{i,j}}}}\) for fixed j are equal.
The following operations deal with matrices over a ring, but only care about the residues of their entries modulo some ring element. In the case of the integers and a prime number \(p\), this is effectively computation in a matrix over the prime field in characteristic \(p\).
‣ InverseMatMod( mat, obj ) | ( operation ) |
For a square matrix mat, InverseMatMod returns a matrix inv such that inv * mat is congruent to the identity matrix modulo obj, if such a matrix exists, and fail otherwise.
gap> mat:= [ [ 1, 2 ], [ 3, 4 ] ];; inv:= InverseMatMod( mat, 5 ); [ [ 3, 1 ], [ 4, 2 ] ] gap> mat * inv; [ [ 11, 5 ], [ 25, 11 ] ]
‣ BasisNullspaceModN( M, n ) | ( function ) |
M must be a matrix of integers and n a positive integer. Then BasisNullspaceModN returns a set B of vectors such that every vector v of integer modulo n satisfying v M = 0 modulo n can be expressed by a Z-linear combination of elements of B.
‣ NullspaceModQ( M, q ) | ( function ) |
‣ NullspaceModN( M, n ) | ( function ) |
M must be a matrix of integers and n a positive integer. Then NullspaceModN returns the set of all vectors of integers modulo n, which solve the homogeneous equation system v M = 0 modulo n.
NullspaceModQ is a synonym for NullspaceModN.
gap> NullspaceModN( [ [ 2 ] ], 8 ); [ [ 0 ], [ 4 ] ] gap> NullspaceModN( [ [ 2, 1 ], [ 0, 2 ] ], 6 ); [ [ 0, 0 ], [ 0, 3 ] ] gap> mat:= [ [ 1, 3 ], [ 1, 2 ], [ 1, 1 ] ];; gap> NullspaceModN( mat, 5 ); [ [ 0, 0, 0 ], [ 1, 3, 1 ], [ 2, 1, 2 ], [ 3, 4, 3 ], [ 4, 2, 4 ] ]
When multiplying two compressed matrices \(M\) and \(N\) over GF(2) of dimensions \(a \times b\) and \(b \times c\), where \(a\), \(b\) and \(c\) are all greater than or equal to 128, GAP by default uses a more sophisticated matrix multiplication algorithm, in which linear combinations of groups of 8 rows of \(M\) are remembered and re-used in constructing various rows of the product. This is called level 8 grease. To optimise memory access patterns, these combinations are stored for \((b+255)/256\) sets of 8 rows at once. This number is called the blocking level.
These levels of grease and blocking are found experimentally to give good performance across a range of processors and matrix sizes, but other levels may do even better in some cases. You can control the levels exactly using the functions below.
We plan to include greased blocked matrix multiplication for other finite fields, and greased blocked algorithms for inversion and other matrix operations in a future release.
‣ PROD_GF2MAT_GF2MAT_SIMPLE( m1, m2 ) | ( function ) |
This function performs the standard unblocked and ungreased matrix multiplication for matrices of any size.
‣ PROD_GF2MAT_GF2MAT_ADVANCED( m1, m2, g, b ) | ( function ) |
This function computes the product of m1 and m2, which must be compressed matrices over GF(2) of compatible dimensions, using level g grease and level b blocking.
Block matrices are a special representation of matrices which can save a lot of memory if large matrices have a block structure with lots of zero blocks. GAP uses the representation IsBlockMatrixRep to store block matrices.
‣ AsBlockMatrix( m, nrb, ncb ) | ( function ) |
returns a block matrix with nrb row blocks and ncb column blocks which is equal to the ordinary matrix m.
‣ BlockMatrix( blocks, nrb, ncb[, rpb, cpb, zero] ) | ( function ) |
BlockMatrix returns an immutable matrix in the sparse representation IsBlockMatrixRep. The nonzero blocks are described by the list blocks of triples \([ \textit{i}, \textit{j}, M(i,j) ]\) each consisting of a matrix \(M(i,j)\) and its block coordinates in the block matrix to be constructed. All matrices \(M(i,j)\) must have the same dimensions. As usual the first coordinate specifies the row and the second one the column. The resulting matrix has nrb row blocks and ncb column blocks.
If blocks is empty (i.e., if the matrix is a zero matrix) then the dimensions of the blocks must be entered as rpb and cpb, and the zero element as zero.
Note that all blocks must be ordinary matrices (see IsOrdinaryMatrix (24.2-2)), and also the block matrix is an ordinary matrix.
gap> M := BlockMatrix([[1,1,[[1, 2],[ 3, 4]]], > [1,2,[[9,10],[11,12]]], > [2,2,[[5, 6],[ 7, 8]]]],2,2); <block matrix of dimensions (2*2)x(2*2)> gap> Display(M); [ [ 1, 2, 9, 10 ], [ 3, 4, 11, 12 ], [ 0, 0, 5, 6 ], [ 0, 0, 7, 8 ] ]
‣ MatrixByBlockMatrix( blockmat ) | ( attribute ) |
returns a plain ordinary matrix that is equal to the block matrix blockmat.
‣ SimplexMethod( A, b, c ) | ( function ) |
Find a rational vector x that maximizes \(\textit{x}\cdot\textit{c}\), subject to the constraint \(\textit{A}\cdot\textit{x}\le\textit{b}\).
gap> A:=[[3,1,1,4],[1,-3,2,3],[2,1,3,-1]];; gap> b:=[12,7,10];;c:=[2,4,3,1];; gap> SimplexMethod(A,b,c); [ [ 0, 52/5, 0, 2/5 ], 42 ]
generated by GAPDoc2HTML