0
$\begingroup$

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.

Thanks in advance.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$
    – j.c.
    Commented Nov 8, 2012 at 13:57
  • $\begingroup$ 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? $\endgroup$
    – j.c.
    Commented Nov 8, 2012 at 14:03

1 Answer 1

Reset to default
2
$\begingroup$

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?

In any case, you might want to clarify your question a bit or, if MDS codes are indeed what you would like to construct, pick your favorite coding theory textbook and read up on them.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .