Linear independent subset of a set of vectors [GAP]

Question

I'm trying to find a linearly independent subset of a set of vectors in a vector space over the rationals. Looking up "independent", "linear independence", or anything of the sort hasn't helped, since I only found the LinearIndependentColumns(mat) function, which isn't what I needed. I looked around in the tutorials, but there is nothing of the sort. Is there a ready function that does this, or do I have to do it myself?

If it's the latter, how can I do it? Is there a way to "choose" the first vector, take the next, and look for non-trivial solutions and add it to my list, if there exist no solutions? Is there a more efficient way to find the subset?

Answer 1

Take the rationals as a vector space over the rationals. Is the set $\{ 1 \} \subset \mathbb{Q}$ linearly independent? Similarly, take $\mathbb{Q}^2$ as a vector space over the rationals. Is the set $\{ (1, 0), (0, 1) \}$ independent? What about the set $\{(1, 0) \} \subset \mathbb{Q}^2$?

Given a vector space $V$ over a field $k$, a set $S \subset V$ is said to be linearly independent provided that if you have a sum of the form $$ \sum_{s \in S}a_s\cdot s = 0 $$ with each $a_s \in k$ and all but finitely many zero, then you must have that $a_s = 0$ for all $s \in S$.

You should be able to see from the definition above that any subset of a nonzero-vector space of cardinality 1 is independent.

This ends up being equivalent to saying that given a set $S \subset V$, we have that $S$ is independent if you can't write any vector in $S$ as a linear combination of the other vectors in $S$.

Does that help clarify things?

Answer 2

Let's use these ten vectors to construct an example:

gap> v:=[ [ 1/2, 2, 1/2, -1/2, 0 ], [ 0, 1, -1, -1, 1/2 ], 
>   [ 0, -2/3, 1/3, -1/2, -3 ], [ 0, 2, 1/5, 1/2, 0 ], 
>   [ 1/2, 2, 1/2, -1/2, 0 ], [ 1/2, 0, -1, 0, 0 ], 
>   [ 1, 0, 2, 0, 1/2 ], [ 0, -2/3, 1/3, -1/2, -3 ], 
>   [ 1/2, 3/5, -1, 0, 1/5 ], [ 0, -2/3, 1/3, -1/2, -3 ] ];;

Now if you need a basis which does not necessarily consist of elements of the given set of vectors, you can use Basis:

gap> V:=VectorSpace(Rationals,v);
<vector space over Rationals, with 10 generators>
gap> Dimension(V);
5
gap> bas:=Basis(V);
SemiEchelonBasis( <vector space of dimension 5 over Rationals>, 
[ [ 1, 4, 1, -1, 0 ], [ 0, 1, -1, -1, 1/2 ], [ 0, 0, 1, 7/2, 8 ],
  [ 0, 0, 0, 1, 93/26 ], [ 0, 0, 0, 0, 1 ] ] )
gap> AsList(bas);
[ [ 1, 4, 1, -1, 0 ], [ 0, 1, -1, -1, 1/2 ], [ 0, 0, 1, 7/2, 8 ],
  [ 0, 0, 0, 1, 93/26 ], [ 0, 0, 0, 0, 1 ] ]

If you need to find elements from the given set, I suggest to enumerate elements of v and add them to the resulting list in case the dimension of the subspace that they generate together increases. The dimension of the vector space gives the upper bound, so the process may be stopped when it is reached:

gap> lis:=[];
[  ]
gap> for r in v do
>   V1:=VectorSpace( Rationals, Concatenation(lis,[r]) );
>   if Dimension(V1) > Length(lis) then
>     Add(lis,r);
>     if Length(lis)=Dimension(V) then
>       break;
>     fi;
>   fi;
> od;
gap> lis;
[ [ 1/2, 2, 1/2, -1/2, 0 ], [ 0, 1, -1, -1, 1/2 ], 
  [ 0, -2/3, 1/3, -1/2, -3 ], [ 0, 2, 1/5, 1/2, 0 ], 
  [ 1/2, 0, -1, 0, 0 ] ]