Linear Dependence Lemma — Jemoka Knowledge Base

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.