6.4 Linear dependence and independence

Motivation

A spanning list tells us which vectors can be generated. It may contain redundancy: one member can be a linear combination of the others, so deleting that member leaves the span unchanged. Linear dependence detects exactly this possibility.

Definitions

Definition 6.4.1

(Linear independence of a finite list)

Let $V$ be a real vector space. A finite list $(u_1,u_2,\ldots,u_n)$ in $V$ is linearly independent if

$$\alpha_1u_1+\alpha_2u_2+\cdots+\alpha_nu_n=0$$

implies $\alpha_1=\alpha_2=\cdots=\alpha_n=0$.

Definition 6.4.2

(Linear dependence of a finite list)

The same list is linearly dependent if there exists a nontrivial choice of scalars (not all zero) with

$$\alpha_1u_1+\alpha_2u_2+\cdots+\alpha_nu_n=0.$$

The equation with all coefficients zero is the trivial relation. Any other relation is nontrivial. Independence means only the trivial relation exists.

Which vector can be removed?

Theorem 6.4.3

(Dependence is equivalent to one vector being generated by the others)

For a finite list $(u_1,\ldots,u_n)$ with $n\ge 2$, the following are equivalent:

1. The list is linearly dependent.
2. At least one vector in the list is a linear combination of the remaining vectors.

So a dependent list always contains a removable vector that does not change the span.

Proof

(Proof of the redundancy criterion)

$(1) \Rightarrow (2)$: start from a nontrivial relation $\sum\limits_{i=1}^n\alpha_i u_i=0$. Choose an index $k$ with $\alpha_k\ne 0$. Rearrange:

$$u_k=-\sum_{i\ne k}\frac{\alpha_i}{\alpha_k}u_i,$$

so $u_k$ is generated by the remaining vectors.

$(2) \Rightarrow (1)$: if $u_k=\sum\limits_{i\ne k}\beta_i u_i$, move all terms to one side. You obtain a nontrivial relation, hence dependence.

The key logic: dependence is exactly the existence of at least one solvable elimination step inside the list.

Proof X-ray

A relation identifies which vectors can be removed

A nontrivial relation means at least one coefficient is nonzero, not that every coefficient is nonzero. The redundancy proof may divide only by a coefficient known to be nonzero. Thus a particular relation identifies removable vectors at its nonzero positions; it does not license deleting an arbitrary vector.

For example, the list $(e_1,e_2,2e_1)$ in $\mathbb R^2$ satisfies $-2e_1+0e_2+1(2e_1)=0$. Either the first or the third vector can be recovered from the other two. Removing $e_2$, however, leaves only multiples of $e_1$ and loses the vector $e_2$ from the span. The zero coefficient on $e_2$ supplies no formula for recovering it. This is why the proof selects an index with nonzero coefficient before rearranging.

Worked example 6.4.4

(A redundant vector can be removed without changing the span)

Let

$$u_1 = \begin{bmatrix}1\\2\\1\end{bmatrix},\qquad u_2 = \begin{bmatrix}0\\1\\1\end{bmatrix},\qquad u_3 = \begin{bmatrix}1\\3\\2\end{bmatrix}.$$

Here $u_3 = u_1 + u_2$. So every vector of the form

$$a u_1 + b u_2 + c u_3$$

can be rewritten as

$$(a+c)u_1 + (b+c)u_2.$$

Therefore

$$\operatorname{Span}\{u_1,u_2,u_3\} = \operatorname{Span}\{u_1,u_2\}.$$

The third vector changes the description, but not the span itself.

Theorem 6.4.5

(A redundant vector can be removed without changing the span)

If one vector in a list is a linear combination of the others, then deleting it does not change the span of the list.

Proof

(Why the span stays the same)

One inclusion is automatic: the shorter list is a subset of the longer list, so its span is contained in the larger span.

For the other inclusion, replace the redundant vector by the combination of the remaining vectors and collect like terms. Every linear combination of the longer list becomes a linear combination of the shorter one.

Counterexample mode

Spanning does not guarantee independence

False claim. A list that spans the whole ambient space must be linearly independent.

Reconsider $(e_1,e_2,2e_1)$ in $\mathbb R^2$. Every $(a,b)^T$ equals $ae_1+be_2+0(2e_1)$, so the list spans all of $\mathbb R^2$. Nevertheless $-2e_1+0e_2+1(2e_1)=0$ is a nontrivial relation. Thus spanning supplies existence of representations, while independence requires uniqueness; existence alone does not supply uniqueness.

Repair. To obtain a basis, require both spanning and independence. Here delete $2e_1$. The remaining $(e_1,e_2)$ still spans, and $ae_1+be_2=0$ forces $a=b=0$ by coordinates. The repair removes redundancy without losing any output.

From a relation to a homogeneous system

The unknowns will be coefficients. A nonzero solution will record a nontrivial relation among the original generators; the pivot test makes this observation computational.

Theorem 6.4.6

(Row-reduction test for dependence in $R^m$)

Let $u_1,\ldots,u_n\in R^m$ and build

$$A=[u_1\ u_2\ \cdots\ u_n].$$

Then $u_1,\ldots,u_n$ are linearly independent iff the homogeneous system

$$Ax=0$$

has only the zero solution. Equivalently, when reducing $A$ to RREF, every column must be a pivot column.

Equivalently, the null space of this column matrix is $N(A)=\{0\}$.

Proof

(Proof of the row-reduction criterion)

By definition, dependence asks whether $\alpha_1u_1+\cdots+\alpha_nu_n=0$ has a nonzero coefficient vector. Writing coefficients as $x=(\alpha_1,\ldots,\alpha_n)^T$, this is exactly $Ax=0$ where columns are the vectors. Elementary row operations preserve the solution set of a homogeneous system, so the question is unchanged in RREF. A free variable gives a nonzero solution and therefore dependence; no free variables give only the zero solution and therefore independence.

This gives a complete algorithm.

1. Put the vectors into a column matrix $A=[u_1\ \cdots\ u_n]$.
2. Solve the homogeneous system $A\alpha=0$.
3. If there is a free variable, choose a nonzero value for it and read a nontrivial relation.
4. If every column is a pivot column, only the trivial solution exists and the vectors are independent.

A useful shortcut also falls out immediately: more than $m$ vectors in $R^m$ must be dependent, because an $m \times n$ matrix with $n>m$ cannot have a pivot in every column.

Common mistake

(Row reduction is allowed because it preserves the homogeneous solution set)

When you row reduce $A$ for independence testing, you are not changing the columns themselves into new vectors you want to study. You are simplifying the equation $A\alpha=0$. Row-equivalent matrices have the same homogeneous solutions, so they have the same dependence relations.

Read the relation, then check an independent list

Worked example 6.4.7

(Read a dependence relation from row reduction)

Take

$$A= \begin{bmatrix} 1 & 0 & 1\\ 2 & 1 & 3\\ 1 & 1 & 2 \end{bmatrix},$$

whose columns are $u_1=(1,2,1)^T$, $u_2=(0,1,1)^T$, and $u_3=(1,3,2)^T$. Row reduction gives

$$\begin{bmatrix} 1 & 0 & 1\\ 2 & 1 & 3\\ 1 & 1 & 2 \end{bmatrix} \xrightarrow{R_2-2R_1,\ R_3-R_1} \begin{bmatrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 0 & 1 & 1 \end{bmatrix} \xrightarrow{R_3-R_2} \begin{bmatrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 0 & 0 & 0 \end{bmatrix}.$$

The third column is not a pivot column, so $\alpha_3$ is free in $A\alpha=0$. Set $\alpha_3=1$. Then the reduced system gives $\alpha_1=-1$ and $\alpha_2=-1$, so

$$-u_1-u_2+u_3=0,$$

or equivalently $u_3=u_1+u_2$.

Worked example 6.4.8

(Independence test by RREF)

Let

$$u_1=(1,2,0),\quad u_2=(0,1,1),\quad u_3=(2,5,1).$$

Set $A=[u_1\ u_2\ u_3]$:

$$A=\begin{bmatrix} 1&0&2\\ 2&1&5\\ 0&1&1 \end{bmatrix} \xrightarrow{R_2-2R_1} \begin{bmatrix} 1&0&2\\ 0&1&1\\ 0&1&1 \end{bmatrix} \xrightarrow{R_3-R_2} \begin{bmatrix} 1&0&2\\ 0&1&1\\ 0&0&0 \end{bmatrix}.$$

Column 3 is non-pivot, so $x_3$ is free in $Ax=0$. Therefore the list is dependent.

Worked example 6.4.9

(Use row reduction to test independence)

Let

$$u_1=\begin{bmatrix}1\\2\\1\end{bmatrix},\quad u_2=\begin{bmatrix}2\\4\\3\end{bmatrix},\quad u_3=\begin{bmatrix}1\\1\\0\end{bmatrix}.$$

Set $A=[u_1\ u_2\ u_3]$. Row reduce:

$$\begin{bmatrix} 1 & 2 & 1\\ 2 & 4 & 1\\ 1 & 3 & 0 \end{bmatrix} \xrightarrow{R_2-2R_1,\ R_3-R_1} \begin{bmatrix} 1 & 2 & 1\\ 0 & 0 & -1\\ 0 & 1 & -1 \end{bmatrix} \xrightarrow{R_2\leftrightarrow R_3} \begin{bmatrix} 1 & 2 & 1\\ 0 & 1 & -1\\ 0 & 0 & -1 \end{bmatrix}.$$

There is a pivot in each column, so the three vectors are linearly independent.

Worked example 6.4.10

(Why a list containing the zero vector is dependent)

Suppose $u_2=0$. Then

$$0\cdot u_1+1\cdot u_2+0\cdot u_3+\cdots+0\cdot u_n=0$$

is already a nontrivial relation (coefficient of $u_2$ is $1$). So any list containing $0$ is dependent.

The geometry behind a dependence relation

The following sequence connects the algebraic test to geometry. A third vector inside the span of the first two can be recovered from them, so adding it changes the list without enlarging its span.

After predicting dependence from the algebra, compare the corresponding geometric configurations below.

Fast low-dimensional tests

Theorem 6.4.11

(Two nonzero vectors are independent exactly when neither is a scalar multiple of the other)

For an ordered pair $(u,v)$ with both vectors nonzero, the pair is linearly independent if and only if one vector is not a scalar multiple of the other. The list convention retains both positions even when $u=v$.

Proof

(Why two vectors reduce to a scalar-multiple test)

If $au+bv=0$ is a nontrivial relation, then at least one coefficient is nonzero. If $b\ne 0$, solve for

$$v = -\frac{a}{b}u.$$

If $a\ne 0$, solve for

$$u = -\frac{b}{a}v.$$

Conversely, if $v=\lambda u$, then $\lambda u-v=0$ is a nontrivial relation; the case $u=\lambda v$ is analogous. Thus two vectors are dependent exactly when one is a scalar multiple of the other.

Worked example 6.4.12

(Two vectors in $R^2$)

Let

$$u = \begin{bmatrix}1\\2\end{bmatrix}, \qquad v = \begin{bmatrix}2\\4\end{bmatrix}.$$

Since $v=2u$, the pair is dependent. Geometrically, both vectors point in the same direction.

Worked example 6.4.13

(Three vectors in $R^2$ must be dependent)

If $u_1,u_2,u_3 \in R^2$, then the matrix $A=[u_1\ u_2\ u_3]$ has size $2\times 3$. After row reduction it can have at most two pivots, so one column is not a pivot column. Therefore $A\alpha=0$ has a nontrivial solution and the three vectors are linearly dependent.

Worked example 6.4.14

(Three vectors in $R^3$ that lie in one plane)

If three vectors in $R^3$ all lie in the plane $z=0$, then they all belong to the span of $e_1$ and $e_2$. But that plane is already generated by two independent directions, so a third vector cannot add a new independent direction. The list is dependent.

Theorem 6.4.15

(Too many vectors in $R^m$ force dependence)

Any list of more than $m$ vectors in $R^m$ is linearly dependent.

Proof

(Why more than $m$ vectors cannot be independent in $R^m$)

If $A$ is an $m\times n$ matrix with $n>m$, then row reduction can produce at most $m$ pivot columns. So at least one column is not a pivot column. That means $A\alpha=0$ has a free variable, hence a nontrivial solution. So the columns are dependent.

Common mistakes

Common mistake

(Confusing dependence with not spanning)

Dependent lists can still span a large space. Dependence only says the list is not minimal.

Common mistake

(Forgetting that order does not matter for dependence)

Permuting vectors changes their positions but not whether a nontrivial relation exists.

Summary

• Linear dependence can be read directly from the definition, as redundancy in a spanning list, or as a nonzero vector in the null space of a column matrix.
• Row reduction is used to simplify the coefficient equation $A\alpha=0$; it is not a replacement of the original vectors by new vectors.
• A free variable gives a nontrivial dependence relation, while a pivot in every column proves independence.
• Low-dimensional shortcuts, such as scalar-multiple tests in $R^2$ and the "more than $m$ vectors in $R^m$" rule, are consequences of the same pivot count logic.

Checkpoints: three ways to detect redundancy

Quick check

(Decide whether $(1,0,0),(0,1,0),(1,1,0)$ in $R^3$ is independent.)

Use either the redundancy criterion or the RREF test.

Solution · Exercise 1

Dependent, because $(1,1,0)=(1,0,0)+(0,1,0)$.

Quick check

(Let $S=\{(1,1),(2,2)\}$ in $R^2$. Is $S$ independent?)

Try to write one vector as a scalar multiple of the other.

Solution · Exercise 2

Dependent, because $(2,2)=2(1,1)$.

Quick check

(If $\{u_1,u_2,u_3\}$ is independent, can $\{u_1,u_2,u_3,u_1+u_2\}$ be independent?)

Translate the question into a linear relation.

Solution · Exercise 3

No. $u_1+u_2-(u_1+u_2)=0$ is a nontrivial relation in the larger list.

Exercises

Quick check

(If a set has 5 vectors in $R^3$, can it be linearly independent?)

Use pivots and the number of rows.

Solution · Answer

No. A $3\times 5$ matrix can have at most 3 pivots, so at least two columns are free-variable columns. Therefore a nontrivial relation must exist.

Quick check

(Determine whether $\{(1,0,1),(2,1,3),(0,1,1)\}$ is independent.)

Set them as columns, reduce, and read pivot columns.

Solution · Guided solution

Let $u_1,u_2,u_3$ denote the vectors in the stated order. The answer is dependent. Put them in the columns of $A$:

$$A=\begin{bmatrix}1&2&0\\0&1&1\\1&3&1\end{bmatrix} \sim\begin{bmatrix}1&2&0\\0&1&1\\0&0&0\end{bmatrix} \sim\begin{bmatrix}1&0&-2\\0&1&1\\0&0&0\end{bmatrix}.$$

The first stage subtracts row $1$ and row $2$ from row $3$; the second subtracts twice row $2$ from row $1$. Only columns $1$ and $2$ are pivot columns. Setting the free coefficient $\alpha_3=1$ gives $\alpha_1=2$ and $\alpha_2=-1$. Direct verification confirms

$$2(1,0,1)-(2,1,3)+(0,1,1)=(0,0,0).$$

The coefficient vector $(2,-1,1)$ is nonzero, so this is a nontrivial relation. Equivalently, $u_2=2u_1+u_3$.

Quick check

(Show that $\{(1,2,3),(2,4,6),(1,0,1)\}$ is dependent by writing one vector from others.)

Look for a direct scalar-multiple relation first.

Solution · Guided solution

$(2,4,6)=2(1,2,3)$, so $2(1,2,3)-(2,4,6)+0(1,0,1)=0$ is nontrivial. The set is dependent.

Quick check

(Is any list containing the zero vector automatically dependent?)

Test the definition directly.

Solution · Answer

Yes. Put coefficient $1$ on the zero vector and $0$ on every other vector. That already gives a nontrivial relation.

Quick check

(If a $4\times 4$ matrix has four pivot columns, what does that say about its columns?)

Use the matrix test.

Solution · Answer

The columns are linearly independent, because $A\alpha=0$ has only the trivial solution.

Quick check

(Explain why any subset of a linearly independent set is linearly independent.)

Think about what would happen if the subset had its own relation.

Solution · Guided solution

If a subset had a nontrivial relation, that same relation would also be a relation among the larger set after giving coefficient $0$ to the vectors that were not used. That would make the larger set dependent. So a subset of an independent set must also be independent.

Quick check

(A list satisfies $2u_1-u_2+0u_3=0$. Which vectors can this relation justify deleting without changing the span?)

Identify the nonzero coefficients; do not assume every vector is removable.

Solution · Guided solution

The relation gives $u_2=2u_1$ and $u_1=\tfrac12u_2$, so either $u_1$ or $u_2$ can be deleted. It gives no expression for $u_3$. For example, if $u_1=e_1$, $u_2=2e_1$ and $u_3=e_2$, deleting $u_3$ changes the span from the plane to a line.

Read this first

This section builds directly on 6.3 Linear combinations and span and the row-reduction workflow in 2.3 Gaussian elimination and RREF.

Independence removes redundancy; it does not guarantee that every target is reachable. In 6.5 Basis and dimension, we require independence and spanning together, then prove that the size of such a list is a property of the space.