# Is there a polynomial time algorithm for creating a set of vectors in general position?

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?

• 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 Jan 2 '15 at 4:09
• ...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ε Jan 3 '15 at 15:11
• 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 Jan 8 '15 at 15:05

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

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<j_2<\ldots<j_n\leq m,$ so we assume $n\leq m$ here. Then for any choice of $1\leq i_1<i_2<\ldots<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.

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.

• I think it's not always true, though. There may be additional conditions. See e.g. mathoverflow.net/questions/60938/… – Sasho Nikolov Jan 3 '15 at 5:36
• 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 Jan 3 '15 at 14:17
• @Emil: but does the OP care about $n-1 \times n-1$ submatrices? – Peter Shor Jan 4 '15 at 12:42
• 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 Jan 4 '15 at 15:35
• @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 Jan 4 '15 at 15:45