Proof of Gram-Schmidt Orthonormalisation

Write (I$k$) for claim $k$ of Elementary Properties of an Orthonormal Family, (L$k$) for claim $k$ of Elementary Properties of Linear Independence, (P$k$) for claim $k$ of The Span of a Finite Family is the Smallest Subspace Containing It, and (M$k$) for claim $k$ of Properties of Complex Conjugation and Modulus. Let $\lVert\cdot\rVert$ be the induced norm, which is a norm by claim 2 of The Induced Norm is a Norm, and Induces a Metric, and let $|z|$ be the modulus of a complex number $z$. Sums of vectors are finite sums in $V$, and $x-y$ abbreviates $x+(-y)$ with the additive inverse of claim 2 of Elementary Identities in a Vector Space.

Normalisation. Let $x\in V$ with $x\ne 0_{V}$, where $0_{V}$ is the zero vector. By the positivity of a norm, $\lVert x\rVert$ is a real number with $0\le\lVert x\rVert$ and $\lVert x\rVert\ne 0$, so $\lambda=\lVert x\rVert^{-1}$ exists in the field of complex numbers. By the absolute homogeneity of a norm, then (M8) applied to the nonnegative real number $\lVert x\rVert$, then (M4),

By (M4) again, $|1|=|1|\,|1|$, and $|1|\ne 0$ by (M3) because $1\ne 0$; multiplying by the inverse of $|1|$ gives $|1|=1$. Hence $\lambda x$ is a unit vector. Note also $\lambda\ne 0$, since $\lambda\lVert x\rVert=1\ne 0$.

The induction. Let $A$ be the set of those $q\in\mathbb{N}$ such that for every linearly independent $c\in V^{q}$ there is an orthonormal $f\in V^{q}$ with $\operatorname{span}(f|_{[k]})=\operatorname{span}(c|_{[k]})$ for every $k\in[q]$. We show $A=\mathbb{N}$ by Principle of Induction for the Natural Numbers.

Base case. Let $c\in V^{1}$ be linearly independent. By (L2), $c_{1}\ne 0_{V}$. Put $\lambda=\lVert c_{1}\rVert^{-1}$ and let $f\in V^{1}$ have component $f_{1}=\lambda c_{1}$. By normalisation $f_{1}$ is a unit vector, and $f$ is orthonormal because $[1]$ contains no two distinct indices. Since $f_{1}=\lambda c_{1}$ lies in $\operatorname{span}(c)$ and $c_{1}=\lambda^{-1}f_{1}$ lies in $\operatorname{span}(f)$, and both spans are linear subspaces by (P1), two applications of (P3) give $\operatorname{span}(f)=\operatorname{span}(c)$. As $[1]$ has the single element $1$ and $f|_{[1]}=f$, $c|_{[1]}=c$, this is the required equality, so $1\in A$.

Induction step. Let $q\in A$ and let $b'\in V^{q+1}$ be linearly independent. By (L1) the restriction $b'|_{[q]}$ is linearly independent, so there is an orthonormal $f\in V^{q}$ with

In particular, taking $k=q$ and using $f|_{[q]}=f$, we get $\operatorname{span}(f)=\operatorname{span}(b'|_{[q]})$.

Apply (I4) to the orthonormal tuple $f$ and the vector $u=b'_{q+1}$: with

one has $u=w+p$ and $\langle f_{j},w\rangle=0$ for every $j\in[q]$.

The vector $w$ is not $0_{V}$. By the definition of the span, $p\in\operatorname{span}(f)=\operatorname{span}(b'|_{[q]})$. If $w=0_{V}$, then $u=p$, so $b'_{q+1}\in\operatorname{span}(b'|_{[q]})$, contradicting (L2) applied to $b'$ with $q+1\in[q+1]$.

Put $\mu=\lVert w\rVert^{-1}$ and define $e\in V^{q+1}$ by $e_{k}=f_{k}$ for $k\in[q]$ and $e_{q+1}=\mu w$.

The tuple $e$ is orthonormal. Each $e_{k}$ with $k\in[q]$ is a unit vector because $f$ is orthonormal, and $e_{q+1}$ is a unit vector by normalisation. Let $i,j\in[q+1]$ be distinct. If both lie in $[q]$, then $e_{i}$ and $e_{j}$ are orthogonal because $f$ is orthonormal. Otherwise exactly one of them equals $q+1$; for $j\in[q]$, condition 3 of Complex Inner Product Space gives

and condition 1 of that definition together with (M1), which gives $\overline{0}=0$ since $0$ is real, yields $\langle e_{q+1},e_{j}\rangle=\overline{\langle e_{j},e_{q+1}\rangle}=0$.

The span equalities. For $k\in[q]$ we have $e|_{[k]}=f|_{[k]}$, so those equalities are exactly the ones already obtained. There remains $k=q+1$, that is, $\operatorname{span}(e)=\operatorname{span}(b')$. By (P1) both spans are linear subspaces of $V$, and by (P1) each component of a tuple lies in its own span.

First, $\operatorname{span}(f)\subseteq\operatorname{span}(e)$: each $f_{k}=e_{k}$ lies in $\operatorname{span}(e)$, so (P3) applies. Every component $b'_{k}$ with $k\in[q]$ lies in $\operatorname{span}(b'|_{[q]})=\operatorname{span}(f)\subseteq\operatorname{span}(e)$, and

where $p\in\operatorname{span}(f)\subseteq\operatorname{span}(e)$ and $\mu^{-1}e_{q+1}\in\operatorname{span}(e)$ by condition 3 of Linear Subspace; hence $b'_{q+1}\in\operatorname{span}(e)$ by condition 2 of that definition. So every component of $b'$ lies in $\operatorname{span}(e)$, and (P3) gives $\operatorname{span}(b')\subseteq\operatorname{span}(e)$.

Conversely, every component $b'_{k}$ with $k\in[q]$ lies in $\operatorname{span}(b')$, so (P3) gives $\operatorname{span}(b'|_{[q]})\subseteq\operatorname{span}(b')$, whence $\operatorname{span}(f)\subseteq\operatorname{span}(b')$ and in particular $e_{k}=f_{k}\in\operatorname{span}(b')$ for $k\in[q]$, and $p\in\operatorname{span}(b')$. Since $b'_{q+1}\in\operatorname{span}(b')$ and $\operatorname{span}(b')$ is a linear subspace, conditions 2 and 3 of Linear Subspace together with claim 5 of Elementary Identities in a Vector Space give $w=b'_{q+1}+(-1)p\in\operatorname{span}(b')$ and then $e_{q+1}=\mu w\in\operatorname{span}(b')$. So every component of $e$ lies in $\operatorname{span}(b')$, and (P3) gives $\operatorname{span}(e)\subseteq\operatorname{span}(b')$.

Therefore $\operatorname{span}(e)=\operatorname{span}(b')$ and $q+1\in A$.

By Principle of Induction for the Natural Numbers, $A=\mathbb{N}$; in particular $m\in A$, which applied to the given tuple $b$ is the assertion.