# QR Decomposition

### Big Ideas
The **QR Decomposition** of a matrix $A$ (where $A=QR$) is a powerful tool for finding *orthonormal bases (ONB)* for the fundamental subspaces associated with $A$. Specifically, if $A$ is an $m \times n$ matrix with full column rank ($\mathrm{rank}(A)=n$), the decomposition splits the $m \times m$ orthogonal matrix $Q$ into $Q=[Q_1 \ Q_2]$:
* The $n$ columns of $Q_1$ form an *ONB for the range* (column space) of $A$, $\mathcal{R}(A)$.
* The remaining $m-n$ columns of $Q_2$ form an *ONB for the orthogonal complement of the range*, $\mathcal{R}(A)^{\perp}$.

## Orthogonal Matrices
:::info
**Definition:**
An orthogonal matrix $A$ is a square matrix whose transpose is its inverse:
$$
A^T A = A A^T = I_n
$$
:::

:::danger
**Proposition** Let $A$ be an orthogonal matrix.
* $A^T = A^{-1}$, i.e. its columns (and rows) form an orthonormal basis.
* $\| A \mathbf{x} \| = \| \mathbf{x} \|$ for all $\mathbf{x} \in \mathbb{R}^n$.
* $\det(A) = \pm 1$.
* The product of two orthogonal matrices is also orthogonal.
:::

:::warning
**Examples**

1. **Rotation Matrices:** A rotation matrix transforms a vector in a coordinate plane while preserving its length.
* 2D Rotation (about the origin): $$A = \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{bmatrix}$$
* 3D Rotation (around the $z$-axis): $$A = \begin{bmatrix} \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{bmatrix}$$

2. **Reflection Matrices:** A reflection matrix performs an orthogonal reflection with respect to a subspace $U$.
* The reflection matrix $R_U$ is defined using the projection matrix onto the orthogonal complement, $P_{U^\perp}$: $$R_U(\mathbf{x}) = \mathbf{x} - 2 P_{U^\perp} \mathbf{x} \equiv R_U \mathbf{x}$$
* (Reflection with respect to the $x$-axis in $\mathbb{R}^2$) Let $U = \operatorname{span}\left\{ \begin{bmatrix} 1 \\ 0 \end{bmatrix} \right\}$ (the $x$-axis).
* The projection matrix onto $U^\perp$ (the $y$-axis) is $P_{U^\perp} = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}$.
* The reflection matrix $R_U$ is:$$R_U = I_2 - 2 P_{U^\perp} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} - 2 \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$$
* Applying $R_U$ reflects a vector $\mathbf{x}=\begin{bmatrix} x \\ y \end{bmatrix}$ across the $x$-axis:$$R_U \left( \begin{bmatrix} x \\ y \end{bmatrix} \right) = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} x \\ -y \end{bmatrix}$$
:::

## QR by Gram-Schmidt
The QR decomposition for an $m \times n$ matrix $A$ with $m \ge n$ and $\operatorname{rank}(A) = n$ is

$$
A = QR
$$

where
* $Q$ is $m \times m$ orthogonal
* $R$ is $m \times n$ upper triangular.

The most fundamental way to derive this decomposition uses the *Gram-Schmidt process* on the linearly independent columns of $A$.

:::info
**Algorithm (QR by Gram-Schmidt)**
1. **Orthonormal Basis:** The Gram-Schmidt algorithm takes the columns of $A$, $\{\mathbf{a}_1, \dots, \mathbf{a}_n\}$, and produces an ONB $\{\mathbf{w}_1, \dots, \mathbf{w}_n\}$ for $\mathcal{R}(A)$.
2. **Upper Triangular Matrix $R_1$:** Because each original vector $\mathbf{a}_i$ is a linear combination of the first $i$ orthonormal vectors $\{\mathbf{w}_1, \dots, \mathbf{w}_i\}$, the relationship $A = Q_1 R_1$ holds: $$\mathbf{a}_k = \sum_{i=1}^k \langle \mathbf{w}_i, \mathbf{a}_k \rangle \mathbf{w}_i$$ When expressed in matrix form, the coefficients $\langle \mathbf{w}_i, \mathbf{a}_k \rangle$ form the entries of an *upper triangular matrix* $R_1$, where $Q_1 = [\mathbf{w}_1 \mid \dots \mid \mathbf{w}_n]$.
3. **Full QR:** The orthonormal basis $\{\mathbf{w}_1, \dots, \mathbf{w}_n\}$ is extended to a full ONB for $\mathbb{R}^m$, $\{\mathbf{w}_1, \dots, \mathbf{w}_m\}$, where the additional vectors $\{\mathbf{w}_{n+1}, \dots, \mathbf{w}_m\}$ form an ONB for the orthogonal complement, $\mathcal{R}(A)^\perp$ (which is $\mathcal{N}(A^T)$). Setting $Q=[\mathbf{w}_1 \mid \dots \mid \mathbf{w}_m]$ and $R = \begin{bmatrix} R_1 \\ \mathbf{0} \end{bmatrix}$, we get the full decomposition $A = QR$.
:::

:::warning
**Example** Consider the $4 \times 3$ matrix $A$, which has full column rank ($\mathrm{rank}(A)=3$):
$$
A = \begin{bmatrix} \mathbf{a}_1 & \mathbf{a}_2 & \mathbf{a}_3 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 0 \\ -1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}
$$

1. We use the Gram-Schmidt process to find an orthonormal basis (ONB) $\{\mathbf{w}_1, \mathbf{w}_2, \mathbf{w}_3\}$ for the column space $\mathcal{R}(A)$.
* Orthonormalize $\mathbf{a}_1$ to get $\mathbf{w}_1$:$$\mathbf{v}_1 = \mathbf{a}_1 = \begin{bmatrix} 1 \\ -1 \\ 0 \\ 0 \end{bmatrix} \quad \implies \quad \mathbf{w}_1 = \frac{\mathbf{v}_1}{\|\mathbf{v}_1\|} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix}$$
* Orthonormalize $\mathbf{a}_2$ to get $\mathbf{w}_2$: The intermediate orthogonal vector is $\mathbf{v}_2 = \mathbf{a}_2 - \mathrm{proj}_{\mathbf{v}_1}(\mathbf{a}_2)$.$$\mathbf{v}_2 \quad \implies \quad \mathbf{w}_2 = \frac{1}{\sqrt{6}} \begin{bmatrix} 1 \\ 1 \\ 2 \\ 0 \end{bmatrix}$$
* Orthonormalize $\mathbf{a}_3$ to get $\mathbf{w}_3$:The intermediate orthogonal vector is $\mathbf{v}_3 = \mathbf{a}_3 - \mathrm{proj}_{\mathbf{v}_1}(\mathbf{a}_3) - \mathrm{proj}_{\mathbf{v}_2}(\mathbf{a}_3)$.$$\mathbf{v}_3 = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} \quad \implies \quad \mathbf{w}_3 = \frac{1}{1} \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix}$$

2. ($A = Q_1 R_1$) The first three orthonormal vectors form the matrix $Q_1$, and the coefficients from the projection formula form the upper triangular matrix $R_1$: $$Q_1 = [\mathbf{w}_1 \mid \mathbf{w}_2 \mid \mathbf{w}_3] = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} & 0 \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} & 0 \\ 0 & \frac{2}{\sqrt{6}} & 0 \\ 0 & 0 & 1 \end{bmatrix}$$ $$R_1 = \begin{bmatrix} \langle \mathbf{w}_1, \mathbf{a}_1 \rangle & \langle \mathbf{w}_1, \mathbf{a}_2 \rangle & \langle \mathbf{w}_1, \mathbf{a}_3 \rangle \\ 0 & \langle \mathbf{w}_2, \mathbf{a}_2 \rangle & \langle \mathbf{w}_2, \mathbf{a}_3 \rangle \\ 0 & 0 & \langle \mathbf{w}_3, \mathbf{a}_3 \rangle \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} 2 & 1 & 1 \\ 0 & \sqrt{3} & \sqrt{3} \\ 0 & 0 & \sqrt{2} \end{bmatrix}$$

3. ($A = QR$) To form the full decomposition, we need to extend $\{\mathbf{w}_1, \mathbf{w}_2, \mathbf{w}_3\}$ to a complete ONB for $\mathbb{R}^4$ by finding a vector $\mathbf{w}_4$ that spans the orthogonal complement, $\mathcal{R}(A)^{\perp}$.
* Complementary Vector $\mathbf{w}_4$: By applying Gram-Schmidt to find a vector orthogonal to $Q_1$, we get the vector $\mathbf{w}_4$: $$\mathbf{w}_4 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \\ 0 \\ 0 \end{bmatrix}$$
* Full Matrices $Q$ and $R$:$$Q = [\, Q_1 \ \ \mathbf{w}_4 \,] = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} & 0 & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} & 0 & -\frac{1}{\sqrt{2}} \\ 0 & \frac{2}{\sqrt{6}} & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$ $$R = \begin{bmatrix} R_1 \\ \mathbf{0} \end{bmatrix} = \begin{bmatrix} \frac{2}{\sqrt{2}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ 0 & \frac{\sqrt{3}}{\sqrt{6}} & \frac{\sqrt{3}}{\sqrt{6}} \\ 0 & 0 & \frac{\sqrt{2}}{\sqrt{2}} \\ 0 & 0 & 0 \end{bmatrix} \quad \implies \quad R = \begin{bmatrix} \sqrt{2} & 1/\sqrt{2} & 1/\sqrt{2} \\ 0 & 1/\sqrt{2} & 1/\sqrt{2} \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}$$
:::

## Orthogonal Projection by QR
The QR decomposition provides an elegant way to compute orthogonal projections onto the fundamental subspaces.

:::danger
**Theorem**
Let $A = QR$ be the QR decomposition, with $Q_1$ containing the first $n$ columns of $Q$.
* The projection of a vector $\mathbf{x} \in \mathbb{R}^m$ onto the *range* $\mathcal{R}(A)$ is given by the projection matrix $P = Q_1 Q_1^T$:$$\mathrm{proj}_{\mathcal{R}(A)}(\mathbf{x}) = Q_1 Q_1^T \mathbf{x}$$
* The projection onto the *orthogonal complement* $\mathcal{R}(A)^{\perp}$ is given by the complementary projection matrix $P_{\perp} = Q_2 Q_2^T$:$$\mathrm{proj}_{\mathcal{R}(A)^{\perp}}(\mathbf{x}) = Q_2 Q_2^T \mathbf{x}$$
:::

:::success
**Exercise**
1. Determine which statement correctly defines orthogonality based on matrix products.
* a. If $A^T A$ is a diagonal matrix, then the columns of $A$ are orthogonal.
* b. If $A A^T$ is a diagonal matrix, then the columns of $A$ are orthogonal.
* c. If $A^T A$ is a diagonal matrix, then the rows of $A$ are orthogonal.
* d. If $A A^T$ is a diagonal matrix, then the rows of $A$ are orthogonal.
2. Let $A = QR$ where $Q$ is orthogonal and $R$ is upper triangular. Then
* a. $\|A\|_2 = \|R\|_2$.
* b. $\|A\|_p = \|R\|_p$ for any $p \ge 1$.
3. Compute the thin QR decomposition of the matrix $A = \left[ \begin{array}{rr} 1 & 1 \\ 1 & -1 \\ 1 & 1 \\ 1 & 1 \end{array} \right]$.
:::