Column Space, Null Space and Rank-Nullity

Published

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

1 Column space and null space

Definition 1 (Column space, range, image)

Definition 1 (Column space, range, image) The column space [1] of an $m \times n$ matrix $\mathbf{A}$ is

\[ \mathcal{C}(\mathbf{A}) \stackrel{\text{def}}{=} \mathopen{}\left\{\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} : \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \in \mathbb{R}^n\right\}\mathclose{}, \]

the set of all vectors $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ in $\mathbb{R}^m$. It is also called the range or image of $\mathbf{A}$.

Definition 2 (Row space)

Definition 2 (Row space) The row space of an $m \times n$ matrix $\mathbf{A}$ is $\mathcal{C}({\mathbf{A}}^{\top})$, a set of vectors in $\mathbb{R}^n$.

Example 1 (The column space of a rank-one matrix)

Example 1 (The column space of a rank-one matrix) Let

\[ \mathbf{A} = \begin{bmatrix} 1 & -2 & -2 \\ 3 & -6 & -6 \end{bmatrix}. \]

For any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \in \mathbb{R}^3$,

\[ \begin{aligned} \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} &= (x_1 - 2x_2 - 2x_3,\; 3\,(x_1 - 2x_2 - 2x_3)) \\ &= (x_1 - 2x_2 - 2x_3)\,(1, 3) \end{aligned} \]

(Definition 13 in Matrices). The number $x_1 - 2x_2 - 2x_3$ can be any real number (take $x_2 = 0$ and $x_3 = 0$), so $\mathcal{C}(\mathbf{A}) = \mathopen{}\left\{c\,(1, 3) : c \in \mathbb{R}\right\}\mathclose{}$, a line in $\mathbb{R}^2$. The vector $(1, 0)$ is not in $\mathcal{C}(\mathbf{A})$: $c\,(1, 3)$ has second entry $3c$, which is $0$ only if $c = 0$, and then the first entry is $0$, not $1$.

Theorem 1 (The column space is the span of the columns)

Theorem 1 (The column space is the span of 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$, then

\[ \mathcal{C}(\mathbf{A}) = \operatorname{span}\mathopen{}\left\{\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\right\}\mathclose{}, \]

so $\mathcal{C}(\mathbf{A})$ is a subspace of $\mathbb{R}^m$, and the row space $\mathcal{C}({\mathbf{A}}^{\top})$ is a subspace of $\mathbb{R}^n$.

Proof

Proof. By Theorem 3 in Subspaces and Rank, $\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$, and as $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ ranges over $\mathbb{R}^n$, the coefficients $x_1, \ldots, x_n$ range over all lists of $n$ numbers. So the set of all $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ (Definition 1) is the set of all linear combinations of the columns, which is their span (Definition 5 in Subspaces and Rank). A span is a subspace (Theorem 2 in Subspaces and Rank). Applying the same argument to ${\mathbf{A}}^{\top}$, whose columns are the rows of $\mathbf{A}$, shows the row space is a subspace of $\mathbb{R}^n$.

Example 2 (Reading off the column space and row space from the columns and rows)

Example 2 (Reading off the column space and row space from the columns and rows) For $\mathbf{A}$ in Example 1, the columns are $(1, 3)$, $(-2, -6) = -2\,(1, 3)$ and $(-2, -6) = -2\,(1, 3)$, so by Theorem 1 $\mathcal{C}(\mathbf{A}) = \operatorname{span}\mathopen{}\left\{(1, 3)\right\}\mathclose{}$, the same line found in Example 1. The rows are $(1, -2, -2)$ and $(3, -6, -6) = 3\,(1, -2, -2)$, so the row space is $\operatorname{span}\mathopen{}\left\{(1, -2, -2)\right\}\mathclose{}$, a line in $\mathbb{R}^3$.

Definition 3 (Null space, kernel)

Definition 3 (Null space, kernel) The null space of an $m \times n$ matrix $\mathbf{A}$ is

\[ \mathcal{N}(\mathbf{A}) \stackrel{\text{def}}{=} \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \in \mathbb{R}^n : \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m\right\}\mathclose{}, \]

the set of solutions of the linear system $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$. It is also called the kernel of $\mathbf{A}$.

Definition 4 (Left null space)

Definition 4 (Left null space) The left null space of an $m \times n$ matrix $\mathbf{A}$ is $\mathcal{N}({\mathbf{A}}^{\top})$, a set of vectors in $\mathbb{R}^m$.

Example 3 (The null space and left null space of a rank-one matrix)

Example 3 (The null space and left null space of a rank-one matrix) For $\mathbf{A}$ in Example 1, $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = (x_1 - 2x_2 - 2x_3,\; 3\,(x_1 - 2x_2 - 2x_3))$, so $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_2$ exactly when $x_1 = 2x_2 + 2x_3$. Writing

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} &= (2x_2 + 2x_3, x_2, x_3) \\ &= x_2\,(2, 1, 0) + x_3\,(2, 0, 1) \end{aligned} \]

shows $\mathcal{N}(\mathbf{A}) = \operatorname{span}\mathopen{}\left\{(2, 1, 0), (2, 0, 1)\right\}\mathclose{}$, a plane in $\mathbb{R}^3$.

For the left null space, ${\mathbf{A}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}} = (y_1 + 3y_2,\; -2\,(y_1 + 3y_2),\; -2\,(y_1 + 3y_2))$, which is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_3$ exactly when $y_1 = -3y_2$, so $\mathcal{N}({\mathbf{A}}^{\top}) = \operatorname{span}\mathopen{}\left\{(-3, 1)\right\}\mathclose{}$, a line in $\mathbb{R}^2$.

Theorem 2 (A null space is a subspace)

Theorem 2 (A null space is a subspace) For any $m \times n$ matrix $\mathbf{A}$, $\mathcal{N}(\mathbf{A})$ (Definition 3) is a subspace of $\mathbb{R}^n$ (Definition 4 in Subspaces and Rank).

Proof

Proof. $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$, so $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n \in \mathcal{N}(\mathbf{A})$, and the null space is not empty. If $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \in \mathcal{N}(\mathbf{A})$ and $c \in \mathbb{R}$, then

\[ \begin{aligned} \mathbf{A}\,(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}) &= \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} + \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} && \text{(}\href{linear-algebra-matrices.qmd#thm-matmul-distrib}{\text{Theorem~6 in Matrices}}\text{)} \\ &= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m && \text{(} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} \text{ and } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \text{ are in the null space)} \\ &= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m && \text{(adding } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m \text{ changes nothing)} \end{aligned} \]

and, for each entry $i = 1, \ldots, m$,

\[ \begin{aligned} \mathopen{}\left(\mathbf{A}\,(c \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}})\right)\mathclose{}_i &= a_{i1} (c u_1) + \cdots + a_{in} (c u_n) && \text{(}\href{linear-algebra-matrices.qmd#def-matvec-mult}{\text{Definition~13 in Matrices}}\text{)} \\ &= c\,(a_{i1} u_1 + \cdots + a_{in} u_n) && \text{(factor } c \text{ out of each term)} \\ &= c\,(\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}})_i && \text{(}\href{linear-algebra-matrices.qmd#def-matvec-mult}{\text{Definition~13 in Matrices}}\text{)} \\ &= c \cdot 0 && \text{(} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} \text{ is in the null space)} \\ &= 0, && \text{(arithmetic)} \end{aligned} \]

so $\mathbf{A}\,(c \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}) = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$. Therefore $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ and $c \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}$ are in $\mathcal{N}(\mathbf{A})$.

Example 4 (The solutions of $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}$ with $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}} \neq \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$ are not a subspace) In Example 3, $(2, 1, 0)$ and $(2, 0, 1)$ are in $\mathcal{N}(\mathbf{A})$, and so is their sum $(4, 1, 1)$, since $4 - 2 \cdot 1 - 2 \cdot 1 = 0$. By contrast, the solutions of $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = (1, 3)$ for the same $\mathbf{A}$ are the vectors with $x_1 - 2x_2 - 2x_3 = 1$. That set does not contain $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_3$, so by Theorem 1 in Subspaces and Rank it is not a subspace.

Theorem 3 (Independent columns exactly when the null space is trivial)

Theorem 3 (Independent columns exactly when the null space is trivial) For an $m \times n$ matrix $\mathbf{A}$, the following are equivalent:

The columns of $\mathbf{A}$ are linearly independent (Definition 1 in Subspaces and Rank).
$\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$ only for $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n$.
$\mathcal{N}(\mathbf{A}) = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n\right\}\mathclose{}$ (Definition 3).

So $\mathbf{A}$ has full column rank (Definition 3 in Subspaces and Rank) exactly when its null space contains only the zero vector.

Proof

Proof. Write $\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$ for the columns of $\mathbf{A}$. For $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = (x_1, \ldots, x_n)$, the matrix-vector product is the combination of the columns with weights $x_1, \ldots, x_n$:

\[ \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. \]

So $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$ says exactly that $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 = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$. By Definition 1 in Subspaces and Rank, the columns are linearly independent exactly when the only weights with this property are $x_1 = \cdots = x_n = 0$. That is statement 2, so statements 1 and 2 are equivalent. Statement 2 says that the only vector in $\mathcal{N}(\mathbf{A})$ is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n$, which is statement 3. The last sentence is the definition of full column rank (Definition 3 in Subspaces and Rank).

Example 5 (Checking independence through the null space)

Example 5 (Checking independence through the null space) For $\mathbf{A} = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}$,

\[ \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \begin{bmatrix} x_1 + x_2 \\ x_1 + 2 x_2 \\ x_1 + 3 x_2 \end{bmatrix}. \]

This is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_3$ only if $x_2 = 0$ (subtract the first entry from the second), and then $x_1 = 0$. So $\mathcal{N}(\mathbf{A}) = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_2\right\}\mathclose{}$ and the two columns are linearly independent.

For $\mathbf{B} = \begin{bmatrix} 1 & 2 \\ 1 & 2 \\ 1 & 2 \end{bmatrix}$, $\mathbf{B} (2, -1) = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_3$, so $\mathcal{N}(\mathbf{B})$ contains a nonzero vector and the columns of $\mathbf{B}$ are linearly dependent.

Theorem 4 (The row space and null space share only the zero vector)

Theorem 4 (The row space and null space share only the zero vector) For any $m \times n$ matrix $\mathbf{A}$,

\[ \mathcal{C}({\mathbf{A}}^{\top}) \cap \mathcal{N}(\mathbf{A}) = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n\right\}\mathclose{}. \]

Proof

Proof. Both sets are subspaces, by Theorem 1 and Theorem 2, so both contain $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n$ (Theorem 1 in Subspaces and Rank).

Now take any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ in both sets. Being in the row space means $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = {\mathbf{A}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}$ for some $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} \in \mathbb{R}^m$ (Definition 1), and being in the null space means $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$ (Definition 3). Then

\[ \begin{aligned} {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} &= {({\mathbf{A}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}})}^{\top}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} && \text{(substitute } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = {\mathbf{A}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} \text{ in the first factor)} \\ &= \mathopen{}\left({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\,{({\mathbf{A}}^{\top})}^{\top}\right)\mathclose{}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} && \text{(}\href{linear-algebra-matrices.qmd#thm-transpose-product}{\text{Theorem~17 in Matrices}}\text{)} \\ &= \mathopen{}\left({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top} \mathbf{A}\right)\mathclose{}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} && \text{(transposing twice returns the original matrix)} \\ &= {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\,(\mathbf{A} \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{)} \\ &= {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}}}^{\top}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m && \text{(substitute } \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m \text{)} \\ &= 0. && \text{(every term of the inner product is } 0 \text{)} \end{aligned} \]

But ${\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = x_1^2 + \cdots + x_n^2$, which is $0$ only when every $x_i = 0$. 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}}_n$.

Example 6 (The row space and null space in Example 3)

Example 6 (The row space and null space in Example 3) For $\mathbf{A}$ in Example 1, the row space is $\operatorname{span}\mathopen{}\left\{(1, -2, -2)\right\}\mathclose{}$ and the null space is $\operatorname{span}\mathopen{}\left\{(2, 1, 0), (2, 0, 1)\right\}\mathclose{}$ (Example 3). A vector $c\,(1, -2, -2)$ of the row space is in the null space only if

\[ \begin{aligned} \mathbf{A}\,\mathopen{}\left(c\,(1, -2, -2)\right)\mathclose{} &= c\,\mathopen{}\left(1 - 2 \cdot(-2) - 2 \cdot(-2),\; 3\,(1 - 2 \cdot(-2) - 2 \cdot(-2))\right)\mathclose{} && \text{(}\href{#exm-null-space}{\text{Example~3}}\text{'s formula for } \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \text{)} \\ &= c\,(9, 27) && \text{(arithmetic)} \end{aligned} \]

is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_2$, that is, only if $c = 0$. So the two subspaces share only $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_3$.

Definition 5 (Cross-product matrix)

Definition 5 (Cross-product matrix) Let $\mathbf{A}$ be 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 $\mathbf{B}$ an $m \times q$ 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}}_q$. The cross-product matrix of $\mathbf{A}$ and $\mathbf{B}$ is the $n \times q$ matrix ${\mathbf{A}}^{\top} \mathbf{B}$, whose entry $(i, j)$ is the dot product $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_i \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}_j$.

This is what R’s crossprod(A, B) computes, and crossprod(A) is ${\mathbf{A}}^{\top} \mathbf{A}$. In NumPy it has no name of its own: write A.T @ B.

For two column vectors it is the $1 \times 1$ matrix holding their dot product. It is unrelated to the cross product $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{u}}\vphantom{u}} \times \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}$ of two vectors in $\mathbb{R}^3$, and differs from the Frobenius inner product $\operatorname{tr}\mathopen{}\left({\mathbf{A}}^{\top} \mathbf{B}\right)\mathclose{}$, which sums the diagonal of this matrix into a single number.

Example 7 (A cross-product matrix)

Example 7 (A cross-product matrix) Let $\mathbf{A} = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix}$ and $\mathbf{B} = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}$. Then ${\mathbf{A}}^{\top} \mathbf{B}$ is $2 \times 1$, and

\[ \begin{aligned} {\mathbf{A}}^{\top} \mathbf{B} &= \begin{bmatrix} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}_1 \\ \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_2 \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{b}}\vphantom{b}}_1 \end{bmatrix} && \text{(}\href{#def-cross-product-matrix}{\text{Definition~5}}\text{)} \\ &= \begin{bmatrix} 1 + 2 + 0 \\ 0 + 2 + 3 \end{bmatrix} && \text{(multiply and add)} \\ &= \begin{bmatrix} 3 \\ 5 \end{bmatrix}. && \text{(add)} \end{aligned} \]

Definition 6 (Gram matrix)

Definition 6 (Gram matrix) The Gram matrix [2] of an $m \times n$ matrix $\mathbf{A}$ is the $n \times n$ matrix ${\mathbf{A}}^{\top} \mathbf{A}$, the cross-product matrix of $\mathbf{A}$ with itself.

Example 8 (A Gram matrix and its entries)

Example 8 (A Gram matrix and its entries) Let $\mathbf{A} = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix}$, with columns $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 = (1, 1, 0)$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_2 = (0, 1, 1)$. Then

\[ \begin{aligned} {\mathbf{A}}^{\top} \mathbf{A} &= \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{bmatrix} && \text{(}\href{linear-algebra-matrices.qmd#def-matrix-transpose}{\text{Definition~3 in Matrices}}\text{)} \\ &= \begin{bmatrix} 1 \cdot 1 + 1 \cdot 1 + 0 \cdot 0 & 1 \cdot 0 + 1 \cdot 1 + 0 \cdot 1 \\ 0 \cdot 1 + 1 \cdot 1 + 1 \cdot 0 & 0 \cdot 0 + 1 \cdot 1 + 1 \cdot 1 \end{bmatrix} && \text{(}\href{linear-algebra-matrices.qmd#def-matrix-mult}{\text{Definition~7 in Matrices}}\text{)} \\ &= \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}. && \text{(multiply and add)} \end{aligned} \]

Row $i$ of ${\mathbf{A}}^{\top}$ is column $i$ of $\mathbf{A}$, so entry $(i, j)$ of the Gram matrix is the dot product $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_i \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_j$: for instance,

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_1 \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_2 &= 0 + 1 + 0 \\ &= 1 \end{aligned} \]

is entry $(1, 2)$.

Theorem 5 (${\mathbf{A}}^{\top} \mathbf{A}$ has the same null space as $\mathbf{A}$)

Theorem 5 (${\mathbf{A}}^{\top} \mathbf{A}$ has the same null space as $\mathbf{A}$) For any $m \times n$ matrix $\mathbf{A}$,

\[ \mathcal{N}({\mathbf{A}}^{\top} \mathbf{A}) = \mathcal{N}(\mathbf{A}). \]

Proof

Proof. $\mathcal{N}(\mathbf{A}) \subseteq \mathcal{N}({\mathbf{A}}^{\top} \mathbf{A})$. If $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$, then

\[ \begin{aligned} {\mathbf{A}}^{\top} \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} &= {\mathbf{A}}^{\top}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m \\ &= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n. \end{aligned} \]

$\mathcal{N}({\mathbf{A}}^{\top} \mathbf{A}) \subseteq \mathcal{N}(\mathbf{A})$. If ${\mathbf{A}}^{\top} \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n$, then

\[ \begin{aligned} 0 &= {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}^{\top}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n && \text{(every term of the inner product is } 0 \text{)} \\ &= {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}^{\top}\,\mathopen{}\left({\mathbf{A}}^{\top} \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\right)\mathclose{} && \text{(substitute } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n = {\mathbf{A}}^{\top} \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \text{)} \\ &= \mathopen{}\left({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}^{\top} {\mathbf{A}}^{\top}\right)\mathclose{}\,(\mathbf{A} \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{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}})}^{\top}\,(\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}) && \text{(}\href{linear-algebra-matrices.qmd#thm-transpose-product}{\text{Theorem~17 in Matrices}}\text{)} \\ &= (\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}) \cdot (\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}) && \text{(}\href{linear-algebra-matrices.qmd#exm-dot-product-matmul}{\text{Example~6 in Matrices}}\text{)} \\ &= \mathopen{}\left\lVert\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\right\rVert\mathclose{}^2. && \text{(square both sides of }\href{linear-algebra-vectors.qmd#eq-l2-norm}{\text{Equation~2 in Vectors}}\text{)} \end{aligned} \]

A vector whose Euclidean norm is $0$ has every entry $0$, so $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$.

Example 9 (The null space of a Gram matrix)

Example 9 (The null space of a Gram matrix) For $\mathbf{A}$ in Example 1,

\[ \begin{aligned} {\mathbf{A}}^{\top} \mathbf{A} &= \begin{bmatrix} 1 & 3 \\ -2 & -6 \\ -2 & -6 \end{bmatrix} \begin{bmatrix} 1 & -2 & -2 \\ 3 & -6 & -6 \end{bmatrix} \\ &= \begin{bmatrix} 10 & -20 & -20 \\ -20 & 40 & 40 \\ -20 & 40 & 40 \end{bmatrix}. \end{aligned} \]

Every row is a multiple of $(1, -2, -2)$, so ${\mathbf{A}}^{\top} \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_3$ exactly when $x_1 - 2x_2 - 2x_3 = 0$, the same condition as for $\mathcal{N}(\mathbf{A})$ in Example 3.

2 Rank-nullity and rank factorization

Source

This section is adapted from Zhou [3], used under the MIT License (see the license text in Section 2 in Subspaces and Rank). Theorem 10 and Corollary 2 restore the source’s statements that a product has rank at most the rank of either factor, and that multiplying by a matrix of full column rank or by a matrix whose rank is its number of rows does not change the rank. These parts of the source are not part of this section:

the names “full row rank”, “full rank” and “singular”
the statement that $\mathcal{C}(\mathbf{C}) \subseteq \mathcal{C}(\mathbf{A})$ exactly when $\mathbf{C} = \mathbf{A}\mathbf{B}$ for some $\mathbf{B}$, and its row space version, and the containment $\mathcal{N}(\mathbf{B}) \subseteq \mathcal{N}(\mathbf{A}\mathbf{B})$
the dimension of a subspace as the largest number of linearly independent vectors in it, or the smallest number of vectors that span it
the properties of a rank factorization $\mathbf{A} = \mathbf{C}\mathbf{R}$ ($\operatorname{rank}(\mathbf{C}) = \operatorname{rank}(\mathbf{R}) = r$, $\mathcal{C}(\mathbf{A}) = \mathcal{C}(\mathbf{C})$, $\mathcal{N}(\mathbf{A}) = \mathcal{N}(\mathbf{R})$), the fact that it is not unique, and the second proof of $\operatorname{rank}(\mathbf{A}) = \operatorname{rank}({\mathbf{A}}^{\top})$ that it gives
calling $\mathbf{A}{\mathbf{A}}^{\top}$ a Gram matrix, and the equation $\mathcal{N}(\mathbf{A}{\mathbf{A}}^{\top}) = \mathcal{N}({\mathbf{A}}^{\top})$ (Theorem 5 applied to ${\mathbf{A}}^{\top}$ gives it)
the statement that $\mathcal{C}(\mathbf{A})$ and $\mathcal{N}({\mathbf{A}}^{\top})$ share only the zero vector (it follows from Theorem 10 in Direct Sums and Orthogonal Complements)

Theorem 6 (The rank is the dimension of the column space)

Theorem 6 (The rank is the dimension of the column space) For any $m \times n$ matrix $\mathbf{A}$,

\[ \operatorname{rank}(\mathbf{A}) = \dim\mathopen{}\left(\mathcal{C}(\mathbf{A})\right)\mathclose{}. \]

Proof

Proof. Let $r = \operatorname{rank}(\mathbf{A})$ (Definition 2 in Subspaces and Rank), and choose $r$ linearly independent columns of $\mathbf{A}$; by Definition 2 in Subspaces and Rank, no larger set of columns is linearly independent. We show the chosen columns are a basis of $\mathcal{C}(\mathbf{A})$ (Definition 6 in Subspaces and Rank).

Every column is in the span of the chosen columns. A chosen column is in that span trivially. If some unchosen column $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_j$ were not in the span, then adding it to the chosen columns would give $r + 1$ linearly independent columns (Theorem 8 in Subspaces and Rank), more than $r$. So every column of $\mathbf{A}$ is in the span of the chosen columns.

The chosen columns span $\mathcal{C}(\mathbf{A})$. The span of the chosen columns is a subspace (Theorem 2 in Subspaces and Rank), so it is closed under addition and scalar multiplication, and it contains every linear combination of the columns of $\mathbf{A}$. By Theorem 1, those combinations make up $\mathcal{C}(\mathbf{A})$, so $\mathcal{C}(\mathbf{A})$ is contained in the span of the chosen columns. The chosen columns are themselves columns of $\mathbf{A}$, so their span is contained in $\mathcal{C}(\mathbf{A})$, and the two sets are equal.

The chosen columns are linearly independent and span $\mathcal{C}(\mathbf{A})$, so they are a basis of it, and $\dim\mathopen{}\left(\mathcal{C}(\mathbf{A})\right)\mathclose{} = r$ (Definition 9 in Subspaces and Rank). If $r = 0$, every column is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$, $\mathcal{C}(\mathbf{A}) = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m\right\}\mathclose{}$, and both sides are $0$.

Example 10 (The rank of the matrix in Example 1)

Example 10 (The rank of the matrix in Example 1) For $\mathbf{A}$ in Example 1, $\mathcal{C}(\mathbf{A}) = \operatorname{span}\mathopen{}\left\{(1, 3)\right\}\mathclose{}$ (Example 2), and $(1, 3)$ is linearly independent because it is nonzero, so it is a basis and $\mathcal{C}(\mathbf{A})$ has dimension $1$. So $\operatorname{rank}(\mathbf{A}) = 1$, by Theorem 6. Directly: the first column $(1, 3)$ is linearly independent on its own, and any two columns are dependent, because each column is a multiple of $(1, 3)$.

Definition 7 (Nullity)

Definition 7 (Nullity) The nullity [4] of a matrix $\mathbf{A}$ is the dimension of its null space (Definition 3):

\[ \operatorname{nullity}(\mathbf{A}) \stackrel{\text{def}}{=}\dim\mathopen{}\left(\mathcal{N}(\mathbf{A})\right)\mathclose{}. \]

Example 11 (The nullity of the matrix in Example 1)

Example 11 (The nullity of the matrix in Example 1) For $\mathbf{A}$ in Example 1, $\mathcal{N}(\mathbf{A}) = \operatorname{span}\mathopen{}\left\{(2, 1, 0), (2, 0, 1)\right\}\mathclose{}$ (Example 3). Those two vectors are linearly independent: $c_1 (2, 1, 0) + c_2 (2, 0, 1) = (2c_1 + 2c_2, c_1, c_2)$, which is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_3$ only if

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

So they are a basis of $\mathcal{N}(\mathbf{A})$, and $\operatorname{nullity}(\mathbf{A}) = 2$. The $2 \times 2$ identity matrix has nullity $0$, because $\mathbf{I} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_2$ only when $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_2$.

Theorem 7 (Rank-nullity theorem)

Theorem 7 (Rank-nullity theorem) For any $m \times n$ matrix $\mathbf{A}$,

\[ \operatorname{rank}(\mathbf{A}) + \operatorname{nullity}(\mathbf{A}) = n. \]

Proof

Proof. Let $\nu= \operatorname{nullity}(\mathbf{A})$. Choose a basis $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_\nu$ of $\mathcal{N}(\mathbf{A})$, and extend it to a basis $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_\nu, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_1, \ldots, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_{n - \nu}$ of $\mathbb{R}^n$ (Theorem 9 in Subspaces and Rank); it has $n$ vectors, because every basis of $\mathbb{R}^n$ has $\dim(\mathbb{R}^n) = n$ vectors (Theorem 7 in Subspaces and Rank, Example 16 in Subspaces and Rank). We show that $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_1, \ldots, \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_{n - \nu}$ are a basis of $\mathcal{C}(\mathbf{A})$, using Theorem 4 in Subspaces and Rank to apply $\mathbf{A}$ to linear combinations.

They are linearly independent. Suppose $\sum_{i=1}^{n-\nu} v_i\,\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_i = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$. Then $\mathbf{A}\,\mathopen{}\left(\sum_i v_i \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_i\right)\mathclose{} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$ (Theorem 4 in Subspaces and Rank), so $\sum_i v_i \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_i \in \mathcal{N}(\mathbf{A})$, and it equals $\sum_{j=1}^{\nu} u_j \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_j$ for some numbers $u_j$, since the $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_j$ span $\mathcal{N}(\mathbf{A})$. Moving everything to one side,

\[ \sum_{j=1}^{\nu} (-u_j)\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_j + \sum_{i=1}^{n-\nu} v_i \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_i = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n, \]

and because the $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$’s and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}$’s together form a basis of $\mathbb{R}^n$, which is linearly independent, every coefficient is $0$; in particular every $v_i = 0$.

They span $\mathcal{C}(\mathbf{A})$. Take any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \in \mathcal{C}(\mathbf{A})$, so $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} = \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}}$ for some $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}} \in \mathbb{R}^n$ (Definition 1). Write $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}} = \sum_j a_j \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_j + \sum_i b_i \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_i$ in the basis of $\mathbb{R}^n$. Then

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} &= \mathbf{A}\,\mathopen{}\left(\sum_{j=1}^{\nu} a_j \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_j + \sum_{i=1}^{n-\nu} b_i \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_i\right)\mathclose{} && \text{(substitute } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{z}}\vphantom{z}} \text{)} \\ &= \sum_{j=1}^{\nu} a_j\,\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_j + \sum_{i=1}^{n-\nu} b_i\,\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_i && \text{(}\href{linear-algebra-subspaces.qmd#thm-matvec-linear}{\text{Theorem~4 in Subspaces and Rank}}\text{)} \\ &= \sum_{j=1}^{\nu} a_j\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m + \sum_{i=1}^{n-\nu} b_i\,\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_i && \text{(each } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_j \in \mathcal{N}(\mathbf{A}) \text{)} \\ &= \sum_{i=1}^{n-\nu} b_i\,\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_i, && \text{(drop the zero terms)} \end{aligned} \]

a linear combination of $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_1, \ldots, \mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}_{n-\nu}$. These vectors are in $\mathcal{C}(\mathbf{A})$, so their span is exactly $\mathcal{C}(\mathbf{A})$.

So $\dim\mathopen{}\left(\mathcal{C}(\mathbf{A})\right)\mathclose{} = n - \nu$, and $\operatorname{rank}(\mathbf{A}) = n - \nu$ by Theorem 6.

Example 12 (Checking rank-nullity on the matrix in Example 1)

Example 12 (Checking rank-nullity on the matrix in Example 1) The matrix $\mathbf{A}$ in Example 1 has $n = 3$ columns, rank $1$ (Example 10) and nullity $2$ (Example 11), and $1 + 2 = 3$. The $2 \times 2$ identity matrix has rank $2$ and nullity $0$ (Example 11), and $2 + 0 = 2$.

Theorem 8 (Multiplying on the right cannot increase the rank)

Theorem 8 (Multiplying on the right cannot increase the rank) If $\mathbf{A}$ is $m \times n$ and $\mathbf{B}$ is $n \times k$, then

\[ \operatorname{rank}(\mathbf{A} \mathbf{B}) \le \operatorname{rank}(\mathbf{A}). \]

Proof

Proof. $\mathcal{C}(\mathbf{A} \mathbf{B}) \subseteq \mathcal{C}(\mathbf{A})$. Any vector in $\mathcal{C}(\mathbf{A} \mathbf{B})$ is $(\mathbf{A} \mathbf{B})\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ for some $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \in \mathbb{R}^k$ (Definition 1), and

\[ \begin{aligned} (\mathbf{A} \mathbf{B})\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} &= \mathbf{A}\,(\mathbf{B} \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{)} \end{aligned} \]

is $\mathbf{A}$ times the vector $\mathbf{B} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \in \mathbb{R}^n$, so it is in $\mathcal{C}(\mathbf{A})$.

Compare dimensions. Both column spaces are subspaces (Theorem 1), so

\[ \begin{aligned} \operatorname{rank}(\mathbf{A} \mathbf{B}) &= \dim\mathopen{}\left(\mathcal{C}(\mathbf{A} \mathbf{B})\right)\mathclose{} && \text{(}\href{#thm-rank-dim}{\text{Theorem~6}}\text{)} \\ &\le \dim\mathopen{}\left(\mathcal{C}(\mathbf{A})\right)\mathclose{} && \text{(}\href{linear-algebra-subspaces.qmd#thm-dim-bound}{\text{Theorem~10 in Subspaces and Rank}}\text{, part 2)} \\ &= \operatorname{rank}(\mathbf{A}). && \text{(}\href{#thm-rank-dim}{\text{Theorem~6}}\text{)} \end{aligned} \]

Example 13 (A product can lose rank)

Example 13 (A product can lose rank) Let

\[ \mathbf{A} = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}, \qquad \mathbf{B} = \begin{bmatrix} 0 & 0 \\ 1 & 0 \end{bmatrix}, \qquad \mathbf{A} \mathbf{B} = \begin{bmatrix} 1 \cdot 0 + 0 \cdot 1 & 1 \cdot 0 + 0 \cdot 0 \\ 0 \cdot 0 + 0 \cdot 1 & 0 \cdot 0 + 0 \cdot 0 \end{bmatrix} = \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}. \]

$\mathbf{A}$ has rank $1$, but $\mathbf{A} \mathbf{B}$ has rank $0$, so the inequality in Theorem 8 can be strict. With the $2 \times 2$ identity in place of $\mathbf{B}$, $\mathbf{A} \mathbf{I} = \mathbf{A}$ keeps rank $1$, and the inequality is an equality.

Theorem 9 (Fundamental theorem of ranks)

Theorem 9 (Fundamental theorem of ranks) For any $m \times n$ matrix $\mathbf{A}$,

\[ \begin{aligned} \operatorname{rank}(\mathbf{A}) &= \operatorname{rank}({\mathbf{A}}^{\top}) \\ &= \operatorname{rank}({\mathbf{A}}^{\top} \mathbf{A}) \\ &= \operatorname{rank}(\mathbf{A} {\mathbf{A}}^{\top}). \end{aligned} \]

In particular, the largest number of linearly independent rows of $\mathbf{A}$ equals the largest number of linearly independent columns.

Proof

Proof. $\operatorname{rank}({\mathbf{A}}^{\top} \mathbf{A}) = \operatorname{rank}(\mathbf{A})$. Both matrices have $n$ columns, and $\mathcal{N}({\mathbf{A}}^{\top} \mathbf{A}) = \mathcal{N}(\mathbf{A})$ (Theorem 5), so they have the same nullity (Definition 7). Then

\[ \begin{aligned} \operatorname{rank}({\mathbf{A}}^{\top} \mathbf{A}) &= n - \operatorname{nullity}({\mathbf{A}}^{\top} \mathbf{A}) && \text{(}\href{#thm-rank-nullity}{\text{Theorem~7}}\text{)} \\ &= n - \operatorname{nullity}(\mathbf{A}) && \text{(equal null spaces)} \\ &= \operatorname{rank}(\mathbf{A}). && \text{(}\href{#thm-rank-nullity}{\text{Theorem~7}}\text{)} \end{aligned} \]

$\operatorname{rank}(\mathbf{A} {\mathbf{A}}^{\top}) = \operatorname{rank}({\mathbf{A}}^{\top})$. Apply the previous step to the $n \times m$ matrix ${\mathbf{A}}^{\top}$, using ${({\mathbf{A}}^{\top})}^{\top} = \mathbf{A}$.

Chain the inequalities.

\[ \begin{aligned} \operatorname{rank}(\mathbf{A}) &= \operatorname{rank}({\mathbf{A}}^{\top} \mathbf{A}) && \text{(first step)} \\ &\le \operatorname{rank}({\mathbf{A}}^{\top}) && \text{(}\href{#thm-rank-product}{\text{Theorem~8}}\text{, with } {\mathbf{A}}^{\top} \text{ on the left)} \\ &= \operatorname{rank}(\mathbf{A} {\mathbf{A}}^{\top}) && \text{(second step)} \\ &\le \operatorname{rank}(\mathbf{A}). && \text{(}\href{#thm-rank-product}{\text{Theorem~8}}\text{, with } \mathbf{A} \text{ on the left)} \end{aligned} \]

The chain starts and ends at $\operatorname{rank}(\mathbf{A})$, so every quantity in it equals $\operatorname{rank}(\mathbf{A})$. The columns of ${\mathbf{A}}^{\top}$ are the rows of $\mathbf{A}$, which gives the statement about rows.

Example 14 (Four equal ranks)

Example 14 (Four equal ranks) For $\mathbf{A}$ in Example 1, $\operatorname{rank}(\mathbf{A}) = 1$ (Example 10). Its transpose ${\mathbf{A}}^{\top} = \begin{bmatrix} 1 & 3 \\ -2 & -6 \\ -2 & -6 \end{bmatrix}$ has second column $3$ times its first, so its rank is $1$. ${\mathbf{A}}^{\top} \mathbf{A}$ in Example 9 has every row a multiple of $(1, -2, -2)$, so its rank is $1$ too, and

\[ \begin{aligned} \mathbf{A} {\mathbf{A}}^{\top} &= \begin{bmatrix} 1 \cdot 1 + (-2)(-2) + (-2)(-2) & 1 \cdot 3 + (-2)(-6) + (-2)(-6) \\ 3 \cdot 1 + (-6)(-2) + (-6)(-2) & 3 \cdot 3 + (-6)(-6) + (-6)(-6) \end{bmatrix} \\ &= \begin{bmatrix} 9 & 27 \\ 27 & 81 \end{bmatrix}, \end{aligned} \]

whose second column is $3$ times its first, so its rank is $1$.

Corollary 1 (The rank is at most the smaller dimension)

Corollary 1 (The rank is at most the smaller dimension) For any $m \times n$ matrix $\mathbf{A}$, $\operatorname{rank}(\mathbf{A}) \le \min\mathopen{}\left\{m, n\right\}\mathclose{}$.

Proof

Proof. $\mathbf{A}$ has $n$ columns, so at most $n$ of them are linearly independent, and $\operatorname{rank}(\mathbf{A}) \le n$ (Definition 2 in Subspaces and Rank). Likewise ${\mathbf{A}}^{\top}$ has $m$ columns, so $\operatorname{rank}(\mathbf{A}) = \operatorname{rank}({\mathbf{A}}^{\top}) \le m$ (Theorem 9).

Example 15 (A $2 \times 3$ matrix has rank at most $2$)

Example 15 (A $2 \times 3$ matrix has rank at most $2$) By Corollary 1, every $2 \times 3$ matrix has rank at most $\min\mathopen{}\left\{2, 3\right\}\mathclose{} = 2$, even though it has $3$ columns. The matrix $\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}$ of Remark 1 in Subspaces and Rank reaches that bound: its first two columns $(1, 0)$ and $(0, 1)$ are linearly independent, so its rank is $2$.

Theorem 10 (Multiplying on the left cannot increase the rank)

Theorem 10 (Multiplying on the left cannot increase the rank) If $\mathbf{A}$ is $m \times n$ and $\mathbf{B}$ is $n \times k$, then

\[ \operatorname{rank}(\mathbf{A} \mathbf{B}) \le \operatorname{rank}(\mathbf{B}). \]

Proof

Proof. \[ \begin{aligned} \operatorname{rank}(\mathbf{A} \mathbf{B}) &= \operatorname{rank}({(\mathbf{A} \mathbf{B})}^{\top}) && \text{(}\href{#thm-rank-transpose}{\text{Theorem~9}}\text{)} \\ &= \operatorname{rank}({\mathbf{B}}^{\top}\,{\mathbf{A}}^{\top}) && \text{(}\href{linear-algebra-matrices.qmd#thm-transpose-product}{\text{Theorem~17 in Matrices}}\text{)} \\ &\le \operatorname{rank}({\mathbf{B}}^{\top}) && \text{(}\href{#thm-rank-product}{\text{Theorem~8}}\text{, with } {\mathbf{B}}^{\top} \text{ on the left)} \\ &= \operatorname{rank}(\mathbf{B}). && \text{(}\href{#thm-rank-transpose}{\text{Theorem~9}}\text{)} \end{aligned} \]

Example 16 (A product of rank 1 with a factor of rank 2)

Example 16 (A product of rank 1 with a factor of rank 2) Let

\[ \mathbf{A} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}, \qquad \mathbf{B} = \begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix}, \qquad \mathbf{A} \mathbf{B} = \begin{bmatrix} 1 \cdot 1 + 1 \cdot 1 & 1 \cdot 0 + 1 \cdot 0 \\ 0 \cdot 1 + 1 \cdot 1 & 0 \cdot 0 + 1 \cdot 0 \end{bmatrix} = \begin{bmatrix} 2 & 0 \\ 1 & 0 \end{bmatrix}. \]

$\mathbf{A}$ has rank $2$, because its columns $(1, 0)$ and $(1, 1)$ are linearly independent. $\mathbf{B}$ has rank $1$, because its second column is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_2$ and its first is not, and $\mathbf{A} \mathbf{B}$ has rank $1$ for the same reason. So $\operatorname{rank}(\mathbf{A} \mathbf{B}) = 1 \le \operatorname{rank}(\mathbf{B}) = 1$ (Theorem 10), and the bound of Theorem 8, $2$, is not the tighter one.

Corollary 2 (Multiplying by a matrix of full rank does not change the rank)

Corollary 2 (Multiplying by a matrix of full rank does not change the rank) Let $\mathbf{A}$ be $m \times n$ and $\mathbf{B}$ be $n \times k$.

If $\mathbf{A}$ has full column rank (Definition 3 in Subspaces and Rank), then $\operatorname{rank}(\mathbf{A} \mathbf{B}) = \operatorname{rank}(\mathbf{B})$.
If $\operatorname{rank}(\mathbf{B}) = n$, then $\operatorname{rank}(\mathbf{A} \mathbf{B}) = \operatorname{rank}(\mathbf{A})$.

Proof

Proof. Part 1. Because $\mathbf{A}$ has full column rank, $\mathbf{A} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m$ only for $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n$ (Theorem 3). So for $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \in \mathbb{R}^k$,

\[ \begin{aligned} \mathbf{A} \mathbf{B} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_m &\iff \mathbf{B} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_n && \text{(}\href{#thm-independent-null-space}{\text{Theorem~3}}\text{, with } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}} = \mathbf{B} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \text{)} \end{aligned} \]

so $\mathcal{N}(\mathbf{A} \mathbf{B}) = \mathcal{N}(\mathbf{B})$ (Definition 3), and the two matrices have the same nullity (Definition 7). Both have $k$ columns, so by Theorem 7 they have the same rank.

Part 2. $\mathcal{C}(\mathbf{B})$ is a subspace of $\mathbb{R}^n$ (Theorem 1) of dimension $n$ (Theorem 6), so $\mathcal{C}(\mathbf{B}) = \mathbb{R}^n$ (Theorem 11 in Subspaces and Rank). Every vector of $\mathcal{C}(\mathbf{A} \mathbf{B})$ is $\mathbf{A}\,(\mathbf{B} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}})$ for some $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ (Definition 1), and $\mathbf{B} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ takes every vector of $\mathbb{R}^n$, so $\mathcal{C}(\mathbf{A} \mathbf{B}) = \mathcal{C}(\mathbf{A})$ and the two matrices have the same rank (Theorem 6).

Example 17 (Ranks of products with a full-rank factor)

Example 17 (Ranks of products with a full-rank factor) Let $\mathbf{B} = \begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix}$, which has rank $1$.

Part 1: $\mathbf{A} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ 0 & 0 \end{bmatrix}$ has two linearly independent columns, so it has full column rank, and $\mathbf{A} \mathbf{B} = \begin{bmatrix} 2 & 0 \\ 1 & 0 \\ 0 & 0 \end{bmatrix}$ has rank $1 = \operatorname{rank}(\mathbf{B})$.
Part 2: let $\mathbf{A} = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}$, which has rank $1$, and let $\mathbf{B} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$, which has rank $2$. Then $\mathbf{A} \mathbf{B} = \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}$ has rank $1 = \operatorname{rank}(\mathbf{A})$.

Theorem 11 (A centered data matrix has rank at most $n - 1$)

Theorem 11 (A centered data matrix has rank at most $n - 1$) Let $\mathbf{X}$ be an $n \times p$ matrix with rows ${\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_1}^{\top}, \ldots, {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_n}^{\top}$, let $\bar{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}} = \frac{1}{n}\sum_{i=1}^n \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_i$ be the mean of the rows, and let $\mathbf{X}_c = \mathbf{X}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}}\,{\bar{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}}^{\top}$ be the matrix whose row $i$ is ${(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_i - \bar{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}})}^{\top}$, where $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}}$ is the ones vector of length $n$ (Definition 16 in Vectors). Then $\operatorname{rank}(\mathbf{X}_c) \le n - 1$.

Proof

Proof. The entries of each column of $\mathbf{X}_c$ sum to zero:

\[ \begin{aligned} {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}}}^{\top}\mathbf{X}_c &= {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}}}^{\top}\mathbf{X}- \mathopen{}\left({\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}}}^{\top}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}}\right)\mathclose{}{\bar{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}}^{\top} && \text{(}\href{linear-algebra-matrices.qmd#thm-matmul-distrib}{\text{Theorem~6 in Matrices}}\text{)} \\ &= \sum_{i=1}^n {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_i}^{\top} - n\,{\bar{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}}^{\top} && \text{(} {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}}}^{\top}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}} = n \text{)} \\ &= n\,{\bar{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}}^{\top} - n\,{\bar{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}}}^{\top} && \text{(definition of } \bar{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}} \text{)} \\ &= {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_p}^{\top}. \end{aligned} \]

Transposing, ${\mathbf{X}_c}^{\top}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_p$. The ones vector is nonzero, so it is in the null space of the $p \times n$ matrix ${\mathbf{X}_c}^{\top}$, and $\operatorname{nullity}({\mathbf{X}_c}^{\top}) \ge 1$. By Theorem 7, applied to the $n$ columns of ${\mathbf{X}_c}^{\top}$,

\[ \begin{aligned} \operatorname{rank}(\mathbf{X}_c) &= \operatorname{rank}({\mathbf{X}_c}^{\top}) && \text{(}\href{#thm-rank-transpose}{\text{Theorem~9}}\text{)} \\ &= n - \operatorname{nullity}({\mathbf{X}_c}^{\top}) && \text{(}\href{#thm-rank-nullity}{\text{Theorem~7}}\text{)} \\ &\le n - 1. && \text{(} \operatorname{nullity}({\mathbf{X}_c}^{\top}) \ge 1 \text{)} \end{aligned} \]

Example 18 (Two points in three dimensions)

Example 18 (Two points in three dimensions) $\mathbf{X}= \begin{bmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{bmatrix}$ has $\bar{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}} = (2, 2, 2)$, so

\[ \mathbf{X}_c = \begin{bmatrix} -1 & 0 & 1 \\ 1 & 0 & -1 \end{bmatrix}. \]

The second row is $-1$ times the first, so $\operatorname{rank}(\mathbf{X}_c) = 1 = n - 1$, and the column sums are zero: ${\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}}}^{\top}\mathbf{X}_c = {\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_3}^{\top}$.

Corollary 3 (A sample covariance matrix from $n \le p$ points is singular)

Corollary 3 (A sample covariance matrix from $n \le p$ points is singular) With $\mathbf{X}_c$ as in Theorem 11, the sample covariance matrix

\[ \mathbf{S} = \frac{1}{n - 1}\,{\mathbf{X}_c}^{\top}\mathbf{X}_c \]

is $p \times p$ with $\operatorname{rank}(\mathbf{S}) \le n - 1$. So if $n \le p$, then $\mathbf{S}$ is not invertible.

Proof

Proof. \[ \begin{aligned} \operatorname{rank}(\mathbf{S}) &= \operatorname{rank}({\mathbf{X}_c}^{\top}\mathbf{X}_c) && \text{(multiplying by } \tfrac{1}{n-1} \ne 0 \text{ does not change the rank)} \\ &= \operatorname{rank}(\mathbf{X}_c) && \text{(}\href{#thm-rank-transpose}{\text{Theorem~9}}\text{)} \\ &\le n - 1. && \text{(}\href{#thm-centered-data-rank}{\text{Theorem~11}}\text{)} \end{aligned} \]

If $n \le p$, then $\operatorname{rank}(\mathbf{S}) \le n - 1 < p$, so $\mathbf{S}$ does not have full column rank, and it is not invertible by Theorem 1 in Diagonalization and Cholesky.

Example 19 (As many points as dimensions)

Example 19 (As many points as dimensions) The $n = 3$ points $(1, 0, 0)$, $(0, 1, 0)$ and $(0, 0, 1)$ in $p = 3$ dimensions have $\bar{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}} = \frac{1}{3}(1, 1, 1)$, so

\[ \mathbf{X}_c = \mathbf{I}_3 - \tfrac{1}{3}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}}{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}}}^{\top}, \qquad \mathbf{S} = \tfrac{1}{2}\,\mathbf{X}_c = \tfrac{1}{6}\begin{bmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{bmatrix}, \]

using ${\mathbf{X}_c}^{\top}\mathbf{X}_c = \mathbf{X}_c$ (the centering matrix is a symmetric projection). Then $\mathbf{S}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{1}}\vphantom{1}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_3$ and $\operatorname{rank}(\mathbf{S}) = 2 = n - 1 < 3$. With one more point than dimensions ($n = p + 1$), the rank bound allows $\mathbf{S}$ to have full rank $p$.

Definition 8 (Affine subspace)

Definition 8 (Affine subspace) An affine subspace [5] of $\mathbb{R}^p$ is a set of the form

\[ \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} : \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} \in \mathcal{S}\right\}\mathclose{} \]

for some vector $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 \in \mathbb{R}^p$ and some subspace $\mathcal{S}$ of $\mathbb{R}^p$ (Definition 4 in Subspaces and Rank): the image of $\mathcal{S}$ under the translation by $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0$ (Definition 18 in Matrices).

Example 20 (A line that misses the origin is an affine subspace)

Example 20 (A line that misses the origin is an affine subspace) The line $\mathcal{T} = \mathopen{}\left\{(x, 1) : x \in \mathbb{R}\right\}\mathclose{}$ of Example 4 in Subspaces and Rank is not a subspace, but it is an affine subspace, with $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 = (0, 1)$ and $\mathcal{S} = \operatorname{span}\mathopen{}\left\{(1, 0)\right\}\mathclose{}$ (Definition 5 in Subspaces and Rank):

\[ \begin{aligned} (0, 1) + c\,(1, 0) &= (0 + c,\; 1 + 0) && \text{(}\href{linear-algebra-matrices.qmd#def-scalar-mult}{\text{Definition~6 in Matrices}}\text{, }\href{linear-algebra-vectors.qmd#def-vector-addition}{\text{Definition~7 in Vectors}}\text{)} \\ &= (c, 1), && \text{(add)} \end{aligned} \]

and as $c$ ranges over $\mathbb{R}$, $(c, 1)$ ranges over all of $\mathcal{T}$. Every subspace $\mathcal{S}$ is also an affine subspace, with $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$.

Theorem 12 (A hyperplane is a translated subspace of dimension $p - 1$)

Theorem 12 (A hyperplane is a translated subspace of dimension $p - 1$) Let $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \in \mathbb{R}^p$ be nonzero, let $b \in \mathbb{R}$, let $\mathcal{H} = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\in \mathbb{R}^p : \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}+ b = 0\right\}\mathclose{}$ be the hyperplane with normal vector $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ and offset $b$ (Definition 22 in Matrices), and let $\mathcal{H}_0 = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\in \mathbb{R}^p : \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= 0\right\}\mathclose{}$ be the hyperplane with the same normal vector and offset $0$.

$\mathcal{H}_0$ is a subspace of $\mathbb{R}^p$ (Definition 4 in Subspaces and Rank) of dimension $p - 1$ (Definition 9 in Subspaces and Rank).
$\mathcal{H}$ is not empty, and for any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 \in \mathcal{H}$, $\mathcal{H} = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} : \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} \in \mathcal{H}_0\right\}\mathclose{}$, so $\mathcal{H}$ is an affine subspace (Definition 8).
For any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}\in \mathcal{H}$, the normal vector is orthogonal to their difference: $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \perp (\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}})$ (Definition 19 in Vectors).

Proof

Proof. Here $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top}$ is a $1 \times p$ matrix, and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ (Example 6 in Matrices).

Part 1. $\mathcal{H}_0$ is the null space $\mathcal{N}(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top})$ (Definition 3), so it is a subspace (Theorem 2). The $p$ columns of $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top}$ are the numbers $w_1, \ldots, w_p$. Some $w_j \ne 0$, because $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \ne \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$, and that column on its own is linearly independent ($c\,w_j = 0$ forces $c = 0$), so $\operatorname{rank}(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top}) \ge 1$ (Definition 2 in Subspaces and Rank); and $\operatorname{rank}(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top}) \le \min\mathopen{}\left\{1, p\right\}\mathclose{} = 1$ (Corollary 1). So

\[ \begin{aligned} \dim(\mathcal{H}_0) &= \operatorname{nullity}(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top}) && \text{(}\href{#def-nullity}{\text{Definition~7}}\text{)} \\ &= p - \operatorname{rank}(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top}) && \text{(}\href{#thm-rank-nullity}{\text{Theorem~7}}\text{, for the } p \text{ columns of } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \text{)} \\ &= p - 1. && \text{(the rank is } 1 \text{)} \end{aligned} \]

Part 2. $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} = w_1^2 + \cdots + w_p^2 > 0$, because some $w_j \ne 0$. So $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}^* \stackrel{\text{def}}{=}-\frac{b}{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ is defined, and

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}^* + b &= -\frac{b}{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}}\,(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}) + b && \text{(homogeneity of } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\mapsto \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\text{, }\href{linear-algebra-matrices.qmd#thm-matrix-map-linear}{\text{Theorem~10 in Matrices}}\text{)} \\ &= -b + b && \text{(} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \text{)} \\ &= 0, && \text{(arithmetic)} \end{aligned} \]

so $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}^* \in \mathcal{H}$, and $\mathcal{H}$ is not empty. Now take any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 \in \mathcal{H}$, so $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 = -b$. For any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\in \mathbb{R}^p$,

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} (\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0) &= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 && \text{(}\href{linear-algebra-subspaces.qmd#thm-matvec-linear}{\text{Theorem~4 in Subspaces and Rank}}\text{, with coefficients } 1 \text{ and } -1 \text{)} \\ &= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}- (-b) && \text{(} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 \in \mathcal{H} \text{)} \\ &= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}+ b, && \text{(arithmetic)} \end{aligned} \]

so $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\in \mathcal{H}$ exactly when $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 \in \mathcal{H}_0$, that is, exactly when $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}}$ with $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 \in \mathcal{H}_0$. $\mathcal{H}_0$ is a subspace (part 1), so $\mathcal{H}$ has the form in Definition 8.

Part 3. For $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}\in \mathcal{H}$, both $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}$ equal $-b$, so

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot (\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}) &= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}^{\top} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}} && \text{(}\href{linear-algebra-subspaces.qmd#thm-matvec-linear}{\text{Theorem~4 in Subspaces and Rank}}\text{, with coefficients } 1 \text{ and } -1 \text{)} \\ &= (-b) - (-b) && \text{(} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}\in \mathcal{H} \text{)} \\ &= 0. && \text{(arithmetic)} \end{aligned} \]

Example 21 (The plane $x_1 + x_2 + x_3 = 1$ in $\mathbb{R}^3$)

Example 21 (The plane $x_1 + x_2 + x_3 = 1$ in $\mathbb{R}^3$) Take $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} = (1, 1, 1)$ and $b = -1$, so $\mathcal{H} = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}: x_1 + x_2 + x_3 - 1 = 0\right\}\mathclose{}$, the plane that Example 5 in Subspaces and Rank showed is not a subspace. By part 1, $\mathcal{H}_0 = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}: x_1 + x_2 + x_3 = 0\right\}\mathclose{}$ is a subspace of dimension $3 - 1 = 2$.

$\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 = (1, 0, 0)$ is in $\mathcal{H}$, since $1 + 0 + 0 - 1 = 0$, and so is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}= (0, 1, 0)$.
Their difference $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 = (-1, 1, 0)$ has entries summing to $-1 + 1 + 0 = 0$, so it is in $\mathcal{H}_0$, and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + (-1, 1, 0)$, as part 2 says.
\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot (-1, 1, 0) &= -1 + 1 + 0 \\ &= 0, \end{aligned} \]

as part 3 says.
The point built in the proof is

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}^* &= -\frac{-1}{3}\,(1, 1, 1) \\ &= \mathopen{}\left(\tfrac{1}{3}, \tfrac{1}{3}, \tfrac{1}{3}\right)\mathclose{}, \end{aligned} \]

and $\tfrac{1}{3} + \tfrac{1}{3} + \tfrac{1}{3} - 1 = 0$.

Theorem 13 (Where a hyperplane passes, and its shape in $\mathbb{R}^2$ and $\mathbb{R}^3$)

Theorem 13 (Where a hyperplane passes, and its shape in $\mathbb{R}^2$ and $\mathbb{R}^3$) Let $\mathcal{H} = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\in \mathbb{R}^p : \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} + b = 0\right\}\mathclose{}$ be a hyperplane (Definition 22 in Matrices).

$\mathcal{H}$ contains the origin $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}$ exactly when $b = 0$.
If $p = 2$, then $\mathcal{H}$ is a line: $\mathcal{H} = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + t\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} : t \in \mathbb{R}\right\}\mathclose{}$ for some $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 \in \mathbb{R}^2$ and some nonzero $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} \in \mathbb{R}^2$.
If $p = 3$, then $\mathcal{H}$ is a plane: $\mathcal{H} = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + s\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + t\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_2 : s, t \in \mathbb{R}\right\}\mathclose{}$ for some $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 \in \mathbb{R}^3$ and some linearly independent $\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 \in \mathbb{R}^3$.

Proof

Proof. Part 1. Since $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}} = 0$,

so $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}\in \mathcal{H}$ exactly when $b = 0$.

Parts 2 and 3. By Theorem 12, $\mathcal{H} = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} : \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} \in \mathcal{H}_0\right\}\mathclose{}$ for any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 \in \mathcal{H}$, where $\mathcal{H}_0$ is a subspace of $\mathbb{R}^p$ of dimension $p - 1$.

For $p = 2$, $\mathcal{H}_0$ has dimension $1$, so it has a basis (Definition 6 in Subspaces and Rank) with one vector $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}$. That vector is nonzero, and $\mathcal{H}_0 = \mathopen{}\left\{t\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} : t \in \mathbb{R}\right\}\mathclose{}$.

For $p = 3$, $\mathcal{H}_0$ has dimension $2$, so it has a basis with two vectors $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_2$. They are linearly independent, and $\mathcal{H}_0 = \mathopen{}\left\{s\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + t\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_2 : s, t \in \mathbb{R}\right\}\mathclose{}$.

Example 22 (A line in $\mathbb{R}^2$ and a plane in $\mathbb{R}^3$, checked on a grid of points)

Example 22 (A line in $\mathbb{R}^2$ and a plane in $\mathbb{R}^3$, checked on a grid of points) In $\mathbb{R}^2$, take $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} = (1, 1)$ and $b = -1$, the line of Example 20 in Matrices. The point $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 = -\frac{b}{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}}\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ is on it, and the vector $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} = (-w_2, w_1)$ is nonzero with $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} = 0$, so it spans the subspace $\mathcal{H}_0$ of Theorem 12. In $\mathbb{R}^3$, take $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} = (1, 1, 1)$ and $b = -1$, the plane of Example 21, with the independent vectors $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 = (1, -1, 0)$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_2 = (0, 1, -1)$ in $\mathcal{H}_0$. The code evaluates $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} + b$ at the origin and at points $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + t\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + s\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + t\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_2$.

level <- function(w, b, x) sum(w * x) + b

w2 <- c(1, 1)
b2 <- -1
point_line <- -b2 / sum(w2 * w2) * w2
v <- c(-w2[2], w2[1])
line_levels <- sapply(-2:2, function(t) level(w2, b2, point_line + t * v))

w3 <- c(1, 1, 1)
b3 <- -1
point_plane <- -b3 / sum(w3 * w3) * w3
v1 <- c(1, -1, 0)
v2 <- c(0, 1, -1)
grid <- expand.grid(s = -2:2, t = -2:2)
plane_levels <- mapply(
  function(s, t) level(w3, b3, point_plane + s * v1 + t * v2),
  grid$s, grid$t
)

c(
  origin_in_R2 = level(w2, b2, c(0, 0)),
  origin_in_R3 = level(w3, b3, c(0, 0, 0)),
  origin_with_b0 = level(w3, 0, c(0, 0, 0))
)
#>   origin_in_R2   origin_in_R3 origin_with_b0 
#>             -1             -1              0

At the origin the left side equals the offset, so the origin is on the line only if $b$ is $0$: it gives -1 for the line and -1 for the plane, and 0 once the offset is changed to $0$. All 5 points $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + t\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}$ on the line and all 25 points $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + s\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_1 + t\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}_2$ on the plane satisfy the equation up to rounding error: 30 of the 30 points have $\mathopen{}\left|\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} + b\right|\mathclose{} < 10^{-10}$.

Definition 9 (Open half-space)

Definition 9 (Open half-space) Let $\mathcal{H} = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\in \mathbb{R}^p : \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} + b = 0\right\}\mathclose{}$ be a hyperplane (Definition 22 in Matrices). The two open half-spaces [6] of $\mathcal{H}$ are

\[ \mathcal{H}^+ \stackrel{\text{def}}{=}\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\in \mathbb{R}^p : \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} + b > 0\right\}\mathclose{} \quad \text{and} \quad \mathcal{H}^- \stackrel{\text{def}}{=}\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\in \mathbb{R}^p : \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} + b < 0\right\}\mathclose{}. \tag{1}\]

Definition 10 (Closed half-space)

Definition 10 (Closed half-space) The closed half-spaces of the hyperplane $\mathcal{H}$ of Definition 9 also include $\mathcal{H}$ itself: $\mathcal{H}^+ \cup \mathcal{H}$ and $\mathcal{H}^- \cup \mathcal{H}$.

Remark

Remark. Replacing $(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}, b)$ by $(-\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}, -b)$ describes the same hyperplane but swaps the names $\mathcal{H}^+$ and $\mathcal{H}^-$. The sign of $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} + b$ tells you which side of the hyperplane $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ is on. A linear classifier uses this sign to assign one of two labels.

Example 23 (Half-spaces of a line in the plane)

Example 23 (Half-spaces of a line in the plane) Let $\mathcal{H}$ be the line in $\mathbb{R}^2$ with $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} = (1, 2)$ and $b = -2$ (Definition 22 in Matrices), so $\mathcal{H} = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}: x_1 + 2 x_2 - 2 = 0\right\}\mathclose{}$. Evaluate $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} + b$ at three points (Definition 9):

At $(0, 0)$ it equals $0 + 0 - 2 = -2 < 0$, so $(0, 0) \in \mathcal{H}^-$.
At $(2, 0)$ it equals $2 + 0 - 2 = 0$, so $(2, 0) \in \mathcal{H}$.
At $(2, 1)$ it equals $2 + 2 - 2 = 2 > 0$, so $(2, 1) \in \mathcal{H}^+$.

Moving from $(2, 0)$ in the direction $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} = (1, 2)$ gives $(3, 2)$, where the value is $3 + 4 - 2 = 5 > 0$. So the direction $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ leads into $\mathcal{H}^+$.

Remark 1 (The two sides of a hyperplane)

Remark 1 (The two sides of a hyperplane). Every point of $\mathbb{R}^p$ is in exactly one of $\mathcal{H}^+$, $\mathcal{H}$ and $\mathcal{H}^-$, because the number $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} + b$ is positive, zero or negative. The vector $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ points into $\mathcal{H}^+$: the number $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} + b$ goes up when $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ moves in the direction $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$.

Theorem 14 (Differences of points in a hyperplane and in a half-space)

Theorem 14 (Differences of points in a hyperplane and in a half-space) Let $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \in \mathbb{R}^p$ be nonzero, let $b \in \mathbb{R}$, and let $\mathcal{H}$, $\mathcal{H}^+$ be the hyperplane and open half-space of Definition 9. For a set $S \subseteq \mathbb{R}^p$, let $D(S) \stackrel{\text{def}}{=}\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}: \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}\in S\right\}\mathclose{}$ be the set of differences of its points.

$D(\mathcal{H}) = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} : \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} = 0\right\}\mathclose{}$, a subspace of dimension $p - 1$.
$D(\mathcal{H}^+) = \mathbb{R}^p$, a subspace of dimension $p$.

The same holds for $\mathcal{H}^-$.

Proof

Proof. Part 1. Let $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}, \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}\in \mathcal{H}$. By Theorem 12 part 3, $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot (\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}) = 0$, so $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{y}}\vphantom{y}}- \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\in \mathcal{H}_0 = \mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} : \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} = 0\right\}\mathclose{}$. Conversely, take any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 \in \mathcal{H}$ (Theorem 12 part 2 gives such a point). For any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} \in \mathcal{H}_0$, the point $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}}$ is in $\mathcal{H}$ by the same part, and $(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}}) - \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}}$. So $D(\mathcal{H}) = \mathcal{H}_0$, which has dimension $p - 1$ by Theorem 12 part 1.

Part 2. Every difference is in $\mathbb{R}^p$, so $D(\mathcal{H}^+) \subseteq \mathbb{R}^p$. For the reverse inclusion, take any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 \in \mathcal{H}$. Take any $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} \in \mathbb{R}^p$. For a number $t > 0$ to be chosen, let $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_t \stackrel{\text{def}}{=}\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + t\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$. Then

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_t + b &= \mathopen{}\left(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 + b\right)\mathclose{} + t\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} && \text{(linearity of } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\mapsto \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \text{)} \\ &= t\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}, && \text{(} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_0 \in \mathcal{H} \text{)} \end{aligned} \]

which is positive, so $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_t \in \mathcal{H}^+$. Next,

\[ \begin{aligned} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot (\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_t + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}) + b &= \mathopen{}\left(\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_t + b\right)\mathclose{} + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} && \text{(linearity of } \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}\mapsto \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} \text{)} \\ &= t\,\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}. && \text{(the display above)} \end{aligned} \]

Because $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} > 0$, this is positive once $t > -\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} / \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$. Choose such a $t > 0$. Then $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_t$ and $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}_t + \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}$ are both in $\mathcal{H}^+$, and their difference is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}}$. So $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{v}}\vphantom{v}} \in D(\mathcal{H}^+)$. The whole space $\mathbb{R}^p$ is a subspace of dimension $p$ (Definition 9 in Subspaces and Rank).

The proof for $\mathcal{H}^-$ is the same with $-\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ and $-b$ in place of $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ and $b$.

Example 24 (Two iris species on either side of a line)

Example 24 (Two iris species on either side of a line) The iris data set in R has the petal length and petal width, in centimeters, of 150 irises. Take the 100 flowers of the species versicolor and virginica, and let $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}= (x_1, x_2)$ be the petal length and petal width of one flower. A logistic regression of the species on $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}}$ gives a coefficient vector $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ and an intercept $b$. The line $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} + b = 0$ is a hyperplane in $\mathbb{R}^2$ (Definition 22 in Matrices), and the two species mostly fall in its two open half-spaces (Definition 9). Figure 1 shows the line and the flowers.

Show R code

two_species <- dplyr::filter(iris, Species != "setosa") |> droplevels()
fit <- glm(
  Species ~ Petal.Length + Petal.Width,
  family = binomial,
  data = two_species
)
w <- coef(fit)[c("Petal.Length", "Petal.Width")]
b <- coef(fit)[["(Intercept)"]]
two_species$score <- as.vector(
  as.matrix(two_species[c("Petal.Length", "Petal.Width")]) %*% w + b
)
two_species$side <- ifelse(two_species$score > 0, "positive", "negative")
ggplot2::ggplot(two_species) +
  ggplot2::aes(x = Petal.Length, y = Petal.Width, colour = Species) +
  ggplot2::geom_point() +
  ggplot2::geom_abline(intercept = -b / w[[2]], slope = -w[[1]] / w[[2]]) +
  ggplot2::labs(x = "Petal length (cm)", y = "Petal width (cm)")

Scatter plot of petal width against petal length for 100 irises. Versicolor points, in one color, are mostly to the lower left. Virginica points, in another color, are mostly to the upper right. A straight line runs between the two groups and separates most of them. — Figure 1: Petal length and width of versicolor and virginica irises, with the line where a logistic regression is indifferent between the two species

table(two_species$Species, two_species$side)
#>             
#>              negative positive
#>   versicolor       47        3
#>   virginica         3       47

The vector $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ points toward the virginica side, so the positive half-space $\mathcal{H}^+$ holds 50 of the 100 flowers, and 47 of them are virginica. The line is a set of dimension $p - 1 = 1$, and each side is a region of the plane of dimension $p = 2$ (Theorem 14).

Exercise 1 (Which side of the plane?)

Exercise 1 (Which side of the plane?) Let $\mathcal{H}$ be the plane in $\mathbb{R}^3$ with $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} = (1, 1, 1)$ and $b = -1$ (Example 21).

For each point, say whether it is in $\mathcal{H}^+$, $\mathcal{H}$ or $\mathcal{H}^-$ (Definition 9): $(0, 0, 0)$, $(1, 0, 0)$ and $(1, 1, 1)$.
Write the plane and its half-spaces using $-\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}}$ and $-b$. Which points from part 1 change sides?
State the dimension of $D(\mathcal{H})$ and of $D(\mathcal{H}^+)$ (Theorem 14).

Solution 1

Solution 1.

Compute $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} \cdot \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{x}}\vphantom{x}} + b = x_1 + x_2 + x_3 - 1$ at each point.
- At $(0, 0, 0)$ it equals $0 + 0 + 0 - 1 = -1 < 0$, so the point is in $\mathcal{H}^-$.
- At $(1, 0, 0)$ it equals $1 + 0 + 0 - 1 = 0$, so the point is in $\mathcal{H}$.
- At $(1, 1, 1)$ it equals $1 + 1 + 1 - 1 = 2 > 0$, so the point is in $\mathcal{H}^+$.
With $-\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{w}}\vphantom{w}} = (-1, -1, -1)$ and $-b = 1$, the equation is $-x_1 - x_2 - x_3 + 1 = 0$. Multiplying both sides by $-1$ gives the original equation, so it is the same plane. The new expression is the negative of the old one at every point, so the new positive half-space is the old $\mathcal{H}^-$ and the new negative half-space is the old $\mathcal{H}^+$. The origin $(0, 0, 0)$ is now in the positive half-space, and $(1, 1, 1)$ is now in the negative half-space. The point $(1, 0, 0)$ stays on the plane. So the origin and $(1, 1, 1)$ both change names, and the point on the plane does not.
Here $p = 3$. $D(\mathcal{H})$ is the subspace $\mathopen{}\left\{\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{s}}\vphantom{s}} : s_1 + s_2 + s_3 = 0\right\}\mathclose{}$, which has dimension $p - 1 = 2$. $D(\mathcal{H}^+) = \mathbb{R}^3$ has dimension $p = 3$.

Definition 11 (Rank factorization)

Definition 11 (Rank factorization) Let $\mathbf{A}$ be an $m \times n$ matrix with $\operatorname{rank}(\mathbf{A}) = r \ge 1$. A rank factorization [7] of $\mathbf{A}$ is a product

\[ \underbrace{\mathbf{A}}_{m \times n} = \underbrace{\mathbf{C}}_{m \times r}\,\underbrace{\mathbf{R}}_{r \times n}. \]

Example 25 (A rank factorization of a rank-one matrix)

Example 25 (A rank factorization of a rank-one matrix) The matrix $\mathbf{A}$ in Example 1 has rank $1$ (Example 10), and

\[ \begin{aligned} \begin{bmatrix} 1 \\ 3 \end{bmatrix} \begin{bmatrix} 1 & -2 & -2 \end{bmatrix} &= \begin{bmatrix} 1 \cdot 1 & 1 \cdot(-2) & 1 \cdot(-2) \\ 3 \cdot 1 & 3 \cdot(-2) & 3 \cdot(-2) \end{bmatrix} \\ &= \begin{bmatrix} 1 & -2 & -2 \\ 3 & -6 & -6 \end{bmatrix}, \end{aligned} \]

so $\mathbf{C} = \begin{bmatrix} 1 \\ 3 \end{bmatrix}$ ($2 \times 1$) and $\mathbf{R} = \begin{bmatrix} 1 & -2 & -2 \end{bmatrix}$ ($1 \times 3$) are a rank factorization. It is not unique: $\mathbf{C} = \begin{bmatrix} 2 \\ 6 \end{bmatrix}$ and $\mathbf{R} = \begin{bmatrix} \frac{1}{2} & -1 & -1 \end{bmatrix}$ give the same product. A product $\mathbf{C} \mathbf{R}$ with $\mathbf{C}$ of size $2 \times 2$ is not a rank factorization of this $\mathbf{A}$, because the inner dimension must equal $\operatorname{rank}(\mathbf{A}) = 1$.

Theorem 15 (Every nonzero matrix has a rank factorization)

Theorem 15 (Every nonzero matrix has a rank factorization) Every $m \times n$ matrix $\mathbf{A}$ with $\operatorname{rank}(\mathbf{A}) = r \ge 1$ has a rank factorization (Definition 11). One is given by taking the columns of $\mathbf{C}$ to be any basis of $\mathcal{C}(\mathbf{A})$.

Proof

Proof. $\mathcal{C}(\mathbf{A})$ has dimension $r$ (Theorem 6), so it has a basis $\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}}_r$ (Theorem 9 in Subspaces and Rank); let $\mathbf{C}$ be the $m \times r$ matrix with these columns. Each column $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_j$ of $\mathbf{A}$ is in $\mathcal{C}(\mathbf{A})$, so $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_j = r_{1j} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_1 + \cdots + r_{rj} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_r$ for some numbers $r_{ij}$, because the basis spans $\mathcal{C}(\mathbf{A})$. Let $\mathbf{R}$ be the $r \times n$ matrix with entries $r_{ij}$, whose column $j$ is $\mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{r}}\vphantom{r}}_j = (r_{1j}, \ldots, r_{rj})$. Then column $j$ of $\mathbf{C} \mathbf{R}$ is

\[ \begin{aligned} \mathbf{C} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{r}}\vphantom{r}}_j &= r_{1j} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_1 + \cdots + r_{rj} \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{c}}\vphantom{c}}_r && \text{(}\href{linear-algebra-subspaces.qmd#thm-matvec-columns}{\text{Theorem~3 in Subspaces and Rank}}\text{)} \\ &= \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{a}}\vphantom{a}}_j, && \text{(choice of the } r_{ij} \text{)} \end{aligned} \]

so $\mathbf{C} \mathbf{R} = \mathbf{A}$.

Example 26 (Building a rank factorization from a basis)

Example 26 (Building a rank factorization from a basis) For $\mathbf{A}$ in Example 1, $(1, 3)$ spans $\mathcal{C}(\mathbf{A})$ (Example 2), and it is linearly independent because it is nonzero ($c\,(1, 3) = \mathord{\smash[b]{\underset{\raise.3ex\hbox{$\scriptstyle\sim$}}{0}}\vphantom{0}}_2$ forces $c = 0$), so it is a basis of $\mathcal{C}(\mathbf{A})$. The columns of $\mathbf{A}$ are $(1, 3) = 1 \cdot(1, 3)$, $(-2, -6) = -2 \cdot(1, 3)$ and $(-2, -6) = -2 \cdot(1, 3)$, so the construction in Theorem 15 gives $\mathbf{C} = \begin{bmatrix} 1 \\ 3 \end{bmatrix}$ and $\mathbf{R} = \begin{bmatrix} 1 & -2 & -2 \end{bmatrix}$, the factorization in Example 25.

References

[1]

Wikipedia contributors, “Row and column spaces — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Row_and_column_spaces

[2]

Wikipedia contributors, “Gram matrix — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Gram_matrix

[3]

H. Zhou, “Rank and nullity.” 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/05-rank/05-rank.html

[4]

Wikipedia contributors, “Rank–nullity theorem — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Rank%E2%80%93nullity_theorem

[5]

Wikipedia contributors, “Affine space — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Affine_space

[6]

Wikipedia contributors, “Half-space (geometry) — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Half-space_(geometry)

[7]

Wikipedia contributors, “Rank factorization — Wikipedia, the free encyclopedia.” 2026. Available: https://en.wikipedia.org/wiki/Rank_factorization