[proofplan] We prove the equality of the two output lists by induction on the index $k$. The induction hypothesis says not only that the previously produced orthonormal vectors agree, but also that they span the same subspace as the previously processed input vectors. At the $k$th stage, the modified algorithm subtracts the same [orthogonal projection](/theorems/437) components as the classical formula, one component at a time. [Linear independence](/page/Linear%20Independence) guarantees that the common residual is nonzero, so the shared normalization rule gives the same normalized vector in both algorithms. [/proofplan]

[step:Initialize the first residual in both algorithms] For $k=1$, both algorithms have no previous orthonormal vectors. Thus the empty sum in the classical formula is zero, and the modified algorithm starts with $w_{1,0}=v_1$. Hence \begin{align*} u_{C,1}=v_1=u_{M,1}. \end{align*} Because $(v_1,\ldots,v_m)$ is linearly independent, $v_1\neq 0$. Therefore $u_{C,1}$ and $u_{M,1}$ are nonzero, and both algorithms normalize by the same positive scalar $|v_1|$. Consequently \begin{align*} e_{C,1}=\frac{v_1}{|v_1|}=e_{M,1}. \end{align*} The list $(e_{C,1})$ is orthonormal, and \begin{align*} \operatorname{span}\{e_{C,1}\}=\operatorname{span}\{v_1\}. \end{align*} [/step]

[step:Assume the previous Gram-Schmidt vectors agree and span the previous inputs] Fix an index $k$ with $2\le k\le m$. Assume that, for every $1\le i<k$, the vectors produced by the two algorithms agree: \begin{align*} e_{C,i}=e_{M,i}. \end{align*} Let $e_i$ denote this common vector for $1\le i<k$. Assume also that $(e_1,\ldots,e_{k-1})$ is orthonormal and that \begin{align*} \operatorname{span}\{e_1,\ldots,e_{k-1}\}=\operatorname{span}\{v_1,\ldots,v_{k-1}\}. \end{align*} We prove the same conclusions at index $k$. [/step]

[step:Compute the modified working vector after each projection]We claim that, for every integer $j$ with $0\le j\le k-1$, the modified working vector satisfies \begin{align*} w_{k,j}=v_k-\sum_{i=1}^{j}(v_k,e_i)_V e_i. \end{align*} For $j=0$, this is the definition $w_{k,0}=v_k$, with the empty sum equal to zero. Now let $j$ satisfy $1\le j\le k-1$, and assume the formula holds for $j-1$. Since $(e_1,\ldots,e_{k-1})$ is orthonormal, we have $(e_i,e_j)_V=0$ for $i<j$ and $(e_j,e_j)_V=1$. Using linearity of the [inner product](/page/Inner%20Product) in the first argument, the coefficient subtracted by the modified algorithm is \begin{align*} (w_{k,j-1},e_j)_V=(v_k,e_j)_V. \end{align*} Indeed, the terms involving $e_i$ with $i<j$ vanish by orthogonality. Substituting this coefficient into the modified update gives \begin{align*} w_{k,j}=w_{k,j-1}-(v_k,e_j)_V e_j. \end{align*} Using the induction formula for $w_{k,j-1}$ yields \begin{align*} w_{k,j}=v_k-\sum_{i=1}^{j}(v_k,e_i)_V e_i. \end{align*} Thus the formula holds for every $0\le j\le k-1$ by finite induction.[/step]

[guided]The purpose of this step is to show that the modified algorithm has not changed the mathematical residual; it has only changed the order in which the projection components are removed. We prove the precise formula \begin{align*} w_{k,j}=v_k-\sum_{i=1}^{j}(v_k,e_i)_V e_i \end{align*} for each $0\le j\le k-1$. When $j=0$, the statement says $w_{k,0}=v_k$, which is exactly the definition of the initial modified working vector. Now suppose the formula has been proved for some $j-1$, where $1\le j\le k-1$. The modified algorithm computes the next coefficient from the current working vector: \begin{align*} (w_{k,j-1},e_j)_V. \end{align*} By the induction formula, \begin{align*} w_{k,j-1}=v_k-\sum_{i=1}^{j-1}(v_k,e_i)_V e_i. \end{align*} Taking the inner product with $e_j$ and using linearity in the first argument gives \begin{align*} (w_{k,j-1},e_j)_V=(v_k,e_j)_V-\sum_{i=1}^{j-1}(v_k,e_i)_V(e_i,e_j)_V. \end{align*} Because $(e_1,\ldots,e_{k-1})$ is orthonormal, every factor $(e_i,e_j)_V$ with $i<j$ is zero. Therefore \begin{align*} (w_{k,j-1},e_j)_V=(v_k,e_j)_V. \end{align*} This is the key point: although modified Gram-Schmidt computes the coefficient from the updated vector $w_{k,j-1}$, exact orthogonality of the previously removed directions makes that coefficient equal to the classical coefficient. Substituting this equality into the modified update, \begin{align*} w_{k,j}=w_{k,j-1}-(w_{k,j-1},e_j)_V e_j, \end{align*} we obtain \begin{align*} w_{k,j}=w_{k,j-1}-(v_k,e_j)_V e_j. \end{align*} Finally, replacing $w_{k,j-1}$ by its induction formula gives \begin{align*} w_{k,j}=v_k-\sum_{i=1}^{j-1}(v_k,e_i)_V e_i-(v_k,e_j)_V e_j. \end{align*} Combining the two displayed subtraction terms into a single finite sum gives \begin{align*} w_{k,j}=v_k-\sum_{i=1}^{j}(v_k,e_i)_V e_i. \end{align*} This completes the induction over $j$.[/guided]

[step:Identify the classical and modified residuals] Taking $j=k-1$ in the formula from the previous step gives \begin{align*} u_{M,k}=w_{k,k-1}=v_k-\sum_{i=1}^{k-1}(v_k,e_i)_V e_i. \end{align*} Since $e_i=e_{C,i}$ for every $1\le i<k$, the classical residual is \begin{align*} u_{C,k}=v_k-\sum_{i=1}^{k-1}(v_k,e_i)_V e_i. \end{align*} Therefore \begin{align*} u_{C,k}=u_{M,k}. \end{align*} Let $u_k$ denote this common residual. [/step]

[step:Use linear independence to rule out a zero residual] Suppose, for contradiction, that $u_k=0$. From the residual formula, \begin{align*} v_k=\sum_{i=1}^{k-1}(v_k,e_i)_V e_i. \end{align*} Thus $v_k\in \operatorname{span}\{e_1,\ldots,e_{k-1}\}$. By the induction hypothesis on spans, \begin{align*} v_k\in \operatorname{span}\{v_1,\ldots,v_{k-1}\}. \end{align*} This contradicts the linear independence of $(v_1,\ldots,v_m)$. Hence $u_k\neq 0$. [/step]

[step:Normalize the common residual and update the induction] Since $u_{C,k}=u_{M,k}=u_k$ and $u_k\neq 0$, both algorithms divide by the same positive scalar $|u_k|$. Hence \begin{align*} e_{C,k}=\frac{u_k}{|u_k|}=e_{M,k}. \end{align*} Moreover, $u_k$ is orthogonal to each $e_j$ with $1\le j<k$, because \begin{align*} (u_k,e_j)_V=(v_k,e_j)_V-\sum_{i=1}^{k-1}(v_k,e_i)_V(e_i,e_j)_V=0. \end{align*} Also $|e_{C,k}|=1$ by construction. Therefore $(e_1,\ldots,e_k)$ is orthonormal. Finally, since \begin{align*} u_k=v_k-\sum_{i=1}^{k-1}(v_k,e_i)_V e_i, \end{align*} we have $u_k\in \operatorname{span}\{v_1,\ldots,v_k\}$ and $v_k\in \operatorname{span}\{e_1,\ldots,e_k\}$. Combining these inclusions with \begin{align*} \operatorname{span}\{e_1,\ldots,e_{k-1}\}=\operatorname{span}\{v_1,\ldots,v_{k-1}\} \end{align*} gives \begin{align*} \operatorname{span}\{e_1,\ldots,e_k\}=\operatorname{span}\{v_1,\ldots,v_k\}. \end{align*} Thus the induction hypotheses are established at index $k$. [/step]

[step:Conclude equality of the full orthonormal lists] By induction on $k$, every residual used by either algorithm is nonzero, and for every $1\le k\le m$ the two algorithms produce the same normalized vector: \begin{align*} e_{C,k}=e_{M,k}. \end{align*} Therefore, in exact arithmetic and under the stated common inner product and normalization conventions, classical Gram-Schmidt and modified Gram-Schmidt produce the same orthonormal list. [/step]