32 Vectors

A important concept in algebra is the vector space over a field F. A vector space V is a set of vectors, for which an addition u + v and a multiplication by scalars, i.e., elements from F, s v must be defined. A base of V is a list of vectors, such that every vector in V can be uniquely written as linear combination of the base vectors. If the base if finite, its size is called the dimension of V. Using a base it can be shown that V is isomorphic to the set n-tuples of elements with the componentwise addition and multiplication.

This comment suggests the representation that is actually used in GAP. A GAP vector is a list without holes whose elements all come from a common field. We call the length of the list the dimension of the vector. This is a little bit lax, because the dimension is a property of the vector space, not of the vector, but should seldom cause confusion.

The first possibility for this field are the rationals (see Rationals). We call a list without holes whose elements are all rationals a rational vector, which is a bit lax too, but should again cause no confusion. For example [ 1/2, 0, -1/3, 2 ] is a rational vector of dimension 4.

The second possibility are cyclotomics (see Cyclotomics). Note that the rationals are the prime field of cyclotomic fields and therefore rational vectors are just a special case of cyclotomic vectors. An example of a cyclotomic vector is [ E(3)+E(3)^2, 1, E(15) ].

Third the common field may be a finite field (see Finite Fields). Note that it is not enough that all elements are finite field elements of the same characteristic, the common finite field containing all elements must be representable in GAP, i.e., must have at most 2^{16} elements. An example of such a vector over the finite field GF(3^4) with 81 elements is [ Z(3^4)^3, Z(3^2)^5, Z(3^4)^11 ].

Finally a list all of whose elements are records is also considered a vector. In that case the records should all have an operations record with the necessary functions +, -, *, ^. This allows for vectors over library and/or user defined fields (or rings) such as a polynomial ring (see Polynomials).

The first section in this chapter describes the operations applicable to vectors (see Operations for Vectors).

The next section describes the function that tests if an object is a vector (see IsVector).

The next section describes the function that returns a canonical multiple of a vector (see NormedVector).

The last section tells you more about the internal representation of vectors (see More about Vectors).

Because vectors are just a special case of lists, all the operations and functions for lists are applicable to vectors also (see chapter Lists). List Elements), changing elements of a vector (see List Assignment), and comparing vectors (see Comparisons of Lists).

Vectorspaces are a special category of domains and are described by vectorspace records (see chapter Vector Spaces).

Vectors play an important role for matrices (see chapter Matrices), which are implemented as lists of vectors.

Subsections

  1. Operations for Vectors
  2. IsVector
  3. NormedVector
  4. More about Vectors

32.1 Operations for Vectors

vec1 + vec2

In this form the addition operator + evaluates to the sum of the two vectors vec1 and vec2, which must have the same dimension and lie in a common field. The sum is a new vector where each entry is the sum of the corresponding entries of the vectors. As an exception it is also possible to add an integer vector to a finite field vector, in which case the integers are interpreted as scalar * GF.one.

scalar + vec
vec + scalar

In this form + evaluates to the sum of the scalar scalar and the vector vec, which must lie in a common field. The sum is a new vector where each entry is the sum of the scalar and the corresponding entry of the vector. As an exception it is also possible to add an integer scalar to a finite field vector, in which case the integer is interpreted as scalar * GF.one.

    gap> [ 1, 2, 3 ] + [ 1/2, 1/3, 1/4 ];
    [ 3/2, 7/3, 13/4 ]
    gap> [ 1/2, 3/2, 1/2 ] + 1/2;
    [ 1, 2, 1 ] 

vec1 - vec2
scalar - vec
vec - scalar

The difference operator - returns the componentwise difference of its two operands and is defined subject to the same restrictions as +.

    gap> [ 1, 2, 3 ] - [ 1/2, 1/3, 1/4 ];
    [ 1/2, 5/3, 11/4 ]
    gap> [ 1/2, 3/2, 1/2 ] - 1/2;
    [ 0, 1, 0 ] 

vec1 * vec2

In this form the multiplication operator * evaluates to the product of the two vectors vec1 and vec2, which must have the same dimension and lie in a common field. The product is the sum of the products of the corresponding entries of the vectors. As an exception it is also possible to multiply an integer vector to a finite field vector, in which case the integers are interpreted as scalar * GF.one.

scalar * vec
vec * scalar

In this form * evaluates to the product of the scalar scalar and the vector vec, which must lie in a common field. The product is a new vector where each entry is the product of the scalar and the corresponding entry of the vector. As an exception it is also possible to multiply an integer scalar to a finite field vector, in which case the integer is interpreted as scalar * GF.one.

    gap> [ 1, 2, 3 ] * [ 1/2, 1/3, 1/4 ];
    23/12
    gap> [ 1/2, 3/2, 1/2 ] * 2;
    [ 1, 3, 1 ] 

Further operations with vectors as operands are defined by the matrix operations (see Operations for Matrices).

32.2 IsVector

IsVector( obj )

IsVector returns true if obj, which may be an object of arbitrary type, is a vector and false else. A vector is a list without holes, whose elements all come from a common field.

    gap> IsVector( [ 0, -3, -2, 0, 6 ] );
    true
    gap> IsVector( [ Z(3^4)^3, Z(3^2)^5, Z(3^4)^13 ] );
    true
    gap> IsVector( [ 0, Z(2^3)^3, Z(2^3) ] );
    false    # integers are not finite field elements
    gap> IsVector( [ , 2, 3,, 5,, 7 ] );
    false    # list that have holes are not vectors
    gap> IsVector( 0 );
    false    # not even a list 

32.3 NormedVector

NormedVector( vec )

NormedVector returns the scalar multiple of vec such that the first nonzero entry of vec is the one from the field over which the vector is defined. If vec contains only zeroes a copy of it is returned.

    gap> NormedVector( [ 0, -3, -2, 0, 6 ] );
    [ 0, 1, 2/3, 0, -2 ]
    gap> NormedVector( [ 0, 0 ] );
    [ 0, 0 ]
    gap> NormedVector( [ Z(3^4)^3, Z(3^2)^5, Z(3^4)^13 ] );
    [ Z(3)^0, Z(3^4)^47, Z(3^2) ] 

32.4 More about Vectors

In the first section of this chapter we defined a vector as a list without holes whose elements all come from a common field. This representation is quite nice to use. However, suppose that GAP would have to check that a list is a vector every time this vector appears as operand in a addition or multiplication. This would be quite wasteful.

To avoid this a list that is a vector may, but need not, have an internal flag set that tells the operations that this list is indeed a vector. Then this operations do not have to check this operand and can perform the operation right away. This section tells you when a vector obtains this flag, so you can write your functions in such a way that you make best use of this feature.

The results of vector operations, i.e., binary operations that involve vectors, are known by construction to be vectors, and thus have the flag set upon creation.

If the operand of one of the binary operation is a list that does not yet have the flag set, those operations will check that this operand is indeed a vector and set the flag if it is. If it is not a vector and not a matrix an error is signalled.

If the argument to IsVector is a list that does not yet have this flag set, IsVector will test if all elements come from a common field. If they do, IsVector will set the flag. Thus on the one hand IsVector is a test whether the argument is a vector. On the other hand IsVector can be used as a hint to GAP that a certain list is indeed a vector.

If you change a vector, that does have this flag set, by assignment, Add, or Append, the vectors will loose its flag, even if the change is such that the resulting list is still a vector. However if the vector is a vector over a finite field and you assign an element from the same finite field the vector will keep its flag. Note that changing a list that is not a vector will never set the flag, even if the resulting list is a vector. Such a vector will obtain the flag only if it appears as operand in a binary operation, or is passed to IsVector.

Vectors over finite fields have one additional feature. If they are known to be vectors, not only do they have the flag set, but also are they represented differently. This representation is much more compact. Instead of storing every element separately and storing for every element separately in which field it lies, the field is only stored once. This representation takes up to 10 times less memory.

Previous Up Next
Index

GAP 3.4.4
April 1997