# 基底正交化

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

from lingeo import random_good_matrix
from linspace import QR, projection_on_vector

## Main idea

Suppose $U$ is an inner product space.
Then every subspace of $U$ has an orthonormal basis.
Indeed, there is an algorithm for converting a basis into an orthonormal basis.
This process is referred to as **orthogonalization**.

Let $V$ be a subspace of $U$ and $S = \{{\bf u}_1, \ldots, {\bf u}_d\}$ a basis of $V$.
Taking $S$ as the input, the following steps generates an orthonormal basis $\hat{S} = \{\hat{\bf u}_1, \ldots, \hat{\bf u}_d\}$ such that $V = \operatorname{span}(S) = \operatorname{span}(\hat{S})$.
1. $\hat{\bf u}_1 = {\bf u}_1$
2. Let $V_{k-1}$ be the space spanned by $S_{k-1} = \{\hat{\bf u}_1,\ldots, \hat{\bf u}_{k-1}\}$.
Then $\hat{\bf u}_{k} = {\bf u}_{k} - \operatorname{proj}_{V_{k-1}}({\bf u}_{k})$, where $\operatorname{proj}_{V_{k-1}}({\bf u}_k)$ is the projection of ${\bf u}_k$ onto the subspace $V_{k-1}$.
Repeat this step for $k = 2,\ldots, d$.
4. Normalize each vector of $\{\hat{\bf u}_1, \ldots, \hat{\bf u}_d\}$ to length one.

This algorithm is called the **Gram--Schmidt process**.

Let $\operatorname{proj}_{\bf v}({\bf u})$ be the projection of ${\bf u}$ onto the line spanned by ${\bf v}$.
Notice here
$$\begin{aligned}
{\bf u}_k &= \hat{\bf u}_k + \operatorname{proj}_{V_{k-1}}({\bf u}_k) \\
&= \operatorname{proj}_{\hat{\bf u}_1}({\bf u}_k) + \cdots + \operatorname{proj}_{\hat{\bf u}_{k-1}}({\bf u}_k) + \hat{\bf u}_k
\end{aligned}
$$
since $\{\hat{\bf u}_1,\ldots,\hat{\bf u}_{k-1}\}$ is orthogonal.
Therefore, ${\bf u}_k \in \operatorname{span}(S_k)$.
Let $Q$ be the matrix whose columns are vectors in $\hat{S}$
and $A$ the matrix whose columns are vectors in $S$.
Then $A = QR$ for some upper triangular matrix.
This decomposition is called the $QR$ decomposition of $A$.

Let $Q$ be an $m\times n$ matrix.
Then the following are equivalent:
1. $Q^\top Q = I_n$.
2. The set of columns of $Q$ is an orthonormal basis of $\mathbb{R}^m$.

A matrix $Q$ satisfying one of these conditions is called a **column-orthogonal** matrix.
Similarly, $Q$ is **row-orthogonal** if the set of rows of $Q$ is an orthonormal basis of $\mathbb{R}^n$.

When $Q$ is an $n\times n$ matrix, then $Q$ is column-orthogonal if and only if $Q$ is row-orthogonal.
Such a matrix is an **orthogonal** matrix.

## Side stories
- code
- `A.QR()`

## Experiments

##### Exercise 1

執行以下程式碼。
令 $S = \{{\bf u}_1,{\bf u}_2,{\bf u}_3\}$ 為 $A$ 中的各行向量。
利用以下的公式計算：
1. $\hat{\bf u}_1 = {\bf u}_1$.
2. $\hat{\bf u}_2 = {\bf u}_2 - \operatorname{proj}_{\hat{\bf u}_1}({\bf u}_2)$.
3. $\hat{\bf u}_3 = {\bf u}_3 - \operatorname{proj}_{\hat{\bf u}_1}({\bf u}_3) - \operatorname{proj}_{\hat{\bf u}_2}({\bf u}_3)$.

### code
set_random_seed(0)
print_ans = False
m,n,r = 4,3,3
A = random_good_matrix(m,n,r,bound=1)
Q, R = QR(A)
u1,u2,u3 = A.transpose()
uh1 = u1
# uh2 = u2 - projection_on_vector(u2, uh1)
# uh3 = ...

print("A =")
show(A)

if print_ans:
    print("u-hat_i are the columns of")
    show(Q)
    D = diagonal_matrix(q.norm() for q in Q.transpose())
    print("An orthonormal basis can be the columns of")
    show(Q * D.inverse())
    print("The QR decomposition can be")
    print("Q =")
    show(Q * D.inverse())
    print("R =")
    show(D.inverse() * R)

##### Exercise 1(a)

計算 $\hat{S} = \{ \hat{\bf u}_1, \hat{\bf u}_2, \hat{\bf u}_3\}$。
可以用 `projection_on_vector(u, v)` 來計算 $\operatorname{proj}_{\bf v}({\bf u})$。

##### Exercise 1(b)

判斷 $\hat{S}$ 是否垂直、是否單位長垂直。
如果不是單位長垂直﹐找出一組單位長垂直的基底。

##### Exercise 1(c)

求出一個垂直矩陣 $Q$ 及一個上三角矩陣 $R$ 使得 $A = QR$。

## Exercises

##### Exercise 2

求出以下空間的垂直基底。
（不一定要把向量縮為單位長。）

##### Exercise 2(a)

求出 $V = \{(x,y,z) : x + y + z = 0\}$ 的一組垂直基底。

##### Exercise 2(b)

求出 $V = \{(x,y,z,w) : x + y + z + w = 0\}$ 的一組垂直基底。

##### Exercise 3

令 $S = \{{\bf u}_1,{\bf u}_2,{\bf u}_3\}$ 為 向量空間 $V$ 的一組基底﹐且 $A$ 的各行向量為 $S$。
令 $\hat{S} = \{ \hat{\bf u}_1, \hat{\bf u}_2, \hat{\bf u}_3\}$ 為 $V$ 的一組單位長垂直基底﹐且 $Q$ 的各行向量為 $\hat{S}$。
已知
$$\begin{aligned}
{\bf u}_1 &= \hat{\bf u}_1, \\
{\bf u}_2 &= 2\hat{\bf u}_1 + 3\hat{\bf u}_2, \\
{\bf u}_3 &= 4\hat{\bf u}_1 + 5\hat{\bf u}_2 + 6\hat{\bf u}_3.\\
\end{aligned}
$$
求上三角矩陣 $R$ 使得 $A = QR$。

##### Exercise 4

令 $QR$ 為 $A$ 的 $QR$ 分解。

##### Exercise 4(a)

說明 $\operatorname{Col}(A) = \operatorname{Col}(Q)$。

##### Exercise 4(b)

因此對 $\operatorname{Col}(A)$ 和對 $\operatorname{Col}(Q)$ 的投影應該是一樣的。
說明 $A(A^\top A)^{-1}A^\top = Q(Q^\top Q)^{-1}Q^\top$。

##### Exercise 5

寫一個程式﹐
讓輸入矩陣 $A$ 後會得出它的 $QR$ 分解。