Constructing vectors in general position

Let a real $k\times n$ ($k\le n$) matrix ${\bf A}$ with the property that any collection of $k$ columns is full rank.

Q: Is there an efficient way to deterministically find a vector ${\bf a}$ such that the augmented matrix ${\bf A}' = [{\bf A}\;{\bf a}]$ preserves the same property as ${\bf A}$: any $k$ columns are full rank.

Relevant Sidenote: A matrix that has this property is the generator of an $(n,k)$ Reed-Solomon Code: adding columns that preserve its Vandermonde structure preserves the rank property.

• I am not sure if I understand your point. I require $k\le n$, $k=n$ is not an issue. Apr 3 '12 at 6:10
• @JɛﬀE k doesn't change: in the case of k = n, only n of the (now) n+1 columns need to be full rank. In this case, the problem should be easy: find an affine transform of the matrix to an orthogonal basis of R^n, and then let a be the vector whose image under this is the all 1s vector. Apr 3 '12 at 6:31
• It seems to me that this should be a way to do this via the Grassmanian, but I don't quite see how. Apr 3 '12 at 6:36
• @Suresh Yes indeed, for the n = k+1 case it seems to be solvable in the way that you mention. Or you can simply choose ${\bf a}$ to be in the nullspace of all $k$, $(k-1)$-collections of vectors. Apr 3 '12 at 6:48
• nice question. sounds like a weaker version of the problem of verifying the restricted isometry property, which is wide open as far as I know. Apr 3 '12 at 14:50

If you choose $\mathbf{a}$ uniformly at random from the hypercube $[0,1]^n$, the matrix $[\mathbf{A}~ \mathbf{a}]$ will have the desired property with probability $1$.
• I cannot but agree :). The problem comes when you want to check that such a vector works (no matter if it does a.s.). You have to check ${{n}\choose{k}}$ subsets of columns. This problem of checking becomes more relevant when you consider finite fields (of fixed order), but I tried to avoid talking about them. Apr 3 '12 at 7:18
• @JɛﬀE Maybe I should have clarified why this question is of some interest. The real question is the same but over finite fields, but I tend to think that fields complicate linear algebra questions. The application is the design of "good" code generator matrices. Random ones (iid entries) can be shown to satisfy the property whp, using tools like the Schwartz–Zippel lemma. For this problem SZ usually requires field orders of $O(2^k)$ and you can't efficiently check that the matrices really work. Why is this important? Because codes that are most probably reliable are some times not preferred. Apr 3 '12 at 22:03