Are Orthogonal Basis perpendicular to Original Basis in Gram-Schmidt?

Question

a, b and c are 3 Independent Vectors. We can generate Orthonormal basis vectors using those 3 vectors using Gram-Schmidt method. Lets say those 3 orthogonal basis vectors generated from a, b and c are $A$, $B$ and $C$. We can generate orthonormal basis vectors by dividing those orthogonal basis vectors with their length.

I am trying to figure out if $C$ will be orthogonal to b (which is one of the original basis vector). It seems like it should be, because $C$ is orthogonal to the plane containing a and b. Is there any way to prove this? I am trying to use the approach below and going into calculations which don't look pretty. $$C = c - \frac{(A^Tc)A}{A^TA} - \frac{(B^Tc)B}{B^TB}$$ Multiplying both sides by $b^T$. Idea is to show $b^TC = 0$ to demonstrate orthogonality

$$b^TC = b^Tc - \frac{(A^Tc)b^TA}{A^TA} - \frac{(B^Tc)b^TB}{B^TB}$$

Using $$B = b - \frac{(A^Tb)A}{A^TA}$$

$$b^TC = b^Tc - \frac{(A^Tc)b^TA}{A^TA} - \frac{\left(b - \frac{(A^Tb)A}{A^TA}\right)^Tcb^T\left(b - \frac{(A^Tb)A}{A^TA}\right)}{B^TB}$$

I am not sure if I need to follow through on this or am I headed in the wrong direction? Thank you.

Answer 1

Yes, this is indeed the case. If we have a sequence of vectors $v_1, \ldots, v_n$, and obtain $e_1, \ldots, e_n$ from the Gram-Schmidt procedure, then it has the additional (sometimes overlooked) property that $$\operatorname{span}\{e_1, \ldots, e_i\} = \operatorname{span}\{v_1, \ldots, v_i\}. \tag{$\star$}$$ In particular, since $e_{i+1}$ is perpendicular to each vector in $\{e_1, \ldots, e_i\}$, and hence to each vector in $\operatorname{span}\{e_1, \ldots, e_i\}$, it will also be perpendicular to each vector in $\operatorname{span}\{v_1, \ldots, v_i\}$, including $v_1, \ldots, v_i$. That is, each vector we obtain from Gram-schmidt will be orthogonal to every previous vector in the list.

To prove $(\star)$, it is best to use induction. Note that $e_1 = v_1$, so $\operatorname{span}\{v_1\} = \operatorname{span}\{e_1\}$. That is, the base case holds.

Suppose $(\star)$ holds when $i = k$. We have $$e_{k+1} = v_{k+1} - \sum_{i=1}^k \frac{v_{k+1}^\top e_i}{e_i^\top e_i} e_i.$$ Note that the subtracted sum lies in $\operatorname{span}\{e_1, \ldots, e_k\}$, which is equal to $\operatorname{span}\{v_1, \ldots, v_k\}$, by assumption. Thus the sum is a linear combination of $v_1, \ldots, v_k$, which makes $e_{k+1}$ a linear combination of $v_1, \ldots, v_{k+1}$. That is, $$e_{k+1} \in \operatorname{span}\{v_1, \ldots, v_{k+1}\}.$$ By assumption, $e_1, \ldots, e_k$ all lie in the smaller space $\operatorname{span}\{v_1, \ldots, v_k\}$, and so they also lie in the large space. Hence $$\operatorname{span}\{e_1, \ldots, e_{k+1}\} \subseteq \operatorname{span}\{v_1, \ldots, v_{k+1}\}.$$ On the other hand, $$v_{k+1} = e_{k+1} + \sum_{i=1}^k \frac{v_{k+1}^\top e_i}{e_i^\top e_i} e_i \in \operatorname{span}\{e_1, \ldots, e_{k+1}\},$$ and $v_1, \ldots, v_k \in \operatorname{span}\{e_1, \ldots, e_k\}$, by assumption, thus $$\operatorname{span}\{e_1, \ldots, e_{k+1}\} = \operatorname{span}\{v_1, \ldots, v_{k+1}\},$$ completing the induction proof.

Answer 2

Yes, if we have linearly independent vectors $x_1,\ldots, x_n$ and we apply Gram-Schmidt orthonormalization moving from left to right, resulting in $X_1,\ldots, X_n$, then each $X_k$ will be orthogonal to $x_1,\ldots, x_{k-1}$.

Without loss of generality, we can assume that the vector space is question is $V=\text{span}\{x_1,\ldots, x_n\}$ (in general, we could be working in a larger space $X$ such that $\text{span}\{x_1,\ldots, x_n\}\subsetneq X$, but the larger space is irrelevant in this context).

For $k=1,\ldots, n$, let $W_k=\text{span}\{x_1,\ldots, x_k\}$. for any subset $S$ of $V$, let $$S^\perp = \{x\in V:(\forall y\in S)(y\cdot x=0)\}.$$ So $S^\perp$ is the set of things orthogonal to everything in $S$. As you said, we'll be interested in the case when $S$ is a plan (the plane spanned by $a,b$). The key point is that the plane spanned by $a,b$ is the same as the plane spanned by $A,B$. It is difficult to reconstruct this "after the fact." It's much easier to prove it as part of the Gram-Schmidt process.

The steps to Gram-Schmidt orthonormalization will be to recursively select $X_1,\ldots, X_n$ in such a way that $W_k=\text{span}\{x_1,\ldots, x_k\}=\text{span}\{X_1,\ldots, X_k\}$ and $X_{k+1}\in W_k^\perp$. The first equality $W_k=\text{span}\{x_1,\ldots, x_k\}$ holds by definition.

Note: Fix $x\in V$ and a non-empty subset $S$ of $V$. If $x\cdot y=0$ for all $y\in S$, then $x\cdot y=0$ for all $y\in \text{span}(S)$. That's because if $y\in \text{span}(S)$, then $y=\sum_{i=1}^m a_iy_i$ for some $m$, some scalars $a_i$, and some $y_i\in S$. Then $$x\cdot y = \sum_{i=1}^m a_i x\cdot y_i=\sum_{i=1}^m a_i\cdot 0=0.$$ So being in $W_k^\perp$ is equivalent to being orthogonal to every member of a spanning set of $W_k$. So if we know that $W_k=\text{span}\{x_1,\ldots, x_k\}=\text{span}\{X_1,\ldots, X_k\}$ and that $X_{k+1}\cdot X_i=0$ for all $i\leqslant k$, then we know that $X_{k+1}$ is orthogonal to every member of $\text{span}\{X_1,\ldots, X_k\}$ (that is, $X_{k+1}\in W_k^\perp$), and therefore it is orthogonal to $x_1,\ldots, x_k$, these these are in $W_k$.

The only thing left to do is show how Gram-Schmidt maintains $\text{span}\{x_1,\ldots, x_k\}=\text{span}\{X_1,\ldots, X_k\}$. Let $Y_1,\ldots, Y_n$ be the orthogonal vectors resulting from Gram-Schmidt, so that $X_i=Y_i/\|Y_i\|$, where $\|Y_i\|$ denotes the length of $Y_i$. It is obvious that $$\text{span}\{X_1,\ldots, X_k\}=\text{span}\{Y_1,\ldots, Y_k\},$$ so we only need to show that $$\text{span}\{x_1,\ldots, x_k\}=\text{span}\{Y_1,\ldots, Y_k\}$$ for all $1\leqslant k\leqslant n$. For this, we'll us something that depends only on the algebra, not on the geometry (orthogonality or normalization).

Proposition: Suppose that $v_1,\ldots, v_n$ is a basis for the vector space $V$. Suppose also that $u_1,\ldots, u_n\in V$ are vectors such that for all $1\leqslant k\leqslant n$, $$u_k=v_k+w_k$$ for some $w_k\in \text{span}\{u_1,\ldots,u_{k-1}\}$. (By convention, when $k=1$, $\{u_1,\ldots, u_{k-1}\}=\varnothing$ and the span of this set is $\{0\}$. In particular, $w_1=0$ and $u_1=v_1$.) Then $\text{span}\{u_1,\ldots, u_k\}=\text{span}\{v_1,\ldots, v_k\}$ for all $1\leqslant k\leqslant n$.

Before proving the proposition, we note that it applies to the Gram-Schmidt process, because we orthogonalize by keeping $Y_1=x_1$, and then $$Y_k=x_k-P_{k-1}x_k,$$ where $P_{W_{k-1}}x_k$ is the orthogonal projection onto $\text{span}\{Y_1,\ldots, Y_{k-1}\}$ ($P_1$ is the zero operator). Since $P_{k-1}x_k\in \text{span}\{X_1,\ldots, X_{k-1}\}$, the proposition applies.

It's also worth noting that the proposition can be reformulated as a statement about the inverses of triangular matrices with $1$s on the main diagonal. It's also worth noting that we don't need the assumption of $1$s on the main diagonal (that is, we can have $u_k=\color{red}{c_k}v_k+w_k$ instead of $u_k=\color{red}{1}v_k+ w_k$), as long as each $c_k$ is non-zero. But that case easily reduces to the case of $1$s on the diagonal by dividing the equations by $c_k$.

Let's prove the proposition by induction. For $k=1$, $u_1=v_1$, so $\text{span}\{u_1\}=\text{span}\{v_1\}$.

Suppose $1<k\leqslant n$ and $W:=\text{span}\{v_1,\ldots, v_{k-1}\}=\text{span}\{u_1,\ldots, u_{k-1}\}$. Then since $$u_k=v_k+w_k$$ and $$w_k\in W,$$ there exist some scalars $(a_j)_{j=1}^{k-1}$, $(b_j)_{j=1}^{k-1}$ such that $$w_k=\sum_{j=1}^{k-1}a_j v_j=\sum_{j=1}^{k-1}b_ju_j.$$ Then if $$x\in \text{span}\{v_1,\ldots, v_k\},$$ we can write $$x=\sum_{j=1}^k c_k v_j=c_kv_k+x',$$ where $x'\in W$. Then $$x=c_kv_k+x'=c_k(u_k-w_k)+x' = c_ku_k+(x'-c_kw_k)\in \text{span}\{u_1,\ldots, u_k\},$$ since $x'-c_kw_k\in W=\text{span}\{u_1,\ldots, u_{k-1}\}$. Similarly, if $x\in \text{span}\{u_1,\ldots, u_k\}$, we can write $$x=\sum_{j=1}^k d_ju_j=d_ku_k+x'',$$ where $x''\in W$. Then $$x=d_k(v_k+w_k)+x''=d_kv_k+(x''+d_kw_k)\in \text{span}\{v_1,\ldots, v_k\},$$ since $x''+d_kw_k\in W$.