LEC ALG1 22

More on orthogonal vectors

Constructing orthonormal basis using Gram-Schmidt

Recall that If $V$ is a finite dimensional inner product space, it has an orthonormal set as a basis.

Example 88.1(Example).

Let $V$ be the set of all polynomials with real coefficients and degree $\le 2$. Define

$$⟨f,g⟩={\int }_{-1}^{1}f(t)g(t)dt$$

The standard basis of $V$ is $({\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3)\equiv (1,t,t^2)$. Applying the Gram-Schmidt Orthogonalization Process, we get

$$\begin{array}{rl}& \\ {\mathbf{w}}_1& =\frac{{\mathbf{v}}_1}{\Vert {\mathbf{v}}_1\Vert }=\frac{1}{\sqrt{{\int }_{-1}^{1}dt}}=\frac{1}{\sqrt{2}}.\\ & \\ {\mathbf{u}}_2& ={\mathbf{v}}_2-⟨{\mathbf{v}}_2,{\mathbf{w}}_1⟩{\mathbf{w}}_1\\ & =t-\left({\int }_{-1}^{1}t\frac{1}{\sqrt{2}}dt\right)\frac{1}{\sqrt{2}}\\ & =t\\ & \\ {\mathbf{w}}_2& =\frac{{\mathbf{u}}_2}{\Vert {\mathbf{u}}_2\Vert }=\frac{t}{\sqrt{{\int }_{-1}^1{t}^{2}dt}}=t\sqrt{\frac{3}{2}}\\ & \\ {\mathbf{u}}_3& ={\mathbf{v}}_3-⟨{\mathbf{v}}_3,{\mathbf{w}}_1⟩{\mathbf{w}}_1-⟨{\mathbf{v}}_3,{\mathbf{w}}_2⟩{\mathbf{w}}_2=t^2-\frac{1}{3}\\ & \\ {\mathbf{w}}_3& =\frac{{\mathbf{u}}_3}{\Vert {\mathbf{u}}_3\Vert }=\frac{\sqrt{10}}{4}(3t^2-1)\end{array}$$

Thus, $\left\{\frac{1}{\sqrt{2}},t\sqrt{\frac{3}{2}},\frac{\sqrt{10}}{4}(3t^2-1)\right\}$ is an orthonormal basis for $V$.

The Orthogonal Decomposition Theorem

Theorem 88.2(Theorem).

If $V$ is a finite dimensional inner product space and $W$ is a subspace of $V$, then

$$V=W\oplus W^{\perp }$$

Proof.

Note that $W$ itself is an inner product space. So, $W$ has an orthonormal basis ${\mathbf{w}}_1,{\mathbf{w}}_2,\dots ,{\mathbf{w}}_r$. For any $\mathbf{v}\in V$, define

$$\begin{array}{r}{\mathbf{v}}_0\equiv \mathbf{v}-\sum _{i=1}^r⟨\mathbf{v},{\mathbf{w}}_i⟩{\mathbf{w}}_i.\end{array}$$

Notice that ${\mathbf{v}}_0$ is orthogonal to each ${\mathbf{w}}_i$. Hence, ${\mathbf{v}}_0$ is orthogonal to $W$, i.e., ${\mathbf{v}}_0\in W^{\perp }$. We can now write

$$\mathbf{v}=\underset{\in W^{\perp }}{\underbrace{{\mathbf{v}}_0}}+\underset{\in W}{\underbrace{\sum _{i=1}^r⟨\mathbf{v},{\mathbf{w}}_i⟩{\mathbf{w}}_i}}.$$

So, $\mathbf{v}\in V$ $⟹$ $\mathbf{v}\in W\oplus W^{\perp }$. We have already shown that $W\cap W^{\perp }=\{0\}$, so this decomposition is unique. Thus, $V=W\oplus W^{\perp }$.□

Proof.

Assume $\mathbb{F}=\mathbb{R}$ for simplicity. Let $\mathbf{v}\in V$.

Claim 88.3(Claim).

We can find ${\mathbf{w}}_0\in W$ such that $\Vert \mathbf{v}-{\mathbf{w}}_0\Vert \le \Vert \mathbf{v}-\mathbf{w}\Vert$ for all $\mathbf{w}\in W$.

Proof..

Let ${\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_k$ be a basis of $W$. Let $\mathbf{w}\in W$ be written as $\mathbf{w}=\sum {\lambda }_i{\mathbf{u}}_i$. Then,

$$\begin{array}{rl}\Vert \mathbf{v}-\mathbf{w}{\Vert }^2& =⟨\mathbf{v}-\sum _{i=1}^k{\lambda }_i{\mathbf{u}}_i,\mathbf{v}-\sum _{i=1}^k{\lambda }_i{\mathbf{u}}_i⟩\\ & =⟨\mathbf{v},\mathbf{v}⟩+\sum _{i,j}{\lambda }_i{\lambda }_j⟨{\mathbf{u}}_i,{\mathbf{u}}_j⟩-2\sum _i{\lambda }_i⟨\mathbf{v},{\mathbf{u}}_i⟩\end{array}$$

Note that only the ${\lambda }_i$‘s are variable in the above expression, and they are determined by $\mathbf{w}$. So, $\Vert \mathbf{v}-\mathbf{w}\Vert$ is a non-negative second degree function in ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k$. Calculus tells us that such functions must attain a minimum for some tuple $({\lambda }_1^{\prime },{\lambda }_2^{\prime },\dots ,{\lambda }_k^{\prime })$. Take ${\mathbf{w}}_0\equiv \sum {\lambda }_i^{\prime }{\mathbf{u}}_i$.□

Proof..

Define a metric $d(\mathbf{x},\mathbf{y})\equiv \Vert \mathbf{x}-\mathbf{y}\Vert$. This makes $V$ a metric space. Let $S=\{\mathbf{w}\in W|\Vert \mathbf{v}-\mathbf{w}\Vert \le \Vert \mathbf{v}\Vert \}$. Let $\mathcal{B}$ be an orthonormal basis of $V$. Let $n=\dim V$. Define an isomorphism $\varphi :V\to {\mathbb{R}}^n$ by $\varphi (\mathbf{v})=[\mathbf{v}{]}_{\mathcal{B}}$. Note that the isomorphism preserves norms, i.e, $\Vert \mathbf{v}\Vert =\Vert [\mathbf{v}{]}_{\mathcal{B}}\Vert$, so $\Vert \mathbf{x}-\mathbf{y}\Vert =\Vert [\mathbf{x}{]}_{\mathcal{B}}-[\mathbf{y}{]}_{\mathcal{B}}\Vert$. Now consider a closed ball $B$ of radius $\Vert \mathbf{v}\Vert$ centered at $[\mathbf{v}{]}_{\mathcal{B}}$ in ${\mathbb{R}}^n$. From subspace topology, we know that $B\cap \varphi (W)$ is closed in $\varphi (W)$. Since $\varphi (W)$ is a subspace of ${\mathbb{R}}^n$, it follows from the Heine Borel theorem that $B\cap \varphi (W)$ is compact. Observe that ${\varphi }^{-1}(B\cap \varphi (W))=S$. Since ${\varphi }^{-1}$ is continuous (choose $\delta =ϵ$), $S$ must also be compact. Define $f:S\to \mathbb{R}$ by $f(\mathbf{w})=\Vert \mathbf{v}-\mathbf{w}\Vert$. $f$ is continuous on its domain. From the extreme value theorem, $f$ must attain a minimum value on $S$. This must be the global minimum of $\Vert \mathbf{v}-\mathbf{w}\Vert$, since $\Vert \mathbf{v}-\mathbf{w}\Vert >\Vert \mathbf{v}\Vert$ outside $S$.□

Claim 88.4(Claim).

$⟨\mathbf{v}-{\mathbf{w}}_0,\mathbf{w}⟩=0$ for all $\mathbf{w}\in W$.

Proof..

From Claim 1, we know that $\Vert \mathbf{v}-{\mathbf{w}}_0\Vert \le \Vert \mathbf{v}-\mathbf{w}\Vert$ for all $\mathbf{w}\in W$. So,

$$\begin{array}{rl}\Vert \mathbf{v}-{\mathbf{w}}_0\Vert & \le \Vert \mathbf{v}-(\mathbf{w}+{\mathbf{w}}_0)\Vert \\ & \\ ⟨\mathbf{v}-{\mathbf{w}}_0,\mathbf{v}-{\mathbf{w}}_0⟩& \le ⟨\mathbf{v}-(\mathbf{w}+{\mathbf{w}}_0),\mathbf{v}-(\mathbf{w}+{\mathbf{w}}_0)⟩\\ & \le ⟨\mathbf{w},\mathbf{w}⟩+⟨\mathbf{v}-{\mathbf{w}}_0,\mathbf{v}-{\mathbf{w}}_0⟩-2⟨\mathbf{v}-{\mathbf{w}}_0,\mathbf{w}⟩\\ & \\ 2⟨\mathbf{v}-{\mathbf{w}}_0,\mathbf{w}⟩& \le ⟨\mathbf{w},\mathbf{w}⟩\forall \mathbf{w}\in W.\end{array}$$

Let $m\in {\mathbb{Z}}^{+}$. $\frac{1}{m}\mathbf{w}\in W\forall \mathbf{w}\in W$. Thus,

$$\begin{array}{rl}2⟨\mathbf{v}-{\mathbf{w}}_0,\frac{\mathbf{w}}{m}⟩& \le ⟨\frac{\mathbf{w}}{m},\frac{\mathbf{w}}{m}⟩\\ ⟨\mathbf{v}-{\mathbf{w}}_0,\mathbf{w}⟩& \le \frac{1}{2m}⟨\mathbf{w},\mathbf{w}⟩\end{array}$$

On letting $m\to \infty$, we get $⟨\mathbf{v}-{\mathbf{w}}_0,\mathbf{w}⟩\le 0$ for all $\mathbf{w}\in W$. Now, consider $-\mathbf{w}\in W$.

$$\begin{array}{rl}⟨\mathbf{v}-{\mathbf{w}}_0,-\mathbf{w}⟩& \le 0\\ ⟨\mathbf{v}-{\mathbf{w}}_0,\mathbf{w}⟩& \ge 0\end{array}$$

Therefore, $⟨\mathbf{v}-{\mathbf{w}}_0,\mathbf{w}⟩=0$ for all $\mathbf{w}\in W$.□

Now, we can express $\mathbf{v}$ like so:

$$\mathbf{v}=\underset{\in W^{\perp }}{\underbrace{(\mathbf{v}-{\mathbf{w}}_0)}}+\underset{\in W}{\underbrace{{\mathbf{w}}_0}}$$ □

Orthogonal projections

We have seen that every $\mathbf{v}\in V$ can be written uniquely as $\mathbf{v}=\mathbf{w}+\mathbf{u}$, where $\mathbf{w}\in W$ and $\mathbf{u}\in W^{\perp }$. The orthogonal projection from $V$ to $W$ is the map $\Pi :V\to W$ defined by $\mathbf{v}\to \mathbf{w}$. Note that $\Pi$ is a linear map. Note that $\Pi (\mathbf{w})=\mathbf{w}$ if $\mathbf{w}\in W$, and $\Pi (\mathbf{w})=0$ if $\mathbf{w}\in W^{\perp }$.

If ${\mathbf{w}}_1,{\mathbf{w}}_2,\dots ,{\mathbf{w}}_k$ is an orthonormal bass for $W$, then

$$\Pi (\mathbf{v})=\sum _{i=1}^k⟨{\mathbf{w}}_i,\mathbf{v}⟩{\mathbf{w}}_i.$$

Note that $\mathbf{v}-\Pi (\mathbf{v})\in W^{\perp }$. If $W$ happened to be $V$, then $W^{\perp }=\{0\}$. So, $\mathbf{v}=\Pi (\mathbf{v})$.