NOTE: Slightly more general question follows my specific one at the top

For $1 \leq i,j \leq n$, let $e_{ij}$ be the vector in $\mathbb{R}^{n^{2}}$ with a 1 in entry $(n-1)i + j$, and 0's everywhere else. Then let $v[a,b,c,d] = e_{ac} + e_{bd} - e_{ad} - e_{bc}$, for $1 \leq a < b \leq n$, $1 \leq c < d \leq n$.

My (slightly fuzzy) question: Pick $M$ distinct vectors of the form $v[a,b,c,d]$ for some valid $a,b,c,d$, say uniformly at random. Call them $v_{1}, \ldots, v_{m}$ How large does $M$ have to be in to allow you to write

$v[1,2,1,2] = \sum_{m = 1}^{M} c_{m} v_{m}$

for $c_{m}$ 'small' (e.g. -10 \leq c_{m} \leq 10) with 'high probability'? Of course, if $M \sim n^{4}$, it will be possible, since $v[1,2,1,2]$ itself eventually shows up. But we get a basis around $M \sim n^{2} \log(n)$, and I would like to know if this becomes possible around the time that a basis appears.

MORE GENERALLY: Is there some theory of linear relationships or bases with small coefficients?