6.4 Linear dependence and independence

Motivation

In chapter 6 we started from span: a list of vectors tells us which vectors can be built by linear combination. The next structural question is whether every vector in that list is genuinely needed.

If one vector is already generated by the others, then the list has redundancy. A redundant list may still span the same space, but it is not minimal. Linear dependence and linear independence provide the exact language for this redundancy question, and they are the bridge to basis and dimension in later sections.

Practical reasons this section matters:

in solving $Ax=b$ , dependence explains why free variables appear;
in modeling, dependence identifies repeated features that do not add new information;
in theory, dependence is the criterion that separates arbitrary spanning sets from candidate bases.

Read and try

Test one set for dependence

The live checker compares small vector sets and explains whether a nontrivial linear relation exists.

Verdict

Independent

The only way to solve c1e1 + c2e2 = 0 is c1 = c2 = 0, so this pair is linearly independent.

Key relation

No nontrivial linear relation appears.

Definitions

Definition

Linear independence of a finite list

Let $V$ be a vector space over a field $F$ . A 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

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.

Definition

Trivial relation and nontrivial relation

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

Theorem/Proposition

Theorem

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:

The list is linearly dependent.
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.

Theorem

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.

Proof sketch or proof idea

Proof

Proof idea for the redundancy criterion

Proof

Proof idea for the row-reduction criterion

Worked examples

Worked example

A dependent list in $R^3$

Take

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

Because $u_3=u_1+u_2$ , we immediately get

u_1+u_2-u_3=0,

which is nontrivial. Hence the list is dependent.

Worked example

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

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.

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.

Matrix criterion and pivot criterion

Suppose we place $u_1,\dots,u_n$ as columns of a matrix

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

Then a relation

\alpha_1 u_1 + \cdots + \alpha_n u_n = 0

is exactly the same as solving

A\alpha = 0,\quad \alpha = (\alpha_1,\dots,\alpha_n)^T.

So linear independence means the homogeneous system has only the trivial solution.

Theorem

Equivalent matrix test for independence

The vectors $u_1,\dots,u_n$ are linearly independent if and only if the matrix $A=[u_1\ \cdots\ u_n]$ has a pivot in every column (equivalently, no free variable in $A\alpha=0$ ).

This gives a complete algorithm.

Put the vectors into a column matrix $A=[u_1\ \cdots\ u_n]$ .
Solve the homogeneous system $A\alpha=0$ .
If there is a free variable, choose a nonzero value for it and read a nontrivial relation.
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.

Worked example

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.

Common mistakes

Common mistake

Forgetting that order does not matter for dependence

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

Working checklist

Independence means uniqueness of the zero-coefficient representation of 0.
Dependence means at least one vector is generated by the others.
For column vectors, row reduction gives an algorithmic criterion through pivots and free variables.
This section is the structural prerequisite for basis and dimension.

Warm-up exercises

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.

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.

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.

Warm-up solutions

Solution

Exercise 1

Solution

Exercise 2

Solution

Exercise 3

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

Exercises

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

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

Dependence means redundancy

Theorem

Equivalent redundancy test

A list of vectors is linearly dependent if and only if one vector in the list can be written as a linear combination of the others.

Proof

Why dependence and redundancy are the same

Worked example

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

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

Common mistake

Dependent does not mean the span gets smaller

A dependent list can still span a whole space. Dependence only says that at least one vector is unnecessary for generating the span.

Column-matrix criterion and null-space viewpoint

Put the vectors into a matrix

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

Then the relation

\alpha_1u_1+\cdots+\alpha_nu_n=0

is exactly the homogeneous system $A\alpha=0$ , where $\alpha=(\alpha_1,\ldots,\alpha_n)^T$ .

Theorem

Matrix test for dependence

The vectors $u_1,\dots,u_n$ are linearly independent if and only if the homogeneous system $A\alpha=0$ has only the trivial solution. Equivalently, the null space N(A) contains only 0.

Proof

Why the homogeneous system controls dependence

Worked example

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$ .

Theorem

Pivot criterion

After row reducing $A$ , the list $u_1,\dots,u_n$ is linearly independent if and only if every column is a pivot column. If one column is not a pivot column, then there is a free variable in $A\alpha=0$ , so a nontrivial relation exists.

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.

Fast low-dimensional tests

Theorem

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

For a pair {u,v} with both vectors nonzero, the set is linearly independent if and only if one vector is not a scalar multiple of the other.

Proof

Why two vectors reduce to a scalar-multiple test

Worked example

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

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

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

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$

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.

Quick checks

Quick check

Is any list containing the zero vector automatically dependent?

Test the definition directly.

Solution

Answer

Quick check

If $u_3 = u_1 + u_2$ , does $\{u_1,u_2,u_3\}$ remain independent?

Write the relation in the standard form $\alpha_1u_1+\alpha_2u_2+\alpha_3u_3=0$ .

Solution

Answer

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

Guided exercises

Quick check

Decide whether `\{(1,1,0),(0,1,1),(1,2,1)\}` is independent, and if not, write one dependence relation.

Set the vectors as columns and look for a free variable after row reduction.

Solution

Guided 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

Quick check

If one vector in a list is redundant, what should you try next?

Use the redundancy viewpoint from this page.

Solution

Guided solution

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.

6.4 Linear dependence and independence

MATH1030: Linear algebra I

Motivation

Test one set for dependence

Definitions

Linear independence of a finite list

Linear dependence of a finite list

Trivial relation and nontrivial relation

Theorem/Proposition

Dependence is equivalent to one vector being generated by the others

Row-reduction test for dependence in RmR^mRm

Proof sketch or proof idea

Proof idea for the redundancy criterion

Proof idea for the row-reduction criterion

Worked examples

A dependent list in R3R^3R3

Independence test by RREF

Why a list containing the zero vector is dependent

Common mistakes

Confusing dependence with not spanning

Matrix criterion and pivot criterion

Equivalent matrix test for independence

Use row reduction to test independence

Common mistakes

Forgetting that order does not matter for dependence

Working checklist

Warm-up exercises

Decide whether (1,0,0),(0,1,0),(1,1,0) in R3R^3R3 is independent.

Let S={(1,1),(2,2)}S=\{(1,1),(2,2)\}S={(1,1),(2,2)} in R2R^2R2. Is SSS independent?

If {u1,u2,u3}\{u_1,u_2,u_3\}{u1​,u2​,u3​} is independent, can {u1,u2,u3,u1+u2}\{u_1,u_2,u_3,u_1+u_2\}{u1​,u2​,u3​,u1​+u2​} be independent?

Warm-up solutions

Exercise 1

Exercise 2

Exercise 3

If a set has 5 vectors in R3R^3R3, can it be linearly independent?

Answer

Exercises

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

Guided solution

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

Guided solution

Dependence means redundancy

Equivalent redundancy test

Why dependence and redundancy are the same

A redundant vector can be removed without changing the span

A redundant vector can be removed without changing the span

Why the span stays the same

Dependent does not mean the span gets smaller

Column-matrix criterion and null-space viewpoint

Matrix test for dependence

Why the homogeneous system controls dependence

Read a dependence relation from row reduction

Pivot criterion

Row reduction is allowed because it preserves the homogeneous solution set

Fast low-dimensional tests

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

Why two vectors reduce to a scalar-multiple test

Two vectors in R2R^2R2

Three vectors in R2R^2R2 must be dependent

Three vectors in R3R^3R3 that lie in one plane

Too many vectors in RmR^mRm force dependence

Why more than m vectors cannot be independent in RmR^mRm

Summary

Quick checks

Is any list containing the zero vector automatically dependent?

Answer

If u3=u1+u2u_3 = u_1 + u_2u3​=u1​+u2​, does {u1,u2,u3}\{u_1,u_2,u_3\}{u1​,u2​,u3​} remain independent?

Answer

If a 4×44\times 44×4 matrix has four pivot columns, what does that say about its columns?

Answer

Guided exercises

Decide whether \{(1,1,0),(0,1,1),(1,2,1)\} is independent, and if not, write one dependence relation.

Guided solution

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

Guided solution

If one vector in a list is redundant, what should you try next?

Guided solution

Read this first

Section mastery checkpoint

Prerequisites

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

A dependent list in $R^3$

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

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

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

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

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

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

Two vectors in $R^2$

Three vectors in $R^2$ must be dependent

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

Too many vectors in $R^m$ force dependence

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

If $u_3 = u_1 + u_2$ , does $\{u_1,u_2,u_3\}$ remain independent?

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

Decide whether `\{(1,1,0),(0,1,1),(1,2,1)\}` is independent, and if not, write one dependence relation.