First: I know that every basis of some vector space contains the same amount of vectors. The question is not about that.
Let $\vec a_1, \dots, \vec a_m \in \mathbb{N}^n \setminus \{\vec 0\}$ be some vectors. And I want to select a basis $\vec b_1, \dots, \vec b_r \in \{\vec a_1, \dots, \vec a_m\}$ of the span of $\vec a_1, \dots, \vec a_m$. This is a trivial task and can be done using some Gauß elimination steps. But, I want the basis to have a very special property:
For each vector $\vec a_j, j\in [m]$ we find a linear combination of the basis vectors:
$$\vec a_j = \sum_{i=1}^r \lambda_i \cdot \vec b_i \qquad \mathrm{with}\quad \lambda_i \in \mathbb{Q}$$
I want to choose the basis in such a way that for every $\vec a_j$ it will hold that
$$\sum_{i=1}^r \lambda_i \stackrel{!}{\geq} 1$$
I hope you can see, why I call that basis the "smallest" possible basis. We need the coefficiants to at least add up to 1 to reach all other vectors. Does there always exist such a basis? How can you find it?
While researching and thinking about this problem, I stumbled upon some related NP hard problem somewhere. I tried to find the specific problem later but I didn't succeed. Maybe there is no better option than just trying all different possible basis? In this case, is there a related NP hard problem?
What I already tried
One immediate idea I had, was selecting the basis, where the total component sum (so $\sum_{i=1}^r\sum_{j=1}^n (\vec b_i)_j$) is minimal. But this will not work. Here is a counterexample: Let $\vec a_1 := (1, 5)^\top$, $\vec a_2 := (0, 1)^\top$ and $\vec a_3 := (3, 9)^\top$. Any pair of these 3 vectors would yield a basis. So let's select the ones where the component sum is the smallest. These are $\vec a_2$ (component sum $0+1=1$) and $\vec a_1$ (component sum $1+5=6$). As it is a basis of $\mathbb{N}^2$ the coefficients are unique. You can quickly see that $-6\vec a_2 + 3\vec a_1 = \vec a_3$. Here, the coefficients sum up to $-6 + 3 = -3$ which is clearly less than 1. But you can reach a positive sum, by selecting $\vec a_2$ and $\vec a_3$ instead, as $2\vec a_2 + \frac{1}{3}\vec a_3 = \vec a_1$ and clearly $2 + \frac{1}{3} \geq 1$. How would know to choose $\vec a_2$ and $\vec a_3$ a priori?
Edit
I've generated 1000 matrices randomly and found that for every of those matrices, such a basis could be selected. Thus I assume, that this basis always exists, but why? And more importantly, how would you figure it out.
By a similar experiment I also found that at least one of the possible basis always include the vector with the smallest component sum. There are sometimes other basis with this property not including this "smallest" vector, but there is always at least one.
Best Answer
Let $\vec v_1,\dots,\vec v_r$ be a linearly independent set in $\Bbb R^n$, and let $H$ be the unique $(r-1)$-dimensional affice space passing through $\vec v_1,\dots,\vec v_r$. Then $H$ separates the $r$-dimensional subspace span$(\vec v_1,\dots,\vec v_r)$ into two open half-spaces: one piece $S_0$ contains the origin and the other piece $S_1$ does not.
The crucial observation is that if $\vec y = \sum_{i=1}^r \lambda_i \vec v_i$ is any vector in span$(\vec v_1,\dots,\vec v_r)$, then $$ \sum_{i=1}^r \lambda_i < 1 \text{ if and only if } \vec y \in S_0. $$
Therefore I believe this procedure always works: