7 Subspaces of \(\mathbb{R}^n\)

Recall that a subset \(W\) of \(\mathbb{R}^n\) is a subspace of \(\mathbb{R}^n\) if it satisfies the following three conditions:

Zero Vector Property: \(\mathbf{0} \in W\)
Closure under Addition: For all \(\mathbf{u}, \mathbf{v} \in W\), \(\mathbf{u} + \mathbf{v} \in W\)
Closure under Scalar Multiplication: For all \(c \in \mathbb{R}\) and \(\mathbf{v} \in W\), \(c\mathbf{v} \in W\)

We showed in Theorem 2.1 that subspaces are also vector spaces with the operations they inherit.

7.1 The Null Space

Definition 7.1 Let \(A\) be an \(m\times n\) matrix, the null space of the matrix \(A\) is defined by \[\text{nul}(A) = \{\mathbf{x}\in\mathbb{R}^n:A\mathbf{x}=\mathbf{0}\}\]

Proposition: Let \(A\) be an \(m\times n\) matrix. Then nul\((A)\) is a subspace of \(\mathbb{R}^n\)

Proof. We need to check the three properties:

Zero Vector Property: \(A\mathbf{0} = \mathbf{0}\) by properties of matrix multiplication. Therefore, \(\mathbf{0} \in \text{nul}(A)\)
Closure under Addition: Let \(\mathbf{x}, \mathbf{y} \in \text{nul}(A)\). Then \(A\mathbf{x} = \mathbf{0}\) and \(A\mathbf{y} = \mathbf{0}\). Then \(A(\mathbf{x} + \mathbf{y}) = A\mathbf{x} + A\mathbf{y} = \mathbf{0} + \mathbf{0} = \mathbf{0}\). Therefore, \(\mathbf{x} + \mathbf{y} \in \text{nul}(A)\)
Closure under Scalar Multiplication: Let \(\mathbf{x} \in \text{nul}(A)\) and \(c \in \mathbb{R}\). Then \(A(c\mathbf{x}) = cA\mathbf{x} = c\mathbf{0} = \mathbf{0}\). Therefore, \(c\mathbf{x} \in \text{nul}(A)\) \(\square\)

If \(A\) is an \(m\times n\) matrix:

\(\text{nul}(A)\) is a subspace of \(\mathbb{R}^n\), and

\(\text{nul}(A^T)\) is a subspace of \(\mathbb{R}^m\).

Since \(\text{nul}(A)\) consists of the solutions of the homogeneous system \(A\mathbf{x}=\mathbf{0}\), we solve it using Gaussain elimination and back substitution. We will see that this process gives a basis of \(\text{nul}(A)\).

Example 1: Find a basis for the null space of \[A = \begin{bmatrix} -1 & 2 & 0 & 1 & 1 \\ 2 & 2 & 6 & 4 & -1 \\ 1 & -1 & 1 & 0 & 1 \\ 1 & 2 & 4 & 3 & 2 \end{bmatrix}.\]

To find the solutions of \(A\mathbf{x}=\mathbf{0}\), we look at the augmented matrix \([A|\mathbf{0}]\), row reduce it:

\[\left[ \begin{array}{ccccc|c} -1 & 2 & 0 & 1 & 1 & 0 \\ 2 & 2 & 6 & 4 & -1 & 0 \\ 1 & -1 & 1 & 0 & 1 & 0 \\ 1 & 2 & 4 & 3 & 2 & 0 \end{array}\right] \xrightarrow{\text{RREF}} \left[ \begin{array}{ccccc|c} 1 & 0 & 2 & 1 & 0 & 0\\ 0 & 1 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right],\] and then we solve the system by back substitution:

From the third row: \(x_5=0\)
\(x_4\) is free
\(x_3\) is free
From the second row: \(x_2= -x_3-x_4\), and
From the first row: \(x_1=-2x_3-x_4\).

Wrting the solution in vector form we get:

\[\mathbf{x}=\begin{bmatrix}x_1\\ x_2\\ x_3\\ x_4\\ x_5\end{bmatrix} =\begin{bmatrix}-2x_3-x_4\\-x_3-x_4\\ x_3\\ x_4\\0\end{bmatrix} =x_3\begin{bmatrix}-2\\-1\\ 1\\ 0\\0\end{bmatrix} +x_4\begin{bmatrix}-1\\-1\\ 0\\ 1\\0\end{bmatrix}. \]

We claim that \[S=\left\{\begin{bmatrix}-2\\-1\\ 1\\ 0\\0\end{bmatrix}, \begin{bmatrix}-1\\-1\\ 0\\ 1\\0\end{bmatrix}\right\}\] is a basis for \(\text{nul}(A)\). Indeed, we just showed that any solution of \(A\mathbf{x}=\mathbf{0}\) can be written as a linear combination of these vectors, showing that \(S\) spans \(\text{nul}(A)\). Then notice that \(S\) is linearly independent, proving that \(S\) is a basis of \(\text{nul}(A)\).

Gaussian Elimination Naturally Produces Basis Vectors

The point is that back substitution gives us vectors that:

Are automatically linearly independent (due to the staggered positioning of pivots and free variables)
Generate all solutions (since we systematically express each variable in terms of free variables)

These two properties are exactly what’s needed for a basis. The systematic nature of Gaussian elimination ensures this happens every time.

7.2 The Span of a Set of Vectors

Let \(\mathbf{v}_1, ..., \mathbf{v}_k \in \mathbb{R}^n\). Recall (Section 1.3) that the span of a set of vectors is defined by \[\text{span}\{\mathbf{v}_1, ..., \mathbf{v}_k\} = \{c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + ... + c_k\mathbf{v}_k : c_1, c_2, ..., c_k \in \mathbb{R}\}.\]

Parts of the following theorem were discussed in Theorem 1.1

Proposition: \(\text{span}\{\mathbf{v}_1, ..., \mathbf{v}_k\}\) is a subspace of \(\mathbb{R}^n\)

Proof. Let \(W=\text{span}\{\mathbf{v}_1, ..., \mathbf{v}_k\}\). We need to check the three conditions:

Zero Vector Property: Let \(c_1 = c_2 = ... = c_k = 0\) Then \(0\mathbf{v}_1 + 0\mathbf{v}_2 + ... + 0\mathbf{v}_k = \mathbf{0}\) Therefore, \(\mathbf{0} \in W\)
Closure under Addition: Let \(\mathbf{x}, \mathbf{y} \in W\) where: \(\mathbf{x} = a_1\mathbf{v}_1 + ... + a_k\mathbf{v}_k\) \(\mathbf{y} = b_1\mathbf{v}_1 + ... + b_k\mathbf{v}_k\)

Then: \(\mathbf{x} + \mathbf{y} = (a_1+b_1)\mathbf{v}_1 + ... + (a_k+b_k)\mathbf{v}_k \in W\)
Closure under Scalar Multiplication: Let \(\mathbf{x} \in W\) where \(\mathbf{x} = a_1\mathbf{v}_1 + ... + a_k\mathbf{v}_k\) For any \(c \in \mathbb{R}\): \(c\mathbf{x} = (ca_1)\mathbf{v}_1 + ... + (ca_k)\mathbf{v}_k \in W\) \(\square\)

An important example is the column space of a matrix:

Definition 7.2 Let \(A\) be an \(m\times n\) matrix \[A = \begin{bmatrix} \uparrow & \uparrow & \cdots & \uparrow \\ \mathbf{c}_1 & \mathbf{c}_2 & \cdots & \mathbf{c}_n \\ \downarrow & \downarrow & \cdots & \downarrow \end{bmatrix},\] \(\text{col}(A)=\text{span}\{\mathbf{c}_1,\mathbf{c}_2,\dots,\mathbf{c}_n\}\)

If \(A\) is an \(m\times n\) matrix:

\(\text{col}(A)\) is a subspace of \(\mathbb{R}^m\), and

\(\text{col}(A^T)\) is a subspace of \(\mathbb{R}^n\).

7.2.1 Finding bases

Let \(W=\text{span}\{\mathbf{v}_1, ..., \mathbf{v}_k\}\subset\mathbb{R}^n\). A basis of \(W\) is a set of vectors that spans \(W\) and that is linearly independent. We already have a spanning set \(\{\mathbf{v}_1, ..., \mathbf{v}_k\}\). If this set is linearly independent, it forms a basis. Otherwise, some vectors can be written as linear combinations of others. Either way, the first step is to check if the set is linearly independent. This leads to a homogeneous system that is solved using Gaussain elimination. This process will tell us how to remove the dependent vectors systematically keeping only the vectors corresponding to pivot columns. This process yields a basis that spans the same subspace \(W\).

Example: Find a basis for \[W=\text{span}\left\{ \begin{bmatrix}-1\\2\\1\\1\end{bmatrix}, \begin{bmatrix}2\\2\\-1\\2\end{bmatrix}, \begin{bmatrix}0\\6\\1\\4\end{bmatrix}, \begin{bmatrix}1\\4\\0\\3\end{bmatrix}, \begin{bmatrix}1\\-1\\1\\2\end{bmatrix} \right\}\]

Notice that this is the same problem as finding a basis for \(\text{col}(A)\), where \(A\) is the matrix of Example 1: \[A = \begin{bmatrix} -1 & 2 & 0 & 1 & 1 \\ 2 & 2 & 6 & 4 & -1 \\ 1 & -1 & 1 & 0 & 1 \\ 1 & 2 & 4 & 3 & 2 \end{bmatrix}= \begin{bmatrix} \uparrow & \uparrow & \uparrow & \uparrow &\uparrow \\ \mathbf{c}_1 & \mathbf{c}_2 & \mathbf{c}_3 & \mathbf{c}_4 & \mathbf{c}_5 \\ \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \end{bmatrix}.\]

The first step is to check if the set is linearly independent. We look at the equation \[x_1\begin{bmatrix}-1\\2\\1\\1\end{bmatrix}+ x_2 \begin{bmatrix}2\\2\\-1\\2\end{bmatrix}+ x_3 \begin{bmatrix}0\\6\\1\\4\end{bmatrix}+ x_4 \begin{bmatrix}1\\4\\0\\3\end{bmatrix}+ x_5 \begin{bmatrix}1\\-1\\1\\2\end{bmatrix} = \begin{bmatrix}0\\0\\0\\0\end{bmatrix}, \] and we solve it by writing the augmented matrix and finding the row reduced echelon form.

\[\left[ \begin{array}{ccccc|c} -1 & 2 & 0 & 1 & 1 & 0 \\ 2 & 2 & 6 & 4 & -1 & 0 \\ 1 & -1 & 1 & 0 & 1 & 0 \\ 1 & 2 & 4 & 3 & 2 & 0 \end{array}\right] \xrightarrow{\text{RREF}} \left[ \begin{array}{ccccc|c} 1 & 0 & 2 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right].\]

With three pivots and two free columns, the columns are not linearly independent. We use the null space basis from Example 1: \[S=\left\{\begin{bmatrix}-2\\-1\\ 1\\ 0\\0\end{bmatrix}, \begin{bmatrix}-1\\-1\\ 0\\ 1\\0\end{bmatrix}\right\}\]

These vectors reveal the dependency of non-pivot columns on pivot columns. Since: \[A\begin{bmatrix}-2\\-1\\ 1\\ 0\\0\end{bmatrix}=\mathbf{0} \quad\text{and}\quad A\begin{bmatrix}-1\\-1\\ 0\\ 1\\0\end{bmatrix}=\mathbf{0}\]

It follows from Equation 3.1 that \(-2\mathbf{c}_1-\mathbf{c}_2+\mathbf{c}_3=\mathbf{0}\) and \(-\mathbf{c}_1-\mathbf{c}_2+\mathbf{c}_4=\mathbf{0}\), yielding: \[\begin{align} \mathbf{c}_3 &= 2\mathbf{c}_1+\mathbf{c}_2\\ \mathbf{c}_4 &=\mathbf{c}_1+\mathbf{c}_2 \end{align}\]

These equations show we can express \(\mathbf{c}_3\) and \(\mathbf{c}_4\) using \(\{\mathbf{c}_1,\mathbf{c}_2,\mathbf{c}_5\}\). Therefore, \(\{\mathbf{c}_1,\mathbf{c}_2,\mathbf{c}_5\}\) spans the column space of \(A\). Since this set is linearly independent, it forms a basis: \[\left\{ \begin{bmatrix}-1\\2\\1\\1\end{bmatrix}, \begin{bmatrix}2\\2\\-1\\2\end{bmatrix}, \begin{bmatrix}1\\-1\\1\\2\end{bmatrix} \right\}\]

Pivot Columns Form a Basis for Col(A)

The pivot columns from RREF give us a basis because:

They are linearly independent (due to the pivot structure in RREF)
Every non-pivot column can be written as a combination of pivot columns (using RREF coefficients)

These two properties are precisely what defines a basis. Since this comes from the systematic row reduction process, it works every time.

7.3 The Orthogonal Complement

Let \(W\) be a subspace of \(\mathbb{R}^n\), the set \[W^\perp = \{\mathbf{v} \in \mathbb{R}^n : \mathbf{v} \cdot \mathbf{w} = 0 \text{ for all } \mathbf{w} \in W\}\] is called the orthogonal complement of \(WS\).

Proposition: \(W^\perp\) is a subspace of \(\mathbb{R}^n\)

Proof. We need to check the three conditions:

Zero Vector Property: For any \(\mathbf{w} \in W\), \(\mathbf{0} \cdot \mathbf{w} = 0\) Therefore, \(\mathbf{0} \in W^\perp\)
Closure under Addition: Let \(\mathbf{x}, \mathbf{y} \in W^\perp\) and \(\mathbf{w} \in W\) \((\mathbf{x} + \mathbf{y}) \cdot \mathbf{w} = \mathbf{x} \cdot \mathbf{w} + \mathbf{y} \cdot \mathbf{w} = 0 + 0 = 0\) Therefore, \(\mathbf{x} + \mathbf{y} \in W^\perp\)
Closure under Scalar Multiplication: Let \(\mathbf{x} \in W^\perp\), \(c \in \mathbb{R}\), and \(\mathbf{w} \in W\) \((c\mathbf{x}) \cdot \mathbf{w} = c(\mathbf{x} \cdot \mathbf{w}) = c(0) = 0\) Therefore, \(c\mathbf{x} \in W^\perp\) \(\square\)

7.4 Fundamental Subspaces of a Matrix

Every matrix gives rise to four fundamental subspaces, which are connected through important orthogonality relationships.

Let \(A\) be an \(m \times n\) matrix. Consider its transpose \(A^T\), which is an \(n \times m\) matrix. The four fundamental subspaces are:

The Column Space of \(A\): \(\text{col}(A)\)
- It is a subspace of \(\mathbb{R}^m\)
The Null Space of \(A\): \(\text{nul}(A)\)
- It is a subspace of \(\mathbb{R}^n\)
- Also called the kernel of \(A\)
The column space of \(A^T\): \(\text{col}(A^T)\)
- It is a subspace of \(\mathbb{R}^n\)
- Also called the row space of \(A\)
The Null Space of \(A^T\): \(\text{nul}(A^T)\)
- It is a subspace of \(\mathbb{R}^m\)

Theorem 7.1 Suppose that \(A\) is an \(m\times n\) matrix. then \[\text{col}(A)^\perp = \text{nul}(A^T)\]

Proof. Let \(A\) be an \(m\times n\) matrix and represent \(A\) and \(A^T\) using the columns of \(A\): \[A = \begin{bmatrix} \uparrow & \uparrow & \cdots & \uparrow \\ \mathbf{c}_1 & \mathbf{c}_2 & \cdots & \mathbf{c}_n \\ \downarrow & \downarrow & \cdots & \downarrow \end{bmatrix}\quad\text{and}\quad A^T = \begin{bmatrix} \leftarrow & \mathbf{c}_1^T &\rightarrow\\ \leftarrow & \mathbf{c}_2^T &\rightarrow\\ \vdots &\vdots&\vdots\\ \leftarrow & \mathbf{c}_n^T &\rightarrow\\ \end{bmatrix}\]

Let \(\mathbf{w}\in\text{col}(A)\) and \(\mathbf{v}\in \mathbb{R}^m\). The proof follows from the following observations:

\(\mathbf{w}=x_1\mathbf{c}_1+\cdots+x_n\mathbf{c}_n\) for some \(x_1,\dots,x_n\in\mathbb{R}\).
\(\mathbf{w}\cdot\mathbf{v}=x_1(\mathbf{c}_1\cdot\mathbf{v})+\cdots+x_n(\mathbf{c}_n\cdot\mathbf{v})\)
From Equation 3.3, \[A^T\mathbf{v}=\begin{bmatrix} \leftarrow & \mathbf{c}_1^T &\rightarrow\\ \leftarrow & \mathbf{c}_2^T &\rightarrow\\ \vdots &\vdots&\vdots\\ \leftarrow & \mathbf{c}_n^T &\rightarrow\\ \end{bmatrix}\mathbf{v} =\begin{bmatrix} \mathbf{c}_1\cdot\mathbf{v}\\\mathbf{c}_2\cdot\mathbf{v}\\\vdots\\ \mathbf{c}_n\cdot\mathbf{v} \end{bmatrix}. \]

Then, from 1. and 2. we see that \(\mathbf{v}\in(\text{col}(A))^\perp\) if and only if \(\mathbf{c}_i\cdot\mathbf{v}=0\) for \(i\leq n\). From 3. we see that these statements are equivalent to \(A^T\mathbf{v}=\mathbf{0}\), which is the definition of \(\mathbf{v}\in\text{nul}(A)\). Therefore, \((\text{col}(A))^\perp=\text{nul}(A^T)\)

Replacing \(A\) by \(A^T\) in Theorem 7.1 we get that \[(\text{col}(A^T))^\perp=\text{nul}(A).\]