QR Factorization

🧩 The Decomposition

Any matrix $A$ with linearly independent columns can be factored as:

$$ A = Q R $$

Q: Orthogonal

Columns are orthonormal basis vectors (from Gram-Schmidt).

R: Upper Triangular

Contains the coefficients from the Gram-Schmidt process.

Existence Theorem

Let $A$ be an $m \times n$ matrix with linearly independent columns. Then $A$ can be factored as $A=QR$, where:

$Q$ is an $m \times n$ matrix with orthonormal columns.
$R$ is an $n \times n$ upper triangular matrix with positive diagonal entries.

Note: If $A$ is square ($m=n$), then $Q$ is orthogonal.

⚙️ The QR Algorithm

We use the Gram-Schmidt process on the columns of $A = [\vec{c}_1, \dots, \vec{c}_n]$.

Step 1: Find Q

Apply Gram-Schmidt to $\{\vec{c}_1, \dots, \vec{c}_n\}$ to get orthogonal vectors $\{\vec{f}_1, \dots, \vec{f}_n\}$.

Normalize them to get orthonormal vectors $\{\vec{q}_1, \dots, \vec{q}_n\}$.

$$ Q = [\vec{q}_1 \quad \vec{q}_2 \quad \dots \quad \vec{q}_n] $$

Step 2: Find R

Since $A = QR$, we have $R = Q^T A$. The entries $r_{ij}$ are given by:

$$ r_{ij} = \vec{q}_i \cdot \vec{c}_j \quad (\text{for } i \le j) $$

Entries below the diagonal ($i > j$) are 0.

📝 Worked Example

Find the QR factorization of $A = \begin{bmatrix} 4 & 1 \\ 2 & 3 \\ 0 & 1 \end{bmatrix}$.

1. Gram-Schmidt on Columns

$\vec{c}_1 = (4, 2, 0)$. Let $\vec{f}_1 = \vec{c}_1$. $\|\vec{f}_1\| = \sqrt{20}$.

$\vec{q}_1 = \frac{1}{\sqrt{20}}(4, 2, 0)$.

$\vec{c}_2 = (1, 3, 1)$.

$\vec{f}_2 = \vec{c}_2 - \text{proj}_{\vec{f}_1}(\vec{c}_2) = (1, 3, 1) - \frac{10}{20}(4, 2, 0) = (-1, 2, 1)$.

$\|\vec{f}_2\| = \sqrt{6}$. $\vec{q}_2 = \frac{1}{\sqrt{6}}(-1, 2, 1)$.

2. Construct Q and R

$$ Q = \begin{bmatrix} \frac{4}{\sqrt{20}} & \frac{-1}{\sqrt{6}} \\ \frac{2}{\sqrt{20}} & \frac{2}{\sqrt{6}} \\ 0 & \frac{1}{\sqrt{6}} \end{bmatrix} $$

$$ r_{11} = \|\vec{f}_1\| = \sqrt{20}, \quad r_{12} = \vec{q}_1 \cdot \vec{c}_2 = \sqrt{5}, \quad r_{22} = \|\vec{f}_2\| = \sqrt{6} $$

$$ R = \begin{bmatrix} \sqrt{20} & \sqrt{5} \\ 0 & \sqrt{6} \end{bmatrix} $$

QR Explorer

See the QR decomposition for a simple $2 \times 2$ matrix.
$A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$ (Shear)

Matrix A

[[1, 1],
[0, 1]]

Note: For $A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}$, the first column is $\vec{e}_1$. The second column projects onto $\vec{e}_1$ as 1. So Gram-Schmidt gives $\vec{q}_1=\vec{e}_1, \vec{q}_2=\vec{e}_2$. Thus $Q=I, R=A$.