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.

  • $\begingroup$ I am not sure if I understand your point. I require $k\le n$, $k=n$ is not an issue. $\endgroup$
    – Dimitris
    Apr 3 '12 at 6:10
  • 2
    $\begingroup$ @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. $\endgroup$ Apr 3 '12 at 6:31
  • $\begingroup$ It seems to me that this should be a way to do this via the Grassmanian, but I don't quite see how. $\endgroup$ Apr 3 '12 at 6:36
  • $\begingroup$ @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. $\endgroup$
    – Dimitris
    Apr 3 '12 at 6:48
  • 1
    $\begingroup$ 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. $\endgroup$ 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$.

  • 1
    $\begingroup$ 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. $\endgroup$
    – Dimitris
    Apr 3 '12 at 7:18
  • 5
    $\begingroup$ 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. $\endgroup$ Apr 3 '12 at 8:44
  • 2
    $\begingroup$ @TsuyoshiIto what, you don't like kittens ? :) $\endgroup$ Apr 3 '12 at 12:33
  • 4
    $\begingroup$ @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. $\endgroup$ Apr 3 '12 at 12:38
  • 3
    $\begingroup$ @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. $\endgroup$
    – Dimitris
    Apr 3 '12 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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