# [GAP Forum] fast linear algebra

Laurent Bartholdi laurent.bartholdi at gmail.com
Mon Oct 2 12:12:00 BST 2006

```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.