If $D=\{x_n : n\in \mathbb{N}\}$ is a countable set dense in a Hilbert space $\mathcal{H}$, how can I show that Gram-Schmidt algorithm applied to $D$ (or a subset of $D$) produces an orthonormal numerable basis for $\mathcal{H}$?

So far I have been able to prove that every ortonormal basis of $\mathcal{H}$ has to be numerable.


Actually, we have a non-constructive proof.

Lemma : Let $\mathcal{H}$ be a Hilbert space. Then it is impossible that $\mathcal{H}$ has a countable dense subset $D$ and an uncountable orthonormal set $\{e_{i}\mid i\in I\}$.

Proof: Prove by contradiction. Suppose the contrary that $\mathcal{H}$ has a countable dense subset $D$ and an uncountable orthonormal set $\{e_{i}\mid i\in I\}.$ Let $r=\frac{1}{4}$ and for each $i\in I$, let $B_{i}=B(e_{i,}r)$, then open ball centered at $e_{i}$ with radius $r$. Note that $B_{i}\cap B_{j}=\emptyset$ whenever $i\neq j$. (For, if there exists $x\in B_{i}\cap B_{j}$, then $||e_{i}-e_{j}||\leq||e_{i}-x||+||x-e_{j}||<2r$. By orthonormality, $||e_{i}-e_{j}||=\sqrt{2}$, which is a contradiction.) For each $i\in I,$ further define $A_{i}=B_{i}\cap D$, which is non-empty because $D$ is dense. Now we obtain a non-empty collection of non-empty sets $\{A_{i}\mid i\in I\}$. By Axiom of Choice, there exists a function $\theta:I\rightarrow\cup_{i\in I}A_{i}$ such that $\theta(i)\in A_{i}$. Note that $\theta$ is injective because $A_{i}\cap A_{j}=\emptyset$ whenever $i\neq j$. Therefore $\mbox{Cardinality}(I)\leq\mbox{Cardinality}(\cup_{i\in I}A_{i})\leq\mbox{Cardinality}(D)$, which is a contradiction.

We are are ready to prove: Suppose that $\mathcal{H}$ is separable (i.e., $\mathcal{H}$ has a countable dense subset), then $\mathcal{H}$ has a countable orthonormal base (finite or countably infinite). By Zorn's lemma, we can find a maximal (with respect to the partial ordering $\subseteq$) orthonormal set $\{e_{i}\mid i\in I\}$. By the lemma, $I$ must be countable. Then for any $x\in\mathcal{H}$, we have $x=\sum_{i\in I}<x,e_{i}>e_{i}$, where the sum is independent of ordering. (I leave the proof to you).


I expand the last line, state it as a theorem and give a self-contained proof. This is known as the Fourier expansion in Hilbert space.


Theorem: Let $\mathcal{H}$ be a Hilbert space (over $\mathbb{R}$ or $\mathbb{C}$) and let $\{e_{i}\mid i\in I\}$ be a maximal (with respect to $\subseteq$) orthonormal set (where the index $I$ may be uncountable). Then for each $x\in\mathcal{H}$, we have $x=\sum_{i\in I}\langle x,e_{i}\rangle e_{i}$, where the series converges in unorder sense (explained in Claim (4) below).


Claim (1) (Bessel's inequality): For any finite subset $I_{1}\subseteq I$ and any $x\in\mathcal{H}$, $\sum_{i\in I_{1}}|\langle x,e_{i}\rangle|^{2}\leq||x||^{2}$.

Proof of Claim (1): Denote $Px=\sum_{i\in I_{1}}\langle x,e_{i}\rangle e_{i}$. Observe that $Px\bot x-Px$, so $||x||^{2}=||Px||^{2}+||x-Px||^{2}\geq||Px||^{2}=\sum_{i\in I_{1}}|\langle x,e_{i}\rangle|^{2}$.

Claim (2): For any $x\in\mathcal{H}$, $\{i\in I\mid\langle x,e_{i}\rangle\neq0\}$ is a countable set.

Proof of Claim (2): Let $I'=\{i\in I\mid\langle x,e_{i}\rangle\neq0\}$. Prove by contradiction. Suppose the contrary that $I'$ is uncountable. For each $n\in\mathbb{N}$, let $I_{n}=\{i\in I\mid|\langle x,e_{i}\rangle|\geq\frac{1}{n}\}$. Observe that $I'=\cup_{n}I_{n}$, so there exists $n$ such that $I_{n}$ is uncountable. Choose $k$ such that $\frac{k}{n^{2}}>||x||^{2}$. Choose a finite subset $I'_{n}\subseteq I_{n}$ that contains $k$ elements, then $\sum_{i\in I'_{n}}|\langle x,e_{i}\rangle|^{2}\geq\frac{k}{n^{2}}>||x||^{2}$, contradicting to claim (1).

Claim (3): Given $x\in\mathcal{H}$ and let $I_{x}=\{i\in I\mid\langle x,e_{i}\rangle\neq0\}$. Fix an enumeration for $I_{x}$, say $I_{x}=\{i_{1},i_{2},\ldots\}$ (finite or infinite), then the series $\sum_{k}\langle x,e_{i_{k}}\rangle e_{i_{k}}$ is convergent.

Proof of Claim (3): If $I_{x}$ is a finite set, we are done. Suppose that $I_{x}$ is a countably infinite set. Let $s_{n}=\sum_{k=1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}}$. By Claim (1), for each $n$, $\sum_{k=1}^{n}|\langle x,e_{i_{k}}\rangle|^{2}\leq||x||^{2}$, so the series $\sum_{k=1}^{\infty}|\langle x,e_{i_{k}}\rangle|^{2}$ is convergent. We show that $\{s_{n}\}$ is a Cauchy sequence in $\mathcal{H}$. Let $\varepsilon>0$. Choose $N$ such that $\sum_{k=N}^{\infty}|\langle x,e_{i_{k}}\rangle|^{2}<\varepsilon^{2}$. For any $m,n\geq N$, we have (without loss of generality, assume that $m<n$): $||s_{n}-s_{m}||^{2}=||\sum_{k=m+1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}}||^{2}=\sum_{k=m+1}^{n}|\langle x,e_{i_{k}}\rangle|^{2}<\varepsilon^{2}$. That is, $||s_{m}-s_{n}||<\varepsilon$. Therefore $\sum_{k}\langle x,e_{i_{k}}\rangle e_{i_{k}}$ is convergent. We denote $y=\sum_{k}\langle x,e_{i_{k}}\rangle e_{i_{k}}$.

Claim (4): The series $\sum_{i\in I}\langle x,e_{i}\rangle e_{i}$ converges to $y$ in unorder sense, where $y$ is the element in Claim (3). More precisely, let $\mathcal{C}$ be the collection of all finite subsets of $I$. Define a binary relation $\preceq$ on $\mathcal{C}$: $I_{1}\preceq I_{2}$ iff $I_{1}\subseteq I_{2}$. Note that $\preceq$ has the properties: (i) For any $I_{0}\in\mathcal{C}$, $I_{0}\preceq I_{0}$ (reflexive), (ii) For any $I_{1},I_{2},I_{3}\in\mathcal{C}$, if $I_{1}\preceq I_{2}$ and $I_{2}\preceq I_{3}$, then $I_{1}\preceq I_{3}$ (transitive), (iii) For any $I_{1},I_{2}\in\mathcal{C}$, there exists $I_{3}\in\mathcal{C}$ such that $I_{1}\preceq I_{3}$ and $I_{2}\preceq I_{3}$. In short, $\left(\mathcal{C},\preceq\right)$ is a directed system. Define $\theta:\mathcal{C\rightarrow\mathcal{H}}$ by $\theta(I_{1})=\sum_{i\in I_{1}}\langle x,e_{i}\rangle e_{i}$, $I_{1}\in\mathcal{C}$. Then the triple $\left(\mathcal{C},\preceq,\theta\right)$ is a net in $\mathcal{H}$. We say that $\sum_{i\in I}\langle x,e_{i}\rangle e_{i}$ converges to $y$ in unorder sense iff the net $\left(\mathcal{C},\preceq,\theta\right)$ converges to $y$. That is, for each open neighborhood $U_{y}$ of $y$, there exists $I_{1}\in\mathcal{C}$ such that for any $I_{2}\in\mathcal{C}$, if $I_{1}\preceq I_{2}$, then $\theta(I_{2})\in U_{y}.$

Proof of Claim (4). Let $y$ be the element in Claim (3). Let $\varepsilon>0$ be arbitrary. Let $U_{y}=B(y,\varepsilon)$ be the open ball centered at $y$ with radius $\varepsilon$. Choose $N$ such that $||\sum_{k=1}^{N}\langle x,e_{i_{k}}\rangle e_{i_{k}}-y||\leq\frac{\varepsilon}{4}$. (If $I_{x}$ in Claim (3) is a finite set, let $N$ be the number of elements in $I_{x}$.) We adopt the notation in Claim (3) and continue to work with the enumeration $I_{x}=\{i_{1},i_{2},\ldots\}$. Let $I_{1}=\{i_{1},i_{2},\ldots,i_{N}\}$. Clearly $I_{1}\in\mathcal{C}$. Consider the case that $I_{x}$ is an infinite set (the finite case is trivial). By continuity of norm (i.e., the continuity of the map $x\mapsto||x||$), we have $$ \lim_{n}||\sum_{k=1}^{N}\langle x,e_{i_{k}}\rangle e_{i_{k}}-\sum_{k=1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}}||=||\sum_{k=1}^{N}\langle x,e_{i_{k}}\rangle e_{i_{k}}-y||\leq\frac{\varepsilon}{4}. $$ On the other hand, for any $n>N$, we have $||\sum_{k=1}^{N}\langle x,e_{i_{k}}\rangle e_{i_{k}}-\sum_{k=1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}}||^{2}=\sum_{k=N+1}^{n}|\langle x,e_{i_{k}}\rangle|^{2}$. Hence $\sum_{k=N+1}^{\infty}|\langle x,e_{i_{k}}\rangle|^{2}\leq\left(\frac{\varepsilon}{4}\right)^{2}$. Let $I_{2}\in\mathcal{C}$ be arbitrary such that $I_{1}\preceq I_{2}$. Then $$ ||\theta(I_{2})-y||\leq||\sum_{k=1}^{N}\langle x,e_{i_{k}}\rangle e_{i_{k}}-y||+||\sum_{i\in I_{2}\setminus I_{1}}\langle x,e_{i}\rangle e_{i}||\leq\frac{\varepsilon}{4}+||\sum_{i\in I_{2}\setminus I_{1}}\langle x,e_{i}\rangle e_{i}||. $$ Observe that $$ ||\sum_{i\in I_{2}\setminus I_{1}}\langle x,e_{i}\rangle e_{i}||^{2}=\sum_{i\in I_{2}\setminus I_{1}}|\langle x,e_{i}\rangle|^{2}\leq\sum_{k=N+1}^{\infty}|\langle x,e_{i_{k}}\rangle|^{2}\leq\left(\frac{\varepsilon}{4}\right)^{2} $$ because for any $i\in I_{2}\setminus I_{1}$, if $i\notin\{i_{N+1},i_{N+2},\ldots\}$, then $\langle x,e_{i}\rangle=0$.

Now we have: $||\theta(I_{2})-y||\leq\frac{\varepsilon}{2}$. This shows that $\sum_{i\in I}\langle x,e_{i}\rangle e_{i}=y$ in unordered sense.

Claim (5): The $y$ defined in Claim (3) and Claim (4) is $x$. That is $x=\sum_{i\in I}\langle x,e_{i}\rangle e_{i}$.

Proof of Claim (5): Let $z=x-y$. Prove by contradiction. Suppose the contrary that $z\neq0$. We adopt the notation in Claim (3) and Claim (4). Recall that for each $a\in\mathcal{H}$, the map $x\mapsto\langle x,a\rangle$ is continuous. Let $i\in I$ be arbitrary. Conside the case that $I_{x}$ is infinite (The finite case is trivial.). We have $$ \langle z,e_{i}\rangle=\lim_{n\rightarrow\infty}\langle x-\sum_{k=1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}},e_{i}\rangle. $$ If $i\notin I_{x}$, we have $\langle x,e_{i}\rangle=0$ and $\langle e_{i_{k}},e_{i}\rangle=0$ for all $k$, and hence $\langle z,e_{i}\rangle=0$. Suppose that $i\in I_{0}$, say $i=i_{k'}$ for some $k'\in\mathbb{N}$. Then for any $n\geq k'$, we have $$ \langle x-\sum_{k=1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}},e_{i}\rangle=\langle x,e_{i}\rangle-\langle\sum_{k=1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}},e_{i}\rangle=\langle x,e_{i_{k'}}\rangle-\langle x,e_{i_{k'}}\rangle=0. $$ Therefore $\langle z,e_{i}\rangle=0$ in all cases. Define $\tilde{z}=z/||z||$, then $\{e_{i}\mid i\in I\}\cup\{\tilde{z}\}$ is an orthonormal set, containing $\{e_{i}\mid i\in I\}$ as a proper subset. This contradicts to the maximality of $\{e_{i}\mid i\in I\}$.


We construct a sequence $\{e_{n}\}$ inductively as follows: Define $$ e_{1}=\begin{cases} 0, & \mbox{ if }x_{1}=0\\ \frac{x_{1}}{||x_{1}||}, & \mbox{ if }x_{1}\neq0 \end{cases}. $$ Suppose that $e_{1},e_{2},\ldots,e_{n}$ have been defined. Define $$ \tilde{e}_{n+1}=x_{n+1}-\sum_{i=1}^{n} < x_{n+1},e_{i} > e_{i} $$ and further let $$ e_{n+1}=\begin{cases} 0, & \mbox{ if }\tilde{e}_{n+1}=0\\ \frac{\tilde{e}_{n+1}}{||\tilde{e}_{n+1}||}, & \mbox{ if }\tilde{e}_{n+1}\neq0 \end{cases}. $$

Claim 1: Prove by induction that $< e_{i},e_{j}>=0$ whenever $i\neq j$ and $||e_{i}||$ is either $0$ or $1$.

Claim 2: Linear span by $\{x_{n}\mid n\in\mathbb{N}\}$ is precisely linear span by $\{e_{n}\mid n\in\mathbb{N}\}$. Hence, taking closure on both sides, we conclude that the closed linear span by $\{e_{n}\mid n\in\mathbb{N}\}$ is $\mathcal{H}$.

Finally, The collection $\{e_{n}\mid e_{n}\neq0\}$ is an orthonormal base for $\mathcal{H}$.

I don't have time to write down the details of the proof. Please tell me if anything is wrong. Thank you.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.