Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I am not sure if I understand your point. I require $k\le n$, $k=n$ is not an issue. –  Dimitris Apr 3 '12 at 6:10
2  
@JɛffE 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. –  Suresh Venkat 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. –  Suresh Venkat 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. –  Dimitris Apr 3 '12 at 6:48
1  
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. –  Sasho Nikolov Apr 3 '12 at 14:50
show 2 more comments

1 Answer

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$.

share|improve this answer
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. –  Dimitris Apr 3 '12 at 7:18
5  
The question specifically asks for an efficient deterministic algorithm. If you answer something related but does not satisfy the condition stated in the question, you should say so explicitly in my opinion. –  Tsuyoshi Ito Apr 3 '12 at 8:44
2  
@TsuyoshiIto what, you don't like kittens ? :) –  Suresh Venkat Apr 3 '12 at 12:33
4  
@Suresh: In practice, it would be amusing if my computer suddenly turns into a kitten. In theory, though, first you have to define a kitten. –  Tsuyoshi Ito Apr 3 '12 at 12:38
3  
@JɛffE 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. –  Dimitris Apr 3 '12 at 22:03
show 10 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.