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?
Is there a polynomial time algorithm for creating a set of vectors in general position?
cc.complexity theory;linear algebra;polynomials
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.  