§10.1.1 The Gram–Schmidt Process

Let $𝑆={\left\{{𝑣}_{𝑘}\right\}}_{𝑘=1}^{𝑚}$ span $𝑉$. If $𝑆$ is linearly independent, then it is already a basis. Otherwise, one of its vectors is a linear combination of the others; removing that vector does not change the span. If the remaining set is still linearly dependent, repeat the same step. Since $𝑆$ is finite, the process will end with a linearly independent set that still spans $𝑉$, a basis.

Now let ${𝑆}_{𝑚}={\left\{{𝑣}_{𝑗}\right\}}_{𝑗=1}^{𝑚}$ and ${𝑆}_{𝑛}={\left\{{𝑤}_{𝑘}\right\}}_{𝑘=1}^{𝑛}$ be two bases such that $𝑚\le 𝑛$. Let ${𝑣}_1={\sum }_{𝑘=1}^{𝑛}{𝑐}_{𝑘}{𝑤}_{𝑘}$. Then at least one of these terms is nonzero, namely ${𝑐}_{{𝑘}_1}{𝑤}_{{𝑘}_1}$. Moreover, since

we obtain a new basis ${\left\{{𝑤}_{𝑘}\right\}}_{\begin{array}{c}𝑘=1\\ 𝑘\ne {𝑘}_1\end{array}}^{𝑛}\cup \left\{{𝑣}_1\right\}$. It is a basis because any vector in $𝑉$ can be written as a linear combination of these vectors by (10.1.1.1)$\text{<a href="../../../pdf/notes.pdf\#loc-662">(10.1.1.4)</a>}\text{<a href="\#loc-2">(10.1.1.1)</a>}$; and linear independence is satisfied, because if ${𝑑}_1{𝑣}_1+{\sum }_{𝑘\ne {𝑘}_1}{𝑑}_{𝑘}{𝑤}_{𝑘}=0$, then a substitution for ${𝑣}_1$ forces all coefficients to $0$.

Now inductively assume that for a $𝑗\in {\mathbb{N}}_{<𝑚}$, the set ${\left\{{𝑤}_{𝑘}\right\}}_{𝑘\in {\mathbb{N}}_{\le 𝑛}\setminus {\left\{{𝑘}_{𝑖}\right\}}_{𝑖\le 𝑗}}\cup {\left\{{𝑣}_{𝑘}\right\}}_{𝑘=1}^{𝑗}$ is a basis for $𝑉$. Let ${𝑣}_{𝑗+1}={\sum }_{𝑘=1}^{𝑗}{𝑐}_{𝑘}{𝑣}_{𝑘}+{\sum }_{𝑘\notin {\left\{{𝑘}_{𝑖}\right\}}_{𝑖=1}^{𝑗}}{𝑐}_{𝑘}{𝑤}_{𝑘}$. Then at least one of these terms, excluding all the multiples of $\left\{{𝑣}_{𝑘}\right\}$, is nonzero, namely ${𝑐}_{{𝑘}_{𝑗+1}}{𝑤}_{{𝑘}_{𝑗+1}}$ (as otherwise, ${𝑣}_{𝑗+1}$ is a linear combination of $\left\{{𝑣}_{𝑘}\right\}$, contradicting independence of ${𝑆}_{𝑚}$).

Therefore, replacing ${𝑤}_{{𝑘}_{𝑗+1}}$ with ${𝑣}_{𝑗+1}$ in ${\left\{{𝑤}_{𝑘}\right\}}_{𝑘\in {\mathbb{N}}_{\le 𝑛}\setminus {\left\{{𝑘}_{𝑖}\right\}}_{𝑖\le 𝑗}}\cup {\left\{{𝑣}_{𝑘}\right\}}_{𝑘=1}^{𝑗}$, giving ${\left\{{𝑤}_{𝑘}\right\}}_{𝑘\in {\mathbb{N}}_{\le 𝑛}\setminus {\left\{{𝑘}_{𝑖}\right\}}_{𝑖\le 𝑗+1}}\cup {\left\{{𝑣}_{𝑘}\right\}}_{𝑘=1}^{𝑗+1}$, is a basis (by the exact same argument as in the base case).

By mathematical induction, we can then transform ${𝑆}_{𝑛}$ into a basis of $𝑛$ elements, including all elements of ${𝑆}_{𝑚}$. Continue to denote the transformed basis by ${𝑆}_{𝑛}$. Then any nonzero vector $𝑣$ in ${𝑆}_{𝑛}\setminus {𝑆}_{𝑚}$ can be written as a linear combination of elements in ${𝑆}_{𝑚}$, which violates the linear independence of vectors in ${𝑆}_{𝑛}$, thus no vector exists in ${𝑆}_{𝑛}\setminus {𝑆}_{𝑚}$, and $𝑛=𝑚$. The case $𝑛\le 𝑚$ follows symmetrically. ⁠$\square$

We proceed by induction on $𝑘$. Since ${𝑣}_1\ne 0$, ${𝑢}_1\ne 0$, $\Vert {𝑒}_1\Vert =1$, and $span\left\{{𝑒}_1\right\}=span\left\{{𝑣}_1\right\}$.

Suppose that ${\left\{{𝑒}_{𝑗}\right\}}_{𝑗=1}^{𝑘-1}$ is orthonormal and that

If ${𝑢}_{𝑘}=0$, then

contradicting the linear independence of ${\left\{{𝑣}_{𝑗}\right\}}_{𝑗=1}^{𝑘}$. Hence ${𝑢}_{𝑘}\ne 0$, so ${𝑒}_{𝑘}$ is well-defined and $\Vert {𝑒}_{𝑘}\Vert =1$.

For every $\ell <𝑘$, orthonormality gives

Therefore ${𝑒}_{𝑘}$ is orthogonal to ${𝑒}_1,\dots ,{𝑒}_{𝑘-1}$, and the enlarged set ${\left\{{𝑒}_{𝑗}\right\}}_{𝑗=1}^{𝑘}$ is orthonormal. Finally, ${𝑢}_{𝑘}$ is obtained from ${𝑣}_{𝑘}$ by subtracting an element of $span\left\{{𝑒}_1,\dots ,{𝑒}_{𝑘-1}\right\}$, while

Thus adjoining either ${𝑢}_{𝑘}$ or ${𝑣}_{𝑘}$ to the preceding span gives the same space, and

by induction. ⁠$\square$