[MathJax on]

26 Vector and Matrix Objects

This chapter describes an interface to vector and matrix objects which are not represented by plain lists (of plain lists), cf. Chapters 23 and 24.

26.1 Concepts and Rules for Vector and Matrix Objects

Traditionally, vectors and matrices in GAP have been represented by (lists of) lists, see the chapters 23 and 24. More precisely, the term vector (corresponding to the filter IsVector (31.14-14)) is used in the abstract sense of an element of a vector space, the term row vector (corresponding to IsRowVector (23.1-1)) is used to denote a coordinate vector which is represented by a GAP list (see IsList (21.1-1)), and the term matrix is used to denote a list of lists, with additional properties (see IsMatrix (24.2-1)).

Unfortunately, such lists (objects in IsPlistRep (21.24-2)) cannot store their type, and so it is impossible to use the advantages of GAP's method selection on them. This situation is unsustainable in the long run since more special representations (compressed, sparse, etc.) have already been and even more will be implemented. Here we describe a programming interface to vectors and matrices, which solves this problem,

The idea of this interface is that GAP should be able to represent vectors and matrices by objects that store their type, in order to benefit from method selection. These objects are created by Objectify (79.1-1), we therefore refer to the them as vector objects and matrix objects respectively.

(Of course the terminology is somewhat confusing: An abstract matrix in GAP can be represented either by a list of lists or by a matrix object. It can be detected from the filter IsMatrixOrMatrixObj (26.2-3); this is the union of the filters IsMatrix (24.2-1) –which denotes those matrices that are represented by lists of lists– and the filter IsMatrixObj (26.2-2) –which defines proper matrix objects in the above sense. In particular, we do not regard the objects in IsMatrix (24.2-1) as special cases of objects in IsMatrixObj (26.2-2), or vice versa. Thus one can install specific methods for all three situations: just for proper matrix objects, just for matrices represented by lists of lists, or for both kinds of matrices. For example, a GAP package may decide to accept only proper matrix objects as arguments of its functions, or it may try to support also objects in IsMatrix (24.2-1) as far as this is possible.)

We want to be able to write (efficient) code that is independent of the actual representation (in the sense of GAP's representation filters, see Section 13.4) and preserves it.

This latter requirement makes it necessary to distinguish between different representations of matrices: Row list matrices (see IsRowListMatrix (26.2-4) behave basically like lists of rows, in particular the rows are individual GAP objects that can be shared between different matrix objects. One can think of other representations of matrices, such as matrices whose subobjects represent columns, or flat matrices which do not have subobjects like rows or columns at all. The different kinds of matrices have to be distinguished already with respect to the definition of the operations for them.

In particular vector and matrix objects know their base domain (see BaseDomain (26.3-1)) and their dimensions. The basic condition is that the entries of vector and matrix objects must either lie in the base domain or naturally embed in the sense that addition and multiplication automatically work with elements of the base domain; for example, a matrix object over a polynomial ring may also contain entries from the coefficient ring.

Vector and matrix objects may be mutable or immutable. Of course all operations changing an object are only allowed/implemented for mutable variants.

Vector objects are equal with respect to \= (31.11-1) if they have the same length and the same entries. It is not necessary that they have the same base domain. Matrices are equal with respect to \= (31.11-1) if they have the same dimensions and the same entries.

For a row list matrix object, it is not guaranteed that all its rows have the same vector type. It is for example thinkable that a matrix object stores some of its rows in a sparse representation and some in a dense one. However, it is guaranteed that the rows of two matrices in the same representation are compatible in the sense that all vector operations defined in this interface can be applied to them and that new matrices in the same representation as the original matrix can be formed out of them.

Note that there is neither a default mapping from the set of matrix object representations to the set of vector representations nor one in the reverse direction. There is in general no associated vector object representation to a matrix object representation or vice versa. (However, CompatibleVectorFilter (26.3-3) may describe a vector object representation that is compatible with a given matrix object.)

The recommended way to write code that preserves the representation basically works by using constructing operations that take template objects to decide about the intended representation for the new object.

Vector and matrix objects do not have to be GAP lists in the sense of IsList (21.1-1). Note that objects not in the filter IsList (21.1-1) need not support all list operations, and their behaviour is not prescribed by the rules for lists, e.g., behaviour w.r.t. arithmetic operations. However, row list matrices behave nearly like lists of row vectors that insist on being dense and containing only vectors of the same length and with the same base domain.

Vector and matrix objects are not likely to benefit from GAP's immediate methods (see section 78.7). Therefore it may be useful to set the filter IsNoImmediateMethodsObject (78.7-2) in the definition of new kinds of vector and matrix objects.

For information on how to implement new IsMatrixObj (26.2-2) and IsVectorObj (26.2-1) representations see Section 26.14.

26.2 Categories of Vector and Matrix Objects

Currently the following categories of vector and matrix objects are supported in GAP. More can be added as soon as there is need for them.

26.2-1 IsVectorObj

The idea behind vector objects is that one wants to deal with objects like coefficient lists of fixed length over a given domain R, say, which can be added and can be multiplied from the left with elements from R. A vector object v, say, is always a copyable object (see IsCopyable (12.6-1)) in IsVector (31.14-14), which knows the values of BaseDomain (26.3-1) (with value R) and Length (21.17-5), where R is a domain (see Chapter 12.4) that has methods for Zero (31.10-3), One (31.10-2), \in (30.6-1), Characteristic (31.10-1), IsFinite (30.4-2). We say that v is defined over R. Typically, R will be at least a semiring.

For creating new vector objects compatible with v, NewVector (26.4-1) requires that also the value of ConstructingFilter (26.3-2) is known for v.

Further, entry access v[i] is expected to return a GAP object, for 1 ≤ i ≤ Length( v ), and that these entries of v belong to the base domain R.

Note that we do not require that v is a list in the sense of IsList (21.1-1), in particular the rules of list arithmetic (see the sections 21.13 and 21.14) need not hold. For example, the sum of two vector objects of different lengths or defined over different base domains is not defined, and a plain list of vector objects is not a matrix. Also unbinding entries of vector objects is not defined.

Scalar multiplication from the left is defined only with elements from R.

The family of v (see FamilyObj (13.1-1)) is the same as the family of its base domain R. However, it is not required that the entries lie in R in the sense of \in (30.6-1), also values may occur that can be naturally embedded into R. For example, if R is a polynomial ring then some entries in v may be elements of the coefficient ring of R.

26.2-2 IsMatrixObj

The idea behind matrix objects is that one wants to deal with objects like m by n arrays over a given domain R, say, which can be added and multiplied and can be multiplied from the left with elements from R. A matrix object M, say, is always a copyable object (see IsCopyable (12.6-1)) in IsVector (31.14-14) and IsScalar (31.14-20), which knows the values of BaseDomain (26.3-1) (with value R), NumberRows (26.3-5) (with value m), NumberColumns (26.3-5) (with value n), where R is a domain (see Chapter 12.4) that has methods for Zero (31.10-3), One (31.10-2), \in (30.6-1), Characteristic (31.10-1), IsFinite (30.4-2). We say that v is defined over R. Typically, R will be at least a semiring.

For creating new matrix objects compatible with M, NewMatrix (26.4-4) requires that also the value of ConstructingFilter (26.3-2) is known for M.

Further, entry access M[i,j] is expected to return a GAP object, for 1 ≤ i ≤ m and 1 ≤ j ≤ n, and that these entries of M belong to the base domain R.

Note that we do not require that M is a list in the sense of IsList (21.1-1), in particular the rules of list arithmetic (see the sections 21.13 and 21.14) need not hold. For example, accessing rows of M via \[\] (21.2-1) is in general not possible, and the sum of two matrix objects with different numbers of rows or columns is not defined. Also unbinding entries of matrix objects is not defined.

Scalar multiplication from the left is defined only with elements from R.

It is not assumed that the multiplication in R is associative, and we do not define what the k-th power of a matrix object is in this case, for positive integers k. (However, a default powering method is available.)

The filter IsMatrixObj alone does not imply that the multiplication is the usual matrix multiplication. This multiplication can be defined via the filter IsOrdinaryMatrix (24.2-2); this filter together with the associativity of the base domain also implies the associativity of matrix multiplication. For example, elements of matrix Lie algebras (see LieObject (64.1-1)) lie in IsMatrixObj but not in IsOrdinaryMatrix (24.2-2).

The family of M (see FamilyObj (13.1-1)) is the collections family (see CollectionsFamily (30.2-1)) of its base domain R. However, it is not required that the entries lie in R in the sense of \in (30.6-1), also values may occur that can be naturally embedded into R. For example, if R is a polynomial ring then some entries in M may be elements of the coefficient ring of R.

26.2-3 IsMatrixOrMatrixObj

Several functions are defined for objects in IsMatrix (24.2-1) and objects in IsMatrixObj (26.2-2). All these objects lie in the filter IsMatrixOrMatrixObj. It should be used in situations where an object can be either a list of lists in IsMatrix (24.2-1) or a proper matrix object in IsMatrixObj (26.2-2), for example as a requirement in the installation of a method for such an argument.

gap> m:= IdentityMat( 2, GF(2) );;
gap> IsMatrix( m );  IsMatrixObj( m ); IsMatrixOrMatrixObj( m );
true
false
true
gap> m:= NewIdentityMatrix( IsPlistMatrixRep, GF(2), 2 );;
gap> IsMatrix( m );  IsMatrixObj( m ); IsMatrixOrMatrixObj( m );
false
true
true

26.2-4 IsRowListMatrix

A row list matrix object is a matrix object (see IsMatrixObj (26.2-2)) M which admits access to its rows, that is, list access M[i] (see \[\] (21.2-1)) yields the i-th row of M, for 1 ≤ i ≤ NumberRows( M ).

All rows are IsVectorObj (26.2-1) objects in the same representation. Several rows of a row list matrix object can be identical objects, and different row list matrices may share rows. Row access just gives a reference to the row object, without copying the row.

Matrix objects in IsRowListMatrix are not necessarily in IsList (21.1-1), and then they need not obey the general rules for lists.

26.3 Defining Attributes of Vector and Matrix Objects

26.3-1 BaseDomain

The vector object vector or matrix object matrix, respectively, is defined over the domain given by its BaseDomain value.

Note that not all entries of the object necessarily lie in its base domain with respect to \in (30.6-1), see Section 26.1.

26.3-2 ConstructingFilter

Returns: a filter

Called with a vector object v or a matrix object M, respectively, ConstructingFilter returns a filter f such that when NewVector (26.4-1) or NewMatrix (26.4-4), respectively, is called with f then a vector object or a matrix object, respectively, in the same representation as the argument is produced.

If the ConstructingFilter value of v or M implies IsCopyable (12.6-1) then mutable versions of v or M can be created, otherwise all vector or matrix objects with this filter are immutable.

26.3-3 CompatibleVectorFilter

Returns: a filter

Called with a matrix object M, CompatibleVectorFilter returns either a filter f such that vector objects with ConstructingFilter (26.3-2) value f are compatible in the sense that M can be multiplied with these vector objects, of fail if no such filter is known.

26.3-4 Length

returns the length of the vector object v, which is defined to be the number of entries of v.

26.3-5 NumberRows and NumberColumns

For a matrix object M, NumberRows and NumberColumns store the number of rows and columns of M, respectively.

NrRows and NrCols are synonyms of NumberRows and NumberColumns, respectively.

26.4 Constructing Vector and Matrix Objects

26.4-1 NewVector and NewZeroVector

For a filter filt, a semiring R, and a list list of elements that belong to R, NewVector returns a vector object which has the ConstructingFilter (26.3-2) filt, the BaseDomain (26.3-1) R, and the entries in list. The list list is guaranteed not to be changed by this operation.

If the global option check is set to false then NewVector need not perform consistency checks.

Similarly, NewZeroVector returns a vector object of length n which has filt and R as ConstructingFilter (26.3-2) and BaseDomain (26.3-1) values, and contains the zero of R in each position.

The returned object is mutable if and only if filt implies IsCopyable (12.6-1).

26.4-2 Vector

Returns: a vector object

If a filter filt is given as the first argument then a vector object is returned that has ConstructingFilter (26.3-2) value filt, is defined over the base domain R, and has the entries given by the list list or the vector object v, respectively.

If a semiring R is given as the first argument then a vector object is returned whose ConstructingFilter (26.3-2) value is guessed from R, again with base domain R and entries given by the last argument.

In the remaining cases with two arguments, the first argument is a list or a vector object that defines the entries of the result, and the second argument is a vector object whose ConstructingFilter (26.3-2) and BaseDomain (26.3-1) are taken for the result.

If only a list list is given then both the ConstructingFilter (26.3-2) and the BaseDomain (26.3-1) are guessed from this list.

The variant Vector( v1, v2 ) is supported also for the case that v2 is a row vector but not a vector object. In this situation, the result is a row vector that is equal to v1 and whose internal representation fits to that of v2.

If the global option check is set to false then Vector need not perform consistency checks.

If the ConstructingFilter (26.3-2) value of the result implies IsCopyable (12.6-1) then the result is mutable if and only if the argument that determines the entries of the result (list, v, v1) is mutable.

In the case of a mutable result, it is not guaranteed that the given list of entries is copied.

Default methods for Vector delegate to NewVector (26.4-1).

26.4-3 ZeroVector

Returns: a vector object

For a filter filt, a semiring R and a nonnegative integer len, this operation returns a new vector object of length len over R in the representation filt containing only zeros.

If only R and len are given, then GAP guesses a suitable representation.

For a vector object v and a nonnegative integer len, this operation returns a new vector object of length len in the same representation as v containing only zeros.

For a matrix object M and a nonnegative integer len, this operation returns a new zero vector object of length len in the representation given by the CompatibleVectorFilter (26.3-3) value of M, provided that such a representation exists.

If the ConstructingFilter (26.3-2) value of the result implies IsCopyable (12.6-1) then the result is mutable.

Default methods for ZeroVector delegate to NewZeroVector (26.4-1).

26.4-4 NewMatrix, NewZeroMatrix, NewIdentityMatrix

For a filter filt, a semiring R, a positive integer ncols, and a list list, NewMatrix returns a matrix object which has the ConstructingFilter (26.3-2) filt, the BaseDomain (26.3-1) R, n columns (see NumberColumns (26.3-5)), and the entries described by list, which can be either a plain list of vector objects of length ncols or a plain list of plain lists of length ncols or a plain list of length a multiple of ncols containing the entries in row major order. The list list is guaranteed not to be changed by this operation.

The corresponding entries must be in or compatible with R. If list already contains vector objects, they are copied.

If the global option check is set to false then NewMatrix need not perform consistency checks.

Similarly, NewZeroMatrix returns a zero matrix object with m rows and n columns which has filt and R as ConstructingFilter (26.3-2) and BaseDomain (26.3-1) values.

Similarly, NewIdentityMatrix returns an identity matrix object with n rows and columns which has filt and R as ConstructingFilter (26.3-2) and BaseDomain (26.3-1) values, and contains the identity element of R in the diagonal and the zero of R in each off-diagonal position.

The returned object is mutable if and only if filt implies IsCopyable (12.6-1).

26.4-5 Matrix

Returns: a matrix object

If a filter filt is given as the first argument then a matrix object is returned that has ConstructingFilter (26.3-2) value filt, is defined over the base domain R, and has the entries given by the list list or the matrix object M, respectively. Here list can be either a list of plain lists that describe the entries of the rows, or a flat list of the entries in row major order, where ncols defines the number of columns.

If a semiring R is given as the first argument then a matrix object is returned whose ConstructingFilter (26.3-2) value is guessed from R, again with base domain R and entries given by the last argument.

In those remaining cases where the last argument is a matrix object, the first argument is a list or a matrix object that defines (together with ncols if applicable) the entries of the result, and the ConstructingFilter (26.3-2) and BaseDomain (26.3-1) of the last argument are taken for the result.

Finally, if only a list list and perhaps ncols is given then both the ConstructingFilter (26.3-2) and the BaseDomain (26.3-1) are guessed from the list.

If the global option check is set to false then Matrix need not perform consistency checks.

If the ConstructingFilter (26.3-2) value of the result implies IsCopyable (12.6-1) then the result is mutable if and only if the argument that determines the entries of the result (list, M, M1) is mutable.

In the case of a mutable result, it is guaranteed that the given list list is copied in the sense of ShallowCopy (12.7-1), and if list is a nested list then it is not guaranteed that also the entries of list are copied.

Default methods for Matrix delegate to NewMatrix (26.4-4).

26.4-6 ZeroMatrix

Returns: a matrix object

For a matrix object M and two nonnegative integers m and n, this operation returns a new matrix object with m rows and n columns in the same representation and over the same base domain as M containing only zeros.

If a semiring R and two nonnegative integers m and n are given, the representation of the result is guessed from R.

If a filter filt and a semiring R are given as the first and second argument, they are taken as the values of ConstructingFilter (26.3-2) and BaseDomain (26.3-1) of the result.

If the ConstructingFilter (26.3-2) value of the result implies IsCopyable (12.6-1) then the result is fully mutable.

Default methods for ZeroMatrix delegate to NewZeroMatrix (26.4-4).

26.4-7 IdentityMatrix

Returns: a matrix object

For a matrix object M and a nonnegative integer n, this operation returns a new identity matrix object with n rows and columns in the same representation and over the same base domain as M.

If a semiring R and a nonnegative integer n is given, the representation of the result is guessed from R.

If a filter filt and a semiring R are given as the first and second argument, they are taken as the values of ConstructingFilter (26.3-2) and BaseDomain (26.3-1) of the result.

If the ConstructingFilter (26.3-2) value of the result implies IsCopyable (12.6-1) then the result is fully mutable.

Default methods for IdentityMatrix delegate to NewIdentityMatrix (26.4-4).

26.5 Operations for Base Domains of Vector and Matrix Objects

26.5-1 OneOfBaseDomain and ZeroOfBaseDomain

These attributes return the identity element and the zero element of the BaseDomain (26.3-1) value of the vector object v or the matrix object M, respectively.

If v or M, respectively, is a plain list (see IsPlistRep (21.24-2)) then computing its BaseDomain (26.3-1) value can be regarded as expensive, whereas calling OneOfBaseDomain or ZeroOfBaseDomain can be regarded as cheap. If v or M, respectively, is not a plain list then one can also call BaseDomain (26.3-1) first, without loss of performance.

26.6 Operations for Vector and Matrix Objects

26.6-1 Comparison of Vector and Matrix Objects

Two vector objects in IsList (21.1-1) are equal if they are equal as lists. Two matrix objects in IsList (21.1-1) are equal if they are equal as lists.

Two vector objects of which at least one is not in IsList (21.1-1) are equal with respect to \= (31.11-1) if they have the same ConstructingFilter (26.3-2) value, the same BaseDomain (26.3-1) value, the same length, and the same entries.

Two matrix objects of which at least one is not in IsList (21.1-1) are equal with respect to \= (31.11-1) if they have the same ConstructingFilter (26.3-2) value, the same BaseDomain (26.3-1) value, the same dimensions, and the same entries.

We do not state a general rule how vector and matrix objects shall behave w.r.t. the comparison by \< (31.11-1). Note that a row lexicographic order would be quite unnatural for matrices that are internally represented via a list of columns.

Note that the operations \= (31.11-1) and \< (31.11-1) are used to form sorted lists and sets of objects, see for example Sort (21.18-1) and Set (30.3-7).

26.6-2 Unpack

Returns: A plain list

Returns a new mutable plain list (see IsPlistRep (21.24-2)) containing the entries of the vector object v or the matrix object M, respectively. In the case of a matrix object, the result is a plain list of plain lists.

Changing the result does not change v or M, respectively. The entries themselves are not copied.

26.6-3 ChangedBaseDomain

For a vector object v (a matrix object M) and a semiring R, ChangedBaseDomain returns a new vector object (matrix object) with BaseDomain (26.3-1) value R, ConstructingFilter (26.3-2) value equal to that of v (M), and the same entries as v (M).

The result is mutable if and only if v (M) is mutable.

For example, one can create a vector defined over GF(4) from a vector defined over GF(2) with this operation.

26.6-4 Randomize

Replaces every entry in the mutable vector object v or matrix object M, respectively, with a random one from the base domain of v or M, respectively, and returns the argument.

If given, the random source Rs is used to compute the random elements. Note that in this case, a Random (14.7-2) method must be available that takes a random source as its first argument and the base domain as its second argument.

26.7 List Like Operations for Vector Objects

The following operations that are defined for lists are useful also for vector objects. (More such operations can be added if this is appropriate.)

26.7-1 Element Access and Assignment for Vector Objects

For a vector object v and a positive integer i that is not larger than the length of v (see Length (26.3-4)), v[i] is the entry at position i.

If v is mutable, i is as above, and obj is an object from the base domain of v then v[i]:= obj assigns obj to the i-th position of v.

If list is a list of positive integers that are not larger than the length of v then v{list} returns a new mutable vector object in the same representation as v (see ConstructingFilter (26.3-2)) that contains the list[ k ]-th entry of v at position k.

If the global option check is set to false then \[\]\:\= need not perform consistency checks.

Note that the sublist assignment operation \{\}\:\= (21.4-1) is left out here since it tempts the programmer to use constructions like v{ [ 1 .. 3 ] }:= w{ [ 4 .. 6 ] } which produces an unnecessary intermediate object; one should use CopySubVector (26.9-3) instead.

26.7-2 PositionNonZero

Returns: An integer

Returns the index of the first entry in the vector object v that is not zero. If all entries are zero, the function returns Length(v) + 1.

26.7-3 PositionLastNonZero

Returns: An integer

Returns the index of the last entry in the vector object v that is not zero. If all entries are zero, the function returns 0.

26.7-4 ListOp

Returns: A plain list

Applies the function func to each entry of the vector object v and returns the results as a mutable plain list. This allows for calling List (30.3-5) on vector objects.

If the argument func is not given, applies IdFunc (5.4-6) to all entries.

26.8 Arithmetical Operations for Vector Objects

26.8-1 Unary Arithmetical Operations for Vector Objects

Returns: a vector object

For a vector object v, the operations for computing the additive inverse with prescribed mutability return a vector object with the same ConstructingFilter (26.3-2) and BaseDomain (26.3-1) values, such that the sum with v is a zero vector. It is not specified what happens if the base domain does not admit the additive inverses of the entries.

Analogously, the operations for computing a zero vector with prescribed mutability return a vector object compatible with v.

IsZero returns true if all entries in v are zero, and false otherwise.

Characteristic returns the corresponding value of the BaseDomain (26.3-1) value of v.

26.8-2 Binary Arithmetical Operations for Vector Objects

The sum and the difference, respectively, of two vector objects v1 and v2 is a new mutable vector object whose entries are the sums and the differences of the entries of the arguments.

The product of a scalar s and a vector object v (from the left or from the right) is a new mutable vector object whose entries are the corresponding products.

The quotient of a vector object v and a scalar s is a new mutable vector object whose entries are the corresponding quotients.

The product of two vector objects v1 and v2 as well as the result of ScalarProduct is the standard scalar product of the two arguments (an element of the base domain of the vector objects).

All this is defined only if the vector objects have the same length and are defined over the same base domain and have the same representation, and if the products with the given scalar belong to the base domain; otherwise it is not specified what happens. If the result is a vector object then it has the same representation and the same base domain as the given vector object(s).

26.8-3 AddVector

Returns: nothing

Called with two vector objects dst and src, this function replaces the entries of dst in-place by the entries of the sum dst + src.

If a scalar mul is given as the third or second argument, respectively, then the entries of dst get replaced by those of dst + src * mul or dst + mul * src, respectively.

If the optional parameters from and to are given then only the index range [from..to] is guaranteed to be affected. Other indices may be affected, if it is more convenient to do so. This can be helpful if entries of src are known to be zero.

If from is bigger than to, the operation does nothing.

26.8-4 MultVector

Returns: nothing

These operations multiply v by mul in-place where MultVectorLeft multiplies with mul from the left and MultVectorRight does so from the right.

Note that MultVector is just a synonym for MultVectorLeft. This was chosen because vectors in GAP are by default row vectors and scalar multiplication is usually written as a ⋅ v = a ⋅ [v_1, ..., v_n] = [a ⋅ v_1, ..., a ⋅ v_n] with scalars being applied from the left.

If the optional parameters from and to are given then only the index range [from..to] is guaranteed to be affected. Other indices may be affected, if it is more convenient to do so. This can be helpful if entries of v are known to be zero. If from is bigger than to, the operation does nothing.

26.9 Operations for Vector Objects

26.9-1 ConcatenationOfVectors

Returns: a vector object

Returns a new mutable vector object in the representation of v1 or the first entry of the nonempty list vlist of vector objects, respectively, such that the entries are the concatenation of the given vector objects.

(Note that Concatenation (21.20-1) is a function for which no methods can be installed.)

26.9-2 ExtractSubVector

Returns: a vector object

Returns a new mutable vector object of the same vector representation as v, containing the entries of v at the positions in the list l.

This is the same as v{l}, the name ExtractSubVector was introduced in analogy to ExtractSubMatrix (26.11-3), for which no equivalent syntax using curly brackets is available.

26.9-3 CopySubVector

Returns: nothing

For two vector objects src and dst, such that dst is mutable, and two lists scols and dcols of positions, CopySubVector assigns the entries src{ scols } (see ExtractSubVector (26.9-2)) to the positions dcols in dst, but without creating an intermediate object and thus –at least in special cases– much more efficiently.

For certain objects like compressed vectors this might be significantly more efficient if scols and dcols are ranges with increment 1.

If the global option check is set to false then CopySubVector need not perform consistency checks.

26.9-4 WeightOfVector

Returns: an integer

returns the Hamming weight of the vector object v, i.e., the number of nonzero entries in v.

26.9-5 DistanceOfVectors

Returns: an integer

returns the Hamming distance of the vector objects v1 and v2, i.e., the number of entries in which the vectors differ. The vectors must have equal length.

26.10 Arithmetical Operations for Matrix Objects

26.10-1 Unary Arithmetical Operations for Matrix Objects

Returns: a matrix object

For a vector object M, the operations for computing the additive inverse with prescribed mutability return a matrix object with the same ConstructingFilter (26.3-2) and BaseDomain (26.3-1) values, such that the sum with M is a zero matrix. It is not specified what happens if the base domain does not admit the additive inverses of the entries.

Analogously, the operations for computing a zero matrix with prescribed mutability return a matrix object compatible with M.

The operations for computing an identity matrix with prescribed mutability return a matrix object compatible with M, provided that the base domain admits this and M is square and nonempty.

Analogously, the operations for computing an inverse matrix with prescribed mutability return a matrix object compatible with M, provided that M is invertible. (If M is not invertible then the operations return fail.)

IsZero returns true if all entries in M are zero, and false otherwise. IsOne returns true if M is nonempty and square and contains the identity of the base domain in the diagonal, and zero in all other places.

Characteristic returns the corresponding value of the BaseDomain (26.3-1) value of M.

26.10-2 Binary Arithmetical Operations for Matrix Objects

The sum and the difference, respectively, of two matrix objects M1 and M2 is a new fully mutable matrix object whose entries are the sums and the differences of the entries of the arguments.

The product of a scalar s and a matrix object M (from the left or from the right) is a new fully mutable matrix object whose entries are the corresponding products.

The product of two matrix objects M1 and M2 is a new fully mutable matrix object; if both M1 and M2 are in the filter IsOrdinaryMatrix (24.2-2) then the entries of the result are those of the ordinary matrix product.

The quotient of a matrix object M and a scalar s is a new fully mutable matrix object whose entries are the corresponding quotients.

For a nonempty square matrix object M over an associative base domain, and a positive integer n, M^n is a fully mutable matrix object whose entries are those of the n-th power of M. If n is zero then M^n is an identity matrix, and if n is a negative integer and M is invertible then M^n is the (-n)-th power of the inverse of M.

All this is defined only if the matrix objects have the same dimensions and are defined over the same base domain and have the same representation, and if the products with the given scalar belong to the base domain; otherwise it is not specified what happens. If the result is a matrix object then it has the same representation and the same base domain as the given matrix object(s).

26.11 Operations for Matrix Objects

26.11-1 MatElm

Returns: an entry of the matrix object

For a matrix object M, this operation returns the entry in row row and column col.

Also the syntax M[ row, col ] is supported.

Note that this is not equivalent to M[ row ][ col ], which would first try to access M[ row ], and this is in general not possible.

26.11-2 SetMatElm

Returns: nothing

For a mutable matrix object M, this operation assigns the object obj to the position in row row and column col, provided that obj is compatible with the BaseDomain (26.3-1) value of M.

Also the syntax M[ row, col ]:= obj is supported.

Note that this is not equivalent to M[ row ][ col ]:= obj, which would first try to access M[ row ], and this is in general not possible.

If the global option check is set to false then SetMatElm need not perform consistency checks.

26.11-3 ExtractSubMatrix

Creates a copy of the submatrix described by the two lists, which mean subsets of row and column positions, respectively. This does M{rows}{cols} and returns the result. It preserves the representation of the matrix.

If the ConstructingFilter (26.3-2) value of the result implies IsCopyable (12.6-1) then the result is fully mutable.

26.11-4 MutableCopyMatrix

For a matrix object M, this operation returns a fully mutable copy of M, with the same ConstructingFilter (26.3-2) and BaseDomain (26.3-1) values,

26.11-5 CopySubMatrix

Returns: nothing

Does dst{drows}{dcols} := src{srows}{scols} without creating an intermediate object and thus –at least in special cases– much more efficiently. For certain objects like compressed vectors this might be significantly more efficient if scols and dcols are ranges with increment 1.

If the global option check is set to false then CopySubMatrix need not perform consistency checks.

26.11-6 CompatibleVector

Returns: a vector object

Called with a matrix object M with m rows, this operation returns a mutable zero vector object v of length m and in the representation given by the CompatibleVectorFilter (26.3-3) value of M (provided that such a representation exists).

The idea is that there should be an efficient way to form the product vM.

26.11-7 RowsOfMatrix

Returns: a plain list

Called with a matrix object M, this operation returns a plain list of objects in the representation given by the CompatibleVectorFilter (26.3-3) value of M (provided that such a representation exists), where the i-th entry describes the i-th row of the input.

26.11-8 CompanionMatrix

Returns: a matrix object

For a monic, univariate polynomial pol whose coefficients lie in the base domain of the matrix object M, CompanionMatrix returns the companion matrix of pol, as a matrix object with the same ConstructingFilter (26.3-2) and BaseDomain (26.3-1) values as M.

We use column convention, that is, the negatives of the coefficients of pol appear in the last column of the result.

If a filter filt and a semiring R are given then the companion matrix is returned as a matrix object with ConstructingFilter (26.3-2) value filt and BaseDomain (26.3-1) value R.

If only pol and a semiring R are given, the representation of the result is guessed from R.

If the ConstructingFilter (26.3-2) value of the result implies IsCopyable (12.6-1) then the result is fully mutable.

gap> x:= X( GF(5) );;  pol:= x^3 + x^2 + 2*x + 3;;
gap> M:= CompanionMatrix( IsPlistMatrixRep, pol, GF(25) );;
gap> Display( M );
<3x3-matrix over GF(5^2):
[[ 0*Z(5), 0*Z(5), Z(5) ]
 [ Z(5)^0, 0*Z(5), Z(5)^3 ]
 [ 0*Z(5), Z(5)^0, Z(5)^2 ]
]>

26.12 Operations for Row List Matrix Objects

In general, matrix objects are not lists in the sense of IsList (21.1-1), and they need not behave like lists, that is, they need not obey all the rules for lists that are stated in Chapter 21. There are situations where one wants to have matrix objects that can on the one hand benefit from GAP's method selection, as is explained in Section 26.1, and do on the other hands support access to GAP objects that represent their rows (which are suitable vector objects). Matrix objects whose ConstructingFilter (26.3-2) value implies IsRowListMatrix (26.2-4) support the operations described in this section.

One implementation of such matrices is given by the ConstructingFilter (26.3-2) value IsPlistMatrixRep (26.16-3), and any row of these matrices is a vector object in IsPlistVectorRep (26.15-3). Note that these objects do not lie in IsList (21.1-1) (and in particular not in IsPlistRep (21.24-2)), thus we are allowed to define the above operations only restrictively, as follows.

Unbinding an entry in a row or unbinding a row in a matrix is allowed only in the last position, that is, the vector and matrix objects insist on being dense. All rows of a matrix must have the same length and the same base domain.

26.12-1 List Access for a Row List Matrix

Returns: a vector object

If M is a row list matrix and if pos is a positive integer not larger than the number of rows of M, this operation returns the pos-th row of M.

It is not specified what happens if pos is larger.

26.12-2 List Assignment for a Row List Matrix

Returns: nothing

If M is a row list matrix, v is a vector object that can occur as a row in M (that is, v has the same base domain, the right length, and the right vector representation), and if pos is a positive integer not larger than the number of rows of M plus 1, this operation sets v as the pos-th row of M.

In all other situations, it is not specified what happens.

26.12-3 Sublist Access for a Row List Matrix

Returns: a row list matrix

For a row list matrix M and a list poss of positions, M{ poss } returns a new mutable row list matrix with the same representation as M, whose rows are identical to the rows at the positions in the list poss in M.

26.12-4 Sublist Assignment for a Row List Matrix

Returns: nothing

For a mutable row list matrix M, a list poss of positions, and a row list matrix M2 of the same vector type and with the same base domain, M{ poss }:= M2 assigns the rows of M2 to the positions poss in the list of rows of M.

It is not specified what happens if the resulting range of row positions is not dense.

26.12-5 IsBound\[\]

Returns: true or false

For a row list matrix M and a positive integer pos, IsBound( M[ pos ] ) returns true if pos is at most the number of rows of M, and false otherwise.

26.12-6 Unbind\[\]

Returns: nothing

For a mutable row list matrix M with pos rows, Unbind( M[ pos ] ) removes the last row. It is not specified what happens if pos has another value.

26.12-7 Add

Returns: nothing

For a mutable row list matrix M and a vector object v that is compatible with the rows of M, the two argument version adds v at the end of the list of rows of M.

If a positive integer pos is given then v is added in position pos, and all later rows are shifted up by one position.

26.12-8 Remove

Returns: a vector object if the removed row exists, otherwise nothing

For a mutable row list matrix M, this operation removes the pos-th row and shifts the later rows down by one position. The default for pos is the number of rows of M.

If the pos-th row existed in M then it is returned, otherwise nothing is returned.

26.12-9 Append

Returns: nothing

For two row list matrices M1, M2 such that M1 is mutable and such that the ConstructingFilter (26.3-2) and BaseDomain (26.3-1) values are equal, this operation appends the rows of M2 to the rows of M1.

26.12-10 ShallowCopy

Returns: a matrix object

For a row list matrix M, this operation returns a new mutable matrix with the same ConstructingFilter (26.3-2) and BaseDomain (26.3-1) values as M, which shares its rows with M.

26.12-11 ListOp

Returns: a plain list

For a row list matrix M, the variant with one argument returns the plain list (see IsPlistRep (21.24-2)) of its rows, and the variant with two arguments returns the plain list of values of these rows under the function func.

26.13 Basic operations for row/column reductions

26.13-1 MultMatrixRowLeft

Returns: nothing

Multiplies the i-th row of the mutable matrix mat with the scalar elm from the left in-place.

MultMatrixRow is a synonym of MultMatrixRowLeft. This was chosen because linear combinations of rows of matrices are usually written as v ⋅ A = [v_1, ... ,v_n] ⋅ A which multiplies scalars from the left.

26.13-2 MultMatrixRowRight

Returns: nothing

Multiplies the i-th row of the mutable matrix M with the scalar elm from the right in-place.

26.13-3 MultMatrixColumnRight

Returns: nothing

Multiplies the i-th column of the mutable matrix M with the scalar elm from the right in-place.

MultMatrixColumn is a synonym of MultMatrixColumnRight. This was chosen because linear combinations of columns of matrices are usually written as A ⋅ v^T = A ⋅ [v_1, ... ,v_n]^T which multiplies scalars from the right.

26.13-4 MultMatrixColumnLeft

Returns: nothing

Multiplies the i-th column of the mutable matrix M with the scalar elm from the left in-place.

26.13-5 AddMatrixRowsLeft

Returns: nothing

Adds the product of elm with the j-th row of the mutable matrix M to its i-th row in-place. The j-th row is multiplied with elm from the left.

AddMatrixRows is a synonym of AddMatrixRowsLeft. This was chosen because linear combinations of rows of matrices are usually written as v ⋅ A = [v_1, ... ,v_n] ⋅ A which multiplies scalars from the left.

26.13-6 AddMatrixRowsRight

Returns: nothing

Adds the product of elm with the j-th row of the mutable matrix M to its i-th row in-place. The j-th row is multiplied with elm from the right.

26.13-7 AddMatrixColumnsRight

Returns: nothing

Adds the product of elm with the j-th column of the mutable matrix M to its i-th column in-place. The j-th column is multiplied with elm from the right.

AddMatrixColumns is a synonym of AddMatrixColumnsRight. This was chosen because linear combinations of columns of matrices are usually written as A ⋅ v^T = A ⋅ [v_1, ... ,v_n]^T which multiplies scalars from the right.

26.13-8 AddMatrixColumnsLeft

Returns: nothing

Adds the product of elm with the j-th column of the mutable matrix M to its i-th column in-place. The j-th column is multiplied with elm from the left.

26.13-9 SwapMatrixRows

Returns: nothing

Swaps the i-th row and j-th row of a mutable matrix M.

26.13-10 SwapMatrixColumns

Returns: nothing

Swaps the i-th column and j-th column of a mutable matrix M.

26.14 Implementing New Vector and Matrix Objects Types

The first step in the design of a new type of vector or matrix objects is to create a new filter that serves as the ConstructingFilter (26.3-2) of the new objects, see the sections 26.15 and 26.16 for an overview of such filters that are already available.

Here we list those operations for vector and matrix objects for which no default methods can be installed. When one implements a new type of vector or matrix objects then one has to install specific methods at least for these operations, in order to make the objects behave as described in this chapter. It is advisable to install specific methods also for other operations, for performance reasons. The installations of default methods can be found in the file lib/matobj.gi of the GAP distribution. There one can check for which operations it makes sense to overload them for the new type of vector or matrix objects. Note that the specific methods must be installed with InstallTagBasedMethod (78.1-6) whenever the default method is installed with this function.

Vector objects

• BaseDomain (26.3-1),

• Length (26.3-4),

• \[\] (26.7-1),

• \[\]\:\= (26.7-1) (with consistency checks if the global option check is not set to false),

• \< (31.11-1) (see \< (26.6-1)),

• ConstructingFilter (26.3-2),

• NewVector (26.4-1) (with consistency checks if the global option check is not set to false, install the method with InstallTagBasedMethod (78.1-6)).

Matrix objects

• BaseDomain (26.3-1),

• NumberRows (26.3-5),

• NumberColumns (26.3-5),

• MatElm (26.11-1),

• SetMatElm (26.11-2) (with consistency checks if the global option check is not set to false),

• \< (31.11-1) (see \< (26.6-1)),

• ConstructingFilter (26.3-2),

• CompatibleVectorFilter (26.3-3),

• NewMatrix (26.4-4) (with consistency checks if the global option check is not set to false, install the method with InstallTagBasedMethod (78.1-6)).

Methods for NewVector (26.4-1) and NewMatrix (26.4-4) must check their arguments for consistency (do the given filter and base domain fit together, are the entries compatible with the given base domain, is the number of matrix entries a multiple of the given number of columns) except if the global option check is set to false. (See Chapter 8 for information about global options.) The same holds for methods for operations that modify mutable vector or matrix objects, such as \[\]\:\= (26.7-1), SetMatElm (26.11-2), CopySubVector (26.9-3), CopySubMatrix (26.11-5), and for those methods of Vector (26.4-2) and Matrix (26.4-5) that do not delegate to NewVector (26.4-1) and NewMatrix (26.4-4), respectively.

26.15 Available Representations of Vector Objects

The following filters define vector objects for which the the functionality described in this chapter is supported.

26.15-1 IsGF2VectorRep

An object obj in IsGF2VectorRep describes a vector object (see IsVectorObj (26.2-1)) with entries in the finite field with 2 elements.

IsGF2VectorRep implies IsCopyable (12.6-1), thus vector objects in this representation can be mutable.

26.15-2 Is8BitVectorRep

An object obj in Is8BitVectorRep describes a vector object (see IsVectorObj (26.2-1)) with entries in a finite field with q elements, for 3 ≤ q ≤ 256. The base domain of obj is not necessarily the smallest field that contains all matrix entries.

Is8BitVectorRep implies IsCopyable (12.6-1), thus vector objects in this representation can be mutable.

26.15-3 IsPlistVectorRep

An object obj in IsPlistVectorRep describes a vector object (see IsVectorObj (26.2-1)) that can occur as a row in a row list matrix (see Section 26.12).

IsPlistVectorRep implies IsCopyable (12.6-1), thus vector objects in this representation can be mutable.

26.15-4 IsZmodnZVectorRep

An object obj in IsZmodnZVectorRep describes a vector object (see IsVectorObj (26.2-1)) with entries in a residue class ring of the ring of integers (see ZmodnZ (14.5-2)). This ring is the base domain (see BaseDomain (26.3-1)) of obj.

IsZmodnZVectorRep implies IsCopyable (12.6-1), thus matrix objects in this representation can be mutable.

26.16 Available Representations of Matrix Objects

The following filters define matrix objects for which the the functionality described in this chapter is supported.

26.16-1 IsGF2MatrixRep

An object obj in IsGF2MatrixRep describes a matrix object (see IsMatrixObj (26.2-2)) with entries in the finite field with 2 elements, which behaves like the list of its rows (see IsRowListMatrix (26.2-4)). The base domain of obj is the field with 2 elements.

IsGF2MatrixRep implies IsCopyable (12.6-1), thus vector objects in this representation can be mutable.

26.16-2 Is8BitMatrixRep

An object obj in Is8BitMatrixRep describes a matrix object (see IsMatrixObj (26.2-2)) that behaves like the list of its rows (see IsRowListMatrix (26.2-4)). The base domain of obj is a field that contains all matrix entries (but not necessarily the smallest such field), it must be a finite field with q elements, for 3 ≤ q ≤ 256.

Is8BitMatrixRep implies IsCopyable (12.6-1), thus matrix objects in this representation can be mutable.

26.16-3 IsPlistMatrixRep

An object obj in IsPlistMatrixRep describes a matrix object (see IsMatrixObj (26.2-2)) that behaves similar to a list of its rows, in the sense of IsRowListMatrix (26.2-4).

IsPlistMatrixRep implies IsCopyable (12.6-1), thus matrix objects in this representation can be mutable.

26.16-4 IsZmodnZMatrixRep

An object obj in IsZmodnZMatrixRep describes a matrix object (see IsMatrixObj (26.2-2)) that behaves like the list of its rows (see IsRowListMatrix (26.2-4)). The matrix entries lie in a residue class ring of the ring of integers (see ZmodnZ (14.5-2)). This ring is the base domain (see BaseDomain (26.3-1)) of obj.

IsZmodnZMatrixRep implies IsCopyable (12.6-1), thus matrix objects in this representation can be mutable.

generated by GAPDoc2HTML