8
$\begingroup$

We all know the Gram-Schmidt orthogonalization is done recursively and takes the linearly independent set of vectors one-by-one. And it can be distinguished from democratic orthogonalization like Löwdin and Wigner, which handles all the given vectors simultaneously and treat them on equal footing 1 2.

I want to understand a particular property of sequential orthogonalization methods like Gram-Schmidt.

Suppose we have a linearly independent set of vectors $A:=\{v_,\cdots,v_i,\cdots,v_n\}$ and we apply the Gram-Schmidt orthogonalization method to get the orthonormal set of vectors $B:=\{w_1,\cdots,w_i,\cdots,w_n\}$.

Now suppose we replace $v_i$ to $\tilde{v}_i$ $(\tilde{v}_i \neq v_i)$ such that the new initial set $\tilde{A}$ is still linearly independent. Then after applying the Gram-Schmidt orthogonalization we get $\tilde{B}:=\{w_1,\cdots,\tilde{w}_i,\cdots,\tilde{w}_n\}$. Can we show that $w_j \neq \tilde{w}_j$ for some $i \leq j \leq n$. Or may be there are some special conditions for which the equality holds. Can we mathematically explore such conditions.

A similar condition is when we exchange positions of $v_i$ and $v_k$ $(1\leq k<i\leq n)$, then again can we answer the above question.

I know that the Gram-Schmidt orthogonalization is not one-one. So most probably the inequality doesn't hold always. But what conditions will result in equality and what conditions to inequality. It would be helpful even if you could point me to some references or explanations.

$\endgroup$
2
  • $\begingroup$ Just to be absolutely clear. I take it you mean a finite sequence $v_1,\dots,v_n$ such that the set is LI. But are you treating $B$ as a set or sequence when you ask about inequality? And also is $n$ the dimension of the vector space or not necessarily so? $\endgroup$ Mar 1, 2022 at 11:33
  • $\begingroup$ @ancientmathematician Sorry for not being clear about these points. Yes, I am taking $v_1,\cdots,v_n$ as a linearly independent sequence of vectors. I am also treating $B$ as a sequence, where order matters. And dimension can be taken to something say $m$ such that $m>n$. $\endgroup$
    – IamKnull
    Mar 1, 2022 at 12:23

1 Answer 1

3
+50
$\begingroup$

Consider a real inner product space $V$, and a linearly independent vector sequence $v=\{v_k\}_{1\leq k\leq n}$. The Gram-Schmidt algorithm uses $v$ to produce an orthonormal sequence $e=\{e_k\}_{1\leq k\leq n}$ recursively, like so. $$u_k = v_k - \sum_{j=1}^{k-1}\operatorname{proj}_{u_j}(v_k) \hspace{24mm} e_k = \frac{u_k}{||u_k||}$$

It can be proven inductively that each $k$ satisfies: $$\operatorname{Span}\{v_1,\cdots,v_k\}=\operatorname{Span}\{e_1,\cdots, e_k\}$$

Using the properties of span, likewise: $$\operatorname{Span}\{e_1,\cdots, e_k\}=\operatorname{Span}\{u_1,\cdots,u_k\}$$

Label $E_k=\operatorname{Span}\{v_1,\cdots,v_k\}$, then we have the following equalities. $$E_k=\operatorname{Span}\{v_1,\cdots,v_k\} = \operatorname{Span}\{e_1,\cdots, e_k\} = \operatorname{Span}\{u_1,\cdots,u_k\}$$

Now, consider a second linearly independent vector sequence $v'=\{v'_k\}_{1\leq k\leq n}$, and define the $e'$ and $E'$ sequences analogously. We want to determine the necessary and sufficient conditions to have $e=e'$. By the previous observations, if $e=e'$ it is necessary to have $E=E'$. Using the contrapositive, this is enough to answer your second question.

If we have $v$ and $v'$ identical except some $i<k$ have $v_i,v_k$ swapped, then $e\neq e'$. Indeed, we have $v_i\notin \operatorname{Span}\{v_1,\cdots,v_{i-1},v_k\}=\operatorname{Span}\{v'_1,\cdots,v'_{i-1},v'_i\}=E'_i$, by linear independence, thus we have $E_i\neq E'_i$ so that $e_i\neq e'_i$, proving $e\neq e'$.

As pointed out by user ancient mathematician, each $e_k$ must be in the orthogonal complement of $E_{k-1}$, so that $e_k\in E_k\cap (E_{k-1})^\perp$. This space is one dimensional however, and thus has exactly two unit vectors, one of which is $e_k$, so the other is $-e_k$. It follows that any unit vector $u\in E_k\cap (E_{k-1})^\perp$ must have $u=\pm e_k$. In particular if we have $E=E'$, the following holds. $$e_k\in E_k\cap (E_{k-1})^\perp = E'_k\cap (E'_{k-1})^\perp \ni e'_k$$ $$\implies e'_k=\pm e_k$$

So if $E=E'$, then all $k$ have $e'_k=\pm e_k$. Since $E_k$ is simply the span of some $e_j$, it is easily shown that, conversely, if all $k$ have $e'_k=\pm e_k$ then necessarily $E=E'$. Thus we have shown that all $k$ have $\operatorname{Span}\{v_1,\cdots,v_k\}=\operatorname{Span}\{v'_1,\cdots,v'_k\}$ if and only if all $k$ have $e'_k=\pm e_k$.

Moreover when $E=E'$, each $\left<e_k, e'_k\right> = \pm 1$, and since $e_k=e'_k$ if and only if $\left<e_k, e'_k\right> = 1$, then $e_k=e'_k$ if and only if $\left<e_k, e'_k\right> > 0$. Since $e'_k=\frac{u'_k}{||u'_k||}$, likewise $e_k=e'_k$ if and only if $\left<e_k, u'_k\right> > 0$. Since we define $u'_k=v'_k-\operatorname{proj}_{E_{k-1}}(v'_k)$, where the projection is necessarily perpendicular to $e_k$, then $\left<e_k, u'_k\right>=\left<e_k, v'_k\right>$, therefore $e_k=e'_k$ if and only if $\left<e_k, v'_k\right> > 0$. In geometric terms, this means the angle between $e_k$ and $v'_k$ is smaller than $90$ degrees.

Using the formula for distance $d(p_1,p_2)=||p_1-p_2||$, and the formula for norm $||p||=\sqrt{\left<p,p\right>}$, it is not too hard to show that $\left<e_k, v'_k\right> > 0$ if and only if $d(v'_k,e_k)<d(v'_k,-e_k)$. In other words, provided that $E=E'$, then $e'_k=e_k$ if and only if $v'_k$ is closer to $e_k$ than to its negation $-e_k$. This is enough to answer your first question.

We have $e=e'$ if and only if all $k$ have $\operatorname{Span}\{v_1,\cdots,v_k\}=\operatorname{Span}\{v'_1,\cdots,v'_k\}$, and we have the distance inequality $d(e_k,v'_k) < d(-e_k,v'_k)$.

So, the Gram-Schmidt algorithm will produce the same orthonormal basis if and only if each of these $E_k$ subspaces are identical to $E'_k$, and each $v'_k$ is "close enough" to $e_k$ that $-e_k$ is further away.

For some intuition, if you fix the sequence $v$ as constant, in general you'll find that for each fixed $k$, exactly half of all $v'$ sequences which satisfy $E=E'$ will also satisfy $e'_k=e_k$. Here I mean "half" in the sense that there will be some hyperplane that partitions the space, where if $v'_k$ is on one side then $e'_k=e_k$, and on the other side $e'_k=-e_k$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .