Be $N$, $K$ natural numbers so that $K > N > 1$.
Be $V$ a set of $K$ vectors in $\mathbb{R}^N$: $V = \{v_1, \ldots, v_K \in \mathbb{R}^N\}$. First of all, I need to find a $V$ so that, for any subset $W$ of $V$ of $N$ elements ($|W| = N$) the vectors in $W$ form a basis for $\mathbb{R}^N$.
As an example, be $N = 2$. Now, let $\alpha_k = \frac{\pi}{2} \frac{k}{K}$. The vectors $v_k = (\cos(\alpha_k), \sin(\alpha_k))$ form a set of $K$ distinct vectors. Every couple of vectors taken from that set is independent, therefore it forms a basis for $\mathbb{R}^2$.
As another example, let $N = 3$ and $K = 6$. The vectors $(1, 0, 0)$, $(0, 1, 0)$, $(0, 0, 1)$, $(2, 1, 1)$, $(1, 2, 1)$, $(1, 1, 2)$ satisfy the preceding condition: any three of them I take, they all form a basis for $\mathbb{R}^3$.
My intuition says that on the real numbers this is definitely possible. For example, let's start with the canonical basis, then add up $K - N$ vectors to it. When I am to add a vector, what I have to do is to look for all the (N - 1)-hyperplanes generated by all the possible subsets of $V$ that have $N - 1$ elements in it, then just find a vector that doesn't lie in any of them. This definitely sounds feasible, but maybe I am somehow mislead.
Now, how far can this be generalized? Can $N$ and $K$ be arbitrary? Is it possible to have a constructive way to build $V$, given $K$?
Now, if it is possible to do such a thing with real vectors, is it possible to do such a thing with vectors which components are all integer valued, and as small as possible? I mean: if that works with real numbers, I can have as close approximations of a real vector with integer numbers as I want, and being my problem discrete, that definitely sounds enough. But how can I prevent my integer components from being huge?
It depends on what you mean by "large", but you can take any set of $K$ pairwise-different strictly positive integers $\{m_1,m_2,\ldots,m_K\}$ (say the first $K$ ones), and consider the following Vandermonde-shaped family of vectors with integer entries: \begin{equation*} v_i =(1,m_i, m_i^2,\ldots,m_i^{N-1}), \quad i=1,\ldots,K. \end{equation*} Then, any subset of $N$ vectors within the family will determine a Vandermonde matrix with nonzero determinant; and thus a basis of $\mathbb{R}^N$ (but not of $\mathbb{Z}^N$, since the absolute value of the determinant will be - except for trivial cases - greater than one).