Proof of the QR decomposition by clearing the first column

Proof

We prove existence by induction on $n$, and uniqueness by comparing two factorisations.

1. For $x, y \in \C^n$ let $\ip{x}{y} = y^* x = \sum_i x_i \overline{y_i}$, where $^*$ is the conjugate transpose. This is an inner product, since it is linear in $x$, $\ip{y}{x} = \overline{\ip{x}{y}}$, and $\ip{x}{x} = \sum_i \abs{x_i}^2 > 0$ for $x \ne 0$.
2. Let $W$ be an $n \times n$ complex matrix with columns $w_1, \dots, w_n$. The $(i, j)$ entry of $W^* W$ is $w_i^* w_j = \ip{w_j}{w_i}$. So $W$ is unitary if and only if its columns form an orthonormal family.
3. For complex matrices $X$ and $Y$ with $XY$ defined, $(XY)^* = Y^* X^*$. This follows from the transpose of a product by taking complex conjugates of all entries.
4. Let $U$ and $V$ be unitary $n \times n$ matrices. Then $(UV)^*(UV) = V^* U^* U V = V^* V = I_n$, so $UV$ is unitary.
5. Since $U^* U = I_n$, the one-sided inverse theorem gives $U U^* = I_n$. As $(U^*)^* = U$, this says that $U^*$ is unitary.
6. Claim: for each $a \in \C^n$ there are a unitary $H$ and a number $\alpha \in \C$ with $Ha = \alpha e_1$, where $e_1$ is the first standard basis vector. If $a = 0$, take $H = I_n$ and $\alpha = 0$.
7. If $a \ne 0$, let $\norm{a} = \sqrt{\ip{a}{a}}$ and $u = a / \norm{a}$. The family $(u)$ is orthonormal. By the existence of an orthonormal basis, it extends to an orthonormal basis $u = w_1, w_2, \dots, w_n$ of $\C^n$.
8. Let $W$ be the matrix with columns $w_1, \dots, w_n$. By step 2, $W$ is unitary. Also $W e_1 = w_1$, so $a = \norm{a}\, W e_1$.
9. Put $H = W^*$, which is unitary by step 5, and $\alpha = \norm{a}$. Then $Ha = \norm{a}\, W^* W e_1 = \alpha e_1$. This proves the claim.
10. Existence for $n = 1$: take $Q = (1)$ and $R = A$. Every $1 \times 1$ matrix is upper triangular.
11. Let $n \ge 2$ and assume existence for size $n - 1$. Let $a$ be the first column of $A$, and take $H$ and $\alpha$ as in step 6.
12. The first column of $HA$ is $Ha = \alpha e_1$. So $HA = \begin{pmatrix} \alpha & r \\ 0 & A' \end{pmatrix}$, with a row $r$ of length $n - 1$ and an $(n-1) \times (n-1)$ matrix $A'$.
13. By the induction hypothesis, $A' = Q' R'$ with $Q'$ unitary and $R'$ upper triangular.
14. Let $G = \begin{pmatrix} 1 & 0 \\ 0 & Q' \end{pmatrix}$. Then $G^* G = \begin{pmatrix} 1 & 0 \\ 0 & Q'^* Q' \end{pmatrix} = I_n$, so $G$ is unitary.
15. Let $R = \begin{pmatrix} \alpha & r \\ 0 & R' \end{pmatrix}$. It is upper triangular because $R'$ is. Block multiplication gives $GR = \begin{pmatrix} \alpha & r \\ 0 & Q'R' \end{pmatrix} = HA$.
16. Multiply step 15 on the left by $H^*$. Since $H^* H = I_n$, we get $A = H^* G R$.
17. Put $Q = H^* G$. It is unitary by steps 4 and 5. So $A = QR$, which completes the induction.
18. Real case: let $A$ be real. Repeat steps 6 to 17 in $\R^n$ with the inner product $\ip{x}{y} = y^T x$. The existence theorem of step 7 also holds over $\R$, so $W$ is real.
19. For real matrices, $X^* = X^T$, so a real unitary matrix is an orthogonal matrix. All matrices built in steps 6 to 17 are then real, so $Q$ is orthogonal and $R$ is real.
20. Uniqueness, first a lemma. Let $T$ be an invertible upper triangular $n \times n$ matrix with entries $t_{ij}$. By the determinant of a triangular matrix, $\det T = t_{11} \cdots t_{nn}$.
21. By the invertibility criterion, $\det T \ne 0$. So $t_{ii} \ne 0$ for all $i$.
22. Fix $j$ and let $x$ be column $j$ of $T^{-1}$, so $Tx = e_j$. For $i > j$, row $i$ of this system reads $\sum_{k \ge i} t_{ik} x_k = 0$.
23. For $i = n, n-1, \dots, j+1$ in turn, this gives $t_{ii} x_i = -\sum_{k > i} t_{ik} x_k = 0$, since the later $x_k$ already vanish. So $x_i = 0$ for all $i > j$.
24. Row $j$ then reads $t_{jj} x_j = 1$. So $T^{-1}$ is upper triangular, with diagonal entries $1/t_{jj}$.
25. If $S$ and $T$ are upper triangular, then $(ST)_{ij} = \sum_k s_{ik} t_{kj}$, and a term is nonzero only if $i \le k \le j$. So $ST$ is upper triangular with diagonal entries $s_{ii} t_{ii}$.
26. Now let $A$ be invertible, and let $A = Q_1 R_1 = Q_2 R_2$ with $Q_1, Q_2$ unitary and $R_1, R_2$ upper triangular with positive diagonal entries.
27. Since the determinant is multiplicative, $0 \ne \det A = \det Q_1 \det R_1$. So $\det R_1 \ne 0$, and $R_1$ is invertible.
28. From $Q_1 R_1 = Q_2 R_2$ we get $Q_2^* Q_1 R_1 = R_2$, so $T = Q_2^* Q_1$ equals $R_2 R_1^{-1}$.
29. By steps 24 and 25, $T$ is upper triangular with positive diagonal entries. By steps 4 and 5, $T$ is unitary.
30. Since $T^* T = I_n$, the one-sided inverse theorem gives $T^{-1} = T^*$. By step 24, $T^*$ is upper triangular.
31. But $T^*$ is the conjugate transpose of an upper triangular matrix, so it is lower triangular. Hence $T^*$ is diagonal, and so is $T$.
32. The diagonal entries $t_{jj}$ are positive reals with $t_{jj}^2 = (T^* T)_{jj} = 1$. So $t_{jj} = 1$ and $T = I_n$.
33. Then $R_2 = T R_1 = R_1$. Also $Q_2^* Q_1 = I_n$, so $Q_1 = Q_2 Q_2^* Q_1 = Q_2$, using $Q_2 Q_2^* = I_n$ from step 5.
34. So every complex $n \times n$ matrix is $QR$, with real orthogonal factors for real $A$. The factorisation is unique for invertible $A$ with positive diagonal in $R$.