Linear Independence, linear algebra I lesson

Take the vectors $(1, 0, 1)$ , $(0, 1, 1)$ and $(1, 1, 2)$ . The weights $2, 1, 0$ and the weights $1, 0, 1$ build the same vector $(2, 1, 3)$ , even though no two of the three vectors are parallel. Two different recipes for one result mean that some vector in the list adds nothing new. Linear independence is the condition that rules this out, and this lesson shows how to test it by elimination and why it is exactly what makes coefficients unique.

Key terms

Linearly independent list

Definition Tuples such as $(1, 0, 1)$ stand for column vectors. Let $\mathbf{v}_1, \dots, \mathbf{v}_k$ be a list of vectors in $\mathbb{R}^n$ . The combination $0\mathbf{v}_1 + \cdots + 0\mathbf{v}_k$ , with every coefficient zero, is the trivial combination, and it always equals $\mathbf{0}$ . A combination with at least one nonzero coefficient is nontrivial. The list is linearly independent if the trivial combination is the only one that equals $\mathbf{0}$ , that is,

\begin{aligned} &c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k = \mathbf{0} \\[0.4em] &\quad \implies c_1 = c_2 = \cdots = c_k = 0. \end{aligned}

Independence is a property of the whole list. It says nothing about lengths, angles or coordinate axes, and the same definition is used in any vector space.

In plain words The only way to combine the vectors of an independent list into zero is to give every one of them the weight zero.

Example For the pair $(1, 0, 1)$ and $(0, 1, 1)$ ,

\begin{aligned} &a(1, 0, 1) + b(0, 1, 1) \\[0.4em] &\quad = (a,\ b,\ a + b). \end{aligned}

If this equals $\mathbf{0}$ , the first entry gives $a = 0$ and the second gives $b = 0$ . Only the trivial combination gives zero, so the pair is independent. The argument covers every real $a$ and $b$ at once, which is what a proof of independence needs.

Linearly dependent list

Definition A list $\mathbf{v}_1, \dots, \mathbf{v}_k$ in $\mathbb{R}^n$ is linearly dependent if it is not linearly independent, that is, if there are scalars $c_1, \dots, c_k$ , not all zero, with

c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k = \mathbf{0}.

A few facts follow at once. A list that contains $\mathbf{0}$ is dependent, since the coefficient $1$ on $\mathbf{0}$ and $0$ on every other vector is nontrivial. A list in which the same vector appears twice is dependent, with coefficients $1$ and $-1$ on the two copies. A single vector is independent exactly when it is not $\mathbf{0}$ , and two vectors are dependent exactly when one of them is a scalar multiple of the other.

In plain words Dependent means zero can be built from the list in a nontrivial way. For two vectors that just means one is a multiple of the other, but with three or more vectors the relation can involve all of them at once.

Example Let $\mathbf{w}_1 = (1, 0, 1)$ , $\mathbf{w}_2 = (0, 1, 1)$ and $\mathbf{w}_3 = (1, 1, 2)$ . No two of them are parallel, yet

\mathbf{w}_1 + \mathbf{w}_2 - \mathbf{w}_3 = \mathbf{0},

so the list is dependent. Checking the vectors two at a time would miss this.

Dependence relation

Definition A dependence relation for a list $\mathbf{v}_1, \dots, \mathbf{v}_k$ is an equation $c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k = \mathbf{0}$ whose coefficients are not all zero. One such relation proves that the list is dependent. If a relation has $c_j \ne 0$ , it can be solved for $\mathbf{v}_j$ ,

\mathbf{v}_j = -\frac{1}{c_j} \sum_{i \ne j} c_i \mathbf{v}_i,

so $\mathbf{v}_j$ lies in the span of the other vectors, and removing $\mathbf{v}_j$ from the list does not change its span. Conversely, if some $\mathbf{v}_j$ is a combination of the others, moving it to the other side gives a relation with coefficient $-1$ on $\mathbf{v}_j$ . So a list of two or more vectors is dependent exactly when one of its vectors is a linear combination of the others. A relation gives no permission to remove a vector whose coefficient in it is zero.

In plain words A relation points to the redundant vectors. Any one vector with a nonzero coefficient can be rebuilt from the rest and dropped without shrinking the span.

Example In $\mathbb{R}^2$ the list $\mathbf{e}_1$ , $2\mathbf{e}_1$ , $\mathbf{e}_2$ satisfies

-2\,\mathbf{e}_1 + 1\,(2\mathbf{e}_1) + 0\,\mathbf{e}_2 = \mathbf{0}.

Either horizontal vector may be removed, and the remaining pair still spans $\mathbb{R}^2$ . The relation does not allow removing $\mathbf{e}_2$ , whose coefficient is $0$ , and indeed $\mathbf{e}_1$ and $2\mathbf{e}_1$ alone span only the $x$ -axis.

Uniqueness of coefficients

Definition A list $\mathbf{v}_1, \dots, \mathbf{v}_k$ in $\mathbb{R}^n$ is linearly independent if and only if every vector in $\operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_k\}$ is a linear combination of the list in exactly one way. If the list is independent and

\sum_{i=1}^{k} a_i \mathbf{v}_i = \sum_{i=1}^{k} b_i \mathbf{v}_i,

then subtracting gives

\sum_{i=1}^{k} (a_i - b_i)\,\mathbf{v}_i = \mathbf{0},

so every $a_i - b_i$ is $0$ . Conversely, a nontrivial relation would be a second way to write $\mathbf{0}$ , next to the trivial combination. The statement is about vectors inside the span. An independent list need not span all of $\mathbb{R}^n$ , and a vector outside its span has no representation at all.

In plain words Independence means no two different weight settings give the same vector. Every vector the list can reach, it reaches with exactly one set of weights.

Example For the dependent list $\mathbf{w}_1, \mathbf{w}_2, \mathbf{w}_3$ above, the vector $(2, 1, 3)$ has infinitely many representations,

\begin{aligned} &(2 - t)\,\mathbf{w}_1 + (1 - t)\,\mathbf{w}_2 + t\,\mathbf{w}_3 \\[0.4em] &\quad = (2, 1, 3) \end{aligned}

for every real $t$ . These weights are $2, 1, 0$ plus $t$ times the coefficients of the relation $-\mathbf{w}_1 - \mathbf{w}_2 + \mathbf{w}_3 = \mathbf{0}$ , and adding a multiple of that relation adds only $\mathbf{0}$ . The independent pair $\mathbf{w}_1, \mathbf{w}_2$ reaches $(2, 1, 3)$ only as $2\mathbf{w}_1 + \mathbf{w}_2$ . It cannot reach $(1, 1, 1)$ at all, since every combination $(a, b, a + b)$ has third entry equal to the sum of the first two.

Independence test by elimination

Definition To test vectors $\mathbf{v}_1, \dots, \mathbf{v}_k$ in $\mathbb{R}^n$ , place them as the columns of the $n \times k$ matrix $V = [\mathbf{v}_1 \ \cdots \ \mathbf{v}_k]$ and solve the homogeneous system $V\mathbf{c} = \mathbf{0}$ for the coefficient vector $\mathbf{c} = (c_1, \dots, c_k)$ . Row reduce $V$ to an echelon form. The zero right-hand side stays zero, so it can be left out. The list is independent exactly when every column of the echelon form has a pivot. If some column has no pivot, its variable is free, and setting that free variable to $1$ and any other free variables to $0$ gives a dependence relation. An $n \times k$ matrix has at most $n$ pivots, so any list of more than $n$ vectors in $\mathbb{R}^n$ is dependent.

In plain words The unknowns are the weights. A pivot in every column forces every weight to be zero, while a free weight gives a nontrivial recipe for zero.

Example Test $\mathbf{p} = (1, 1, 0)$ , $\mathbf{q} = (0, 1, 1)$ and $\mathbf{r} = (1, 0, 1)$ .

\begin{aligned} V &= \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \\[0.4em] &\xrightarrow{R_2 \to R_2 - R_1} \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \\ 0 & 1 & 1 \end{bmatrix} \\[0.4em] &\xrightarrow{R_3 \to R_3 - R_2} \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \\ 0 & 0 & 2 \end{bmatrix} \end{aligned}

Every column has a pivot. Back substitution gives $2c_3 = 0$ , then $c_2 = c_3 = 0$ , then $c_1 = -c_3 = 0$ , so the list is independent. For $\mathbf{w}_1, \mathbf{w}_2, \mathbf{w}_3$ the steps $R_3 \to R_3 - R_1$ and $R_3 \to R_3 - R_2$ produce a zero row instead. The third column has no pivot, $c_3 = t$ is free, and $c_1 = c_2 = -t$ . With $t = 1$ this is the relation $-\mathbf{w}_1 - \mathbf{w}_2 + \mathbf{w}_3 = \mathbf{0}$ .

Check yourself

Are the vectors $(2, -1)$ and $(-6, 3)$ linearly independent? If not, give a dependence relation.

Show the answer

No. The second vector is $-3$ times the first, so

3\,(2, -1) + 1\,(-6, 3) = (0, 0)

is a dependence relation. Two vectors are dependent exactly when one is a multiple of the other.

No two of the vectors $(1, 2, 3)$ , $(4, 5, 6)$ and $(7, 8, 9)$ are parallel. Use elimination to decide whether the list is independent, and give a dependence relation if it is not.

Show the answer

Put the vectors in the columns of $V$ and reduce.

\begin{aligned} V &= \begin{bmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{bmatrix} \\[0.4em] &\xrightarrow{R_2 \to R_2 - 2R_1} \begin{bmatrix} 1 & 4 & 7 \\ 0 & -3 & -6 \\ 3 & 6 & 9 \end{bmatrix} \\[0.4em] &\xrightarrow{R_3 \to R_3 - 3R_1} \begin{bmatrix} 1 & 4 & 7 \\ 0 & -3 & -6 \\ 0 & -6 & -12 \end{bmatrix} \\[0.4em] &\xrightarrow{R_3 \to R_3 - 2R_2} \begin{bmatrix} 1 & 4 & 7 \\ 0 & -3 & -6 \\ 0 & 0 & 0 \end{bmatrix} \end{aligned}

The third column has no pivot, so the list is dependent even though no two vectors are parallel. Set $c_3 = t$ . The second row gives $-3c_2 - 6t = 0$ , so $c_2 = -2t$ , and the first gives $c_1 = -4c_2 - 7c_3 = t$ . With $t = 1$ ,

\begin{aligned} &(1, 2, 3) - 2\,(4, 5, 6) + (7, 8, 9) \\[0.4em] &\quad = (0, 0, 0). \end{aligned}

For which real numbers $k$ is the list $(1, 0, 1)$ , $(0, 1, 1)$ , $(1, 1, k)$ linearly independent?

Show the answer

Reduce the matrix with these columns.

\begin{aligned} &\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & k \end{bmatrix} \\[0.4em] &\xrightarrow{R_3 \to R_3 - R_1} \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & k - 1 \end{bmatrix} \\[0.4em] &\xrightarrow{R_3 \to R_3 - R_2} \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & k - 2 \end{bmatrix} \end{aligned}

The third column has a pivot exactly when $k - 2 \ne 0$ . So the list is independent for every $k \ne 2$ . When $k = 2$ the third vector $(1, 1, 2)$ is the sum of the first two, and the list is dependent.

Linear Independence

Key terms

Linearly independent list

Linearly dependent list

Dependence relation

Uniqueness of coefficients

Independence test by elimination

Check yourself

How this lesson connects

Builds on

Used later in