# 垂直幾何

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_int_list, random_good_matrix
from linspace import QR

## Main idea

The notion of "angle" is not necessary possible for every vector space.
However, many vector spaces over $\mathbb{R}$ or $\mathbb{C}$ do have (at least) one meaningful inner product, and the angle is therefore defined.
Such a vector space is called an _inner product space_.
Here, we only focus on concrete examples.

Let $V$ be a vector space and $\langle \cdot, \cdot \rangle$ an inner product on $V$.
Recall that ${\bf u}$ and ${\bf v}$ are **orthogonal** if $\langle {\bf u}, {\bf v} \rangle = 0$.
Let $S = \{{\bf u}_1, \ldots, {\bf u}_k\}$ be a collection of vectors.
Then $S$ is **orthogonal** if $\langle {\bf u}_i, {\bf u}_j \rangle = 0$ for any pair of distinct $i,j$.
Moreover, if $S$ is orthogonal and $\|{\bf u}\|^2 = \langle {\bf u}_i, {\bf u}_i \rangle = 1$ for any $i$, then $S$ is called **orthognormal**.
If a basis $\beta$ is orthogonal, then one may rescale every vector to length one to make it orthonormal.

Suppose $S = \{{\bf u}_1, \ldots, {\bf u}_k\}$ is orthogonal.
Then
$$\begin{array}{cc}
& (a_1{\bf u}_1 + \cdots a_k{\bf u}_k) \\
\cdot & (b_1{\bf u}_1 + \cdots b_k{\bf u}_k) \\
= & (a_1b_1\|{\bf u}_1\|^2 + \cdots a_kb_k\|{\bf u}_k\|^2) \\
\end{array}
$$
holds for any two linear combination of $S$.
In particular, when $S$ is orthonormal, the inner product is
$$(a_1{\bf u}_1 + \cdots a_k{\bf u}_k) \cdot
(b_1{\bf u}_1 + \cdots b_k{\bf u}_k) =
a_1b_1 + \cdots + a_kb_k,
$$
and the length is
$$\|a_1{\bf u}_1 + \cdots a_k{\bf u}_k\| = a_1^2 + \cdots + a_k^2.
$$

Let ${\bf b}$ be a vector and $S = \{{\bf u}_1, \ldots, {\bf u}_k\}$ is orthogonal.
Suppose ${\bf b}_1, \ldots, {\bf b}_k$ are the projection of ${\bf b}$ onto each vectors ${\bf u}_1, \ldots, {\bf u}_k$, respectively, and ${\bf b}_S$ is the projection of ${\bf b}$ onto $\operatorname{span}(S)$.
Then ${\bf b}_S = {\bf b}_1 + \cdots {\bf b}_k$.

Let ${\bf b}$ be a vector and $V$ a subspace.
Suppose ${\bf b}$ can be written as ${\bf b} = {\bf w} + {\bf h}$ such that ${\bf w}\in V$ and ${\bf h}\in V^\perp$.
Then ${\bf v} = {\bf w}$ minimize the length $\|{\bf b} - {\bf v}\|$ among all vector ${\bf v} \in V$.

## Side stories
- linear regression
- inner product space

## Experiments

##### Exercise 1

執行以下程式碼。
令 $S = \{{\bf u}_1,\ldots,{\bf u}_3\}$ 為 $Q$ 中的各行向量。
己知 ${\bf b}\in \operatorname{span}(S)$。

### 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)
v = vector(random_int_list(3,2))
b = Q * v

print("Q =")
show(Q)
print("b =", b)

if print_ans:
    print("S is orthogonal but not orthonormal.")
    print("b = " + " + ".join("%s u%s"%(v[i],i+1) for i in range(n)))
    print("Length of b =", b.norm())

此題取 `seed(0)`
$Q=\begin{bmatrix}
1 & \frac{1}{2} & -\frac{1}{2}\\
-1 & \frac{1}{2} &\frac{1}{2}\\
1&-\frac{1}{2}&\frac{1}{2}\\
1&\frac{1}{2}&\frac{1}{2}
\end{bmatrix}$
$b=(3/2,-7/2,5/2,1/2)$

:::warning

- [x] 複製一下你們用的 `seed` 以及題目給的數字
:::

##### Exercise 1(a)

判斷 $S$ 是否垂直、
是否單位長垂直。

答:
$S$ 為垂直，因為 $S$ 當中的向量互相內積為 $0$。
然而，不為單位長垂直，因為 $S$ 中有長度不為 $1$ (單位長)的向量。

##### Exercise 1(b)

找出一組向量 $S'$ 使得 $\operatorname{span}(S') = \operatorname{span}(S)$
且 $S'$ 是單位長垂直。

:::warning

- [x] $u1$ --> $\bu_1$ 其它類似；後面幾小題也是
- [x] 適當換行
:::

答:
令$\bu_1=(1/2,-1/2,1/2,1/2)$
$\bu_2 =(1/2,1/2,-1/2,1/2)$
$\bu_3 =(-1/2,1/2,1/2,1/2)$
取 $S'= \{\bu_1,\bu_2,\bu_3\}$。

##### Exercise 1(c)

將 ${\bf b}$ 寫成 $S$ 的線性組合。

:::warning

- [x] 向量粗體
- [x] 不是集合不用寫大括號
:::

答:
$\bb =4\bu_1+(-2)\bu_2+(-1)\bu_3$ 。

##### Exercise 1(d)

利用 ${\bf b}$ 的線性組合算出 ${\bf b}$ 的長度。

:::warning

- [x] 向量長度用 $\|?\|$
- [x] 確認長度
:::

答:
$\|\bb\|=\sqrt{\|4\bu_1
\|^2+\|(-2)\bu_2\|^2+\|(-1)\bu_3\|^2}=\sqrt{21}$。

## Exercises

##### Exercise 2

以下小題討論垂直和線性獨立的關係。

##### Exercise 2(a)

證明如果 $S$ 是單位長垂直的﹐則 $S$ 線性獨立。

:::warning

- [x] 第一句沒用到
- [x] $\bu_m$ 是什麼東西? $m$ 是什麼?

令 $S = \{\bu_1, \ldots, \bu_k\}$。
假設 $c_1\bu_1 + \cdots + c_k\bu_k = \bzero$。
對於任意的 $i = 1,\ldots, k$，
將左右兩式同時和 $???$ 取內積，
可得 ...。
因此 ...。
:::

令 $S = \{\bu_1, \ldots, \bu_k\}$。
假設 $\bzero=c_1\bu_1+ \ldots +c_k\bu_k$。
對於任意的 $i=1,\ldots,k$，
將左右兩式同時和 $\bu_i$ 取內積，
可得到 $0=c_i\|\bu_i\|^2$，因為 $\|\bu_i\| = 1$，所以 $c_i = 0$，
因此 $S$ 為線性獨立。

##### Exercise 2(b)

找一組向量集合 $S$ 使得它是垂直的但不線性獨立。

:::warning

- [x] 左括號用 `\left\{` 右括號用 `\right\}`
:::

$$S=\left\{
\begin{bmatrix}
1 \\
1 \\
1 \\
1 \\
\end{bmatrix},\begin{bmatrix}
0 \\
0 \\
0 \\
0 \\
\end{bmatrix}
\right\}.
$$

##### Exercise 3

令
$$A = \begin{bmatrix}
1 & 1 \\
1 & 2 \\
1 & 3 \\
1 & 4 \\
\end{bmatrix}
$$
而 ${\bf b} = (2.4, 3.1, 3.4, 4.1)$。

##### Exercise 3(a)

求 $\operatorname{Col}(A)$ 中和 ${\bf b}$ 最接近的向量 ${\bf w}$、
並將它寫成 $A$ 的行向量的線性組合。

:::warning

- [x] 中英數間空格
- [x] 標點
- [x] $C(C^\top C)^{-1}C^\top{\bf b} = (2.44, 2.98, 3.52, 4.06)$。
$(2.44, 2.98, 3.52, 4.06) = 1.9(1, 1, 1, 1) + 0.54(1, 2, 3, 4)$ --> 因此 $\bw = C(C^\top C)^{-1}C^\top{\bf b} = (2.44, 2.98, 3.52, 4.06)$，
其中 $(2.44, 2.98, 3.52, 4.06) = 1.9(1, 1, 1, 1) + 0.54(1, 2, 3, 4)\in\Col(A)$。
:::

Ans:
令 $C = \operatorname{Col}(A)$。
找 ${\bf b}$ 投影在 $C$ 上的向量，即為最接近的向量。
因此 $\bw = C(C^\top C)^{-1}C^\top{\bf b} = (2.44, 2.98, 3.52, 4.06)$，
其中 $(2.44, 2.98, 3.52, 4.06) = 1.9(1, 1, 1, 1) + 0.54(1, 2, 3, 4)\in\Col(A)$。

##### Exercise 3(b)\b

令 $(x_1,x_2,x_3,x_4) = (1,2,3,4)$ 為 $A$ 的第二個行向量
且 $(y_1,y_2,y_3,y_4) = (2.4, 3.1, 3.4, 4.1) = {\bf b}$。
求解 $c_0$ 和 $c_1$ 使得 $\sum_{i=1}^4 (c_0 + c_1x_i - y_i)^2$ 最小。

:::warning

- [x] (1, 1, ,1 , 1) 有錯
- [x] $c_0 = 1.9, c_1 = 0.54$ --> 因此 $c_0 = 1.9, c_1 = 0.54$。
:::

Ans:
因 $A$ 的第一個行向量為 $(1,1,1,1)$，所以，
$c_0(1, 1 ,1 , 1) + c_1(1, 2, 3, 4)$ 即可表示 $\operatorname{Col}(A)$ 中任一向量。
因此，要使得 $\sum_{i=1}^4 (c_0 + c_1x_i - y_i)^2$ 最小
即是找 $\operatorname{Col}(A)$ 中最接近 ${\bf b}$ 的向量。
此向量為 $(2.44, 2.98, 3.52, 4.06) = 1.9(1, 1, 1, 1) + 0.54(1, 2, 3, 4)$，
因此 $c_0 = 1.9, c_1 = 0.54$。

##### Exercise 4

令
$$A = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
0 & 1 & 2 & 3 \\
\end{bmatrix}
$$
且 ${\bf b} = (3,3,2)$。
求解集合 $U = \{ {\bf x}\in\mathbb{R}^4 : A{\bf x} = {\bf b} \}$ 中長度最短的向量。

:::warning

- [x] 句子寫完整，加標點
- [x] 用 `aligned` 排版
:::

答:
###### 代數法:
$[A|b]$ 經過列運算之後得到 $R$ ,
其中 $$R= \left
[
\begin{array}{cccc|c}
1&0&-1&-2&1\\
0&1&2&3&2\\
0&0&0&0&0\\
\end{array}\right
]
$$
其中有一解為 $(1,
2,
0,
0 )$.
令 ${\bf x}=(x_1,x_2,x_3,x_4)$，可得 $A\bx = \bb$ 的解都可以寫為
$$\left\{
\begin{aligned}
x_1&=1+r+2s,
&r,s\in\mathbb{R} \\
x_2&=2-2r-3s, \\
x_3&=r, \\
x_4&=s.
\end{aligned}\right.
$$
直接計算可得
$$\begin{aligned}
\|{\bf x}\|&=\sqrt{x_1^2+x_2^2+x_3^2+x_4^2}\\
&=\sqrt{
(1+r+2s)^2+(2-2r-3s)^2+r^2+s^2
}\\
&=\sqrt{
6r^2+14s^2+16rs-6r-8s+5
}\\
&=\sqrt{
\frac{1}{6}(6r+8s-3)^2+\frac{10} {3}s^2+\frac{7}{2}.
}\end{aligned}
$$
當 $r=\frac{1}{2},s=0$ 時， $\|{\bf x}\|$ 有最小值 $\sqrt{\frac{7}{2}}$,
此時 ${\bf x}=(\frac{3}{2},1,\frac{1}{2},0)$.

:::warning

- [x] 最簡階梯形的零列會在最下面
- [x] 句子、標點
- [x] 投影公式有錯
- [x] 矩陣不用粗體
:::

###### 幾何觀點:

$\begin{bmatrix}A|b\end{bmatrix}$ 的最簡列梯形矩陣為 $$\begin{bmatrix}
1 & 0 & -1 & -2 & 1 \\
0 & 1 & 2 & 3 & 2\\
0 & 0 & 0 & 0 & 0\\
\end{bmatrix}，$$

所以 $\begin{bmatrix}
x_1\\
x_2\\
x_3\\
x_4\\
\end{bmatrix}=\begin{bmatrix}
1\\
2\\
0\\
0\\
\end{bmatrix}+c_0\begin{bmatrix}
1\\
-2\\
1\\
0\\
\end{bmatrix}+c_1\begin{bmatrix}
2\\
-3\\
0\\
1\\
\end{bmatrix}，$

因為 $\begin{bmatrix}
1\\
-2\\
1\\
0\\\end{bmatrix},\begin{bmatrix}
2\\
-3\\
0\\
1\\
\end{bmatrix}$ 跟 $\Row(A)$ 垂直，所以特解投影到 $\Row(A)$ 上的長度為最短向量 $\bw$。
令
$$B = \begin{bmatrix}
1 & 0 \\
0 & 1 \\
-1 & 2 \\
-2 & 3
\end{bmatrix}
$$
使得 $B$ 的行集合為 $\Row(A)$ 的基底。
故 $\bw=B(B\trans B)^{-1}B\trans\bb，\bb=\begin{bmatrix}
1\\
2\\
0\\
0\\
\end{bmatrix}。$

得到 $\bw=\begin{bmatrix}
\frac{3}{2}\\
1\\
\frac{1}{2}\\
0\\\end{bmatrix}$，$\|\bw\|=\frac{\sqrt{7}}{\sqrt{2}}$。

##### Exercise 5

一個_內積_ $\langle \cdot, \cdot \rangle$ 要符合以下的條件：
1. $\langle{\bf x}_1 + {\bf x}_2,{\bf y}\rangle = \langle{\bf x}_1,{\bf y}\rangle + \langle{\bf x}_2,{\bf y}\rangle$.
2. $\langle k{\bf x},{\bf y}\rangle = k\langle{\bf x},{\bf y}\rangle$.
3. $\langle {\bf x},{\bf y}\rangle = \langle {\bf y},{\bf x}\rangle$.
4. $\langle {\bf x}, {\bf x} \rangle \geq 0$, and the equality holds if and only if ${\bf x} = {\bf 0}$.

驗證以下定義的各種雙變數函數都可視為內積。

##### Exercise 5(a)

考慮 $V = \mathcal{M}_{2,3}$。
定義兩矩陣 $A$ 和 $B$ 的內積為
$$\langle A, B \rangle = \operatorname{tr}(B^\top A).$$

:::warning
這系列幾乎只要把定義抄一次就好。
但是要想清楚每一步是不是對的。
（後面幾題用類似的方式修正。）

1. 可驗證
$$\begin{aligned}
\langle A_1 + A_2,B\rangle &= \tr(B\trans(A_1 + A_2)) = \tr(B\trans A_1 + B\trans A_2) \\
&= \tr(B\trans A_1) + \tr(B\trans A_2) \\
&= \langle A_1, B\rangle + \langle A_2, B\rangle.
\end{aligned}
$$
2. 可驗證
$$\begin{aligned}
\langle kA, B\rangle &= \tr(B\trans(kA)) \\
&= k\tr(B\trans A) = k\langle A, B\rangle.
\end{aligned}
$$
3. 可驗證
$$\begin{aligned}
\langle A, B\rangle &= \tr(B\trans A) \\
&= \tr((B\trans A)\trans) = \tr(A\trans B) =
\langle B, A\rangle.
\end{aligned}
$$
4. 若
$$A = \begin{bmatrix} a_1 & a_2 & a_3 \\ a_4 & a_5 & a_6 \end{bmatrix}.$$
則 $\langle A, A\rangle = a_1^1 + \cdots + a_6^2 \geq 0$
且此式只有在 $A = O$ 時為 $0$。

因此此函數可視為 $V$ 中的內積。
:::

ANS:

1. 可驗證
$$\begin{aligned}
\langle A_1 + A_2,B\rangle &= \tr(B\trans(A_1 + A_2)) = \tr(B\trans A_1 + B\trans A_2) \\
&= \tr(B\trans A_1) + \tr(B\trans A_2) \\
&= \langle A_1, B\rangle + \langle A_2, B\rangle.
\end{aligned}
$$
2. 可驗證
$$\begin{aligned}
\langle kA, B\rangle &= \tr(B\trans(kA)) \\
&= k\tr(B\trans A) = k\langle A, B\rangle.
\end{aligned}
$$
3. 可驗證
$$\begin{aligned}
\langle A, B\rangle &= \tr(B\trans A) \\
&= \tr((B\trans A)\trans) = \tr(A\trans B) =
\langle B, A\rangle.
\end{aligned}
$$
4. 若
$$A = \begin{bmatrix} a_1 & a_2 & a_3 \\ a_4 & a_5 & a_6 \end{bmatrix}.
$$
則 $\langle A, A\rangle = a_1^1 + \cdots + a_6^2 \geq 0$
且此式只有在 $A = O$ 時為 $0$。

因此此函數可視為 $V$ 中的內積。

##### Exercise 5(b)

考慮 $V = \mathcal{P}_3$。
定義兩多項式
$$\begin{aligned}
p_1 &= a_0 + a_1x + a_2x^2 + a_3x^3 \\
p_2 &= b_0 + b_1x + b_2x^2 + b_3x^3 \\
\end{aligned}
$$
的內積為
$$\langle p_1, p_2 \rangle = a_0b_0 + a_1b_1 + a_2b_2 + a_3b_3.
$$

ANS:\
Let $$ p_3 = c_0 + c_1x + c_2x^2 + c_3x^3.
$$

1. $$\langle p_1+p_3, p_2 \rangle = (a_0+c_0)b_0 + (a_1+c_1)b_1 + (a_2+c_2)b_2 + (a_3+c_3)b_3\\
=a_0b_0+c_0b_0+a_1b_1+c_1b_1+a_2b_2+c_2b_2+a_3b_3+c_3b_3\\
=(a_0b_0 + a_1b_1 + a_2b_2 + a_3b_3)+(c_0b_0 + c_1b_1 + c_2b_2 + c_3b_3)=\langle p_1+p_3, p_2 \rangle.
$$
2. $$\langle kp_1, p_2 \rangle = ka_0b_0 + ka_1b_1 + ka_2b_2 + ka_3b_3\\
=k(a_0b_0 + a_1b_1 + a_2b_2 + a_3b_3)=k\langle p_1, p_2 \rangle.
$$
3. $$\langle p_1, p_2 \rangle = a_0b_0 + a_1b_1 + a_2b_2 + a_3b_3\\
=b_0a_0 + b_1a_1 + b_2a_2 + b_3a_3=\langle p_2, p_1 \rangle.
$$
4. $$\langle p_1, p_1 \rangle = a_0^2 + a_1^2 + a_2^2 + a_3^2\geq 0.
$$

且此式只有在 $p_1=0$ 的時候才為 $0$。
因此此函數可視$V$中的內積。

##### Exercise 5(c)

考慮 $V = \mathcal{P}_3$。
定義兩多項式
$$\begin{aligned}
p_1 &= a_0 + a_1x + a_2x^2 + a_3x^3 \\
p_2 &= b_0 + b_1x + b_2x^2 + b_3x^3 \\
\end{aligned}
$$
的內積為
$$\langle p_1, p_2 \rangle = p_1(1)p_2(1) + p_1(2)p_2(2) + p_1(3)p_2(3) + p_1(4)p_2(4).
$$

ANS:
Let $$p_3= c_0 + c_1x + c_2x^2 + c_3x^3.
$$
1. 可驗證
$$\begin{aligned}
\langle p_1+p_3,p_2\rangle &=
(p_1(1)+p_3(1))p_2(1)+ \cdots + (p_1(4)+p_3(4))p_2(4)\\
&= p_1(1)p_2(1)+p_3(1)p_2(1)+ \cdots +p_1(4)p_2(4)+p_3(4)p_2(4).
\end{aligned}
$$
重新整理後得到
$$\begin{aligned}
\langle p_1+p_3,p_2\rangle &=
(p_1(1)p_2(1) + \cdots + p_1(4)p_2(4))+
(p_3(1)p_2(1) + \cdots + p_3(4)p_2(4))\\
&=\langle p_1,p_2\rangle+\langle p_3,p_2\rangle.
\end{aligned}
$$
2. 可驗證
$$\langle kp_1,p_2\rangle=kp_1(1)p_2(1) + kp_1(2)p_2(2) + kp_1(3)p_2(3) + kp_1(4)p_2(4).$$\
把k提出來得到$$\langle kp_1,p_2\rangle=k（p_1(1)p_2(1) + p_1(2)p_2(2) + p_1(3)p_2(3) + p_1(4)p_2(4)）=k\langle p_1, p_2 \rangle.$$
3. 可驗證
$$\langle p_1, p_2 \rangle = p_1(1)p_2(1) + p_1(2)p_2(2) + p_1(3)p_2(3) + p_1(4)p_2(4)\\
=p_2(1)p_1(1) + p_2(2)p_1(2) + p_2(3)p_1(3) + p_2(4)p_1(4)=\langle p_2, p_1 \rangle .
$$
4. $$\langle p_1, p_1 \rangle = p_1^2(1) + p_1^2(2) + p_1^2(3) + p_1^2(4)\geq 0.
$$

且此式只有在 $p_1=0$ 的時候才為 $0$。
因此此函數可視為 $V$ 中的內積。

##### Exercise 5(c)

考慮 $V$ 為 $[0,1]$ 區間上的所有連續函數。
定義兩函數 $f$ 和 $g$ 的內積為
$$\langle f, g \rangle = \int_0^1 fg\, dx.
$$

ANS:
Let $h(x)$ be a function in $[0,1]$.

1. 可驗證
$$\begin{aligned}
\langle f+g,h\rangle &= \int_0^1 (f(x)+g(x))h(x)\, dx=\int_0^1 (f(x)h(x)+g(x)h(x))\, dx \\
&= \int_0^1 f(x)h(x)\, dx+\int_0^1 g(x)h(x)\, dx \\
&= \langle f,h\rangle+\langle g,h\rangle.
\end{aligned}
$$
2. 可驗證
$$\langle kf,g\rangle=\int_0^1 kf(x)g(x)\, dx=k\int_0^1 f(x)g(x)\, dx=k\langle f,g\rangle.
$$
3. 可驗證
$$\langle f,g\rangle=\int_0^1 f(x)g(x)\, dx=\int_0^1 g(x)f(x)=\langle g,f\rangle\, .$$
4. 由於
$$\langle f,f\rangle=\int_0^1 f(x)^2\, dx\geq 0.
$$

且此式只有在 $f(x)=0$ 的時候才為 $0$。
因此此函數可視為 $V$ 中的內積。

:::info
目前分數 6.5
:::