%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A vector.tex GAP documentation Martin Schoenert %% %A @(#)$Id: vector.tex,v 3.7 1993/05/04 11:42:30 fceller Rel $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file describes those functions that mainly deal with vectors. %% %H $Log: vector.tex,v $ %H Revision 3.7 1993/05/04 11:42:30 fceller %H fixed a spelling error %H %H Revision 3.6 1993/02/19 10:48:42 gap %H adjustments in line length and spelling %H %H Revision 3.5 1993/02/11 17:14:10 martin %H vectors may now contain records %H %H Revision 3.4 1993/02/05 08:17:44 felsch %H examples fixed %H %H Revision 3.3 1991/12/27 16:07:04 martin %H revised everything for GAP 3.1 manual %H %H Revision 3.2 1991/07/26 09:01:07 martin %H changed |\GAP\ | to |{\GAP}| %H %H Revision 3.1 1991/07/25 16:16:59 martin %H fixed some minor typos %H %H Revision 3.0 1991/04/11 11:36:02 martin %H Initial revision under RCS %H %% \Chapter{Vectors}% \index{scalars}\index{base!of vector space}\index{dimension!of vector space} 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"). This especially includes accessing elements of a vector (see "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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Operations for Vectors}% \index{operations!for vectors} ' + ' In this form the addition operator '+' evaluates to the sum of the two vectors and , 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 ' \*\ .one'. ' + ' \\ ' + ' In this form '+' evaluates to the sum of the scalar and the vector , 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 ' \*\ .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 ] | ' - ' \\ ' - ' \\ ' - ' 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 ] | ' \*\ ' In this form the multiplication operator '\*' evaluates to the product of the two vectors and , 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 ' \*\ .one'. ' \*\ ' \\ ' \*\ ' In this form '\*' evaluates to the product of the scalar and the vector , 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 ' \* .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"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsVector}% \index{test!for a vector} 'IsVector( )' 'IsVector' returns 'true' if , 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{NormedVector}% 'NormedVector( )' 'NormedVector' returns the scalar multiple of such that the first nonzero entry of is the one from the field over which the vector is defined. If 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) ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables %% %% Local Variables: %% mode: outline %% outline-regexp: "\\\\Chapter\\|\\\\Section" %% fill-column: 73 %% eval: (hide-body) %% End: %%