<p>Here is what I think S. Nikolov meant.</p>

<p>Take an $m\times m$ Vandermonde matrix $V(x_1,\ldots,x_m)$ where $V_{i,j}=x_i^{j-1}$ for $1\leq i,j\leq m.$ </p>

<p>Take any $1\leq j_1&lt;j_2&lt;\ldots&lt;j_n\leq m,$ so we assume $n\leq m$ here. Then for any choice of $1\leq i_1&lt;i_2&lt;\ldots&lt;i_n\leq m$ the $n\times n$ submatrix formed by
$$[V_{i_t,j_s}]_{1\leq t,s\leq n}$$ 
is linearly independent.</p>

<p>The nontriviality condition of the Vandermonde matrix requires that the points $x_i$ be distinct. If you are working over a finite field of size $q,$ then $q\geq m$ must hold. Over an infinite field this isn't required and clearly you can make $m$ as large as you wish.</p>

<p><strong>Edit:</strong> I am sorry, this construction won't work in general, see the comments by Sasho Nikolov and Emil Jerabek.</p>

CC BY-SA 3.0
2015-01-02T20:56:00.270Z
This is what I meant but I am not longer sure it works for Vandermonde: do you have a proof or reference? It works trivially for non-degenerate $m\times n$ Cauchy matrices, because any $n \times n$ submatrix is a square Cauchy matrix with non-zero determinant.
Sasho Nikolov
CC BY-SA 3.0
2015-01-03T03:04:51.987Z
@SashoNikolov I just did some numeric runs on Vandermonde matrices and they seem to work just fine! Starting at number 2 at least... $a_i=i+2$
Flávio Botelho
CC BY-SA 3.0
2015-01-03T03:14:14.913Z
@SashoNikolov Now searching on google scholar for every Vondermonde submatrix being invertible shows lots of hits... Great find!
Flávio Botelho
CC BY-SA 3.0
2015-01-03T05:36:24.733Z
I think it's not always true, though. There may be additional conditions. See e.g. http://mathoverflow.net/questions/60938/is-any-n-1-times-n-1-submatrix-of-an-n-times-n-vandermonde-matrix-inver
Sasho Nikolov
CC BY-SA 3.0
2015-01-03T13:32:47.247Z
@SashoNikolov, I added proof that I hope shows it will work for distinct $x_i$
kodlu
CC BY-SA 3.0
2015-01-03T14:17:04.753Z
The proof only works if $j_1=1,\dots,j_n=n$ (in which case the submatrix is a Vandermonde matrix in its own right anyway). The post linked by Sasho above includes the trivial counterexample $V(1,0)=\bigl(\begin{smallmatrix}1&1\\1&0\end{smallmatrix}\bigr)$, whose $(0)$ submatrix is not invertible.
Emil Jeřábek
CC BY-SA 3.0
2015-01-04T12:42:23.157Z
@Emil: but does the OP care about $n-1 \times n-1$ submatrices?
Peter Shor 
CC BY-SA 3.0
2015-01-04T15:15:28.653Z
@PeterShor: I’m not sure I understand your question. The $n-1$ in mathoverflow.net/questions/60938 is $n$ here, and the $n$ there is $m$ here, if that’s the issue.
Emil Jeřábek
CC BY-SA 3.0
2015-01-04T15:35:07.357Z
Ah, or do you mean that the special case of $n\times n$ submatrices with $j_1=1,\dots,j_n=n$ is enough for Flávio Botelho’s question? I think that’s right, I was more concerned with the general claim made in the answer than with the original question.
Emil Jeřábek
CC BY-SA 3.0
2015-01-04T15:45:01.973Z
@Emil: that's what I meant ... an $m \times n$ matrix with any $n \times n$ submatrix invertible is enough for the original question.
Peter Shor 
CC BY-SA 3.0
2015-01-02T10:22:40.323Z
2015-01-04T07:39:00.217Z
2015-01-04T07:39:00.217Z
kodlu
<p>Let me give some details for the Cauchy matrix construction, which is simple. Let $x = (x_1, \ldots, x_n)$, $y = (y_1, \ldots, y_m)$ be sequences of pairwise distinct numbers. The corresponding <a href="http://en.wikipedia.org/wiki/Cauchy_matrix">Cauchy matrix</a> is
$$
C = \begin{pmatrix}
\frac{1}{x_1 - y_1} &amp; \frac{1}{x_1 - y_2} &amp; \ldots &amp; \frac{1}{x_1 - y_m}\\
\frac{1}{x_2 - y_1} &amp; \frac{1}{x_2 - y_2} &amp; \ldots &amp; \frac{1}{x_2 - y_m}\\
\vdots &amp; \vdots &amp; \ddots &amp; \vdots\\
\frac{1}{x_n - y_1} &amp; \frac{1}{x_n - y_2} &amp; \ldots &amp; \frac{1}{x_n - y_m}\\
\end{pmatrix}
$$</p>

<p>Then any square submatrix of $C$ is an invertible square Cauchy matrix. In particular, the $n\times n$ submatrix $C_J$ with columns indexed by $J = \{j_1, \ldots, j_n\}$, $j_1 \leq \ldots \leq j_n$, has determinant<br>
$$
\det C_J = \frac{\prod_{i = 2}^n\prod_{k = 1}^{i-1}{(x_i - x_k)(y_{j_i} - y_{j_k})}}{\prod_{i = 1}^n\prod_{k = 1}^n{(x_i - y_{j_k})}}.
$$</p>

<p>Because $x$ and $y$ are sequences of distinct numbers, the determinant is nonzero, and $C_J$ is invertible. </p>

<p>If you prefer something even more concrete, you can take the Hilbert matrix: the Cauchy matrix with $x = (1, \ldots, n)$ and $y = (0, -1, -2, \ldots, -m)$. With $n = 3$ you get the points $(1, 1/2, 1/3),\ (1/2, 1/3, 1/4),\ (1/3, 1/4, 1/5),\ (1/4, 1/5, 1/6)$ and so on.  </p>

CC BY-SA 3.0
2015-01-02T21:22:37.727Z
2015-01-02T21:22:37.727Z
Sasho Nikolov
<p>It seems to be possible to create a set of vectors in $\mathbb{R}^n$ such that any subset of $n$ vectors forms a basis.</p>

<p>For example, in $\mathbb{R}^3$, here is such a set with 21 vectors:</p>

<p>$$
\left\{
  [1,2,3], [2,3,1], [3,1,2], \\
  [1,4,5], [4,5,1], [5,1,4], \\
  [1,6,8], [6,8,1], [8,1,6], \\
  [1,8,12], [8,12,1], [12,1,8], \\
  [1,10,17], [10,17,1], [17,1,10], \\
  [1,12,23], [12,23,1], [23,1,12], \\
  [1,14,30], [14,30,1], [30,1,14]
\right\}
$$</p>

<p>Any combination of 3 of these vectors is linearly independent.</p>

<p>Is it possible to create a set satisfying this property with arbitrarily many vectors? I think so, but the specific pattern used in the set above breaks down around 50 vectors; I think some more complicated pattern should work. </p>

<p>Is it possible to create this set in time polynomial in the number of vectors in the set?</p>

CC BY-SA 3.0
2015-01-02T04:09:28.340Z
Any number of random unit length vectors will work with probability 1. If you want an explicit construction, a Cauchy or Vandermonde matrix will work. The property is known as "general position".
Sasho Nikolov
CC BY-SA 3.0
2015-01-03T15:11:44.433Z
...as will any number of independent Gaussian vectors, or any number of vectors chosen uniformly and independently from the unit cube $[0,1]^d$, or any number of vectors chosen independently from any probability distribution such that the projection of the support onto the unit sphere has positive measure.
Jeffε
CC BY-SA 3.0
2015-01-08T15:05:29.877Z
FYI:

If you ask for more than linear independent vectors, i.e., the subset of vectors to be close to orthogonal then your question is related to the quest for deterministically constructing matrices that satisfy the restricted isometry property (RIP). Take a look on the relevant literature there are several interesting results.
Zouzias
<cc.complexity-theory><linear-algebra><polynomials>
Is there a polynomial time algorithm for creating a set of vectors in general position?
Flávio Botelho
# Is there a polynomial time algorithm for creating a set of vectors in general position?

(Asked by: username_0 on 2015-01-02)

It seems to be possible to create a set of vectors in $\mathbb{R}^n$ such that any subset of $n$ vectors forms a basis.

For example, in $\mathbb{R}^3$, here is such a set with 21 vectors:

$$
\left\{
[1,2,3], [2,3,1], [3,1,2], \\
[1,4,5], [4,5,1], [5,1,4], \\
[1,6,8], [6,8,1], [8,1,6], \\
[1,8,12], [8,12,1], [12,1,8], \\
[1,10,17], [10,17,1], [17,1,10], \\
[1,12,23], [12,23,1], [23,1,12], \\
[1,14,30], [14,30,1], [30,1,14]
\right\}
$$

Any combination of 3 of these vectors is linearly independent.

Is it possible to create a set satisfying this property with arbitrarily many vectors? I think so, but the specific pattern used in the set above breaks down around 50 vectors; I think some more complicated pattern should work.

Is it possible to create this set in time polynomial in the number of vectors in the set?

**Tags:** cc.complexity-theory, linear-algebra, polynomials
> **Comments:**
> **username_1**: Any number of random unit length vectors will work with probability 1. If you want an explicit construction, a Cauchy or Vandermonde matrix will work. The property is known as "general position".  
> **username_2**: ...as will any number of independent Gaussian vectors, or any number of vectors chosen uniformly and independently from the unit cube $[0,1]^d$, or any number of vectors chosen independently from any probability distribution such that the projection of the support onto the unit sphere has positive measure.  
> **username_3**: FYI:  If you ask for more than linear independent vectors, i.e., the subset of vectors to be close to orthogonal then your question is related to the quest for deterministically constructing matrices that satisfy the restricted isometry property (RIP). Take a look on the relevant literature there are several interesting results.  

---

## 2 answers

### Answer by username_1 on 2015-01-02. Score: 6 | Accepted answer

Let me give some details for the Cauchy matrix construction, which is simple. Let $x = (x\_1, \ldots, x\_n)$, $y = (y\_1, \ldots, y\_m)$ be sequences of pairwise distinct numbers. The corresponding [Cauchy matrix](http://en.wikipedia.org/wiki/Cauchy_matrix) is
$$
C = \begin{pmatrix}
\frac{1}{x\_1 - y\_1} & \frac{1}{x\_1 - y\_2} & \ldots & \frac{1}{x\_1 - y\_m}\\
\frac{1}{x\_2 - y\_1} & \frac{1}{x\_2 - y\_2} & \ldots & \frac{1}{x\_2 - y\_m}\\
\vdots & \vdots & \ddots & \vdots\\
\frac{1}{x\_n - y\_1} & \frac{1}{x\_n - y\_2} & \ldots & \frac{1}{x\_n - y\_m}\\
\end{pmatrix}
$$

Then any square submatrix of $C$ is an invertible square Cauchy matrix. In particular, the $n\times n$ submatrix $C\_J$ with columns indexed by $J = \{j\_1, \ldots, j\_n\}$, $j\_1 \leq \ldots \leq j\_n$, has determinant  
$$
\det C\_J = \frac{\prod\_{i = 2}^n\prod\_{k = 1}^{i-1}{(x\_i - x\_k)(y\_{j\_i} - y\_{j\_k})}}{\prod\_{i = 1}^n\prod\_{k = 1}^n{(x\_i - y\_{j\_k})}}.
$$

Because $x$ and $y$ are sequences of distinct numbers, the determinant is nonzero, and $C\_J$ is invertible.

If you prefer something even more concrete, you can take the Hilbert matrix: the Cauchy matrix with $x = (1, \ldots, n)$ and $y = (0, -1, -2, \ldots, -m)$. With $n = 3$ you get the points $(1, 1/2, 1/3),\ (1/2, 1/3, 1/4),\ (1/3, 1/4, 1/5),\ (1/4, 1/5, 1/6)$ and so on.


---

### Answer by username_4 on 2015-01-02. Score: 4

Here is what I think S. Nikolov meant.

Take an $m\times m$ Vandermonde matrix $V(x\_1,\ldots,x\_m)$ where $V\_{i,j}=x\_i^{j-1}$ for $1\leq i,j\leq m.$

Take any $1\leq j\_1

The nontriviality condition of the Vandermonde matrix requires that the points $x\_i$ be distinct. If you are working over a finite field of size $q,$ then $q\geq m$ must hold. Over an infinite field this isn't required and clearly you can make $m$ as large as you wish.

**Edit:** I am sorry, this construction won't work in general, see the comments by Sasho Nikolov and Emil Jerabek.

> **Comments:**
> **username_1**: This is what I meant but I am not longer sure it works for Vandermonde: do you have a proof or reference? It works trivially for non-degenerate $m\times n$ Cauchy matrices, because any $n \times n$ submatrix is a square Cauchy matrix with non-zero determinant.  
> **username_0**: @SashoNikolov I just did some numeric runs on Vandermonde matrices and they seem to work just fine! Starting at number 2 at least... $a_i=i+2$  
> **username_0**: @SashoNikolov Now searching on google scholar for every Vondermonde submatrix being invertible shows lots of hits... Great find!  
> **username_1**: I think it's not always true, though. There may be additional conditions. See e.g. http://mathoverflow.net/questions/60938/is-any-n-1-times-n-1-submatrix-of-an-n-times-n-vandermonde-matrix-inver  
> **username_4**: @SashoNikolov, I added proof that I hope shows it will work for distinct $x_i$  
> **username_5**: The proof only works if $j_1=1,\dots,j_n=n$ (in which case the submatrix is a Vandermonde matrix in its own right anyway). The post linked by Sasho above includes the trivial counterexample $V(1,0)=\bigl(\begin{smallmatrix}1&1\\1&0\end{smallmatrix}\bigr)$, whose $(0)$ submatrix is not invertible.  
> **username_6**: @Emil: but does the OP care about $n-1 \times n-1$ submatrices?  
> **username_5**: @PeterShor: I’m not sure I understand your question. The $n-1$ in mathoverflow.net/questions/60938 is $n$ here, and the $n$ there is $m$ here, if that’s the issue.  
> **username_5**: Ah, or do you mean that the special case of $n\times n$ submatrices with $j_1=1,\dots,j_n=n$ is enough for Flávio Botelho’s question? I think that’s right, I was more concerned with the general claim made in the answer than with the original question.  
> **username_6**: @Emil: that's what I meant ... an $m \times n$ matrix with any $n \times n$ submatrix invertible is enough for the original question.  

---

