# 垂直幾何

Orthogonal geometry

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

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

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 $\inp{\cdot}{\cdot}$ an inner product on $V$.
Recall that $\bu$ and $\bv$ are **orthogonal** if $\inp{\bu}{\bv} = 0$.
Let $S = \{\bu_1, \ldots, \bu_k\}$ be a collection of vectors.
Then $S$ is **orthogonal** if $\inp{\bu_i}{\bu_j} = 0$ for any pair of distinct $i,j$.
Moreover, if $S$ is orthogonal and $\|\bu\|^2 = \inp{\bu_i}{\bu_i} = 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 = \{\bu_1, \ldots, \bu_k\}$ is orthogonal.
Then

$$
\begin{array}{cc}
& (a_1\bu_1 + \cdots a_k\bu_k) \\
\cdot & (b_1\bu_1 + \cdots b_k\bu_k) \\
= & (a_1b_1\|\bu_1\|^2 + \cdots a_kb_k\|\bu_k\|^2) \\
\end{array}
$$

holds for any two linear combination of $S$.
In particular, when $S$ is orthonormal, the inner product is

$$
(a_1\bu_1 + \cdots a_k\bu_k) \cdot
(b_1\bu_1 + \cdots b_k\bu_k) =
a_1b_1 + \cdots + a_kb_k,
$$

and the length is

$$
\|a_1\bu_1 + \cdots a_k\bu_k\| = a_1^2 + \cdots + a_k^2.
$$

Let $\bb$ be a vector and $S = \{\bu_1, \ldots, \bu_k\}$ is orthogonal.
Suppose $\bb_1, \ldots, \bb_k$ are the projection of $\bb$ onto each vectors $\bu_1, \ldots, \bu_k$, respectively, and $\bb_S$ is the projection of $\bb$ onto $\vspan(S)$.
Then $\bb_S = \bb_1 + \cdots + \bb_k$.

Let $\bb$ be a vector and $V$ a subspace.
Suppose $\bb$ can be written as $\bb = \bw + \bh$ such that $\bw\in V$ and $\bh\in V^\perp$.
Then $\bv = \bw$ minimize the length $\|\bb - \bv\|$ among all vector $\bv \in V$.

## Side stories
- linear regression
- inner product space

## Experiments

##### Exercise 1

執行以下程式碼。
令 $S = \{\bu_1,\ldots,\bu_3\}$ 為 $Q$ 中的各行向量。
己知 $\bb\in \vspan(S)$。

<!-- eng start -->
Run the code below. Let $S = \{\bu_1,\ldots,\bu_3\}$ be the columns of $Q$. Suppose $\bb\in \vspan(S)$.
<!-- eng end -->

### 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())

##### Exercise 1(a)

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

<!-- eng start -->
Is $S$ orthogonal? Is it orthonormal?
<!-- eng end -->

##### Exercise 1(b)

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

<!-- eng start -->
Find an orthonormal set $S'$ such that $\vspan(S') = \vspan(S)$.
<!-- eng end -->

##### Exercise 1(c)

將 $\bb$ 寫成 $S$ 的線性組合。

<!-- eng start -->
Write $\bb$ as a linear combination of $S$.
<!-- eng end -->

##### Exercise 1(d)

利用 $\bb$ 的線性組合算出 $\bb$ 的長度。

<!-- eng start -->
Use the linear combination of $\bb$ to calculate the length of $\bb$.
<!-- eng end -->

## Exercises

##### Exercise 2

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

<!-- eng start -->
The following problems study the relations between orthogonality and linear independence.
<!-- eng end -->

##### Exercise 2(a)

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

<!-- eng start -->
Show that if $S$ is orthonormal, then $S$ is linearly independent.
<!-- eng end -->

##### Exercise 2(b)

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

<!-- eng start -->
Find an example of an orthogonal set $S$ such that $S$ is not linearly independent.
<!-- eng end -->

##### Exercise 3

令

$$
A = \begin{bmatrix}
1 & 1 \\
1 & 2 \\
1 & 3 \\
1 & 4 \\
\end{bmatrix}
$$

而 $\bb = (2.4, 3.1, 3.4, 4.1)$。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
1 & 1 \\
1 & 2 \\
1 & 3 \\
1 & 4 \\
\end{bmatrix}
$$

and $\bb = (2.4, 3.1, 3.4, 4.1)$.
<!-- eng end -->

##### Exercise 3(a)

求 $\Col(A)$ 中和 $\bb$ 最接近的向量 $\bw$、
並將它寫成 $A$ 的行向量的線性組合。

<!-- eng start -->
Find the vector in $\Col(A)$ that is the closest to $\bw$ and write it as a linear combination of columns of $A$.
<!-- eng end -->

##### Exercise 3(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) = \bb$。
求解 $c_0$ 和 $c_1$ 使得 $\sum_{i=1}^4 (c_0 + c_1x_i - y_i)^2$ 最小。

<!-- eng start -->
Let $(x_1,x_2,x_3,x_4) = (1,2,3,4)$ be the second column of $A$ and $(y_1,y_2,y_3,y_4) = (2.4, 3.1, 3.4, 4.1) = \bb$. Find $c_0$ and $c_1$ such that $\sum_{i=1}^4 (c_0 + c_1x_i - y_i)^2$ is minimized.
<!-- eng end -->

##### Exercise 4

令

$$
A = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
0 & 1 & 2 & 3 \\
\end{bmatrix}
$$

且 $\bb = (3,3,2)$。
求解集合 $U = \{ \bx\in\mathbb{R}^4 : A\bx = \bb \}$ 中長度最短的向量。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 \\
0 & 1 & 2 & 3 \\
\end{bmatrix}
$$

and $\bb = (3,3,2)$. Find the vector in the solution set $U = \{ \bx\in\mathbb{R}^4 : A\bx = \bb \}$ with the minimum length.
<!-- eng end -->

##### Exercise 5

一個_內積_ $\inp{\cdot}{\cdot}$ 要符合以下的條件：

1. $\inp{\bx_1 + \bx_2}{\by} = \inp{\bx_1}{\by} + \inp{\bx_2}{\by}$.
2. $\inp{k\bx}{\by} = k\inp{\bx}{\by}$.
3. $\inp{\bx}{\by} = \inp{\by}{\bx}$.
4. $\inp{\bx}{\bx} \geq 0$, and the equality holds if and only if $\bx = \bzero$.

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

<!-- eng start -->
An _inner product_ $\inp{\cdot}{\cdot}$ is a bivariate function with the following properties：

1. $\inp{\bx_1 + \bx_2}{\by} = \inp{\bx_1}{\by} + \inp{\bx_2}{\by}$.
2. $\inp{k\bx}{\by} = k\inp{\bx}{\by}$.
3. $\inp{\bx}{\by} = \inp{\by}{\bx}$.
4. $\inp{\bx}{\bx} \geq 0$, and the equality holds if and only if $\bx = \bzero$.

Verify each of the following bivariate functions can be viewed as an inner product.
<!-- eng end -->

##### Exercise 5(a)

考慮 $V = \mathcal{M}_{2,3}$。
定義兩矩陣 $A$ 和 $B$ 的內積為

$$
\inp{A}{B} = \tr(B\trans A).
$$

<!-- eng start -->
Consider $V = \mathcal{M}_{2,3}$. Define the inner product of two matrices $A$ and $B$ as

$$
\inp{A}{B} = \tr(B\trans A).
$$
<!-- eng end -->

##### 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}
$$

的內積為

$$
\inp{p_1}{p_2} = a_0b_0 + a_1b_1 + a_2b_2 + a_3b_3.
$$

<!-- eng start -->
Consider $V = \mathcal{P}_{3}$. Define the inner product of two polynomials

$$
\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}
$$

as

$$
\inp{p_1}{p_2} = a_0b_0 + a_1b_1 + a_2b_2 + a_3b_3.
$$
<!-- eng end -->

##### Exercise 5(c)

考慮 $V = \mathcal{P}_3$。
定義兩多項式 $p_1$ 和 $p_2$ 的內積為

$$
\inp{p_1}{p_2} = p_1(1)p_2(1) + p_1(2)p_2(2) + p_1(3)p_2(3) + p_1(4)p_2(4).
$$

<!-- eng start -->
Consider $V = \mathcal{P}_{3}$. Define the inner product of two polynomials $p_1$ and $p_2$ as

$$
\inp{p_1}{p_2} = p_1(1)p_2(1) + p_1(2)p_2(2) + p_1(3)p_2(3) + p_1(4)p_2(4).
$$
<!-- eng end -->

##### Exercise 5(d)

考慮 $V$ 為 $[0,1]$ 區間上的所有連續函數。
定義兩函數 $f$ 和 $g$ 的內積為

$$
\inp{f}{g} = \int_0^1 fg\, dx.
$$

<!-- eng start -->
Consider $V$ as the vector space of all continuous functions on the interval $[0,1]$. Define the inner product of two functions $f$ and $g$ as

$$
\inp{f}{g} = \int_0^1 fg\, dx.
$$
<!-- eng end -->