Linear Dependence Lemma is AFAIK one of the more important results of elementary linear algebra.

## statement

Suppose \(v_1, \dots v_{m}\) is an linearly dependent list in \(V\); then \(\exists j \in \{1, 2, \dots m\}\) such that…

- \(v_{j} \in span(v_1, \dots, v_{j-1})\)
- the span of the list constructed by removing \(v_{j}\) from \(v_1, \dots v_{m}\) equals the span of \(v_1, \dots v_{m}\) itself

intuition: “in a linearly dependent list of vectors, one of the vectors is in the span of the previous ones, and we can throw it out without changing the span.”

## proof

By definition of linear dependence, given the list \((v_1, \dots v_{m}\)) is linearly dependent, there exists some not-all-zero \(a_1, \dots, a_{m} \in \mathbb{F}\) such that:

\begin{equation} a_1v_1+\dots +a_{m}v_{m} = 0 \end{equation}

Let \(a_{j}\) be the last non-zero scalar in the expression (making the term actually exist). You can, in this circumstance, chuck everything to the right and divide by \(a_{j}\) to recover \(v_{j}\):

\begin{equation} v_{j}= -\frac{a_1}{a_{j}} v_1 - \dots -\frac{a_{j-1}}{a_{j}}v_{j-1} \end{equation}

We were able to construct \(v_{j}\) as a linear combination of \(v_{1}, \dots v_{j-1}\), therefore:

\begin{equation} v_{j} \in span(v_1, \dots, v_{j-1}) \end{equation}

showing \((1)\).

For \(2\), the intuition behind the proof is just that you can take that expression for \(v_{j}\) above to replace \(v_{j}\), therefore getting rid of one vector but still keeping the same span.

Formally, \(\forall u \in span(v_1, \dots v_{m})\), we can write it as some:

\begin{equation} u = c_1v_1 + \dots c_{j}v_{j} + \dots + c_{m}v_{m} \end{equation}

now we replace \(v_{j}\) with the isolated expression for \(v_{j}\) above.

Exception: if \(j=1\) and \(v_1=0\), note that you can just replace \(v_1\) with \(0\) without doing any special substitution.

Having written all arbitrary \(u \in span(v_1, \dots v_{m})\) as a linear combination of \(v_1\dots v_{m}\) *without* … \(v_{j}\), we see that the renaming vectors span the same space. \(\blacksquare\)

## issue

note that if we chose \(j=1\) in the above result, \(v_1=0\). Contrapositively, if \(v_1 \neq 0\), \(j\neq 1\). This is because of the fact that:

if \(j=1\), the lemma tells us that \(v_{1} \in span(v_{1-1}) \implies v_1 \in span()\). As per definition, the span of the empty set is \(\{0\}\). Therefore, \(v_1 \in \{0\} \implies v_1=0\).