Linear independence

Linear independence is one of the most fundamental conceptual ideas in linear algebra, along with the notion of a span. So this section, and the subsequent , will explore this new idea.

1. S=\set{\colvector{1\\2\\-1},\,\colvector{3\\-4\\2},\,\colvector{4\\-2\\1}}
2. S=\set{\colvector{1\\-1\\0},\,\colvector{3\\2\\2},\,\colvector{4\\3\\-4}}
3. \begin{bmatrix} 1 &3 &4\\ -1 &2 &3\\ 0 &2 &-4 \end{bmatrix}

Determine if the sets of vectors in Exercises C20C25 are linearly independent or linearly dependent. When the set is linearly dependent, exhibit a nontrivial relation of linear dependence.

tells us that a solution to a homogeneous system of equations is a linear combination of the columns of the coefficient matrix that equals the zero vector. We used just this situation to our advantage (twice!) in where we reduced the set of vectors used in a span construction from four down to two, by declaring certain vectors as surplus. The next two definitions will allow us to formalize this situation.

Notice that a relation of linear dependence is an equation. Though most of it is a linear combination, it is not a linear combination (that would be a vector). Linear independence is a property of a set of vectors. It is easy to take a set of vectors, and an equal number of scalars, all zero, and form a linear combination that equals the zero vector. When the easy way is the only way, then we say the set is linearly independent. Here are a couple of examples.

and relied on solving a homogeneous system of equations to determine linear independence. We can codify this process in a time-saving theorem.

Since is an equivalence, we can use it to determine the linear independence or dependence of any set of column vectors, just by creating a matrix and analyzing the row-reduced form. Let us illustrate this with two more examples.

As an equivalence, gives us a straightforward way to determine if a set of vectors is linearly independent or dependent.

They are very similar, differing only in the last two slots of the third vector. This resulted in slightly different matrices when row-reduced, and slightly different values of $r$, the number of nonzero rows. Notice, too, that we are less interested in the actual solution set, and more interested in its form or size. These observations allow us to make a slight improvement in .

The situation in is slick enough to warrant formulating as a theorem.

Condensed: the full section is in Beezer, A First Course in Linear Algebra.

We will now specialize to sets of $n$ vectors from $\complex{n}$. This will put off-limits, while will involve square matrices. Let us begin by contrasting and .

That and have opposite properties for the columns of their coefficient matrices is no accident. Here is the theorem, and then we will update our equivalences for nonsingular matrices, .

Here is the update to .

As will be our habit, we can illustrate properties of nonsingular matrices with random square matrices. Review for a refresher on generating these matrices. Here we will illustrate the fifth condition, half of .

You should always get an empty list ([]) as the result of the second compute cell, no matter which random (unimodular) matrix you produce prior. Note that the list of vectors created using .columns() is exactly the list we want to feed to .linear_dependence().

In we proved which provided $n-r$ vectors that could be used with the span construction to build the entire null space of a matrix. As we have hinted in , and as we will see again going forward, linearly dependent sets carry redundant vectors with them when used in building a set as a span. Our aim now is to show that the vectors provided by form a linearly independent set, so in one sense they are as efficient as possible a way to describe the null space. Notice that the vectors $\vect{z}_j$, $1\leq j\leq n-r$ first appear in the vector form of solutions to arbitrary linear systems (). The exact same vectors appear again in the span construction in the conclusion of . Since this second theorem specializes to homogeneous systems the only real difference is that the vector $\vect{c}$ in is the zero vector for a homogeneous system. Finally, will now show that these same vectors are a linearly independent set. We will set the stage for the proof of this theorem with a moderately large example. Study the example carefully, as it will make it easier to understand the proof.

The proof of is really quite straightforward, and relies on the pattern of zeros and ones that arise in the vectors $\vect{z}_i$, $1\leq i\leq n-r$ in the entries that arise with the locations of the non-pivot columns. Play along with as you study the proof. Also, take a look at , and , especially at the conclusion of Step 2 (temporarily ignore the construction of the constant vector, $\vect{c}$). This proof is also a good first example of how to prove a conclusion that states a set is linearly independent.

Condensed: the full section is in Beezer, A First Course in Linear Algebra.

In linear algebra, a set of vectors is said to be linearly independent if there exists no vector in the set that is equal to a linear combination of the other vectors in the set. If such a vector exists, then the vectors are said to be linearly dependent. Linear independence is part of the definition of linear basis.

A vector space can be of finite dimension or infinite dimension depending on the maximum number of linearly independent vectors. The definition of linear dependence and the ability to determine whether a subset of vectors in a vector space is linearly dependent are central to determining the dimension of a vector space.

A sequence of vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_k\) from a vector space V is said to be linearly dependent, if there exist scalars \(a_1, a_2, \dots, a_k,\) not all zero, such that

\(a_1\mathbf{v}_1 + a_2\mathbf{v}_2 + \cdots + a_k\mathbf{v}_k = \mathbf{0},\)

where \(\mathbf{0}\) denotes the zero vector.

If ⁠\(k=1\)⁠, this implies that a single vector is linear dependent if and only if it is the zero vector.

If ⁠\(k>1\)⁠, this implies that at least one of the scalars is nonzero, say \(a_1\ne 0\), and the above equation is able to be written as

\(\mathbf{v}_1 = \frac{-a_2}{a_1}\mathbf{v}_2 + \cdots + \frac{-a_k}{a_1} \mathbf{v}_k.\)

Thus, a set of vectors is linearly dependent if and only if one of them is zero or a linear combination of the others.

A sequence of vectors \(\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n\) is said to be linearly independent if it is not linearly dependent, that is, if the equation

\(a_1\mathbf{v}_1 + a_2 \mathbf{v}_2 + \cdots + a_n\mathbf{v}_n = \mathbf{0},\)

can only be satisfied by \(a_i=0\) for \(i=1,\dots,n.\) This implies that no vector in the sequence can be represented as a linear combination of the remaining vectors in the sequence. In other words, a sequence of vectors is linearly independent if the only representation of \(\mathbf 0\) as a linear combination of its vectors is the trivial representation in which all the scalars \(a_i\) are zero. Even more concisely, a sequence of vectors is linearly independent if and only if \(\mathbf 0\) can be represented as a linear combination of its vectors in a unique way.

Condensed: the full section is in Wikipedia.

An infinite set of vectors is linearly independent if every finite subset is linearly independent. This definition applies also to finite sets of vectors, since a finite set is a finite subset of itself, and every subset of a linearly independent set is also linearly independent.

Conversely, an infinite set of vectors is linearly dependent if it contains a finite subset that is linearly dependent, or equivalently, if some vector in the set is a linear combination of other vectors in the set.

An indexed family of vectors is linearly independent if it does not contain the same vector twice, and if the set of its vectors is linearly independent. Otherwise, the family is said to be linearly dependent.

A set of vectors which is linearly independent and spans some vector space, forms a basis for that vector space. For example, the vector space of all polynomials in x over the reals has the (infinite) subset {1, x, x, ...} as a basis.

Let \(V\) be a vector space. A set \(X \subseteq V\) is linearly independent if and only if \(X\) is a minimal element of

\(\{Y \subseteq V \mid X \subseteq \operatorname{Span}(Y)\}\)

by the inclusion order. In contrast, \(X\) is linearly dependent if it has a proper subset whose span is a superset of \(X\).

• \(\vec u\) and \(\vec v\) are independent and define the plane P.
• \(\vec u\), \(\vec v\) and \(\vec w\) are dependent because all three are contained in the same plane.
• \(\vec u\) and \(\vec j\) are dependent because they are parallel to each other.
• \(\vec u\) , \(\vec v\) and \(\vec k\) are independent because \(\vec u\) and \(\vec v\) are independent of each other and \(\vec k\) is not a linear combination of them or, equivalently, because they do not belong to a common plane. The three vectors define a three-dimensional space.
• The vectors \(\vec o\) (null vector, whose components are equal to zero) and \(\vec k\) are dependent since \(\vec o = 0 \vec k\).

A person describing the location of a certain place might say, "It is 3 miles north and 4 miles east of here." This is sufficient information to describe the location, because the geographic coordinate system may be considered as a 2-dimensional vector space (ignoring altitude and the curvature of the Earth's surface). The person might add, "The place is 5 miles northeast of here." This last statement is true, but it is not necessary to find the location.

In this example the "3 miles north" vector and the "4 miles east" vector are linearly independent. That is to say, the north vector cannot be described in terms of the east vector, and vice versa. The third "5 miles northeast" vector is a linear combination of the other two vectors, and it makes the set of vectors linearly dependent, that is, one of the three vectors is unnecessary to define a specific location on a plane.

Also note that if altitude is not ignored, it becomes necessary to add a third vector to the linearly independent set. In general, n linearly independent vectors are required to describe all locations in n-dimensional space.

If one or more vectors from a given sequence of vectors \(\mathbf{v}_1, \dots, \mathbf{v}_k\) is the zero vector \(\mathbf{0}\) then the vectors \(\mathbf{v}_1, \dots, \mathbf{v}_k\) are necessarily linearly dependent (and consequently, they are not linearly independent). To see why, suppose that \(i\) is an index (i.e. an element of \(\{ 1, \ldots, k \}\)) such that \(\mathbf{v}_i = \mathbf{0}.\) Then let \(a_{i} := 1\) (alternatively, letting \(a_{i}\) be equal to any other non-zero scalar will also work) and then let all other scalars be \(0\) (explicitly, this means that for any index \(j\) other than \(i\) (i.e. for \(j \neq i\)), let \(a_{j} := 0\) so that consequently \(a_{j} \mathbf{v}_j = 0 \mathbf{v}_j = \mathbf{0}\)). Simplifying \(a_1 \mathbf{v}_1 + \cdots + a_k\mathbf{v}_k\) gives:

\(a_1 \mathbf{v}_1 + \cdots + a_k\mathbf{v}_k = \mathbf{0} + \cdots + \mathbf{0} + a_i \mathbf{v}_i + \mathbf{0} + \cdots + \mathbf{0} = a_i \mathbf{v}_i = a_i \mathbf{0} = \mathbf{0}.\)

Because not all scalars are zero (in particular, \(a_{i} \neq 0\)), this proves that the vectors \(\mathbf{v}_1, \dots, \mathbf{v}_k\) are linearly dependent.

As a consequence, the zero vector can not possibly belong to any collection of vectors that is linearly independent.

Now consider the special case where the sequence of \(\mathbf{v}_1, \dots, \mathbf{v}_k\) has length \(1\) (i.e. the case where \(k = 1\)). A collection of vectors that consists of exactly one vector is linearly dependent if and only if that vector is zero. Explicitly, if \(\mathbf{v}_1\) is any vector then the sequence \(\mathbf{v}_1\) (which is a sequence of length \(1\)) is linearly dependent if and only if \(\mathbf{v}_1 = \mathbf{0}\); alternatively, the collection \(\mathbf{v}_1\) is linearly independent if and only if \(\mathbf{v}_1 \neq \mathbf{0}.\)

This example considers the special case where there are exactly two vector \(\mathbf{u}\) and \(\mathbf{v}\) from some real or complex vector space. The vectors \(\mathbf{u}\) and \(\mathbf{v}\) are linearly dependent if and only if at least one of the following is true:

1. \(\mathbf{u}\) is a scalar multiple of \(\mathbf{v}\) (explicitly, this means that there exists a scalar \(c\) such that \(\mathbf{u} = c \mathbf{v}\)) or
2. \(\mathbf{v}\) is a scalar multiple of \(\mathbf{u}\) (explicitly, this means that there exists a scalar \(c\) such that \(\mathbf{v} = c \mathbf{u}\)).

If \(\mathbf{u} = \mathbf{0}\) then by setting \(c := 0\) we have \(c \mathbf{v} = 0 \mathbf{v} = \mathbf{0} = \mathbf{u}\) (this equality holds no matter what the value of \(\mathbf{v}\) is), which shows that (1) is true in this particular case. Similarly, if \(\mathbf{v} = \mathbf{0}\) then (2) is true because \(\mathbf{v} = 0 \mathbf{u}.\) If \(\mathbf{u} = \mathbf{v}\) (for instance, if they are both equal to the zero vector \(\mathbf{0}\)) then both (1) and (2) are true (by using \(c := 1\) for both).

If \(\mathbf{u} = c \mathbf{v}\) then \(\mathbf{u} \neq \mathbf{0}\) is only possible if \(c \neq 0\) and \(\mathbf{v} \neq \mathbf{0}\); in this case, it is possible to multiply both sides by \(\frac{1}{c}\) to conclude \(\mathbf{v} = \frac{1}{c} \mathbf{u}.\) This shows that if \(\mathbf{u} \neq \mathbf{0}\) and \(\mathbf{v} \neq \mathbf{0}\) then (1) is true if and only if (2) is true; that is, in this particular case either both (1) and (2) are true (and the vectors are linearly dependent) or else both (1) and (2) are false (and the vectors are linearly independent). If \(\mathbf{u} = c \mathbf{v}\) but instead \(\mathbf{u} = \mathbf{0}\) then at least one of \(c\) and \(\mathbf{v}\) must be zero. Moreover, if exactly one of \(\mathbf{u}\) and \(\mathbf{v}\) is \(\mathbf{0}\) (while the other is non-zero) then exactly one of (1) and (2) is true (with the other being false).

The vectors \(\mathbf{u}\) and \(\mathbf{v}\) are linearly independent if and only if \(\mathbf{u}\) is not a scalar multiple of \(\mathbf{v}\) and \(\mathbf{v}\) is not a scalar multiple of \(\mathbf{u}\).

Three vectors: Consider the set of vectors \(\mathbf{v}_1 = (1, 1),\) \(\mathbf{v}_2 = (-3, 2),\) and \(\mathbf{v}_3 = (2, 4),\) then the condition for linear dependence seeks a set of non-zero scalars, such that

\(a_1 \begin{bmatrix} 1\\1\end{bmatrix} + a_2 \begin{bmatrix} -3\\2\end{bmatrix} + a_3 \begin{bmatrix} 2\\4\end{bmatrix} =\begin{bmatrix} 0\\0\end{bmatrix},\)

\(\begin{bmatrix} 1 & -3 & 2 \\ 1 & 2 & 4 \end{bmatrix}\begin{bmatrix} a_1\\ a_2 \\ a_3 \end{bmatrix}= \begin{bmatrix} 0\\0\end{bmatrix}.\)

Row reduce this matrix equation by subtracting the first row from the second to obtain,

\(\begin{bmatrix} 1 & -3 & 2 \\ 0 & 5 & 2 \end{bmatrix}\begin{bmatrix} a_1\\ a_2 \\ a_3 \end{bmatrix}= \begin{bmatrix} 0\\0\end{bmatrix}.\)

Continue the row reduction by (i) dividing the second row by 5, and then (ii) multiplying by 3 and adding to the first row, that is

\(\begin{bmatrix} 1 & 0 & 16/5 \\ 0 & 1 & 2/5 \end{bmatrix}\begin{bmatrix} a_1\\ a_2 \\ a_3 \end{bmatrix}= \begin{bmatrix} 0\\0\end{bmatrix}.\)

Rearranging this equation allows us to obtain

\(\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} a_1\\ a_2 \end{bmatrix}= \begin{bmatrix} a_1\\ a_2 \end{bmatrix}=-a_3\begin{bmatrix} 16/5\\2/5\end{bmatrix}.\)

which shows that non-zero a_i exist such that \(\mathbf{v}_3 = (2, 4)\) can be defined in terms of \(\mathbf{v}_1 = (1, 1)\) and \(\mathbf{v}_2 = (-3, 2).\) Thus, the three vectors are linearly dependent.

Two vectors: Now consider the linear dependence of the two vectors \(\mathbf{v}_1 = (1, 1)\) and \(\mathbf{v}_2 = (-3, 2),\) and check,

\(a_1 \begin{bmatrix} 1\\1\end{bmatrix} + a_2 \begin{bmatrix} -3\\2\end{bmatrix} =\begin{bmatrix} 0\\0\end{bmatrix},\)

\(\begin{bmatrix} 1 & -3 \\ 1 & 2 \end{bmatrix}\begin{bmatrix} a_1\\ a_2 \end{bmatrix}= \begin{bmatrix} 0\\0\end{bmatrix}.\)

\(\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} a_1\\ a_2 \end{bmatrix}= \begin{bmatrix} 0\\0\end{bmatrix}.\)

Condensed: the full section is in Wikipedia.

In order to determine if the three vectors in \(\mathbb{R}^4,\)

\(\mathbf{v}_1= \begin{bmatrix}1\\4\\2\\-3\end{bmatrix}, \mathbf{v}_2=\begin{bmatrix}7\\10\\-4\\-1\end{bmatrix}, \mathbf{v}_3=\begin{bmatrix}-2\\1\\5\\-4\end{bmatrix}.\)

are linearly dependent, form the matrix equation,

\(\begin{bmatrix}1&7&-2\\4& 10& 1\\2&-4&5\\-3&-1&-4\end{bmatrix}\begin{bmatrix} a_1\\ a_2 \\ a_3 \end{bmatrix} = \begin{bmatrix}0\\0\\0\\0\end{bmatrix}.\)

Row reduce this equation to obtain,

\(\begin{bmatrix} 1& 7 & -2 \\ 0& -18& 9\\ 0 & 0 & 0\\ 0& 0& 0\end{bmatrix} \begin{bmatrix} a_1\\ a_2 \\ a_3 \end{bmatrix} = \begin{bmatrix}0\\0\\0\\0\end{bmatrix}.\)

Rearrange to solve for v₃ and obtain,

\(\begin{bmatrix} 1& 7 \\ 0& -18 \end{bmatrix} \begin{bmatrix} a_1\\ a_2 \end{bmatrix} = -a_3\begin{bmatrix}-2\\9\end{bmatrix}.\)

This equation is easily solved to define non-zero a_i,

\(a_1 = -3 a_3 /2, a_2 = a_3/2,\)

where \(a_3\) can be chosen arbitrarily. Thus, the vectors \(\mathbf{v}_1, \mathbf{v}_2,\) and \(\mathbf{v}_3\) are linearly dependent.

An alternative method relies on the fact that \(n\) vectors in \(\mathbb{R}^n\) are linearly independent if and only if the determinant of the matrix formed by taking the vectors as its columns is non-zero.

In this case, the matrix formed by the vectors is

\(A = \begin{bmatrix}1&-3\\1&2\end{bmatrix} .\)

We may write a linear combination of the columns as

\(A \Lambda = \begin{bmatrix}1&-3\\1&2\end{bmatrix} \begin{bmatrix}\lambda_1 \\ \lambda_2 \end{bmatrix} .\)

We are interested in whether AΛ = 0 for some nonzero vector Λ. This depends on the determinant of \(A\), which is

\(\det A = 1\cdot2 - 1\cdot(-3) = 5 \ne 0.\)

Since the determinant is non-zero, the vectors \((1, 1)\) and \((-3, 2)\) are linearly independent.

Otherwise, suppose we have \(m\) vectors of \(n\) coordinates, with m < n.\) Then A is an n×m matrix and Λ is a column vector with \(m\) entries, and we are again interested in AΛ = 0. As we saw previously, this is equivalent to a list of \(n\) equations. Consider the first \(m\) rows of \(A\), the first \(m\) equations; any solution of the full list of equations must also be true of the reduced list. In fact, if ⟨i₁,...,i_m⟩ is any list of \(m\) rows, then the equation must be true for those rows.

\(A_{\lang i_1,\dots,i_m \rang} \Lambda = \mathbf{0} .\)

Furthermore, the reverse is true. That is, we can test whether the \(m\) vectors are linearly dependent by testing whether

\(\det A_{\lang i_1,\dots,i_m \rang} = 0\)

Condensed: the full section is in Wikipedia.

If there are more vectors than dimensions, the vectors are linearly dependent. This is illustrated in the example above of three vectors in \(\R^2.\)

Let \(V = \R^n\) and consider the following elements in \(V\), known as the natural basis vectors:

\(\begin{matrix} \mathbf{e}_1 & = & (1,0,0,\ldots,0) \\ \mathbf{e}_2 & = & (0,1,0,\ldots,0) \\ & \vdots \\ \mathbf{e}_n & = & (0,0,0,\ldots,1).\end{matrix}\)

Then \(\mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_n\) are linearly independent.

Suppose that \(a_1, a_2, \ldots, a_n\) are real numbers such that

\(a_1 \mathbf{e}_1 + a_2 \mathbf{e}_2 + \cdots + a_n \mathbf{e}_n = \mathbf{0}.\)

Since

\(a_1 \mathbf{e}_1 + a_2 \mathbf{e}_2 + \cdots + a_n \mathbf{e}_n = \left( a_1 ,a_2 ,\ldots, a_n \right),\)

then \(a_i = 0\) for all \(i = 1, \ldots, n.\)

Let \(V\) be the vector space of all differentiable functions of a real variable \(t\). Then the functions \(e^t\) and \(e^{2t}\) in \(V\) are linearly independent.