Proof of Gram-Schmidt Orthonormalization of a Finite Family of Vectors

All dot products are those of $\mathbb{R}^{n}$, and $\sqrt{\,\cdot\,}$ is the positive square root. We use that $v\cdot v=\sum_{j}v_j^{2}\ge0$, with $v\cdot v>0$ exactly when $v$ is not the zero vector, directly from the definition of the dot product. The proof is by induction on $r$.

Base $r=1$. If $x_1=0$, the first alternative holds. Otherwise set $s=\sqrt{x_1\cdot x_1}>0$ and $e_1=(1/s)\,x_1$. Then $e_1\cdot e_1=(1/s^{2})\,x_1\cdot x_1=1$, so $(e_1)$ is an orthonormal family with $p=1\le r$; moreover $x_1\cdot e_1=(1/s)\,x_1\cdot x_1=s$, so $x_1=s\,e_1=(x_1\cdot e_1)\,e_1$, proving part 1, and part 2 holds with $c_{11}=1/s$.

Step from $r-1$ to $r$, $r\ge2$. Apply the induction hypothesis to $x_1,\dots,x_{r-1}$. There are two cases.

Case (i): $x_1,\dots,x_{r-1}$ are all zero. If also $x_r=0$, the first alternative holds. Otherwise the base construction applied to $x_r$ yields an orthonormal family $(e_1)$ with $x_r=(x_r\cdot e_1)\,e_1$ and $e_1=c\,x_r$ for a real $c$; part 1 holds for $i<r$ as well, since $x_i=0$ and $x_i\cdot e_1=0$; and $p=1\le r$.

Case (ii): the induction hypothesis provides $p'\le r-1$ and an orthonormal family $e_1,\dots,e_{p'}$ with parts 1 and 2 for $x_1,\dots,x_{r-1}$. Define

For each $1\le u'\le p'$, bilinearity of the dot product (immediate from its definition as a finite sum) and orthonormality give

If $y=0$, keep the family $e_1,\dots,e_{p'}$ and $p=p'\le r$: part 1 for $x_r$ reads $x_r=\sum_{u}(x_r\cdot e_u)\,e_u$, which is exactly $y=0$; parts 1 and 2 for the remaining data are inherited.

If $y\ne0$, set $s=\sqrt{y\cdot y}>0$ and $e_{p'+1}=(1/s)\,y$, and take $p=p'+1\le r$. Then $e_{p'+1}\cdot e_{p'+1}=1$ and $e_{p'+1}\cdot e_{u'}=(1/s)\,y\cdot e_{u'}=0$ for $u'\le p'$, so $e_1,\dots,e_{p'+1}$ is an orthonormal family. Part 1: for $i<r$, part 1 of the induction hypothesis gives $x_i=\sum_{u\le p'}(x_i\cdot e_u)\,e_u$, and then $x_i\cdot e_{p'+1}=\sum_{u\le p'}(x_i\cdot e_u)(e_u\cdot e_{p'+1})=0$, so the expansion over $u\le p'+1$ adds only a zero term. For $i=r$: from the definition of $y$,

and $x_r\cdot e_{p'+1}=y\cdot e_{p'+1}+\sum_{u\le p'}(x_r\cdot e_u)(e_u\cdot e_{p'+1})=(1/s)\,y\cdot y=s$, so the displayed identity is the required expansion. Part 2: each $e_u$ with $u\le p'$ is a linear combination of $x_1,\dots,x_{r-1}$ by the induction hypothesis, and

is a linear combination of $x_r$ and of $e_1,\dots,e_{p'}$; substituting the expressions of the $e_u$ in terms of $x_1,\dots,x_{r-1}$ and collecting coefficients exhibits $e_{p'+1}$ as a linear combination of $x_1,\dots,x_r$. This completes the induction. $\blacksquare$