Function to generate linearly independent vectors

sparse_matrix

Hi,

I want to whether there is a function (/matrix) such that it can generate a m-dimensional vector such that this generated vector will always be linearly independent of the set of vectors the function has already generated.

My problem can be written in pseudocode format as follow. I therefore expect that any m randomly picked vectors from the pool of the N vectors will generate a full-rank matrix.

For (n=1; n<N; n++) { //N>m

S = Span (v₁, v₂, ..., v_n-1)

Generate vector v_n, such that v_n is not an element of S;

//i.e. v_n is linearly independent of the set of vectors already generated.

S = Span (v₁, v₂, ..., v_n)

}

Vandermonde matrix is one possible option, but it requires the use of exponentially large field size. So I am looking for vectors generated over smaller field size. Any help in this direction will be greatly appreciated.

Thanks in advance.

mathwonk

your problem is not clearly posed. do you want to begin with a general fixed collection of N vectors and then decide how to choose a basis from that set? if the collection is general, then any way of choosing m vectors will work. if you get to specify the N vectors you can arrange that.

are you assuming you have a fixe collection of N vectors containing some basis, but such that not every subset of m vectors is a basis?

what are you given and what do you want to accomplish.

In general, the first technique taught in linear algebra, namely gaussian elimination, will do pretty much whatever can be done along these lines.

e.g. put your vectors in as the columns of a matrix and row reduce. then the original columns that correspond to (i.e. in the same columns positions as) independent columns (i.e. pivot columns) of the reduced matrix were also independent.