11
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I am not sure if I understand your point. I require $k\le n$, $k=n$ is not an issue. $\endgroup$
    – Dimitris
    Commented Apr 3, 2012 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$ Commented Apr 3, 2012 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$ Commented Apr 3, 2012 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
    Commented Apr 3, 2012 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$ Commented Apr 3, 2012 at 14:50

1 Answer 1

1
$\begingroup$

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

$\endgroup$
15
  • 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
    Commented Apr 3, 2012 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$ Commented Apr 3, 2012 at 8:44
  • 2
    $\begingroup$ @TsuyoshiIto what, you don't like kittens ? :) $\endgroup$ Commented Apr 3, 2012 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$ Commented Apr 3, 2012 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
    Commented Apr 3, 2012 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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