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

CC BY-SA 3.0
2012-04-03T07:08:25.240Z
True, but I wanted to know if there is a deterministic (easy) way to find it.
Dimitris
CC BY-SA 3.0
2012-04-03T07:11:04.177Z
Why?  It's more likely that your computer will spontaneously turn into a kitten than that the algorithm will return a bad result.
Jeffε
CC BY-SA 3.0
2012-04-03T07:18:08.800Z
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
CC BY-SA 3.0
2012-04-03T07:34:14.913Z
How to check that the algorithm worked: Is my computer a kitten?  :-)
Jeffε
CC BY-SA 3.0
2012-04-03T07:43:59.003Z
I don't mean to be pedantic, but is that even in NP? :)
Dimitris
CC BY-SA 3.0
2012-04-03T07:55:46.290Z
You're dealing with real numbers, so of course not.
Jeffε
CC BY-SA 3.0
2012-04-03T08:44:33.840Z
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
CC BY-SA 3.0
2012-04-03T12:33:02.183Z
@TsuyoshiIto what, you don't like kittens ? :)
Suresh Venkat
CC BY-SA 3.0
2012-04-03T12:38:22.473Z
@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
CC BY-SA 3.0
2012-04-03T19:39:54.243Z
@TsuyoshiIto: "You're asking the wrong question" is a legitimate answer.
Jeffε
CC BY-SA 3.0
2012-04-03T20:30:21.870Z
Of course “You are asking a wrong question” is a legitimate answer in general, but (1) in this case, whether it is wrong or not depends on what the asker wants to use the deterministic algorithm for, and (2) your answer is simply confusing.  If you are fine with this confusing answer to the question, I have nothing else to say.  I have already posted a warning to future readers as a comment that this does not answer the exact question being asked.
Tsuyoshi Ito
CC BY-SA 3.0
2012-04-03T22:03:47.690Z
@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.
Dimitris
CC BY-SA 3.0
2012-04-06T07:45:39.217Z
"You are asking a wrong question" is a legitimate _comment_ :-). In cspractice.stackexchange.com this answer would get my upvote! :-D
Aryabhata
CC BY-SA 3.0
2012-04-06T15:40:22.883Z
@Dimitris: Yup.  Another way to read my answer is that by changing from finite fields to the reals, you've made the problem boring/trivial.
Jeffε
CC BY-SA 3.0
2012-04-06T19:40:46.590Z
@JɛﬀE I agree that over the reals it is not an interesting question. I should have asked the (fixed order) finite field variant. Any insights for that case are more than welcome.
Dimitris
CC BY-SA 3.0
2012-04-03T07:03:06.353Z
2012-04-03T07:03:06.353Z
Jeffε
<p>Let a real $k\times n$  ($k\le n$) matrix ${\bf A}$ with the property that any collection of $k$ columns is full rank. </p>

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

<p><em>Relevant Sidenote:</em> 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.</p>

CC BY-SA 3.0
2012-04-03T06:10:59.540Z
I am not sure if I understand your point. I require $k\le n$, $k=n$ is not an issue.
Dimitris
CC BY-SA 3.0
2012-04-03T06:31:28.253Z
@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.
Suresh Venkat
CC BY-SA 3.0
2012-04-03T06:36:26.673Z
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
CC BY-SA 3.0
2012-04-03T06:48:15.360Z
@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
CC BY-SA 3.0
2012-04-03T07:03:47.773Z
(Oops, my mistake.)
Jeffε
CC BY-SA 3.0
2012-04-03T14:50:33.183Z
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
CC BY-SA 3.0
2012-04-03T15:12:29.567Z
@Sahso It does looks similar to RIP (haven't thought of it that way!), but testing RIP is hard I think. Finding the exact upper bound of the RIP condition is equivalent to solving a sparse-PCA problem (which is NP-hard). But having a matrix that satisfies the RIP and augmenting it with one column such that it still satisfies RIP seems to be slightly different, and hopefully is easier than the general "RIP test". But I don't know. [meta: I guess that is why RS generator like matrices (fft-like) have been used for sensing.]
Dimitris
<ds.algorithms><linear-algebra><matrices><coding-theory>
Constructing vectors in general position
Dimitris
# Constructing vectors in general position

(Asked by: username_0 on 2012-04-03)

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.

**Tags:** ds.algorithms, linear-algebra, matrices, coding-theory
> **Comments:**
> **username_0**: I am not sure if I understand your point. I require $k\le n$, $k=n$ is not an issue.  
> **username_1**: @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.  
> **username_1**: It seems to me that this should be a way to do this via the Grassmanian, but I don't quite see how.  
> **username_0**: @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.  
> **username_2**: (Oops, my mistake.)  
> **username_3**: 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.  
> **username_0**: @Sahso It does looks similar to RIP (haven't thought of it that way!), but testing RIP is hard I think. Finding the exact upper bound of the RIP condition is equivalent to solving a sparse-PCA problem (which is NP-hard). But having a matrix that satisfies the RIP and augmenting it with one column such that it still satisfies RIP seems to be slightly different, and hopefully is easier than the general "RIP test". But I don't know. [meta: I guess that is why RS generator like matrices (fft-like) have been used for sensing.]  

---

## 1 answers

### Answer by username_2 on 2012-04-03. Score: 1

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

> **Comments:**
> **username_0**: True, but I wanted to know if there is a deterministic (easy) way to find it.  
> **username_2**: Why?  It's more likely that your computer will spontaneously turn into a kitten than that the algorithm will return a bad result.  
> **username_0**: 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.  
> **username_2**: How to check that the algorithm worked: Is my computer a kitten?  :-)  
> **username_0**: I don't mean to be pedantic, but is that even in NP? :)  
> **username_2**: You're dealing with real numbers, so of course not.  
> **username_4**: 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.  
> **username_1**: @TsuyoshiIto what, you don't like kittens ? :)  
> **username_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.  
> **username_2**: @TsuyoshiIto: "You're asking the wrong question" is a legitimate answer.  
> **username_4**: Of course “You are asking a wrong question” is a legitimate answer in general, but (1) in this case, whether it is wrong or not depends on what the asker wants to use the deterministic algorithm for, and (2) your answer is simply confusing.  If you are fine with this confusing answer to the question, I have nothing else to say.  I have already posted a warning to future readers as a comment that this does not answer the exact question being asked.  
> **username_0**: @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.  
> **username_5**: "You are asking a wrong question" is a legitimate _comment_ :-). In cspractice.stackexchange.com this answer would get my upvote! :-D  
> **username_2**: @Dimitris: Yup.  Another way to read my answer is that by changing from finite fields to the reals, you've made the problem boring/trivial.  
> **username_0**: @JɛﬀE I agree that over the reals it is not an interesting question. I should have asked the (fixed order) finite field variant. Any insights for that case are more than welcome.  

---

