Subspaces and Rank

Published

Last modified: 2026-10-27 20:53:54 (PDT)

1 Rank

Definition 1 (Linearly independent vectors)

Definition 1 (Linearly independent vectors) Vectors $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k$ of the same length $p$ are linearly independent [1] if the only numbers $c_1, \ldots, c_k$ with

\[c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + c_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\]

are

\[ \begin{aligned} c_1 &= \cdots \\ &= c_k \\ &= 0. \end{aligned} \]

Vectors that are not linearly independent are linearly dependent.

Example 1 (Independent and dependent pairs of vectors)

Example 1 (Independent and dependent pairs of vectors)

$\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 = (1, 0)$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_2 = (1, 1)$ are linearly independent: $c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + c_2 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_2 = (c_1 + c_2, c_2)$, which is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$ only if $c_2 = 0$ and then $c_1 = 0$.
$\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 = (1, 2)$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_2 = (2, 4)$ are not: $2 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 - \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_2 = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$.

Definition 2 (Rank)

Definition 2 (Rank) The rank [2] of a matrix $\mathbf{A}$, written $\operatorname{rank}(\mathbf{A})$, is the largest number of columns of $\mathbf{A}$ that are linearly independent (Definition 1).

Example 2 (The rank of two $3 \times 2$ matrices)

Example 2 (The rank of two $3 \times 2$ matrices) The matrix $\begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}$ has rank $2$: if $c_1 (1, 1, 1) + c_2 (1, 2, 3) = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$, then subtracting the first entry from the second gives $c_2 = 0$, and then $c_1 = 0$.

The matrix $\begin{bmatrix} 1 & 2 \\ 1 & 2 \\ 1 & 2 \end{bmatrix}$ has rank $1$: its second column is twice its first, so the two columns are not linearly independent, but the first column on its own is.

Definition 3 (Full column rank)

Definition 3 (Full column rank) An $n \times p$ matrix has full column rank if its rank (Definition 2) is $p$, so that all of its columns are linearly independent.

Remark 1 (Full column rank needs at least as many rows as columns)

Remark 1 (Full column rank needs at least as many rows as columns). In Example 2, the first matrix has full column rank: its rank is $2$, and it has $2$ columns. The second does not, because its rank is $1$.

An $n \times p$ matrix can have full column rank only when $p \le n$, because more than $n$ vectors of length $n$ are never linearly independent. For example, the $2 \times 3$ matrix $\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}$ has $3$ columns of length $2$, and $1 \cdot(1, 0) + 1 \cdot(0, 1) - 1 \cdot(1, 1) = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$, with coefficients that are not all zero. So its $3$ columns are not linearly independent, and its rank is less than $3$.

2 Subspaces

Source and license

This section is adapted from Zhou [3], used under the MIT License. The license text is:

Copyright (c) 2024 ucla-biostat-216

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Definition 4 (Subspace, linear subspace)

Definition 4 (Subspace, linear subspace) A set $\mathcal{S}$ of vectors in $\mathbb{R}^p$ is a subspace [4] of $\mathbb{R}^p$ if it is not empty and it is closed under vector addition and scalar multiplication:

if $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} \in \mathcal{S}$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} \in \mathcal{S}$, then $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} \in \mathcal{S}$;
if $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} \in \mathcal{S}$ and $c \in \mathbb{R}$, then $c \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} \in \mathcal{S}$.

A subspace is also called a linear subspace.

Example 3 (A line through the origin is a subspace)

Example 3 (A line through the origin is a subspace) Let $\mathcal{S} = \mathopen{}\left\{c\,(1, 2) : c \in \mathbb{R}\right\}\mathclose{}$, the line in $\mathbb{R}^2$ through $(0, 0)$ and $(1, 2)$.

Addition: $a\,(1, 2) + b\,(1, 2) = (a + b)\,(1, 2)$, which is in $\mathcal{S}$.
Scalar multiplication: $c\,\mathopen{}\left(a\,(1, 2)\right)\mathclose{} = (ca)\,(1, 2)$, which is in $\mathcal{S}$.

So $\mathcal{S}$ is a subspace of $\mathbb{R}^2$. Two other subspaces of $\mathbb{R}^p$ are the set $\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\right\}\mathclose{}$ that holds only the zero vector, and $\mathbb{R}^p$ itself.

Example 4 (A line that misses the origin is not a subspace)

Example 4 (A line that misses the origin is not a subspace) Let $\mathcal{T} = \mathopen{}\left\{(x, 1) : x \in \mathbb{R}\right\}\mathclose{}$, the horizontal line in $\mathbb{R}^2$ at height $1$. The vectors $(0, 1)$ and $(2, 1)$ are in $\mathcal{T}$, but their sum $(2, 2)$ is not, because its second entry is $2$, not $1$. So $\mathcal{T}$ is not closed under addition, and it is not a subspace.

Theorem 1 (Every subspace contains the zero vector)

Theorem 1 (Every subspace contains the zero vector) If $\mathcal{S}$ is a subspace of $\mathbb{R}^p$ (Definition 4), then $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\in \mathcal{S}$.

Proof

Proof. A subspace is not empty, so it contains some vector $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}$. Closure under scalar multiplication with $c = 0$ puts $0 \cdot\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}$ in $\mathcal{S}$, and $0 \cdot\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$.

Example 5 (Using the zero vector to rule out a subspace)

Example 5 (Using the zero vector to rule out a subspace) The plane $\mathopen{}\left\{(x, y, z) : x + y + z = 1\right\}\mathclose{}$ in $\mathbb{R}^3$ does not contain $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}= (0, 0, 0)$, because $0 + 0 + 0 = 0 \neq 1$. So, by Theorem 1, it is not a subspace. The line $\mathcal{T}$ in Example 4 fails the same test: $(0, 0)$ is not in $\mathcal{T}$, because its second entry is not $1$.

Containing $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$ is necessary but not sufficient. The union of the two coordinate axes in $\mathbb{R}^2$, $\mathopen{}\left\{(x, 0) : x \in \mathbb{R}\right\}\mathclose{} \cup \mathopen{}\left\{(0, y) : y \in \mathbb{R}\right\}\mathclose{}$, contains $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$, but $(1, 0) + (0, 1) = (1, 1)$ lies on neither axis, so the union is not closed under addition and is not a subspace.

Definition 5 (Span)

Definition 5 (Span) The span [5] of vectors $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k \in \mathbb{R}^p$ is the set of all their linear combinations:

\[ \operatorname{span}\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k\right\}\mathclose{} \stackrel{\text{def}}{=} \mathopen{}\left\{c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + c_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k : c_1, \ldots, c_k \in \mathbb{R}\right\}\mathclose{}. \]

The vectors $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k$ span a set $\mathcal{S}$ if their span equals $\mathcal{S}$.

By convention, the span of the empty list ($k = 0$) is $\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\right\}\mathclose{}$, and the empty list counts as linearly independent (Definition 1), since it has no coefficients that could fail to be zero.

Example 6 (Two spans in $\mathbb{R}^3$)

Example 6 (Two spans in $\mathbb{R}^3$)

$\operatorname{span}\mathopen{}\left\{(1, 0, 0), (0, 1, 0)\right\}\mathclose{}$ is the set of vectors $(c_1, c_2, 0)$, the plane $z = 0$ in $\mathbb{R}^3$.
$\operatorname{span}\mathopen{}\left\{(1, 2, 3), (2, 4, 6)\right\}\mathclose{}$ is only the line $\mathopen{}\left\{c\,(1, 2, 3) : c \in \mathbb{R}\right\}\mathclose{}$, because $(2, 4, 6) = 2\,(1, 2, 3)$, so $c_1 (1, 2, 3) + c_2 (2, 4, 6) = (c_1 + 2 c_2)\,(1, 2, 3)$. Adding a vector to a list does not always enlarge its span.

Theorem 2 (A span is a subspace)

Theorem 2 (A span is a subspace) For any vectors $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k \in \mathbb{R}^p$, $\operatorname{span}\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k\right\}\mathclose{}$ (Definition 5) is a subspace of $\mathbb{R}^p$ (Definition 4).

Proof

Proof. The span is not empty: it contains $0 \cdot\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + 0 \cdot\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$.

Addition. Take two vectors in the span, $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} = a_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + a_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} = b_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + b_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k$. Then

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} &= (a_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + a_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k) + (b_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + b_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k) && \text{(substitute the two combinations)} \\ &= (a_1 + b_1)\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + (a_k + b_k)\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k && \text{(regroup, and distribute each } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_i \text{)} \end{aligned} \]

which is a linear combination of $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k$, so it is in the span.

Scalar multiplication. For $c \in \mathbb{R}$,

\[ \begin{aligned} c\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} &= c\,(a_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + a_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k) && \text{(substitute the combination)} \\ &= (c a_1)\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + (c a_k)\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k && \text{(distribute } c \text{ over the sum)} \end{aligned} \]

which is again in the span.

Example 7 (The line in Example 3 is a span)

Example 7 (The line in Example 3 is a span) The line $\mathcal{S} = \mathopen{}\left\{c\,(1, 2) : c \in \mathbb{R}\right\}\mathclose{}$ in Example 3 is $\operatorname{span}\mathopen{}\left\{(1, 2)\right\}\mathclose{}$, so Theorem 2 gives a second proof that it is a subspace. Likewise, the plane $z = 0$ in Example 6 is a subspace of $\mathbb{R}^3$, because it is $\operatorname{span}\mathopen{}\left\{(1, 0, 0), (0, 1, 0)\right\}\mathclose{}$.

Theorem 3 (A matrix-vector product combines the columns)

Theorem 3 (A matrix-vector product combines the columns) If $\mathbf{A}$ is an $m \times n$ matrix with columns $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_n$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \in \mathbb{R}^n$, then

\[ \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = x_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 + \cdots + x_n \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_n. \]

Proof

Proof. Compare entry $i$ of the two sides, for each $i = 1, \ldots, m$. Entry $i$ of $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_j$ is $a_{ij}$, so

\[ \begin{aligned} (\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}})_i &= a_{i1} x_1 + \cdots + a_{in} x_n && \text{(}\href{linear-algebra-matrices.qmd#def-matvec-mult}{\text{Definition~13 in Matrices}}\text{)} \\ &= x_1 a_{i1} + \cdots + x_n a_{in} && \text{(multiplication of numbers is commutative)} \\ &= (x_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 + \cdots + x_n \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_n)_i && \text{(entry } i \text{ of each } x_j \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_j \text{ is } x_j a_{ij} \text{)} \end{aligned} \]

Example 8 (A product as a combination of columns)

Example 8 (A product as a combination of columns) \[ \begin{aligned} \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \begin{bmatrix} 1 \\ -1 \end{bmatrix} &= 1 \cdot\begin{bmatrix} 1 \\ 3 \end{bmatrix} + (-1) \cdot\begin{bmatrix} 2 \\ 4 \end{bmatrix} && \text{(}\href{#thm-matvec-columns}{\text{Theorem~3}}\text{)} \\ &= \begin{bmatrix} -1 \\ -1 \end{bmatrix}, && \text{(arithmetic)} \end{aligned} \]

the same answer as computing each entry as a row-times-vector dot product (Remark 4 in Matrices).

Theorem 4 (A matrix maps a combination to the same combination of images)

Theorem 4 (A matrix maps a combination to the same combination of images) If $\mathbf{A}$ is an $m \times n$ matrix, $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_k \in \mathbb{R}^n$ and $c_1, \ldots, c_k \in \mathbb{R}$, then

\[ \mathbf{A}\,(c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_1 + \cdots + c_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_k) = c_1\,\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_1 + \cdots + c_k\,\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_k. \]

Proof

Proof. The function $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\mapsto \mathbf{A}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ is a linear map by Theorem 10 in Matrices, and a linear map preserves linear combinations by Theorem 11 in Matrices. Applying that theorem with $f(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}) = \mathbf{A}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_i = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_i$ gives the identity.

Example 9 (Applying a matrix to a combination)

Example 9 (Applying a matrix to a combination) Let $\mathbf{A} = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$, $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_1 = (1, 0)$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_2 = (0, 1)$. Then $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_1 = (1, 3)$ and $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_2 = (2, 4)$, and for the combination $2 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_1 - \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_2 = (2, -1)$:

\[ \begin{aligned} \mathbf{A}\,(2, -1) &= (1 \cdot 2 + 2 \cdot(-1),\; 3 \cdot 2 + 4 \cdot(-1)) && \text{(}\href{linear-algebra-matrices.qmd#def-matvec-mult}{\text{Definition~13 in Matrices}}\text{)} \\ &= (0, 2) && \text{(arithmetic)} \\ &= 2\,(1, 3) - (2, 4), && \text{(arithmetic)} \end{aligned} \]

which is $2\,\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_1 - \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}_2$, as Theorem 4 says.

Theorem 5 (More than $p$ vectors in $\mathbb{R}^p$ are linearly dependent)

Theorem 5 (More than $p$ vectors in $\mathbb{R}^p$ are linearly dependent) If $k > p$, then any $k$ vectors $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k \in \mathbb{R}^p$ are not linearly independent (Definition 1): some numbers $c_1, \ldots, c_k$, not all zero, satisfy $c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + c_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_p$.

Proof

Proof. Induction on $p$.

Base case, $p = 1$. Each $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_i$ is a single number $v_i$, and $k \ge 2$. If $v_1 = 0$, take $c_1 = 1$ and every other $c_i = 0$. Otherwise take $c_1 = v_2$, $c_2 = -v_1$ and every other $c_i = 0$; then $c_2 \neq 0$, and $v_2 v_1 - v_1 v_2 = 0$.

Inductive step. Let $p \ge 2$, assume the theorem holds for vectors in $\mathbb{R}^{p-1}$, and take $k > p$ vectors in $\mathbb{R}^p$. Write $v_{i,p}$ for the last entry of $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_i$.

Case 1: every $v_{i,p} = 0$. Deleting the last entry gives $k > p - 1$ vectors in $\mathbb{R}^{p-1}$, which by the inductive hypothesis have a combination with coefficients not all zero that equals $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_{p-1}$. The same coefficients combine the original vectors to $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_p$, since every last entry is $0$.

Case 2: some $v_{i,p} \neq 0$. Renumber the vectors so that $v_{k,p} \neq 0$, and for $i = 1, \ldots, k-1$ let

\[ \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}_i \stackrel{\text{def}}{=}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_i - \frac{v_{i,p}}{v_{k,p}}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k. \]

The last entry of $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}_i$ is $v_{i,p} - \frac{v_{i,p}}{v_{k,p}}\,v_{k,p} = 0$. Deleting that zero last entry gives $k - 1 > p - 1$ vectors in $\mathbb{R}^{p-1}$, so by the inductive hypothesis there are numbers $c_1, \ldots, c_{k-1}$, not all zero, whose combination of the shortened vectors is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_{p-1}$. Putting the zero last entries back gives $c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}_1 + \cdots + c_{k-1} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}_{k-1} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_p$. Then

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_p &= c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}_1 + \cdots + c_{k-1} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}_{k-1} && \text{(choice of } c_1, \ldots, c_{k-1} \text{)} \\ &= \sum_{i=1}^{k-1} c_i \mathopen{}\left(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_i - \frac{v_{i,p}}{v_{k,p}}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k\right)\mathclose{} && \text{(definition of } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}_i \text{)} \\ &= \sum_{i=1}^{k-1} c_i \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_i - \sum_{i=1}^{k-1} \frac{c_i v_{i,p}}{v_{k,p}}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k && \text{(distribute each } c_i \text{, and distribute the sum over the difference)} \\ &= c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + c_{k-1} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_{k-1} - \mathopen{}\left(\sum_{i=1}^{k-1} \frac{c_i v_{i,p}}{v_{k,p}}\right)\mathclose{}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k, && \text{(factor } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k \text{ out of the second sum)} \end{aligned} \]

a combination of $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k$ equal to $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_p$ whose first $k - 1$ coefficients are not all zero.

Example 10 (Three vectors in $\mathbb{R}^2$)

Example 10 (Three vectors in $\mathbb{R}^2$) Theorem 5 says the three vectors $(1, 0)$, $(0, 1)$ and $(1, 1)$ in $\mathbb{R}^2$ are linearly dependent, and indeed $1 \cdot(1, 0) + 1 \cdot(0, 1) - 1 \cdot(1, 1) = (0, 0)$. The theorem says nothing about $k \le p$ vectors: $(1, 0)$ and $(0, 1)$ are linearly independent, while $(1, 2)$ and $(2, 4)$ are not (Example 1).

Definition 6 (Basis)

Definition 6 (Basis) A basis [6] of a subspace $\mathcal{S}$ (Definition 4) is a list of vectors that are linearly independent (Definition 1) and span $\mathcal{S}$ (Definition 5).

Example 11 (Two bases of $\mathbb{R}^2$)

Example 11 (Two bases of $\mathbb{R}^2$)

$(1, 0)$ and $(0, 1)$ form a basis of $\mathbb{R}^2$: they are linearly independent, and any $(x, y) \in \mathbb{R}^2$ equals $x\,(1, 0) + y\,(0, 1)$.
$(1, 0)$ and $(1, 1)$ also form a basis of $\mathbb{R}^2$: Example 1 shows they are linearly independent, and any $(x, y)$ equals $(x - y)\,(1, 0) + y\,(1, 1)$, because $(x - y) + y = x$ in the first entry and $0 + y = y$ in the second.

Example 12 (Lists that are not bases of $\mathbb{R}^2$)

Example 12 (Lists that are not bases of $\mathbb{R}^2$)

$(1, 0)$ and $(2, 0)$ are not a basis of $\mathbb{R}^2$. They are not linearly independent, since $2\,(1, 0) - (2, 0) = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$, and they do not span $\mathbb{R}^2$: every combination $c_1 (1, 0) + c_2 (2, 0)$ has second entry $0$, so $(0, 1)$ is not in their span.
$(1, 0)$, $(0, 1)$ and $(1, 1)$ span $\mathbb{R}^2$, but they are not a basis: $(1, 0) + (0, 1) - (1, 1) = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$, so they are not linearly independent.

Theorem 6 (Coefficients in a basis are unique)

Theorem 6 (Coefficients in a basis are unique) If $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k$ is a basis of a subspace $\mathcal{S}$ (Definition 6), then every $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \in \mathcal{S}$ is a linear combination $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 + \cdots + c_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k$ for exactly one list of numbers $c_1, \ldots, c_k$.

Proof

Proof. At least one such list exists, because the basis spans $\mathcal{S}$ (Definition 5).

Suppose two lists both work:

\[ \begin{aligned} c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 + \cdots + c_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k &= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \\ &= d_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 + \cdots + d_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k. \end{aligned} \]

Subtracting the right side from the left side gives

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}} &= (c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 + \cdots + c_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k) - (d_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 + \cdots + d_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k) && \text{(both combinations equal } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \text{)} \\ &= (c_1 - d_1)\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 + \cdots + (c_k - d_k)\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k && \text{(regroup, and distribute each } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_i \text{)} \end{aligned} \]

Because $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k$ are linearly independent (Definition 1), every coefficient $c_i - d_i$ is $0$, so $c_i = d_i$ for each $i$.

Example 13 (Coefficients of $(3, 5)$ in two bases)

Example 13 (Coefficients of $(3, 5)$ in two bases) In the basis $(1, 0), (0, 1)$ of Example 11, $(3, 5) = 3\,(1, 0) + 5\,(0, 1)$, and no other coefficients work. In the basis $(1, 0), (1, 1)$, the formula in Example 11 gives

\[ \begin{aligned} (3, 5) &= (3 - 5)\,(1, 0) + 5\,(1, 1) \\ &= -2\,(1, 0) + 5\,(1, 1). \end{aligned} \]

The same vector has different coefficients in different bases, but within one basis its coefficients are unique.

The list $(1, 0), (0, 1), (1, 1)$ in Example 12 spans $\mathbb{R}^2$ but is not linearly independent, and the coefficients of $(3, 5)$ are not unique:

\[ \begin{aligned} (3, 5) &= 3\,(1, 0) + 5\,(0, 1) + 0\,(1, 1) \\ &= 0\,(1, 0) + 2\,(0, 1) + 3\,(1, 1). \end{aligned} \]

Definition 7 (Coordinates in a basis)

Definition 7 (Coordinates in a basis) Let $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k$ be a basis of a subspace $\mathcal{S}$ (Definition 6), and let $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \in \mathcal{S}$. The coordinates [7] of $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ in this basis are the numbers $c_1, \ldots, c_k$ with $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 + \cdots + c_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k$. By Theorem 6 there is exactly one such list of numbers.

Definition 8 (Coordinate vector)

Definition 8 (Coordinate vector) With $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ and its coordinates $c_1, \ldots, c_k$ as in Definition 7, $(c_1, \ldots, c_k) \in \mathbb{R}^k$ is the coordinate vector of $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$.

Example 14 (Coordinates of $(4, 1)$ in two bases of $\mathbb{R}^2$)

Example 14 (Coordinates of $(4, 1)$ in two bases of $\mathbb{R}^2$) In the basis $(1, 0), (1, 1)$ of Example 11, the coordinates of $(4, 1)$ are $3$ and $1$:

\[ \begin{aligned} 3\,(1, 0) + 1\,(1, 1) &= (3 + 1,\; 0 + 1) && \text{(}\href{linear-algebra-vectors.qmd#def-linear-combination}{\text{Definition~9 in Vectors}}\text{, entry by entry)} \\ &= (4, 1). && \text{(add)} \end{aligned} \]

In the basis $(1, 0), (0, 1)$, its coordinates are its entries, $4$ and $1$.

Theorem 7 (All bases of a subspace have the same number of vectors)

Theorem 7 (All bases of a subspace have the same number of vectors) If $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}_l$ are both bases of a subspace $\mathcal{S}$ of $\mathbb{R}^p$ (Definition 6), then $k = l$.

Proof

Proof. Let $\mathbf{A}$ be the $p \times k$ matrix with columns $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k$, and $\mathbf{B}$ the $p \times l$ matrix with columns $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}_l$.

Write $\mathbf{A}$ in terms of $\mathbf{B}$. Each $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_j$ is in $\mathcal{S}$, and the $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}$’s span $\mathcal{S}$ (Definition 5), so $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_j = \mathbf{B} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_j$ for some $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_j \in \mathbb{R}^l$ (Definition 13 in Matrices). Let $\mathbf{C}$ be the $l \times k$ matrix with columns $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_k$. Then $\underbrace{\mathbf{A}}_{p \times k} = \underbrace{\mathbf{B}}_{p \times l}\,\underbrace{\mathbf{C}}_{l \times k}$, because column $j$ of $\mathbf{B} \mathbf{C}$ is $\mathbf{B} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_j$.

The columns of $\mathbf{C}$ are linearly independent. Suppose $\mathbf{C} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$ for some $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \in \mathbb{R}^k$. Then

\[ \begin{aligned} \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} &= (\mathbf{B} \mathbf{C})\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} && \text{(substitute } \mathbf{A} = \mathbf{B} \mathbf{C} \text{)} \\ &= \mathbf{B}\,(\mathbf{C} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}) && \text{(}\href{linear-algebra-matrices.qmd#thm-matmul-assoc}{\text{Theorem~5 in Matrices}}\text{)} \\ &= \mathbf{B}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}} && \text{(substitute } \mathbf{C} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\text{)} \\ &= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}} && \text{(a matrix times the zero vector is } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\text{)} \end{aligned} \]

$\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ is the combination $x_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 + \cdots + x_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_k$ (Theorem 3), and the $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}$’s are linearly independent (Definition 1), so $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$. So the only combination of the columns of $\mathbf{C}$ that equals $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$ has all coefficients $0$.

Count. $\mathbf{C}$ has $k$ linearly independent columns of length $l$. More than $l$ vectors in $\mathbb{R}^l$ are never linearly independent (Theorem 5), so $k \le l$. Exchanging the roles of the two bases gives $l \le k$, so $k = l$.

Example 15 (Both bases of $\mathbb{R}^2$ in Example 11 have two vectors)

Example 15 (Both bases of $\mathbb{R}^2$ in Example 11 have two vectors) The bases $(1, 0), (0, 1)$ and $(1, 0), (1, 1)$ of $\mathbb{R}^2$ in Example 11 both have $2$ vectors, as Theorem 7 requires. So no list of $3$ vectors is a basis of $\mathbb{R}^2$, which agrees with Example 12: the list $(1, 0), (0, 1), (1, 1)$ spans $\mathbb{R}^2$ but is not linearly independent.

Definition 9 (Dimension)

Definition 9 (Dimension) The dimension of a subspace $\mathcal{S}$, written $\dim(\mathcal{S})$, is the number of vectors in any basis of $\mathcal{S}$ (Definition 6). Theorem 7 makes this number well defined. By convention, the empty list is the basis of $\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\right\}\mathclose{}$, so $\dim(\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\right\}\mathclose{}) = 0$.

Example 16 (The dimensions of some subspaces)

Example 16 (The dimensions of some subspaces)

$\dim(\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\right\}\mathclose{}) = 0$, by the convention in Definition 9.
$\dim(\mathbb{R}^2) = 2$, by Example 11. More generally, $\dim(\mathbb{R}^p) = p$: the indicator vectors $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{e}}\vphantom{e}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{e}}\vphantom{e}}_p$ (Definition 18 in Vectors) are linearly independent, since $c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{e}}\vphantom{e}}_1 + \cdots + c_p \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{e}}\vphantom{e}}_p = (c_1, \ldots, c_p)$, which is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_p$ only if every $c_i = 0$; and they span $\mathbb{R}^p$, since any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = x_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{e}}\vphantom{e}}_1 + \cdots + x_p \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{e}}\vphantom{e}}_p$.
The line in Example 3 has dimension $1$: the single vector $(1, 2)$ is linearly independent and spans the line.
The plane $z = 0$ in Example 6 has dimension $2$, with basis $(1, 0, 0), (0, 1, 0)$.

Theorem 8 (Adding a vector outside the span keeps a list independent)

Theorem 8 (Adding a vector outside the span keeps a list independent) If $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k$ are linearly independent (Definition 1) and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ is not in $\operatorname{span}\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k\right\}\mathclose{}$ (Definition 5), then $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ are linearly independent.

Proof

Proof. Suppose $c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + c_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k + d\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$.

The coefficient $d$ is $0$. If $d \neq 0$, then

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} &= \frac{1}{d}\,\mathopen{}\left(d\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}\right)\mathclose{} && \text{(} d \neq 0 \text{)} \\ &= \frac{1}{d}\,\mathopen{}\left(-c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 - \cdots - c_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k\right)\mathclose{} && \text{(solve the supposed equation for } d\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \text{)} \\ &= \mathopen{}\left(-\frac{c_1}{d}\right)\mathclose{}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + \mathopen{}\left(-\frac{c_k}{d}\right)\mathclose{}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k, && \text{(distribute } \tfrac{1}{d} \text{)} \end{aligned} \]

which puts $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ in $\operatorname{span}\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k\right\}\mathclose{}$, contrary to the assumption.

The other coefficients are $0$. With $d = 0$, the equation reads $c_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + \cdots + c_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$, so every $c_i = 0$, because $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k$ are linearly independent.

Example 17 (Adding $(0, 0, 1)$ to two independent vectors in $\mathbb{R}^3$)

Example 17 (Adding $(0, 0, 1)$ to two independent vectors in $\mathbb{R}^3$) The vectors $(1, 0, 0)$ and $(0, 1, 0)$ are linearly independent, and their span is the plane $z = 0$ (Example 6). The vector $(0, 0, 1)$ has third entry $1$, so it is not in that plane, and by Theorem 8 the three vectors $(1, 0, 0)$, $(0, 1, 0)$, $(0, 0, 1)$ are linearly independent. Adding $(1, 1, 0)$ instead would not work: $(1, 1, 0)$ is in the span, and $(1, 0, 0) + (0, 1, 0) - (1, 1, 0) = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$.

Theorem 9 (An independent list extends to a basis)

Theorem 9 (An independent list extends to a basis) If $\mathcal{S}$ is a subspace of $\mathbb{R}^p$ (Definition 4) and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_k \in \mathcal{S}$ are linearly independent (Definition 1), then adding vectors of $\mathcal{S}$ to the list gives a basis of $\mathcal{S}$ (Definition 6). Starting from the empty list shows that every subspace has a basis.

Proof

Proof. Repeat the following step. If the current list spans $\mathcal{S}$, stop: it is linearly independent and spans $\mathcal{S}$, so it is a basis. Otherwise, some $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \in \mathcal{S}$ is not in the span of the current list; add $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ to the list, which stays linearly independent by Theorem 8.

Every list produced is a linearly independent list of vectors in $\mathbb{R}^p$, so it has at most $p$ vectors (Theorem 5). Each step adds one vector, so the process stops after at most $p - k$ steps, and when it stops the list is a basis of $\mathcal{S}$.

For the empty list, which is linearly independent and spans $\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\right\}\mathclose{}$ by the conventions in Definition 5, the first step asks whether $\mathcal{S} = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\right\}\mathclose{}$: if so, the empty list is already a basis; if not, the process adds vectors as described.

Example 18 (Extending $(1, 1, 0)$ to a basis of $\mathbb{R}^3$)

Example 18 (Extending $(1, 1, 0)$ to a basis of $\mathbb{R}^3$) Start with the single vector $(1, 1, 0)$.

$(1, 0, 0)$ is not in $\operatorname{span}\mathopen{}\left\{(1, 1, 0)\right\}\mathclose{}$, because every multiple $c\,(1, 1, 0)$ has equal first and second entries. Add it.
$(0, 0, 1)$ is not in $\operatorname{span}\mathopen{}\left\{(1, 1, 0), (1, 0, 0)\right\}\mathclose{}$, because every combination of those two vectors has third entry $0$. Add it.
The list $(1, 1, 0), (1, 0, 0), (0, 0, 1)$ spans $\mathbb{R}^3$: $(x, y, z) = y\,(1, 1, 0) + (x - y)\,(1, 0, 0) + z\,(0, 0, 1)$. Stop.

The result is a basis of $\mathbb{R}^3$ that contains the starting vector.

Theorem 10 (An independent list in a subspace has at most $\dim$ vectors)

Theorem 10 (An independent list in a subspace has at most $\dim$ vectors) Let $\mathcal{S}$ be a subspace of $\mathbb{R}^p$ with $\dim(\mathcal{S}) = d$ (Definition 9).

Any linearly independent list of vectors in $\mathcal{S}$ has at most $d$ vectors.
If $\mathcal{T}$ is a subspace with $\mathcal{T} \subseteq \mathcal{S}$, then $\dim(\mathcal{T}) \le \dim(\mathcal{S})$.

Proof

Proof. Part 1. If $d = 0$, then $\mathcal{S} = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\right\}\mathclose{}$, so every vector in a nonempty list from $\mathcal{S}$ is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$, and $1 \cdot\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$ shows the list is not linearly independent; only the empty list, with $0 = d$ vectors, is. Now let $d \ge 1$, and let $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_d$ be a basis of $\mathcal{S}$, and let $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}_k \in \mathcal{S}$ be linearly independent. Each $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}_j$ is in $\mathcal{S}$, so $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}_j = c_{1j} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 + \cdots + c_{dj} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_d$ for some coordinate vector $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_j = (c_{1j}, \ldots, c_{dj}) \in \mathbb{R}^d$. Suppose $k > d$. Then $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_k$ are $k > d$ vectors in $\mathbb{R}^d$, so some $x_1, \ldots, x_k$, not all zero, satisfy $x_1 \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_1 + \cdots + x_k \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_k = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_d$ (Theorem 5); entry $i$ of that equation says $\sum_{j=1}^{k} x_j c_{ij} = 0$. Then

\[ \begin{aligned} \sum_{j=1}^{k} x_j \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}_j &= \sum_{j=1}^{k} x_j \sum_{i=1}^{d} c_{ij} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_i && \text{(substitute each } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}_j \text{)} \\ &= \sum_{j=1}^{k} \sum_{i=1}^{d} x_j c_{ij}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_i && \text{(distribute each } x_j \text{ over the inner sum)} \\ &= \sum_{i=1}^{d} \sum_{j=1}^{k} x_j c_{ij}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_i && \text{(swap the order of the finite sums)} \\ &= \sum_{i=1}^{d} \mathopen{}\left(\sum_{j=1}^{k} x_j c_{ij}\right)\mathclose{}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_i && \text{(factor } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_i \text{ out of the inner sum)} \\ &= \sum_{i=1}^{d} 0 \cdot\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_i && \text{(entry } i \text{ of } \textstyle\sum_j x_j \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_j = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_d \text{)} \\ &= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_p, && \text{(a zero multiple of a vector is } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\text{)} \end{aligned} \]

a combination of $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}_k$ with coefficients not all zero that equals $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_p$. That contradicts their linear independence, so $k \le d$.

Part 2. $\mathcal{T}$ has a basis (Theorem 9) with $\dim(\mathcal{T})$ vectors. Those vectors are linearly independent and lie in $\mathcal{S}$, so by Part 1 there are at most $\dim(\mathcal{S})$ of them.

Example 19 (Subspaces of a plane have dimension at most two)

Example 19 (Subspaces of a plane have dimension at most two) The plane $\mathcal{S} = \mathopen{}\left\{(x, y, 0) : x, y \in \mathbb{R}\right\}\mathclose{}$ in $\mathbb{R}^3$ has dimension $2$ (Example 16). By Theorem 10, no three vectors with third entry $0$ are linearly independent; for instance, $(1, 0, 0) + (0, 1, 0) - (1, 1, 0) = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$. The line $\mathcal{T} = \operatorname{span}\mathopen{}\left\{(1, 1, 0)\right\}\mathclose{}$ lies in $\mathcal{S}$, and

\[ \begin{aligned} \dim(\mathcal{T}) &= 1 \\ &\le 2 \\ &= \dim(\mathcal{S}). \end{aligned} \]

Theorem 11 (A subspace inside another of the same dimension equals it)

Theorem 11 (A subspace inside another of the same dimension equals it) If $\mathcal{T}$ and $\mathcal{S}$ are subspaces of $\mathbb{R}^p$ with $\mathcal{T} \subseteq \mathcal{S}$ and $\dim(\mathcal{T}) = \dim(\mathcal{S})$ (Definition 9), then $\mathcal{T} = \mathcal{S}$.

Proof

Proof. Let $d = \dim(\mathcal{S})$, and let $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{t}}\vphantom{t}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{t}}\vphantom{t}}_d$ be a basis of $\mathcal{T}$ (Theorem 9); it has $d$ vectors because $\dim(\mathcal{T}) = d$. (When $d = 0$ it is the empty list, whose span is $\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\right\}\mathclose{}$ by the convention in Definition 5, and the argument is unchanged.) Suppose some $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} \in \mathcal{S}$ is not in $\operatorname{span}\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{t}}\vphantom{t}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{t}}\vphantom{t}}_d\right\}\mathclose{} = \mathcal{T}$. Then $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{t}}\vphantom{t}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{t}}\vphantom{t}}_d, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}}$ are linearly independent (Theorem 8), and they are $d + 1$ vectors of $\mathcal{S}$, which contradicts part 1 of Theorem 10. So every vector of $\mathcal{S}$ is in $\mathcal{T}$, that is, $\mathcal{S} \subseteq \mathcal{T}$. Together with $\mathcal{T} \subseteq \mathcal{S}$, this inclusion gives $\mathcal{T} = \mathcal{S}$.

Example 20 (Two independent vectors in a plane span it)

Example 20 (Two independent vectors in a plane span it) Let $\mathcal{S} = \mathopen{}\left\{(x, y, 0) : x, y \in \mathbb{R}\right\}\mathclose{}$, the plane $z = 0$, which has dimension $2$ (Example 16), and let $\mathcal{T} = \operatorname{span}\mathopen{}\left\{(1, 0, 0), (1, 1, 0)\right\}\mathclose{}$. Both vectors have third entry $0$, so $\mathcal{T} \subseteq \mathcal{S}$. They are linearly independent: $c_1 (1, 0, 0) + c_2 (1, 1, 0) = (c_1 + c_2, c_2, 0)$, which is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$ only if $c_2 = 0$ and then $c_1 = 0$. So $\dim(\mathcal{T}) = 2$, and Theorem 11 gives $\mathcal{T} = \mathcal{S}$ without solving for any coefficients. As a check, $(x, y, 0) = (x - y)\,(1, 0, 0) + y\,(1, 1, 0)$.

Example 21 (Equal dimensions without containment)

Example 21 (Equal dimensions without containment) The lines $\operatorname{span}\mathopen{}\left\{(1, 0, 0)\right\}\mathclose{}$ and $\operatorname{span}\mathopen{}\left\{(0, 1, 0)\right\}\mathclose{}$ in $\mathbb{R}^3$ both have dimension $1$, but they are not equal: $(1, 0, 0)$ is in the first and not the second. Theorem 11 does not apply, because neither line contains the other.

References

[1]

Wikipedia contributors, “Linear independence — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Linear_independence

[2]

Wikipedia contributors, “Rank (linear algebra) — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Rank_(linear_algebra)

[3]

H. Zhou, “Vector space.” Lecture notes for Biostat 216, Mathematical Methods for Biostatistics, University of California, Los Angeles, 2024. Accessed: Oct. 05, 2026. [Online]. Available: https://ucla-biostat-216.github.io/2024fall/slides/04-vecsp/04-vecsp.html

[4]

Wikipedia contributors, “Linear subspace — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Linear_subspace

[5]

Wikipedia contributors, “Linear span — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Linear_span

[6]

Wikipedia contributors, “Basis (linear algebra) — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Basis_(linear_algebra)

[7]

Wikipedia contributors, “Coordinate vector — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Coordinate_vector