# 5.2: Linear Independence

- Page ID
- 290

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

We are now going to define the notion of linear independence of a list of vectors. This concept will be extremely important in the sections that follow, and especially when we introduce bases and the dimension of a vector space.

Definition 5.2.1: linearly independent Vectors

A list of vectors \((v_1,\ldots,v_m)\) is called **linearly independent** if the only solution for \(a_1,\ldots,a_m\in\mathbb{F}\) to the equation

\[ a_1 v_1 + \cdots + a_m v_m = 0 \]

is \(a_1=\cdots = a_m=0\). In other words, the zero vector can only trivially be written as a linear combination of \((v_1,\ldots,v_m)\).

Definition 5.2.2: Linearly dependent Vectors

A list of vectors \((v_1,\ldots,v_m)\) is called **linearly dependent** if it is not linearly independent. That is, \((v_1,\ldots,v_m)\) is linear dependent if there exist \(a_1,\ldots,a_m\in \mathbb{F}\), not all zero, such that

\[ a_1 v_1 + \cdots + a_m v_m = 0.\]

Example \(\PageIndex{1}\):

The vectors \((e_1,\ldots,e_m)\) of Example 5.1.4 are linearly independent. To see this, note that the only solution to the vector equation

\[ 0 = a_1 e_1 + \cdots + a_m e_m = (a_1,\ldots,a_m) \]

is \(a_1=\cdots=a_m=0\). Alternatively, we can reinterpret this vector equation as the homogeneous linear system

\[ \left. \begin{array}{cccccc} a_{1} & & ~ & ~ & = & 0 \\ ~ & a_{2} & ~ & ~ & = & 0 \\ ~ & ~ & \ddots & ~ & \vdots & \vdots \\ ~ & ~ & ~ & a_{m} & = & 0 \end{array} \right\}, \]

which clearly has only the trivial solution. (See Section A.3.2 for the appropriate definitions.)

Example \(\PageIndex{2}\):

The vectors \(v_1=(1,1,1),v_2=(0,1,-1)\), and \(v_3=(1,2,0)\) are linearly dependent. To see this, we need to consider the vector equation

\[ \begin{eqnarray} a_1 v_1 + a_2 v_2 + a_3 v_3 & = & a_1 (1,1,1) + a_2 (0,1,-1) + a_3 (1,2,0)\\ & = & (a_1+a_3,a_1+a_2+2a_3,a_1-a_2) = (0,0,0). \end{eqnarray} \]

Solving for \(a_1,a_2\), and \(a_3\), we see, for example, that \((a_1,a_2,a_3) = (1,1,-1)\) is a nonzero solution. Alternatively, we can reinterpret this vector equation as the homogeneous linear system

\[ \left. \begin{array}{ccccccc} a_{1} & ~ & ~ & + & a_{3} & = & 0 \\ a_{1} & + & a_{2} & + & 2a_{3} & = & 0 \\ a_{1} & - & a_{2} & ~ & ~ & = & 0 \end{array} \right\}. \]

Using the techniques of Section A.3, we see that solving this linear system is equivalent to solving the following linear system:

\[ \left. \begin{array}{ccccccc} a_{1} & ~ & ~ & + & a_{3} & = & 0 \\ ~ & ~ & a_{2} & + & a_{3} & = & 0 \end{array} \right\}. \]

Note that this new linear system clearly has infinitely many solutions. In particular, the set of all solutions is given by

\[ N = \{ (a_1,a_2,a_3) \in \mathbb{F}^{n} \ | \ a_{1} = a_{2} = -a_{3} \} = \Span((1,1,-1)). \]

Example \(\PageIndex{3}\):

The vectors \((1,z,\ldots,z^m)\) in the vector space \(\mathbb{F}_m[z]\) are linearly independent. Requiring that

\[ a_0 1 + a_1 z +\cdots+ a_m z^m = 0 \]

means that the polynomial on the left should be zero for all \(z\in \mathbb{F}\). This is only possible for \(a_0=a_1=\cdots=a_m=0\).

An important consequence of the notion of linear independence is the fact that any vector in the span of a given list of linearly independent vectors can be uniquely written as a linear combination.

Lemma 5.2.6

*The list of vectors* \((v_1,\ldots,v_m)\) *is linearly independent if and only if every* \(v\in\Span(v_1,\ldots,v_m)\) *can be uniquely written as a linear combination of *\((v_1,\ldots,v_m)\).

Proof

\(( "\Longrightarrow" )\) Assume that \((v_1,\ldots,v_m)\) is a linearly independent list of vectors.

Suppose there are two ways of writing \(v\in\Span(v_1,\ldots,v_m)\) as a linear combination of the \(v_i\):

\[ v=a_1v_1 + \cdots a_m v_m,\\ v=a^{'}_1v_1 + \cdots a^{'}_m v_m. \]

Subtracting the two equations yields \(0=(a_1-a_1')v_1 + \cdots + (a_m-a_m')v_m\).

Since \((v_1,\ldots,v_m)\) is linearly independent, the only solution to this equation is \(a_1-a_1'=0,\ldots,a_m-a_m'=0\), or equivalently \(a_1=a_1',\ldots,a_m=a_m'\).

\(( "\Longleftarrow" )\) Now assume that, for every \(v \in \Span(v_1,\ldots,v_m)\), there are unique \(a_1,\ldots,a_m \in \mathbb{F}\) such that

\[ v = a_1 v_1 + \cdots + a_m v_m. \]

This implies, in particular, that the only way the zero vector \(v=0\) can be written as a linear combination of \(v_1,\ldots,v_m\) is with \(a_1=\cdots=a_m=0\). This shows that \((v_1,\ldots,v_m)\) are linearly independent.

\(\square\)

It is clear that if \((v_1,\ldots,v_m)\) is a list of linearly independent vectors, then the list \((v_1,\ldots,v_{m-1})\) is also linearly independent.

For the next lemma, we introduce the following notation: If we want to drop a vector \(v_j\) from a given list \((v_1,\ldots,v_m)\) of vectors, then we indicate the dropped vector by a hat. I.e., we write

\[ (v_1,\ldots,\hat{v}_j,\ldots,v_m) = (v_1,\ldots,v_{j - 1}, v_{j + 1},\ldots,v_m). \]

Lemma 5.2.7: Linear Dependence Lemma

*If *\((v_1,\ldots,v_m)\) *is linearly dependent and* \(v_1\neq 0\),* then there exists an index *\(j\in \{2,\ldots,m\}\) *such that the following two conditions hold.*

- \(v_j\in \Span(v_1,\ldots, v_{j-1})\).
*If*\(v_j\)*is removed from*\((v_1,\ldots,v_m)\),*then*\(\Span(v_1,\ldots,\hat{v}_j,\ldots,v_m) = \Span(v_1,\ldots,v_m)\).

Proof

Since \((v_1,\ldots,v_m)\) is linearly dependent there exist \(a_1,\ldots,a_m\in \mathbb{F}\) not all zero such that \(a_1v_1+\cdots+ a_mv_m =0\). Since by assumption \(v_1\neq 0\), not all of \(a_2,\ldots,a_m\) can be zero. Let \(j\in\{2,\ldots,m\}\) be largest such that \(a_j\neq 0\). Then we have

\[ v_j = -\frac{a_1}{a_j} v_1-\cdots - \frac{a_{j-1}}{a_j} v_{j-1}, \label{5.2.1} \]

which implies Part~1.

Let \(v\in\Span(v_1,\ldots,v_m)\). This means, by definition, that there exist scalars \(b_1,\ldots,b_m\in\mathbb{F}\) such that

\[ v = b_1 v_1 + \cdots + b_m v_m. \]

The vector \(v_j\) that we determined in Part 1 can be replaced by Equation \ref{5.2.1}) so that \(v\) is written as a linear combination of \((v_1,\ldots,\hat{v}_j,\ldots,v_m)\). Hence, \(\Span(v_1,\ldots,\hat{v}_j,\ldots,v_m) = \Span(v_1,\ldots,v_m)\).

\(\square\)

Example \(\PageIndex{4}\):

The list \((v_1,v_2,v_3)=((1,1),(1,2),(1,0))\) of vectors spans \(\mathbb{R}^2\).

To see this, take any vector \(v=(x,y)\in \mathbb{R}^2\). We want to show that \(v\) can be written as a linear combination of \((1,1),(1,2),(1,0)\), i.e., that there exist scalars \(a_{1}, a_{2}, a_{3} \in \mathbb{F}\) such that

\[ v = a_1 (1,1) + a_2 (1,2) + a_3 (1,0),\]

or equivalently that

\[ (x,y) = (a_1+a_2+a_3,a_1+2a_2). \]

Clearly \(a_1=y\), \(a_2=0\), and \(a_3=x-y\) form a solution for any choice of \(x, y\in \mathbb{R}\), and so \(\mathbb{R}^2=\Span((1,1),(1,2),(1,0))\). However, note that

\[ 2 (1,1) - (1,2) - (1,0) = (0,0), \label{5.2.2} \]

which shows that the list \(((1,1),(1,2),(1,0))\) is linearly dependent.

## The Linear Dependence

Lemma 5.2.7 thus states that one of the vectors can be dropped from \(((1,1),(1,2),(1,0))\) and that the resulting list of vectors will still span \(\mathbb{R}^2\). Indeed, by Equation \ref{5.2.2},

\[ v_3 = (1,0) = 2(1,1)-(1,2) = 2v_1-v_2, \]

and so \(\Span((1,1),(1,2),(1,0))=\Span((1,1),(1,2)).\)

The next result shows that linearly independent lists of vectors that span a finite-dimensional vector space are the smallest possible spanning sets.

Theorem 5.2.9

*Let* \(V\) *be a finite-dimensional vector space. Suppose that* \((v_1,\ldots,v_m)\) *is a linearly independent list of vectors that spans* \(V\), *and let* \((w_1,\ldots,w_n)\) *be any list that spans* \(V\).* Then* \(m\le n\).

Proof

The proof uses the following iterative procedure: start with an arbitrary list of vectors \(\mathcal{S}_0=(w_1,\ldots,w_n)\) such that \(V = \Span(\mathcal{S}_0)\). At the \(k^{\text{th}}\) step of the procedure, we construct a new list \(\mathcal{S}_k\) by replacing some vector \(w_{j_k}\) by the vector \(v_k\) such that \(\mathcal{S}_k\) still spans \(V\). Repeating this for all \(v_k\) then produces a new list \(\mathcal{S}_m\) of length \(n\) that contains each of \(v_1,\ldots,v_m\), which then proves that \(m\le n\). Let us now discuss each step in this procedure in detail.

**Step 1.** Since \((w_1,\ldots,w_n)\) spans \(V\), adding a new vector to the list makes the new list linearly dependent. Hence \((v_1,w_1,\ldots,w_n)\) is linearly dependent. By Lemma 5.2.7, there exists an index \(j_1\) such that

\[ w_{j_1} \in \Span(v_1,w_1,\ldots, w_{j_1-1}).\]

Hence \(\mathcal{S}_1=(v_1,w_1,\ldots,\hat{w}_{j_1},\ldots,w_n)\) spans \(V\). In this step, we added the vector \(v_1\) and removed the vector \(w_{j_1}\) from \(\mathcal{S}_0\).

**Step **\(k\)**.** Suppose that we already added \(v_1,\ldots,v_{k-1}\) to our spanning list and removed the vectors \(w_{j_1},\ldots,w_{j_{k-1}}\). It is impossible that we have reached the situation where all of the vectors \(w_1,\ldots, w_n\) have been removed from the spanning list at this step if \(k\leq m\) because then we would have \(V=\Span(v_1,\ldots, v_{k-1})\) which would allow \(v_k\) to be expressed as a linear combination of \(v_1,\ldots,v_{k-1}\) (in contradiction with the assumption of linear independence of \(v_1,\ldots,v_n\)).

Now, call the list reached at this step \(\mathcal{S}_{k-1}\), and note that \(V = \Span(\mathcal{S}_{k-1})\). Add the vector \(v_k\) to \(\mathcal{S}_{k-1}\). By the same arguments as before, adjoining the extra vector \(v_k\) to the spanning list \(\mathcal{S}_{k-1}\) yields a list of linearly dependent vectors. Hence, by Lemma 5.2.7, there exists an index \(j_k\) such that \(\mathcal{S}_{k-1}\) with \(v_k\) added and \(w_{j_k}\) removed still spans \(V\). The fact that \((v_1,\ldots,v_k)\) is linearly independent ensures that the vector removed is indeed among the \(w_j\). Call the new list \(\mathcal{S}_k\), and note that \(V = \Span(\mathcal{S}_{k})\).

The final list \(\mathcal{S}_m\) is \(\mathcal{S}_0\) but with each \(v_1,\ldots,v_m\) added and each \(w_{j_1},\ldots, w_{j_m}\) removed. Moreover, note that \(\mathcal{S}_{m}\) has length \(n\) and still spans \(V\). It follows that \(m\le n\).

\(\square\)

## Contributors

- Isaiah Lankham, Mathematics Department at UC Davis
- Bruno Nachtergaele, Mathematics Department at UC Davis
- Anne Schilling, Mathematics Department at UC Davis

Both hardbound and softbound versions of this textbook are available online at WorldScientific.com.