# Function (/matrix) to generate linearly independent vectors.

Hi,

I want to whether there is a vector generating function (/matrix) such that it can generate a m-dimensional vector which will always be linearly independent of the set of m-dimensional 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 (v1, v2, ..., vn-1)

//i.e. vn is linearly independent of the set of vectors already generated.
Generate vector vn, such that vn is not an element of S;

S = Span (v1, v2, ..., vn)
}


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.

If this is an open research problem, then please do advice me.

-
I might be misunderstanding what you're trying to do but how could you ever have $N$ linearly independent $m$-dimensional vectors when $N>m$? – j.c. Nov 8 '12 at 13:57
Maybe what you are looking for is a way of generating sets of $N$ $m$-dimensional vectors such that any subset of size $m$ is linearly independent? – j.c. Nov 8 '12 at 14:03

I don't quite follow the first paragraph of your question. But reading the rest of your post, if you only need a set $S$ of $N$ $m$-dimensional vectors over the finite field of some small order in which any subset $S' \subset S$ of cardinality $m$ is a set of linearly independent vectors, that's a parity-check matrix of an MDS code over $\mathbb{F}_q$.
Take an $m \times N$ parity-check matrix $H$ of an $[N, N-m, m+1]_q$ code (i.e., a $q$-nary linear code of length $N$, dimension $N-m$, and minimum distance $m+1$). Then whichever $m$ or fewer columns you pick from $H$, they're always linearly independent.
The binary case is no good because the only MDS codes are the trivial ones. For larger $q$, there are known nontrivial MDS codes. Reed-Solomon codes are good examples. They're cyclic codes so you can realize the codewords as an ideal of the polynomial ring $\mathbb{F}_q[x]/(x^N-1)$; you can generate them through multiplication between a certain monic polynomial that divides $x^N-1$ and all polynomials of degree less than $N-m$ (including $0$). Maybe this is systematic enough to work for your purpose?