Gram-Schmidt Process

Orthogonal

Definition 1. Let $(V, \langle \cdot, \cdot \rangle)$ be an inner product space. Let $x, y \in V$, and let $S \subseteq V$. Then
(a) $x$ and $y$ are orthogonal (or perpendicular) if $\langle x, y\rangle = 0$.
(b) $S$ is orthogonal if any two distinct vector in $S$ are orthogonal.

고등학교 시절 내적을 배웠다면, 내적의 정의를 $x \cdot y = |x| |y| \cos \theta$로 기억하고 있을 것이다. 이 경우 $\theta = 90^{\circ}$일 때 두 벡터가 직교하고, 내적은 0이 된다. 그러나 이는 $\mathbb{R}^3$와 같이 두 벡터 사이의 각 $\theta$를 직관적으로 측정할 수 있는 경우에만 가능하고, 더 추상적인 공간을 다루게 되면 더 이상 두 벡터 사이의 각을 측정함으로 내적을 구할 수 없다. 따라서 어떻게 내적이 정의되어 있든 그 값이 0이라면 두 벡터는 수직, 혹은 직교한다고 말하고, 서로 수직인 벡터들을 모아놓으면 그 벡터들의 집합을 직교집합이라고 부른다. 

    자연스럽게 벡터 공간의 기저가 직교집합이 되는 경우를 생각해 볼 수 있고, 아래와 같이 정의한다.

Orthonormal Basis

Definition 2. Let $(V, \langle \cdot, \cdot \rangle)$ be an inner product space, and let $\beta \subseteq V$. Then
(a) $\beta$ is orthonormal if $\beta$ is orthogonal and consists entirely of unit vectors.
(b) $\beta$ is an orthonormal basis for $V$ if $\beta$ is an ordered basis that is orthonormal.

Remark

Remark. Let $(V, \langle \cdot, \cdot \rangle)$ be an inner product space, and let $x \in V$.
(a) If $S = \{v_1, v_2, ...\}$, then $S$ is orthonormal $\iff$ $\langle v_i, v_j\rangle = \delta_{ij}$.
(b) We call $x$ an unit vector if $||x|| = 1$. If $x \neq \mathbf{0}$, then $\frac{x}{||x||}$ is a unit vector. The process of multiplying a nonzero vector by the reciprocal of its length is called normalizing.

Theorem 1

Theorem 1. Let $(V, \langle \cdot, \cdot \rangle)$ be an inner product space and $S = \{v_1, ..., v_k\}$ be an orthogonal subset of $V$ consisting of nonzero vectors. If $y \in \langle S \rangle$, then $$y = \sum_{i=1}^k \frac{\langle y, v_i \rangle}{||v_i||^2} v_i.$$

Proof. Let denote $y = \sum_{i=1}^k a_iv_i$. Since $\langle y, v_i \rangle$ = $a_i||v_i||^2$, we have $a_i = \frac{\langle y, v_i \rangle}{||v_i||^2}$ for each $i$. Thus $y = \sum_{i=1}^k \frac{\langle y, v_i \rangle}{||v_i||^2}v_i$. $\blacksquare$

직관적으로 말하면 $y$를 orthgonal subset의 벡터들의 정사영들의 합으로 나타낼 수 있다는 것이다. 단순하게 $\langle x, y\rangle = ||x|| ||y|| \cos \theta$로 생각하자. 그러면 $\langle y, v_i \rangle$는 ($y$의 $v_i$ 방향으로의 크기) * ($v_i$의 크기) 이고, $||v_i||$로 나눠줌으로써 $v_i$의 크기를 상쇄시켜준다. 그리고 $v_i$ 방향으로 만들어 주면 되므로 단위벡터 $\frac{v_i}{||v_i||}$를 곱한다. 이를 모든 $i$에 대해서 적용한 뒤 더해주면 $y$를 표현할 수 있다.

Corollary 1

Corollary 1. Let $(V, \langle \cdot, \cdot \rangle)$ be an inner product space, and let $S$ be an orthogonal subset of $V$ consisting of nonzero vectors. Then $S$ is linearly independent.

Proof. Suppose that for $v_1, ..., v_k \in S$, $\sum_{i=1}^k a_iv_i = \mathbf{0}$. By Theorem 1, we have that $a_i = \frac{\langle \mathbf{0}, v_i \rangle}{||v_i||^2} = 0$ for each $i$. Thus $S$ is linearly independent. $\blacksquare$

Theorem 2

Theorem 2. Let $(V, \langle \cdot, \cdot \rangle)$ be an inner product space and $S = \{w_1, ..., w_n\}$ be a linearly independent subset of $V$. Define $S' = \{v_1, ..., v_n\}$ where $v_1 = w_1$ and $$v_k = w_k - \sum_{j=1}^{k-1} \frac{\langle w_k, v_j \rangle}{||v_j||^2} v_j \, \text{ for } \, 2 \leq k \leq n.$$ Then $S'$ is an orthogonal set of nonzero vectros such that $\langle S'\rangle = \langle S\rangle$.

Proof. The proof is by mathematical induction on $n$. Denote $S_k = \{w_1, ..., w_k\}$ for $k = 1, ..., n$.
If $n=1$, then $S = S'$. Thus the theorem is proved because $v_1 = w_1 \neq \mathbf{0}$.
Assume that the theorem is true for $n-1$ where $n-1 \geq 1$.
If $v_n = \mathbf{0}$, then $w_n \in \langle S'_{n-1} \rangle = \langle S_{n-1}\rangle$. So $S_{n-1} \cup \{w_n \} = S_n$ is linearly independent. $\bigotimes$ Thus $v_n \neq \mathbf{0}$.
For any $i (1 \leq i \leq n-1)$, we have $$\langle v_n, v_i \rangle = \langle w_n - \sum_{j=1}^{n-1} \frac{\langle w_n, v_j \rangle}{||v_j||^2}v_j, v_i \rangle \\ = \langle w_n, v_i\rangle - \sum_{j=1}^{n-1}\frac{\langle w_n, v_j \rangle}{||v_j||^2}\langle v_j, v_i\rangle = \langle w_n, v_i \rangle - \frac{\langle w_n, v_i \rangle}{||v_i||^2}\langle v_i, v_i \rangle = 0$$ because $\langle v_j, v_i \rangle = \delta_{ji}$. Thus $S'_n$ is an orthogonal set of nonzero vectors. Note that $\langle S'_n \rangle \subseteq \langle S_n \rangle$. By Corollary, $S'_n$ is linearly independent. Thus $\dim(\langle S'_n \rangle) = \dim(\langle S_n \rangle) = n \Longrightarrow \langle S'_n \rangle = \langle S_n \rangle$. $\blacksquare$ 

Figure 1 (Linear Algebra 4ed. written by S. Friedberg 344p.)

Theorem 3

Theorem 3. Let $(V, \langle \cdot, \cdot \rangle)$ be a nonzero finite-dimensional inner product space. Then $V$ has an orthonormal basis $\beta$. Furthermore, if $\beta = \{v_1, ..., v_n\}$ and $x \in V$, then $$x = \sum_{i=1}^n \langle x, v_i \rangle v_i.$$

정리하면, Theorem 2를 통해 linearly independent set으로부터 동일한 벡터공간을 생성하는 직교집합을 만들 수 있고, 각 벡터들을 그 크기로 나눠줌으로써, 즉 normalization함으로써 orthonormal set을 얻을 수 있다. 따라서 이러한 과정을 벡터공간의 기저에 적용하면 항상 정규직교기저를 얻을 수 있다. 이 과정을 Gram-Schmidt Process라고 부른다.

Corollary 2

Corollary 2. Let $V$ and $W$ be finite-dimensional inner product space with inner products $\langle \cdot, \cdot \rangle _1$ and $\langle \cdot, \cdot \rangle _2$, respectively. Let $\beta = \{v_1, ..., v_n\}$ and $\gamma = \{w_1, ..., w_m\}$ be orthonormal bases for $V$ and $W$, respectively. Let $T \in \mathcal{L}(V, W)$, and let $A = [T]_{\beta}^{\gamma}$. Then for any $i, j$, $A_{ij} = \langle T(v_j), w_i \rangle _2$.

Proof. Note that $$\langle T(v_j), w_i \rangle _2 = \langle \sum_{i=1}^n A_{ij}w_i, w_i\rangle _2 = A_{ij}. \blacksquare$$