---
title: Linear Independence
module: Linear Equations in Linear Algebra
moduleNumber: 1
lessonNumber: 4
order: 104
summary: >
  A set of vectors is linearly independent when the only linear combination equal
  to zero is the trivial one; otherwise a dependence relation writes one vector in
  terms of the others. For the columns of A the question becomes whether Ax = 0 has
  only the trivial solution — a pivot in every column. Counting pivots settles
  independence, and any set with more vectors than entries is automatically
  dependent.
topics: [Linear Equations in Linear Algebra]
sources:
  - book: Lay
    ref: "Ch. 1 — Linear Equations; §1.7 Linear Independence"
---

A [solution set](/linear-algebra/linear-systems/solution-sets-and-applications)
written as a span uses one spanning vector per free variable. Whether that
spanning set is as small as possible, or carries a redundant vector that some
combination of the others already reaches, is the question of **linear
independence**. Like the questions before it, it reduces to counting pivots in a
homogeneous system.

## The definition

Independence is a property of a _set_ of vectors, phrased through the homogeneous
vector equation they generate.

> **Definition (Linear independence).** An indexed set $\{\mathbf{v}_1, \dots,
> \mathbf{v}_p\}$ in $\mathbb{R}^n$ is **linearly independent** if
> $$
> x_1 \mathbf{v}_1 + x_2 \mathbf{v}_2 + \cdots + x_p \mathbf{v}_p = \mathbf{0}
> $$
> has only the trivial solution $x_1 = \cdots = x_p = 0$. The set is **linearly
> dependent** if there exist weights $c_1, \dots, c_p$, **not all zero**, with
> $$
> c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + c_p \mathbf{v}_p = \mathbf{0}.
> $$
> Such an equation with nonzero weights is a **linear dependence relation**.

The trivial solution always exists; independence says it is the _only_ one.
Dependence says there is a genuine one, a way to combine the vectors to zero
without using all-zero weights.

### Testing by row reduction

Because the test is whether a homogeneous vector equation has a nontrivial
solution, it is a row reduction.

> **Worked example.** Determine whether $\{\mathbf{v}_1, \mathbf{v}_2,
> \mathbf{v}_3\}$ is linearly independent, and if not, find a dependence relation,
> where
>
> $$
> \mathbf{v}_1 = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix},\quad
> \mathbf{v}_2 = \begin{bmatrix} 4 \\ 5 \\ 6 \end{bmatrix},\quad
> \mathbf{v}_3 = \begin{bmatrix} 2 \\ 1 \\ 0 \end{bmatrix}.
> $$
>
> Reduce $[\,\mathbf{v}_1\ \mathbf{v}_2\ \mathbf{v}_3\ \mathbf{0}\,]$. Subtract $2$
> times row 1 from row 2 and $3$ times row 1 from row 3, then clear the $-6$ below
> the second pivot:
>
> $$
> \begin{bmatrix} 1 & 4 & 2 & 0 \\ 2 & 5 & 1 & 0 \\ 3 & 6 & 0 & 0 \end{bmatrix}
> \;\longrightarrow\;
> \begin{bmatrix} 1 & 4 & 2 & 0 \\ 0 & -3 & -3 & 0 \\ 0 & -6 & -6 & 0 \end{bmatrix}
> \;\longrightarrow\;
> \begin{bmatrix} 1 & 4 & 2 & 0 \\ 0 & -3 & -3 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}.
> $$
>
> Column 3 has no pivot, so $x_3$ is free: nontrivial solutions exist and the set
> is **dependent**. Solving fully gives $x_1 = 2x_3$, $x_2 = -x_3$; choosing
> $x_3 = 5$ produces one dependence relation,
>
> $$
> 10\mathbf{v}_1 - 5\mathbf{v}_2 + 5\mathbf{v}_3 = \mathbf{0}.
> $$

The augmented column of zeros never changes under row operations, so in practice
one reduces $A = [\,\mathbf{v}_1\ \cdots\ \mathbf{v}_p\,]$ alone.

> **Fact (Columns of a matrix).** The columns of $A$ are linearly independent if
> and only if $A\mathbf{x} = \mathbf{0}$ has only the trivial solution — that is,
> if and only if every column of $A$ is a pivot column.

An independent set produces a pivot in every column.

> **Worked example.** Determine whether the columns of
>
> $$
> A = \begin{bmatrix} 0 & 1 & 4 \\ 1 & 2 & -1 \\ 5 & 8 & 0 \end{bmatrix}
> $$
>
> are linearly independent. Interchange rows 1 and 2 to place a pivot in the top
> left, subtract $5$ times the new row 1 from row 3, then clear below the second
> pivot:
>
> $$
> \begin{bmatrix} 0 & 1 & 4 \\ 1 & 2 & -1 \\ 5 & 8 & 0 \end{bmatrix}
> \;\longrightarrow\;
> \begin{bmatrix} 1 & 2 & -1 \\ 0 & 1 & 4 \\ 0 & -2 & 5 \end{bmatrix}
> \;\longrightarrow\;
> \begin{bmatrix} 1 & 2 & -1 \\ 0 & 1 & 4 \\ 0 & 0 & 13 \end{bmatrix}.
> $$
>
> All three columns are pivot columns and no variable is free, so
> $A\mathbf{x} = \mathbf{0}$ has only the trivial solution and the columns are
> **independent**.

### Independence as a condition on a parameter

Many problems ask for the values of an unknown entry that make a set dependent.
The dependence appears exactly when the reduction produces a free variable. Take

$$
\mathbf{v}_1 = \begin{bmatrix} 1 \\ -3 \\ 2 \end{bmatrix},\quad
\mathbf{v}_2 = \begin{bmatrix} -3 \\ 9 \\ -6 \end{bmatrix},\quad
\mathbf{v}_3 = \begin{bmatrix} 5 \\ -7 \\ h \end{bmatrix}.
$$

Here $\mathbf{v}_2 = -3\mathbf{v}_1$ already, so $\{\mathbf{v}_1, \mathbf{v}_2\}$
is dependent, and adding any $\mathbf{v}_3$ keeps the set dependent for **every**
value of $h$: a dependence relation among the first two, padded with weight $0$ on
$\mathbf{v}_3$, still has a nonzero weight. No value of the parameter can make an
already-dependent set independent.

When the first vectors are independent, the parameter can matter. For

$$
\mathbf{v}_1 = \begin{bmatrix} 1 \\ -1 \\ -3 \end{bmatrix},\quad
\mathbf{v}_2 = \begin{bmatrix} -5 \\ 7 \\ 8 \end{bmatrix},\quad
\mathbf{v}_3 = \begin{bmatrix} 1 \\ 1 \\ h \end{bmatrix},
$$

row reduction leaves a bottom-row pivot in column 3 unless $h$ takes one specific
value that zeros it; at that value $x_3$ becomes free and the set turns dependent.
The parameter is fixed by demanding the third pivot vanish.

## Small cases by inspection

For one or two vectors, no computation is needed.

- **One vector.** $\{\mathbf{v}\}$ is independent if and only if $\mathbf{v} \ne
  \mathbf{0}$. The equation $x_1\mathbf{v} = \mathbf{0}$ forces $x_1 = 0$ exactly
  when $\mathbf{v}$ is nonzero.
- **Two vectors.** $\{\mathbf{v}_1, \mathbf{v}_2\}$ is dependent if and only if one
  is a scalar multiple of the other. Geometrically, dependent means the two lie on
  a common line through the origin.

$$
% caption: Two vectors: independent when they point along different lines through
% 0 (left); dependent when one is a scalar multiple of the other (right).
\begin{tikzpicture}[scale=0.95, font=\footnotesize, >=stealth]
\definecolor{acc}{HTML}{4A6FA5}
% --- independent ---
\begin{scope}
  \draw[black, ->] (-0.3,0) -- (3.2,0); \draw[black, ->] (0,-0.3) -- (0,2.8);
  \draw[acc, thick, ->] (0,0) -- (2.4,0.8) node[right] {$\mathbf{v}_1$};
  \draw[acc, thick, ->] (0,0) -- (0.9,2.2) node[above] {$\mathbf{v}_2$};
  \node[anchor=north] at (1.4,-0.5) {independent};
\end{scope}
% --- dependent ---
\begin{scope}[xshift=6cm]
  \draw[black, ->] (-0.3,0) -- (3.2,0); \draw[black, ->] (0,-0.3) -- (0,2.8);
  \draw[black, dashed] (-0.4,-0.4) -- (3.0,3.0);
  \draw[acc, thick, ->] (0,0) -- (1.0,1.0) node[above left] {$\mathbf{v}_1$};
  \draw[acc, thick, ->] (0,0) -- (2.2,2.2) node[right] {$\mathbf{v}_2 = 2\mathbf{v}_1$};
  \node[anchor=north] at (1.4,-0.5) {dependent};
\end{scope}
\end{tikzpicture}
$$

## Dependence means one vector is redundant

The name "dependent" is justified by rewriting a dependence relation.

> **Theorem (Characterization of dependence).** A set $S = \{\mathbf{v}_1, \dots,
> \mathbf{v}_p\}$ of two or more vectors is linearly dependent if and only if at
> least one vector in $S$ is a linear combination of the others. If $S$ is
> dependent and $\mathbf{v}_1 \ne \mathbf{0}$, then some $\mathbf{v}_j$ (with $j >
> 1$) is a linear combination of the preceding vectors $\mathbf{v}_1, \dots,
> \mathbf{v}_{j-1}$.

If $\mathbf{v}_j = c_1\mathbf{v}_1 + \cdots$ is a combination of the others, move
it across: $(-1)\mathbf{v}_j + c_1\mathbf{v}_1 + \cdots = \mathbf{0}$ is a
dependence relation with nonzero weight $-1$. Conversely, given a dependence
relation, let $j$ be the largest index with $c_j \ne 0$; then $c_j\mathbf{v}_j =
-c_1\mathbf{v}_1 - \cdots - c_{j-1}\mathbf{v}_{j-1}$ solves for $\mathbf{v}_j$ in
terms of the earlier vectors.[^lay-17]

> **Caution.** The theorem does _not_ say every vector in a dependent set is a
> combination of the others. A particular vector may fail to be, while the set as
> a whole is still dependent.

This connects independence back to span. If $\mathbf{u}, \mathbf{v}$ are
independent in $\mathbb{R}^3$, they span a plane, and a third vector $\mathbf{w}$
makes $\{\mathbf{u}, \mathbf{v}, \mathbf{w}\}$ dependent exactly when $\mathbf{w}$
lies in that plane.

$$
% caption: With u, v independent, {u, v, w} is dependent iff w lies in the plane
% they span (left) and independent iff w points out of it (right).
\begin{tikzpicture}[scale=1.0, font=\footnotesize, >=stealth]
\definecolor{acc}{HTML}{4A6FA5}
% --- dependent: w in plane ---
\begin{scope}
  \draw[acc!55, fill=acc!8] (-1.5,-0.7) -- (1.8,-0.3) -- (1.5,1.5) -- (-1.8,1.1) -- cycle;
  \draw[acc, thick, ->] (0,0.1) -- (1.2,0.45) node[below right] {$\mathbf{u}$};
  \draw[acc, thick, ->] (0,0.1) -- (-0.9,0.7) node[above left] {$\mathbf{v}$};
  \draw[black!70, thick, ->] (0,0.1) -- (0.9,0.95) node[above right] {$\mathbf{w}$};
  \node[anchor=north] at (0,-1.0) {dependent};
\end{scope}
% --- independent: w out of plane ---
\begin{scope}[xshift=6cm]
  \draw[acc!55, fill=acc!8] (-1.5,-0.7) -- (1.8,-0.3) -- (1.5,1.5) -- (-1.8,1.1) -- cycle;
  \draw[acc, thick, ->] (0,0.1) -- (1.2,0.45) node[below right] {$\mathbf{u}$};
  \draw[acc, thick, ->] (0,0.1) -- (-0.9,0.7) node[above left] {$\mathbf{v}$};
  \draw[black!70, thick, ->] (0,0.1) -- (0.35,2.3) node[above] {$\mathbf{w}$};
  \node[anchor=north] at (0,-1.0) {independent};
\end{scope}
\end{tikzpicture}
$$

## Two automatic dependences

Some sets are dependent for structural reasons, without any reduction.

> **Theorem (Too many vectors).** If a set $\{\mathbf{v}_1, \dots, \mathbf{v}_p\}$
> in $\mathbb{R}^n$ has more vectors than entries — that is, $p > n$ — then the set
> is linearly dependent.

The matrix $A = [\,\mathbf{v}_1\ \cdots\ \mathbf{v}_p\,]$ is $n \times p$, so
$A\mathbf{x} = \mathbf{0}$ has $n$ equations in $p > n$ unknowns; with more columns
than rows, some column has no pivot, hence a free variable, hence a nontrivial
solution.

> **Theorem (A set containing $\mathbf{0}$).** Any set that contains the zero
> vector is linearly dependent.

If $\mathbf{v}_1 = \mathbf{0}$, the relation $1\cdot\mathbf{v}_1 + 0\cdot\mathbf{v}_2 +
\cdots + 0\cdot\mathbf{v}_p = \mathbf{0}$ has a nonzero weight.

$$
% caption: In R^n a set can be independent only while p <= n; once p exceeds n,
% dependence is forced by the too-many-vectors theorem.
\begin{tikzpicture}[scale=1.0, font=\footnotesize, >=stealth]
\definecolor{acc}{HTML}{4A6FA5}
\draw[black, ->] (-0.4,0) -- (8.6,0) node[right] {$p$};
\foreach \x/\lab in {1/1, 2/2, 4/n, 6/{n+1}, 7.5/{n+2}} {
  \draw[black] (\x,0.12) -- (\x,-0.12);
  \node[anchor=north] at (\x,-0.18) {$\lab$};
}
\draw[acc, line width=2pt] (0.6,0.35) -- (4,0.35);
\node[acc, anchor=south] at (2.3,0.4) {can be independent};
\draw[black!70, line width=2pt] (4.6,0.35) -- (8.2,0.35);
\node[black!70, anchor=south] at (6.4,0.4) {always dependent};
\draw[black, dashed] (4,-0.6) -- (4,0.7);
\end{tikzpicture}
$$

For example, three vectors in $\mathbb{R}^2$ are always dependent (there are more
vectors than entries), even when no one of them is a multiple of another — the
dependence involves all three at once.

$$
% caption: Any third vector in R^2 is a combination of two independent ones, so
% three vectors in the plane are always dependent even with no two parallel.
\begin{tikzpicture}[scale=1.0, font=\footnotesize, >=stealth]
\definecolor{acc}{HTML}{4A6FA5}
\draw[black, ->] (-0.3,0) -- (3.4,0);
\draw[black, ->] (0,-0.3) -- (0,3.0);
\coordinate (v1) at (2.2,0.55);
\coordinate (v2) at (0.65,1.95);
\coordinate (v3) at (2.85,2.5);
\draw[black, dashed] (v1) -- (v3);
\draw[black, dashed] (v2) -- (v3);
\draw[acc, thick, ->] (0,0) -- (v1) node[below right] {$\mathbf{v}_1$};
\draw[acc, thick, ->] (0,0) -- (v2) node[above left] {$\mathbf{v}_2$};
\draw[black!70, very thick, ->] (0,0) -- (v3) node[above right] {$\mathbf{v}_3$};
\end{tikzpicture}
$$

## Pivot criteria

Independence, span, and the shape of solution sets all read off the pivot pattern.
Collecting the criteria for the columns of an $m \times n$ matrix $A$:

| Property of the columns of $A$ | Pivot condition | Requires |
| --- | --- | --- |
| Linearly independent | a pivot in every column | $n$ pivots ($n \le m$) |
| Span $\mathbb{R}^m$ | a pivot in every row | $m$ pivots ($n \ge m$) |
| Both (independent and spanning) | a pivot in every row and column | $m = n$ pivots |

Independence caps the number of vectors at $m$; spanning $\mathbb{R}^m$ requires
at least $m$. A set that does both must have exactly $m = n$ vectors — the
defining condition of a
[basis](/linear-algebra/vector-spaces/bases-and-independent-sets).

[^lay-17]: **Lay**, _Linear Algebra and Its Applications_, §1.7 — Linear Independence: the definition via the homogeneous equation, the characterization of a dependent set as one whose vectors include a combination of the others, and the theorems that $p > n$ vectors in $\mathbb{R}^n$ or any set containing $\mathbf{0}$ is dependent.