Houjun Liu

Linear Dependence Lemma

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


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

  1. \(v_{j} \in span(v_1, \dots, v_{j-1})\)
  2. 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.”


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\)


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\).