Intersection of Span of Vectors and Hypercube Consider a set of vectors $\{v_1,\ldots,v_k\}\in\mathbb{R}^n$. Denote the span of these vectors by $Sp(v_1,\ldots,v_k)$. Is there a method to determine,
$Sp(v_1,\ldots,v_k)\cap \{0,1\}^n$
That is, the intersection of the span of the vectors and the $n$-hypercube?
Some thoughts: If the set of vectors is linear independent then every $u\in Sp(v_1,\ldots,v_k)$ can be expressed as $u=\sum_i a_iv_i$ for some real numbers $a_i$. If we try to solve for $a_i$ such that $u=e_j$ where $e_j$ is the $j$-th unit vector, we may find a solution. The it follows that $e_j\in Sp(v_1,\ldots,v_k) \cap \{0,1\}^n$. If $e_{j_1}$ and $e_{j_2}$ are both in the span, then their sum is in the span as well (simply sum the respective $a_i$ terms). Ultimately, we arrive at the set of all unit vectors in the span. Then all combinations of these will give all points on the hypercube.
Is this reasoning valid? Is there an easier way?
 A: You didn't mention whether you wanted computational efficiency or not, so I'm going to start by assuming "not". 
In that case, you can do the following:
Extend $v_1, \ldots, v_k$ by $e_1, \ldots, e_n$ to get an ordered list of $n+k$ vectors that certainly spans $n$-space (because the last $n$ do!). 
Now apply Gram-Schmidt to those, with the rule that whenever you get a $0$-vector, you simply ignore it. For instance, if $v_1 = e_2, v_2 = e_2+e_1$, then your initial set would be 
$$
e_2, e_2+e_1, e_1, e_2 e_3
$$
and Gram-Schmidt, one step at a time, would produce
$$
e_2 \\
e_2, e_1 \\
e_2, e_1, 0 [which~we~delete] \\
e_2, e_1, [0], [0] \\
e_2, e_1, [0], [0], e_3
$$
where the brackets indicate elements that were computed and then thrown out. 
When you're done, you end up with a list of orthogonal vectors
$$
u_1, u_2, \ldots, u_p, w_1, w_2, \ldots, w_{n-p}
$$
with the property that the span of the $u$s is the same as the span of the $v$s, while the $w$s span the orthogonal complement of the $v$s. 
Form a matrix 
$$
W = \begin{bmatrix}
w_1 & w_2 & \ldots & w_{n-p}
\end{bmatrix}
$$
whose columns are the $w$ vectors, and for each vertex $P_i$ of the $n$-cube, compute
$$
t_i = wP_i.
$$
This is the projection of $P_i$ onto the orthog complement of span{$v_1, \ldots, v_k$}, in $w$-coordinates. If $t_i$ is zero, then $P_i$ is in the span of the original $v$s; if it's nonzero, then it's not in the span. 
As written, you have to do this for all $2^n$ points, which is slow. But as you observe, once you find $r$ vectors in the span, all $2^r$ other vectors that are formed as positive sums of those will also be in the span, so there should be some way to simplify a bit. 
I suspect that if you put the vectors $t_i$ into a matrix $T$ (where rather than using every vertex $P_i$ of the $n$-cube, you just just $e_1, \ldots, e_n$), you can apply Gaussian elimination to the columns of $T$, and can eventually use this to find a spanning set of vertices that are in the subspace $V$. For instance, if $t_1 = Me_1$ and $t_2 = Me_2$ are both nonzero, but happen to be negatives of one another, then $M(e_1 + e_1)$ will be in $V$. And I just realized that the matrix $T$ I've just described is really just the original matrix $M$. I'll also observe that since you only want POSITIVE linear combinations of things, straight Gaussian elimination won't suffice...but something a lot like it might well do. 
I grant this isn't a complete solution, but I hope it's a useful start. 
