---
title: Linearly Independent Sets and Bases
module: Vector Spaces
moduleNumber: 4
lessonNumber: 3
order: 403
summary: >
  A basis is a spanning set with no redundancy: linearly independent and still
  large enough to reach every vector. The spanning-set theorem shows any spanning
  set can be trimmed to a basis by discarding dependent vectors, and the pivot
  columns of a matrix give a basis for its column space. Independence and spanning
  are defined for abstract spaces exactly as in $\mathbb{R}^n$.
topics: [Vector Spaces]
draft: false
sources:
  - book: Lay
    ref: "§4.3 Linearly Independent Sets; Bases"
---

A spanning set describes a subspace but may carry redundant vectors. A linearly
independent set carries no redundancy but may fail to reach every vector. A
**basis** is both at once: independent and spanning. It is the most efficient
description of a subspace, and every vector in the space is a unique combination of
it. The definitions of independence and spanning transfer from $\mathbb{R}^n$ to
any vector space without change.[^lay-basis]

## Linear independence in a vector space

> **Definition (Linear independence).** An indexed set $\{v_1, \dots, v_p\}$ in a
> vector space $V$ is linearly independent if the equation
> $$
> c_1 v_1 + c_2 v_2 + \cdots + c_p v_p = 0
> $$
> has only the trivial solution $c_1 = \cdots = c_p = 0$. The set is linearly
> dependent if there exist weights, not all zero, for which the equation holds; such
> an equation is a linear dependence relation.

The small cases match $\mathbb{R}^n$: a single vector $\{v\}$ is independent iff
$v \neq 0$; a pair is dependent iff one vector is a multiple of the other; and any
set containing the zero vector is dependent. The general test is a chain condition.

> **Theorem (Dependence and predecessors).** An indexed set $\{v_1, \dots, v_p\}$
> of two or more vectors, with $v_1 \neq 0$, is linearly dependent if and only if
> some $v_j$ (with $j > 1$) is a linear combination of the preceding vectors
> $v_1, \dots, v_{j-1}$.

When the vectors are not columns of numbers, the dependence equation usually
cannot be turned into a matrix equation $Ax = 0$, so the definition and the
dependence-and-predecessors theorem are the working tools.

> **Worked example.** In $\mathbb{P}$, is $\{p_1, p_2, p_3\}$ with $p_1(t) = 1$,
> $p_2(t) = t$, $p_3(t) = 4 - t$ independent? In $C[0, 1]$, is
> $\{\sin t \cos t,\ \sin 2t\}$ independent?
>
> The three polynomials are dependent: $p_3 = 4p_1 - p_2$, so
> $$
> 4p_1 - p_2 - p_3 = 0
> $$
> is a dependence relation with weights $(4, -1, -1)$, not all zero. For the two
> functions, the double-angle identity $\sin 2t = 2 \sin t \cos t$ holds for every
> $t$, so $2(\sin t \cos t) - \sin 2t = 0$ is a nontrivial dependence relation; the
> pair is dependent. By contrast $\{\sin t, \cos t\}$ is independent, since neither
> is a scalar multiple of the other.

## Bases

> **Definition (Basis).** Let $H$ be a subspace of a vector space $V$. An indexed
> set $\mathcal{B} = \{b_1, \dots, b_p\}$ in $V$ is a basis for $H$ if
> $\mathcal{B}$ is linearly independent and $H = \operatorname{Span}\{b_1, \dots,
> b_p\}$.

Taking $H = V$ recovers the notion of a basis for the whole space. The two most
common bases are the standard ones:

- **The standard basis for $\mathbb{R}^n$** is $\{e_1, \dots, e_n\}$, the columns
  of the $n \times n$ identity matrix. Any invertible $n \times n$ matrix's columns
  also form a basis for $\mathbb{R}^n$, since they are independent and span by the
  Invertible Matrix Theorem.
- **The standard basis for $\mathbb{P}_n$** is $\{1, t, t^2, \dots, t^n\}$. It
  spans by definition, and it is independent because a polynomial of degree at most
  $n$ with more than $n$ roots must be the zero polynomial, forcing every
  coefficient to zero.

$$
% caption: The standard basis of $\mathbb{R}^3$: three mutually independent axis
% vectors, each a unit step along one coordinate direction.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
\definecolor{acc}{HTML}{2F6DB5}
\draw[->, black] (0,0) -- (2.6,0);
\draw[->, black] (0,0) -- (0,2.4);
\draw[->, black] (0,0) -- (-1.5,-1.1);
\draw[->, acc, very thick] (0,0) -- (1.7,0) node[below right] {$e_1$};
\draw[->, acc, very thick] (0,0) -- (0,1.7) node[above left] {$e_2$};
\draw[->, acc, very thick] (0,0) -- (-1.05,-0.77) node[below left] {$e_3$};
\fill[black] (0,0) circle (1.4pt);
\end{tikzpicture}
$$

$$
% caption: The standard basis of $\mathbb{P}_2$ drawn as functions: the constant
% $1$, the line $t$, and the parabola $t^2$. They are independent because a nonzero
% polynomial of degree at most $2$ has at most two roots.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
\definecolor{acc}{HTML}{2F6DB5}
\draw[->, black] (-1.7,0) -- (1.9,0) node[right] {$t$};
\draw[->, black] (0,-0.4) -- (0,2.5);
\draw[acc, thick] (-1.6,1.0) -- (1.8,1.0);
\node[acc, anchor=south west] at (1.15,1.0) {$1$};
\draw[black, thick] (-1.55,-0.35) -- (1.55,2.35);
\node[black, anchor=west] at (1.5,2.3) {$t$};
\draw[black, thick] plot[domain=-1.5:1.5, samples=40] (\x, {\x*\x});
\node[black, anchor=east] at (-1.35,2.1) {$t^2$};
\end{tikzpicture}
$$

## The spanning-set theorem

A basis can be built from any spanning set by throwing away vectors that
contribute nothing new. Discarding a vector that is a linear combination of the
others leaves the span unchanged.

> **Theorem (Spanning-set theorem).** Let $S = \{v_1, \dots, v_p\}$ be a set in
> $V$ and $H = \operatorname{Span}\{v_1, \dots, v_p\}$.
> a. If one vector in $S$ — say $v_k$ — is a linear combination of the rest, then
> the set formed by removing $v_k$ still spans $H$.
> b. If $H \neq \{0\}$, some subset of $S$ is a basis for $H$.

Part (a) is the trimming step; part (b) is its repeated application. As long as the
spanning set is dependent, some vector depends on the others and can be deleted
without shrinking the span. The process stops precisely when the set becomes
independent, which is a basis.

$$
% caption: A three-vector spanning set of a plane with $v_3 = 5v_1 + 3v_2$; the
% redundant $v_3$ is discarded, and the independent pair $\{v_1, v_2\}$ remains a
% basis for the same plane.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
\fill[acc!8] (-2.3,-1.0) -- (2.4,-0.3) -- (2.4,1.5) -- (-2.3,0.8) -- cycle;
\draw[acc, thick] (-2.3,-1.0) -- (2.4,-0.3) -- (2.4,1.5) -- (-2.3,0.8) -- cycle;
\draw[->, black, thick] (0,0) -- (1.3,0.15) node[below] {$v_1$};
\draw[->, black, thick] (0,0) -- (0.35,0.75) node[above left] {$v_2$};
\draw[->, red, thick, dashed] (0,0) -- (1.95,0.6) node[right] {$v_3 = 5v_1 + 3v_2$};
\fill[black] (0,0) circle (1.4pt);
\node[red, font=\scriptsize] at (0.9,-1.35) {discard $v_3$; keep basis $v_1$, $v_2$};
\end{tikzpicture}
$$

> **Worked example.** Let $v_1 = (0, 2, -1)$, $v_2 = (2, 2, 0)$,
> $v_3 = (6, 16, -5)$, and $H = \operatorname{Span}\{v_1, v_2, v_3\}$. Find a basis
> for $H$.
>
> Check for a dependence. Direct computation gives $v_3 = 5v_1 + 3v_2$:
> $$
> 5\begin{bmatrix} 0 \\ 2 \\ -1 \end{bmatrix} + 3\begin{bmatrix} 2 \\ 2 \\ 0 \end{bmatrix}
> = \begin{bmatrix} 6 \\ 16 \\ -5 \end{bmatrix} = v_3.
> $$
> By the spanning-set theorem, discarding $v_3$ leaves
> $\operatorname{Span}\{v_1, v_2\} = H$. The pair $\{v_1, v_2\}$ is independent —
> neither is a multiple of the other — so it is a basis for $H$, and $\dim H = 2$.

## Bases for the null space and column space

The two subspaces of a matrix each come with a standard basis-finding procedure.

**Null space.** The spanning set produced by solving $Ax = 0$ — one vector per
free variable — is automatically linearly independent, as shown when the
[null space](/linear-algebra/vector-spaces/null-and-column-spaces) was described
explicitly. So that spanning set is already a basis for $\operatorname{Nul} A$.

**Column space.** The pivot columns of $A$ form a basis for $\operatorname{Col}
A$. Each nonpivot column is a linear combination of pivot columns to its left, so
the spanning-set theorem discards it; the pivot columns that remain are
independent.

> **Theorem (Pivot columns as a basis).** The pivot columns of a matrix $A$ form
> a basis for its column space $\operatorname{Col} A$.

The proof uses that row reduction preserves the linear dependence relations among
columns: $Ax = 0$ and $Bx = 0$ have the same solutions when $B$ is row equivalent
to $A$. So a dependence among the columns of $B$ is a dependence among the columns
of $A$ in the same positions, and conversely.

> **Warning.** Use the pivot columns of $A$ itself, not of its echelon form $B$.
> Row operations change the column space; the columns of $B$ generally do not lie
> in $\operatorname{Col} A$ at all. Echelon form only _locates_ the pivot positions.

```algorithm
caption: $\textsc{ColumnBasis}(A)$ — a basis for $\operatorname{Col} A$
row-reduce $A$ to an echelon form $B$
identify the pivot positions of $B$
for each pivot column index $j$ do
  select column $a_j$ of the original matrix $A$
return the selected columns of $A$
```

For example, if the pivots of an echelon form of $A$ sit in columns $1, 2, 4$, then
columns $1, 2, 4$ **of $A$** are a basis for $\operatorname{Col} A$, no matter how
different the echelon form looks.

$$
% caption: An echelon form marks pivots in columns 1, 2, 4; the basis for
% $\operatorname{Col} A$ is columns 1, 2, 4 of the original $A$, not of the echelon
% form.
\begin{tikzpicture}[font=\footnotesize]
\definecolor{acc}{HTML}{2F6DB5}
% echelon staircase
\node[font=\small] at (1.9,2.7) {echelon form $B$};
\draw[black] (0,0) rectangle (3.8,2.2);
\draw[acc, thick] (0.05,2.15) rectangle (0.95,0.05);
\draw[acc, thick] (0.95,2.15) rectangle (1.9,0.05);
\draw[acc, thick] (2.85,2.15) rectangle (3.75,0.05);
\node[acc, font=\scriptsize] at (0.5,-0.35) {piv};
\node[acc, font=\scriptsize] at (1.42,-0.35) {piv};
\node[black, font=\scriptsize] at (2.37,-0.35) {free};
\node[acc, font=\scriptsize] at (3.3,-0.35) {piv};
\draw[->, acc, very thick] (4.3,1.1) -- (5.6,1.1) node[midway, above, font=\scriptsize] {take from $A$};
% original
\node[font=\small] at (7.9,2.7) {original $A$};
\draw[black] (6.0,0) rectangle (9.8,2.2);
\fill[acc!14] (6.05,0.05) rectangle (6.95,2.15);
\fill[acc!14] (6.95,0.05) rectangle (7.9,2.15);
\fill[acc!14] (8.85,0.05) rectangle (9.75,2.15);
\node[acc, font=\scriptsize] at (6.5,-0.35) {basis};
\node[acc, font=\scriptsize] at (7.42,-0.35) {basis};
\node[acc, font=\scriptsize] at (9.3,-0.35) {basis};
\end{tikzpicture}
$$

> **Worked example.** Find a basis for $\operatorname{Col} B$, where
> $$
> B = \begin{bmatrix} 1 & 4 & 0 & 2 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}.
> $$
>
> $B$ is already in reduced echelon form, with pivots in columns $1, 3, 5$. Each
> nonpivot column depends on the pivot columns to its left: $b_2 = 4b_1$ and
> $b_4 = 2b_1 + b_3$. The spanning-set theorem discards $b_2$ and $b_4$, so
> $$
> \{b_1, b_3, b_5\} = \left\{
> \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix},\;
> \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix},\;
> \begin{bmatrix} 0 \\ 0 \\ 1 \\ 0 \end{bmatrix} \right\}
> $$
> is a basis for $\operatorname{Col} B$. No vector in this set is a combination of
> its predecessors, so it is independent by the dependence-and-predecessors theorem.

## Two views of a basis

A basis is optimal from opposite directions.

- **A spanning set as small as possible.** When the spanning-set theorem trims a
  set down, deletion must stop once the set is independent. Removing one more vector
  loses the span, because that vector was not a combination of the rest.
- **An independent set as large as possible.** If $S$ is a basis for $V$ and any
  vector $w$ from $V$ is added, the enlarged set is dependent: $w$ is already a
  combination of $S$, giving a nontrivial dependence relation.

These two views bracket the size of every basis: an independent set can be grown to
a basis and a spanning set shrunk to one, and both processes terminate at the same
count. That common count is the
[dimension](/linear-algebra/vector-spaces/dimension-and-rank) of the space, and the
unique coefficients a basis assigns to each vector are its
[coordinates](/linear-algebra/vector-spaces/coordinate-systems).

[^lay-basis]: **Lay**, _Linear Algebra and Its Applications_, §4.3 — Linearly Independent Sets; Bases: Theorem 4 (dependence via predecessors), the basis definition, Theorem 5 (spanning-set theorem), and Theorem 6 (pivot columns as a basis for $\operatorname{Col} A$).