[GAP Forum] fast linear algebra

[degraaf at science.unitn.it]

Dear Laurent,

GAP has functions to do the things you want. Let me
illustrate them by an example:

# first we create some vectors, and the vector space spanned by them:
gap> v:= [[1,2,3,4],[1,1,1,1]];;
gap> V:= VectorSpace( Rationals, v );;

# then we can construct the basis of the space that consists of the
# given vectors:
gap> B:= Basis( V, v );
Basis( <vector space over Rationals, with 2 generators>,
[ [ 1, 2, 3, 4 ], [ 1, 1, 1, 1 ] ] )

# get coeficients, and ask whether an element lies in the space:
gap> Coefficients( B, [2,3,4,5] );
[ 1, 1 ]
gap> [5,6,8,9] in V;
false

# for dealing with quotient spaces there is a function
# NaturalHomomorphismBySubspace:
gap> W:= Rationals^4;
( Rationals^4 )
gap> f:= NaturalHomomorphismBySubspace( W, V );
<linear mapping by matrix, ( Rationals^4 ) -> ( Rationals^2 )>
gap> Image( f, v[1] );
[ 0, 0 ]
gap> PreImagesRepresentative( f, [1,2] );
[ 1, 2, 0, 0 ]

# So we can make images, and preimages.

# Now suppose that you have a matrix U : W --> W that leaves the
# subspace V invariant. Then you can get the matrix acting on the
# quotient as follows (in the example I take the identity matrix).
gap> U:= IdentityMat( 4, Rationals );
[ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ]
gap> R:= Range( f );
( Rationals^2 )
gap> b:= List( Basis(R), w -> PreImagesRepresentative( f, w ) );
[ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ] ]
gap> List( b, w -> Coefficients( Basis(R), Image( f, w*U ) ) );
[ [ 1, 0 ], [ 0, 1 ] ]


I hope this helps (and that I have understood your questions
correctly). Please ask again if you need anything more/else.

Best wishes,

Willem de Graaf




> dear forum,
> i try to find the most efficient way to code the following, and the
> manual didn't help me:
>
> 1) given a vector space given by a set R of row vectors, rewrite a
> family of vectors belonging to the span of R as full row vectors over
> another space (isomorphic to the space spanned by R).
>
> my implementation: complete R to a basis B of the full row space; use
> 'Coefficients(B,v)' to obtain the coefficients in that basis, then
> throw away the last 0's to obtain the coefficients in the basis of the
> subspace spanned by R.
>
> this seems extremely inefficient.
>
> 2) given a set R of row vectors, determine whether v is in the span of
> these vectors.
>
> my implementation: test if Rank(R)=Rank(Concatenation(R,v)).
>
> again, i suspect there should be something much better.
>
> 3) given a set R of row vectors, rewrite a family of vectors as
> vectors (in the full row space K^n) as full row vectors over a space
> isomorphic to the quotient K^n/<R>.
>
> my implementation: complete R to a basis R cup S; extract the coefficients of
> S
>
> 4) given a matrix K^n -> K^n, that leaves the span of R invariant,
> extract a matrix K^n/<R> -> K^n/<R>.
>
> again, my implementation: complete R to a basis R cup S; for each
> vector in S, compute its image, and rewrite it using step 3) in the
> basis S; use that as a row of the new matrix.
>
> thanks in advance, laurent
>
> --
> Laurent Bartholdi          \  laurent.bartholdi<at>gmail<dot>com
> EPFL SB SMA IMB MAD         \    Téléphone: +41 21-6935458
> Station 8                    \ Secrétaire: +41 21-6935501
> CH-1015 Lausanne, Switzerland \      Fax: +41 21-6930339
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>