16 Orthogonal Complementary Subspaces, Projections, Normal Form

Lecture from 08.11.2024 | Video: Videos ETHZ

Orthogonal Complementary Subspaces

Recall that for a subspace $V$ of ${\mathbb{R}}^n$, its orthogonal complement $V^{\perp }$ is defined as:

$V^{\perp }=\{\mathbf{x}\in {\mathbb{R}}^n|{\mathbf{v}}^T\mathbf{x}=0\text{ for all }\mathbf{v}\in V\}$

$V^{\perp }$ is also a subspace of ${\mathbb{R}}^n$.

Key Properties of Orthogonal Complements:

If $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ is a basis for $V$ and $\{{\mathbf{w}}_1,\dots ,{\mathbf{w}}_l\}$ is a basis for $V^{\perp }$, then:

1. Dimensionality: $l=n-k$ (The dimensions of a subspace and its orthogonal complement add up to the dimension of the ambient space).
2. Basis of ${\mathbb{R}}^n$: $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k,{\mathbf{w}}_1,\dots ,{\mathbf{w}}_l\}$ forms a basis for ${\mathbb{R}}^n$.
3. Unique Decomposition: Every vector $\mathbf{x}\in {\mathbb{R}}^n$ can be uniquely expressed as $\mathbf{x}=\mathbf{v}+\mathbf{w}$, where $\mathbf{v}\in V$ and $\mathbf{w}\in V^{\perp }$.

Also recall the crucial relationship between the nullspace and row space: $N(A)=R(A{)}^{\perp }=C(A^T{)}^{\perp }$.

Decomposition of ${\mathbb{R}}^n$

Lemma: Double Orthogonal Complement

For any subspace $V$ of ${\mathbb{R}}^n$, $V=(V^{\perp }{)}^{\perp }$. (The orthogonal complement of the orthogonal complement of a subspace is the subspace itself.)

Proof

Let $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_k\}$ and $\{{\mathbf{w}}_1,\dots ,{\mathbf{w}}_l\}$ be bases for $V$ and $V^{\perp }$, respectively. We know $l=n-k$.

By definition of orthogonal complements, ${\mathbf{v}}_i^T{\mathbf{w}}_j=0$ for all $i$ and $j$. Consider $(V^{\perp }{)}^{\perp }$: the set of all vectors orthogonal to every vector in $V^{\perp }$. Since ${\mathbf{v}}_i^T{\mathbf{w}}_j=0$, each ${\mathbf{v}}_i$ belongs to $(V^{\perp }{)}^{\perp }$. Therefore, $V\subseteq (V^{\perp }{)}^{\perp }$.

Now, $\text{dim}(V)=k$ and $\text{dim}((V^{\perp }{)}^{\perp })=n-\text{dim}(V^{\perp })=n-(n-k)=k$. Since $V$ is contained within $(V^{\perp }{)}^{\perp }$ and they have the same dimension, we conclude $V=(V^{\perp }{)}^{\perp }$.

Corollary: Decomposition of ${\mathbb{R}}^n$

For any subspace $V$ of ${\mathbb{R}}^n$, ${\mathbb{R}}^n=V+V^{\perp }=\{\mathbf{v}+\mathbf{w}|\mathbf{v}\in V,\mathbf{w}\in V^{\perp }\}$. This means any vector in ${\mathbb{R}}^n$ can be written as the sum of a vector in $V$ and a vector in $V^{\perp }$.

The Set of All Solutions to a System of Linear Equations

Corollary: Nullspace and Column Space of Transpose

For a matrix $A\in {\mathbb{R}}^{m\times n}$, $N(A)=C(A^T{)}^{\perp }$ and $C(A^T)=N(A{)}^{\perp }$.

Understanding Linear Systems

Consider the subspaces $N(A)$ (the nullspace of $A$) and $R(A)=C(A^T)$ (the row space of $A$). These are orthogonal complements in ${\mathbb{R}}^n$. Consequently, any vector $\mathbf{x}\in {\mathbb{R}}^n$ can be uniquely decomposed as $\mathbf{x}={\mathbf{x}}_0+{\mathbf{x}}_1$, where ${\mathbf{x}}_0\in N(A)$ and ${\mathbf{x}}_1\in R(A)$.

Theorem: Solution Set of $A\mathbf{x}=\mathbf{b}$

The set of all solutions to the linear system $A\mathbf{x}=\mathbf{b}$ is given by ${\mathbf{x}}_1+N(A)$, where ${\mathbf{x}}_1\in R(A)$ is a particular solution satisfying $A{\mathbf{x}}_1=\mathbf{b}$.

Proof

• If $\mathbf{x}$ is a solution, then $A(\mathbf{x}-{\mathbf{x}}_1)=A\mathbf{x}-A{\mathbf{x}}_1=\mathbf{b}-\mathbf{b}=0$. This means $\mathbf{x}-{\mathbf{x}}_1\in N(A)$, so $\mathbf{x}={\mathbf{x}}_1+{\mathbf{x}}_0$ for some ${\mathbf{x}}_0\in N(A)$, and thus $\mathbf{x}\in {\mathbf{x}}_1+N(A)$.

• Conversely, if $\mathbf{x}\in {\mathbf{x}}_1+N(A)$, then $\mathbf{x}={\mathbf{x}}_1+{\mathbf{x}}_0$ for some ${\mathbf{x}}_0\in N(A)$. Then $A\mathbf{x}=A({\mathbf{x}}_1+{\mathbf{x}}_0)=A{\mathbf{x}}_1+A{\mathbf{x}}_0=\mathbf{b}+0=\mathbf{b}$, showing that $\mathbf{x}$ is indeed a solution.

A Link Between the Nullspaces of $A$ and $A^{T}A$

Lemma: Nullspaces of $A$ and $A^{T}A$

For any matrix $A\in {\mathbb{R}}^{m\times n}$, the following holds:

• $\mathcal{N}(A)=\mathcal{N}(A^{T}A)$ (The nullspaces of $A$ and $A^{T}A$ are identical.)
• $\mathcal{C}(A^T)=\mathcal{C}(A{A}^T)$ (The column space of $A^T$ is the same as the column space of $A{A}^T$.)

Proof:

• $\mathcal{N}(A)=\mathcal{N}(A^{T}A)$:

  • $\mathcal{N}(A)\subseteq \mathcal{N}(A^{T}A)$: If $\mathbf{x}$ is in the nullspace of $A$ ($A\mathbf{x}=0$), then $A^{T}A\mathbf{x}=A^{T}0=0$. This means $\mathbf{x}$ is also in the nullspace of $A^{T}A$.
  • $\mathcal{N}(A^{T}A)\subseteq \mathcal{N}(A)$: If $\mathbf{x}$ is in the nullspace of $A^{T}A$ ($A^{T}A\mathbf{x}=0$), pre-multiplying by ${\mathbf{x}}^T$ gives ${\mathbf{x}}^T{A}^{T}A\mathbf{x}=(A\mathbf{x}{)}^T(A\mathbf{x})=\Vert A\mathbf{x}{\Vert }^2=0$. The squared norm of a vector is zero if and only if the vector itself is zero. Thus, $A\mathbf{x}=0$, meaning $\mathbf{x}$ is in the nullspace of $A$.

• $\mathcal{C}(A^T)=\mathcal{C}(A{A}^T)$: We know from previous results that $\mathcal{C}(A^T)=\mathcal{N}(A{)}^{\perp }$ (the column space of $A^T$ is the orthogonal complement of the nullspace of $A$) and $\mathcal{C}(A{A}^T)=\mathcal{N}(A^{T}A{)}^{\perp }$. Since we’ve just proven that $\mathcal{N}(A)=\mathcal{N}(A^{T}A)$, their orthogonal complements must also be equal. Therefore, $\mathcal{C}(A^T)=\mathcal{C}(A{A}^T)$.

Projections

Note for readers: This is a much more intuitive and simpler explanation of this part…

Definition: Projection of a Vector onto a Subspace

The projection of a vector $\mathbf{b}\in {\mathbb{R}}^m$ onto a subspace $S\subseteq {\mathbb{R}}^m$ is the point $\mathbf{p}\in S$ closest to $\mathbf{b}$. Formally:

${\text{proj}}_S(\mathbf{b})=\underset{\mathbf{p}\in S}{\mathrm{argmin}}\Vert \mathbf{b}-\mathbf{p}\Vert$

This is well-defined if the minimum exists and is unique.

The One-Dimensional Case

Lemma: Projection onto a Line

Let $\mathbf{a}\in {\mathbb{R}}^m,\mathbf{a}\ne 0$. The projection of $\mathbf{b}\in {\mathbb{R}}^m$ onto the line $S=\{\lambda \mathbf{a}|\lambda \in \mathbb{R}\}=\mathcal{C}(\mathbf{a})$ is given by:

${\text{proj}}_S(\mathbf{b})=\frac{\mathbf{a}{\mathbf{a}}^T}{{\mathbf{a}}^T\mathbf{a}}\mathbf{b}=\frac{{\mathbf{a}}^T\mathbf{b}}{\Vert \mathbf{a}{\Vert }^2}\mathbf{a}$

Here’s how we derive this formula, starting with the geometric intuition that the error vector ($\mathbf{b}$ minus its projection) is orthogonal to $\mathbf{a}$:

1. Orthogonality Condition: The projection of $\mathbf{b}$ onto the line spanned by $\mathbf{a}$ is some scalar multiple of $\mathbf{a}$. Let’s call this scalar $\lambda$. So, the projection is $\lambda \mathbf{a}$. The error vector is $\mathbf{b}-\lambda \mathbf{a}$. This error vector must be orthogonal to $\mathbf{a}$. Mathematically, this orthogonality is expressed as: ${\mathbf{a}}^T(\mathbf{b}-\lambda \mathbf{a})=0$

2. Solving for $\lambda$: Expanding the dot product gives:

   ${\mathbf{a}}^T\mathbf{b}-\lambda {\mathbf{a}}^T\mathbf{a}=0$

   Solving for $\lambda$:

   $\lambda =\frac{{\mathbf{a}}^T\mathbf{b}}{{\mathbf{a}}^T\mathbf{a}}=\frac{{\mathbf{a}}^T\mathbf{b}}{\Vert \mathbf{a}{\Vert }^2}$

3. The Projection Formula: Substituting this value of $\lambda$ back into the expression for the projection ($\lambda \mathbf{a}$) gives:

   ${\text{proj}}_S(\mathbf{b})=\frac{{\mathbf{a}}^T\mathbf{b}}{\Vert \mathbf{a}{\Vert }^2}\mathbf{a}=\frac{\mathbf{a}{\mathbf{a}}^T}{{\mathbf{a}}^T\mathbf{a}}\mathbf{b}$

   The second form arises from recognizing that ${\mathbf{a}}^T\mathbf{b}$ is a scalar, and scalar multiplication is commutative. $\frac{\mathbf{a}{\mathbf{a}}^T}{{\mathbf{a}}^T\mathbf{a}}$ is often called the projection matrix (for projection onto the line spanned by $\mathbf{a}$).

Proof

Let $\mathbf{p}\in S$, so $\mathbf{p}=\lambda \mathbf{a}$ for some scalar $\lambda$. Our goal is to find the value of $\lambda$ that minimizes the distance between $\mathbf{b}$ and $\mathbf{p}$, which is equivalent to minimizing the squared distance $\Vert \mathbf{b}-\mathbf{p}{\Vert }^2=\Vert \mathbf{b}-\lambda \mathbf{a}{\Vert }^2$.

1. Expanding the Squared Distance: We expand the squared distance using the dot product: $\Vert \mathbf{b}-\lambda \mathbf{a}{\Vert }^2=(\mathbf{b}-\lambda \mathbf{a}{)}^T(\mathbf{b}-\lambda \mathbf{a})$

   Distributing the terms gives: $={\mathbf{b}}^T\mathbf{b}-\lambda {\mathbf{b}}^T\mathbf{a}-\lambda {\mathbf{a}}^T\mathbf{b}+{\lambda }^2{\mathbf{a}}^T\mathbf{a}$

   Since ${\mathbf{b}}^T\mathbf{a}$ and ${\mathbf{a}}^T\mathbf{b}$ are both scalars and equal to each other (dot product is commutative), we can simplify this to:

   $=\Vert \mathbf{b}{\Vert }^2-2\lambda {\mathbf{b}}^T\mathbf{a}+{\lambda }^2\Vert \mathbf{a}{\Vert }^2$

   Let’s call this expression $g(\lambda )$.

2. Minimizing $g(\lambda )$: To find the minimum value of $g(\lambda )$, we take its derivative with respect to $\lambda$ and set it equal to zero:

   $\frac{dg(\lambda )}{d\lambda }=-2{\mathbf{b}}^T\mathbf{a}+2\lambda \Vert \mathbf{a}{\Vert }^2=0$

3. Solving for $\lambda$: Now we solve for $\lambda$:

   $2\lambda \Vert \mathbf{a}{\Vert }^2=2{\mathbf{b}}^T\mathbf{a}$

   $\lambda =\frac{{\mathbf{b}}^T\mathbf{a}}{\Vert \mathbf{a}{\Vert }^2}$ This value of $\lambda$ minimizes the squared distance. Let’s call it ${\lambda }^{\ast }$.

4. The Projection: Substitute ${\lambda }^{\ast }$ back into the expression for the projection $\mathbf{p}=\lambda \mathbf{a}$:

   ${\text{proj}}_S(\mathbf{b})={\lambda }^{\ast }\mathbf{a}=\frac{{\mathbf{b}}^T\mathbf{a}}{\Vert \mathbf{a}{\Vert }^2}\mathbf{a}$

   This can also be written as:

   ${\text{proj}}_S(\mathbf{b})=\frac{\mathbf{a}{\mathbf{a}}^T}{{\mathbf{a}}^T\mathbf{a}}\mathbf{b}$

   because ${\mathbf{a}}^T\mathbf{b}$ is a scalar and can be moved to the left of $\mathbf{a}$. $\mathbf{a}{\mathbf{a}}^T$ is a matrix, and ${\mathbf{a}}^T\mathbf{a}=\Vert \mathbf{a}{\Vert }^2$ is a scalar.

Intuition and Check

• Orthogonality of the Error Vector: The error vector $\mathbf{e}=\mathbf{b}-{\text{proj}}_S(\mathbf{b})$ is orthogonal to $\mathbf{a}$. You can verify this by computing ${\mathbf{a}}^T\mathbf{e}$. This orthogonality is a fundamental property of projections.

• Projection of a Collinear Vector: If $\mathbf{b}$ is already a multiple of $\mathbf{a}$ (i.e., $\mathbf{b}$ lies on the line spanned by $\mathbf{a}$), then the projection of $\mathbf{b}$ onto $S$ should be $\mathbf{b}$ itself. You can verify this using the formula. This makes intuitive sense, as the closest point on the line to a point already on the line is the point itself.

The General Case: Projection onto a Subspace

Lemma: Projection onto a Subspace

Let $S$ be an $n$-dimensional subspace of ${\mathbb{R}}^m$, and let $\{{\mathbf{a}}_1,\dots ,{\mathbf{a}}_n\}$ be a basis for $S$. Form the matrix $A=[\begin{array}{cccc}|& |& & |\\ a_1& a_2& \cdots & a_n\\ |& |& & |\end{array}]$, so $S=\mathcal{C}(A)$ (meaning $S$ is the column space of $A$). The projection of a vector $\mathbf{b}\in {\mathbb{R}}^m$ onto $S$ is given by ${\text{proj}}_S(\mathbf{b})=A\hat{\mathbf{x}}$, where $\hat{\mathbf{x}}$ satisfies the normal equations:

$A^{T}A\hat{\mathbf{x}}=A^T\mathbf{b}$

Proof

1. Decomposition of b: We can decompose $\mathbf{b}$ into two components: $\mathbf{b}=\mathbf{p}+\mathbf{e}$, where $\mathbf{p}$ is the projection of $\mathbf{b}$ onto $S$ (so $\mathbf{p}\in S$), and $\mathbf{e}$ is the error vector, which is orthogonal to $S$ (so $\mathbf{e}\in S^{\perp }$).

2. Minimizing the Distance: The projection $\mathbf{p}$ is the point in $S$ that is closest to $\mathbf{b}$. This means we want to minimize the distance between $\mathbf{b}$ and any arbitrary point ${\mathbf{p}}^{\prime }$ in $S$. We do this by minimizing the squared distance $\Vert \mathbf{b}-{\mathbf{p}}^{\prime }{\Vert }^2$.

3. Considering another point in S: Let ${\mathbf{p}}^{\prime }$ be any other point in $S$. Since both $\mathbf{p}$ and ${\mathbf{p}}^{\prime }$ are in $S$, their difference $\mathbf{p}-{\mathbf{p}}^{\prime }$ is also in $S$. Because $\mathbf{e}$ is orthogonal to $S$, $\mathbf{e}$ is orthogonal to $\mathbf{p}-{\mathbf{p}}^{\prime }$. This means their dot product is zero: $(\mathbf{p}-{\mathbf{p}}^{\prime }{)}^T\mathbf{e}=0$

4. Expanding the Squared Distance: Now, let’s expand the squared distance between $\mathbf{b}$ and ${\mathbf{p}}^{\prime }$: $\Vert \mathbf{b}-{\mathbf{p}}^{\prime }{\Vert }^2=\Vert \mathbf{p}+\mathbf{e}-{\mathbf{p}}^{\prime }{\Vert }^2=\Vert (\mathbf{p}-{\mathbf{p}}^{\prime })+\mathbf{e}{\Vert }^2$

   Using the Pythagorean theorem (which applies because $\mathbf{p}-{\mathbf{p}}^{\prime }$ and $\mathbf{e}$ are orthogonal), we get: $=\Vert \mathbf{p}-{\mathbf{p}}^{\prime }{\Vert }^2+\Vert \mathbf{e}{\Vert }^2$

   Since $\Vert \mathbf{p}-{\mathbf{p}}^{\prime }{\Vert }^2$ is always non-negative, this entire expression is greater than or equal to $\Vert \mathbf{e}{\Vert }^2$:

   $\Vert \mathbf{b}-{\mathbf{p}}^{\prime }{\Vert }^2\ge \Vert \mathbf{e}{\Vert }^2=\Vert \mathbf{b}-\mathbf{p}{\Vert }^2$

5. The Minimum Distance: The inequality above shows that the squared distance between $\mathbf{b}$ and any point ${\mathbf{p}}^{\prime }$ in $S$ is always greater than or equal to $\Vert \mathbf{e}{\Vert }^2$, which is the squared distance between $\mathbf{b}$ and $\mathbf{p}$. The minimum distance is achieved when ${\mathbf{p}}^{\prime }=\mathbf{p}$.

6. Expressing the Projection: Since $\mathbf{p}$ is in the column space of $A$ ($\mathbf{p}\in \mathcal{C}(A)$), we can express $\mathbf{p}$ as a linear combination of the columns of $A$: $\mathbf{p}=A\hat{\mathbf{x}}$ for some vector $\hat{\mathbf{x}}\in {\mathbb{R}}^n$.

7. Orthogonality and the Normal Equations: The error vector $\mathbf{e}=\mathbf{b}-A\hat{\mathbf{x}}$ is orthogonal to $S$. This means $\mathbf{e}$ is orthogonal to every vector in $S$, including the basis vectors ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_n$ that form the columns of $A$. So, for each column ${\mathbf{a}}_i$: ${\mathbf{a}}_i^T(\mathbf{b}-A\hat{\mathbf{x}})=0$

   This can be written compactly as: $A^T(\mathbf{b}-A\hat{\mathbf{x}})=0$

   Distributing $A^T$ gives us the normal equations: $A^{T}A\hat{\mathbf{x}}=A^T\mathbf{b}$

Solving this system of equations for $\hat{\mathbf{x}}$ allows us to compute the projection $\mathbf{p}=A\hat{\mathbf{x}}$.

Continue here: 17 Projections, Least Squares, Linear Regression