# 基底

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

## Main idea

Let $V$ be a subspace in $\mathbb{R}^n$ and $S$ a set of vectors.
The set $S$ is a **spanning set** of $V$ if $V = \operatorname{span}(S)$.
The set $S$ is a **basis** of $V$ if
1. $S$ is a spanning set of $V$, and
2. $S$ is independent.

In other words, $S$ is a basis of $V$ if every vector in $V$ can be written as a linear combination of $S$ and the representation is unique.

Let $\mathcal{E}_n = \{ {\bf e}_1, \ldots, {\bf e}_n \}$ be the columns of $I_n$.
Then $\beta$ is a basis of $\mathbb{R}^n$.
We call $\mathcal{E}_n$ as the **standard basis** of $\mathbb{R}^n$.

Let $S$ and $T$ be two sets of vectors in $\mathbb{R}^n$.
If $T\subseteq\operatorname{span}(S)$, then $\operatorname{span}(T)\subseteq\operatorname{span}(S)$.
Suppose the sets $S$ and $T$ are finite.
Let $A_S$ and $A_T$ be the matrices whose columns are vectors in $S$ and in $T$, respectively.
Let $\left[\begin{array}{c|c} R_S & R_T \end{array}\right]$ be the reduced echelon form of $\left[\begin{array}{c|c} A_S & A_T \end{array}\right]$.
Then the following are equivalent:
1. $T\subseteq\operatorname{span}(S)$.
2. A row in $R_T$ is zero whenever the corresponding row in $R_S$ is zero.

Let $A$ be an $m\times n$ matrix.
Then the set of columns of $A$ is a basis of $\operatorname{Col}(A)$ if $\operatorname{ker}(A) = \{{\bf 0}\}$.
In particular, if $m = n$ and $A$ is invertible, then the set of columns of $A$ is a basis of $\mathbb{R}^n$.

## Side stories
- basis of polynomials
- interpolation

## Experiments

##### Exercise 1

執行下方程式碼。
令 $S$ 和 $T$ 為 $A_S$ 和 $A_T$ 的各行向量。
已知 $\left[\begin{array}{c|c} A_S & A_T \end{array}\right]$ 的最簡階梯形式矩陣為 $\left[\begin{array}{c|c} R_S & R_T \end{array}\right]$﹐
而 $\left[\begin{array}{c|c} A_T & A_S \end{array}\right]$ 的最簡階梯形式矩陣為 $\left[\begin{array}{c|c} Q_T & Q_S \end{array}\right]$。

### code
set_random_seed(0)
print_ans = False
m,n,r = 5,4,4
A = random_good_matrix(m,n,r)
ES = random_good_matrix(3,3,3)
ET = random_good_matrix(3,3,3)
SinT = choice([True, False])
TinS = choice([True, False])
if SinT and TinS:
    AS,AT = A[:,:3],A[:,:3]
if SinT and not TinS:
    AS,AT = A[:,[0,1,1]],A[:,:3]
if not SinT and TinS:
    AS,AT = A[:,:3],A[:,[0,1,1]]
if not SinT and not TinS:
    AS,AT = A[:,:3],A[:,1:]
AS = AS * ES
AT = AT * ET

ST = AS.augment(AT, subdivide=True)
RST = ST.rref()
TS = AT.augment(AS, subdivide=True)
QTS = TS.rref()

print("[ A_S | A_T ] =")
show(ST)
print("[ R_S | R_T ] =")
show(RST)
print("[ Q_T | Q_S ] =")
show(QTS)

if print_ans:
    print("span(S) in span(T)?", SinT)
    print("span(T) in span(S)?", TinS)

藉由 `seed = 0`得到

$\left[\begin{array}{c|c} A_S & A_T \end{array}\right] = \left[\begin{array}{ccc|ccc}
42 & -71 & 244 & 49 & 72 & 8 \\
-159 & 270 & 919 & -191 & -279 & -35 \\
610 & -1035 & -3529 & 729 & 1066 & 131 \\
-2590 & 4396 & 14978 & -3102 & -4534 & -562 \\
6356 & -10789 & -36753 & 7617 & 11132 &1383
\end{array}\right]$

$\left[\begin{array}{c|c} R_S & R_T \end{array}\right] = \left[\begin{array}{ccc|ccc}
1 & 0 & 0 & 43 & 67 & 6 \\
0 & 1 & 0 & 11 & 18 & 0 \\
0 & 0 & 1 & 4 & 6 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{array}\right]$

$\left[\begin{array}{c|c} Q_T & Q_S \end{array}\right] = \left[\begin{array}{ccc|ccc}
1 & 0 & 0 & 18 & -31 & -108 \\
0 & 1 & 0 & -11 & 19 & 66 \\
0 & 0 & 1 & -6 & 10 & 37 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{array}\right]$

##### Exercise 1(a)

問 $\operatorname{span}(S)\subseteq\operatorname{span}(T)$？

:::success
漂亮的解法！
:::

$Ans:$

$\left[\begin{array}{c|c} A_T & A_S \end{array}\right]$ 的最簡階梯形式為

$$
\left[\begin{array}{ccc|ccc}
1 & 0 & 0 & 18 & -31 & -108\\
0 & 1 & 0 & -11 & 19 & 66\\
0 & 0 & 1 & -6 & 10 & 37\\
0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0\\
\end{array}\right]，
$$

所以

$$
A_T
\begin{bmatrix}
18 & -31 & -108\\
-11 & 19 & 66\\
-6 & 10 & 37\\
\end{bmatrix}=A_S，
$$

可以看出每個 $S$ 中的向量都在 $\operatorname{Col}(A_T)$ 中，即 $S \subseteq \operatorname{Col}(A_T) = \vspan(T)$。

因為 $S \subseteq \vspan(T)$ 得證 $\vspan(S) \subseteq \vspan(T)$。

##### Exercise 1(b)

問 $\operatorname{span}(T)\subseteq\operatorname{span}(S)$？

$Ans$:

同上題

$$
A_S
\begin{bmatrix}
43 & 67 & 6\\
11 & 18 & 0\\
4 & 6 & 1\\
\end{bmatrix}=A_T，
$$

可以看出每個 $T$ 中的向量都在 $\operatorname{Col}(A_S)$ 中，即 $T \subseteq \operatorname{Col}(A_S) = \vspan(S)$。

因為 $T \subseteq \vspan(S)$ 得證 $\vspan(T) \subseteq \vspan(S)$。

所以其實 $\vspan(S) = \vspan(T)$。

## Exercises

##### Exercise 2(a)

執行以下程式碼。
其中 $R$ 是 $A$ 的最簡階梯形式矩陣。
說明 $A$ 的行向量所成的集合
是 $A$ 的行空間的基底。

### code
set_random_seed(0)
# print_ans = False
m,n,r = 5,3,3
A = random_good_matrix(m,n,r)
print("A =")
show(A)
R = A.rref()
print("R =")
show(R)

:::warning

- [x] 個人喜好：我覺得 RREF 是文字，所以不用進數學模式。
- [x] 行向量所形成的集合 $\beta_c=$ 還有那個矩陣 <-- 可以拿掉，我看不懂在寫什麼
- [x] $A$ 的所有行向量所生成的集合 $\operatorname{span({\bf A}^{（1）},{\bf A}^{（2）},{\bf A}^{（3）}）} = CS(A)$， --> 同時 $\Col(A)$ 為 $A$ 的所有行向量所生成，
:::

$Ans$:
令 `set_random_seed(0)`，
則

$$
A = \begin{bmatrix}
1 & 3 & 5\\
-5 & -14 & -30\\
-15 & -42 & -89\\
28 & 79 & 162\\
-13 & -37 & -73
\end{bmatrix}，
R = \begin{bmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1\\
0 & 0 & 0\\
0 & 0 & 0
\end{bmatrix}，
$$

根據 $A$ 的 RREF，$\ker(A) = \{ {\bf 0} \}$，所以 $A$ 的所有行向量線性獨立。
同時 $\Col(A)$ 為 $A$ 的所有行向量所生成，
故 $A$ 的所有行向量所成集合為行空間的基底。

##### Exercise 2(b)

執行以下程式碼。
其中 $R$ 是 $A$ 的最簡階梯形式矩陣。
說明 $A$ 的行向量所成的集合
是 $\mathbb{R}^4$ 的基底。

### code
set_random_seed(0)
# print_ans = False
m,n,r = 4,4,4
A = random_good_matrix(m,n,r)
print("A =")
show(A)
R = A.rref()
print("R =")
show(R)

:::warning

- [x] 數學式裡不要放全型括號，也不要放任何中文
- [x] 這裡還沒有維度的概念，從 $\dim$ ... 那邊開始改成：

由最簡階梯形式可以發現不存在自由變數，所以 $\ker(A) = \{\bzero\}$ 且 $A$ 的行向量獨立。另一方面，由於 $R$ 有 $4$ 個軸，所以對任何 $\bb\in\mathbb{R}^4$ 來說 $A\bx = \bb$ 都有解，也就是任何 $\bb\in\mathbb{R}^4$ 都落在 $\Col(A)$ 中，因此 $A$ 的行向量集形成 $\mathbb{R}^4$ 的一組基底。
:::

$Ans$:
令 `set_random_seed(0)`，
則

$$
A = \begin{bmatrix}
1 & 3 & 5 & -5\\
-3 & -8 & -20 & 15\\
15 & 41 & 96 & -72\\
43 & 118 & 272 & -208
\end{bmatrix}, R = \begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1
\end{bmatrix}.
$$

由最簡階梯形式可以發現不存在自由變數，所以 $\ker(A) = \{\bzero\}$ 且 $A$ 的行向量獨立。
另一方面，由於 $R$ 有 $4$ 個軸，所以對任何 $\bb\in\mathbb{R}^4$ 來說 $A\bx = \bb$ 都有解，
也就是任何 $\bb\in\mathbb{R}^4$ 都落在 $\Col(A)$ 中，因此 $A$ 的行向量集形成 $\mathbb{R}^4$ 的一組基底。

##### Exercise 2(c)

令

$$\beta = \left\{
\begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix},
\begin{bmatrix} 0 \\ 1 \\ -1 \end{bmatrix}
\right\}$$
且
$$V = \{ {\bf x}\in\mathbb{R}^3 : \langle {\bf 1},{\bf x}\rangle = 0 \}.
$$

其中 ${\bf 1}$ 是 $\mathbb{R}^3$ 中的全 $1$ 向量。
證明 $\beta$ 是 $V$ 的一組基底。

:::success
清楚明瞭~
:::

$Ans$:
由定義知道

$$
\vspan(\beta) = \left\{
\begin{bmatrix}
c_1\\
-c_1 + c_2\\
-c_2
\end{bmatrix}:c_1,c_2 \in \mathbb{R}
\right\}，
$$

對於所有 $\vspan(\beta)$ 中的元素 ${\bf b}$，都有 $\langle {\bf 1} , {\bf b} \rangle = c_1 - c_1 + c_2 - c_2 = 0$，
所以 $\vspan(\beta) \subseteq V$。
而 $V$ 也可以寫成 $V = \{ (x_1,x_2,x_3) \in \mathbb{R}^3 : x_1 + x_2 + x_3 = 0 \}$，對於所有 $V$ 中的元素 $(x_1,x_2,x_3)$，
都可以寫成 $(x_1,-x_1-x_3 ,-(-x_3))$ ，所以 $V \subseteq \vspan(\beta)$。
所以 $V = \vspan(\beta)$。

解 $\left[
\begin{array}{cc|c}
1 & 0 & 0\\
-1 & 1 & 0\\
0 & -1 & 0
\end{array}
\right]$，只有零解，所以 $\beta$ 內所有元素線性獨立，

所以 $\beta$ 是 $V$ 的一組基底。

##### Exercise 3

以下的例子說明了多項式也有類似地基底的性質：
每一個多項式都可以被某些多項式組合出來、
而且「表示法唯一」。

##### Exercise 3(a)

證明每一個二次多項式 $f(x)$ 都可以寫成 $c_0 + c_1(x-1) + c_2(x-1)^2$ 的樣子﹐
而且 $c_0,c_1,c_2$ 的選擇唯一。

:::success
水啦~
:::

$Ans$:
將題目的多項式展開:
$(c_0 - c_1 + c_2) + (c_1x - 2c_2) + c_2x^2$
可發現 $c_2$ 決定了二項式 $x^2$的係數，$c_1$ 決定 $x$ 的係數，$c_3$ 則是決定常數項的係數。
因此只要 $c_1$ 、 $c_2$ 、 $c_3$ 彼此可運算，則可用來表示所有二次多項式。

我們可以把問題看成，$S = \left\{ \begin{bmatrix}
0\\0\\1
\end{bmatrix},\begin{bmatrix}
0\\1\\-1
\end{bmatrix},\begin{bmatrix}
1\\-2\\1
\end{bmatrix}
\right\}$ 是不是 $\mathbb{R}^3$ 的一組基底，

令 $A$ 為一矩陣其行向量為 $S$ 的所有元素。
因為 $\ker(A) = \{ {\bf 0} \}$ 所以 $S$ 中元素為線性獨立且 $S$ 有三個元素，
所以，$S$ 內的所有元素是 $\mathbb{R}^3$ 的一組基底，並且每一個二次多項式 $f(x)$ 都可以寫成 $c_0 + c_1(x-1) + c_2(x-1)^2$。

##### Exercise 3(b)

令

$$\begin{aligned}
f_1(x) &= \frac{(x-2)(x-3)}{(1-2)(1-3)}, \\
f_2(x) &= \frac{(x-1)(x-3)}{(2-1)(2-3)}, \\
f_3(x) &= \frac{(x-1)(x-2)}{(3-1)(3-2)}. \\
\end{aligned}
$$

證明每一個二次多項式 $f(x)$ 都可以寫成 $c_1f_1(x) + c_2f_2(x) + c_3f_3(x)$ 的樣子﹐
而且 $c_1,c_2,c_3$ 的選擇唯一。
$Ans$:
我們可從題目發現
當 $x=1，f_1(x) = 1，f_2(x) = 0，f_3(x) = 0，$
$x=2，f_1(x) = 0，f_2(x) = 1，f_3(x) = 0，$
$x=3，f_1(x) = 0，f_2(x) = 0，f_3(x) = 1，$
因此多項式 $f(x) = c_1f_1(x) + c_2f_2(x) + c_3f_3(x)$
$f(1) = c_1，f(2) = c_2，f(3) = c_3$
當兩二次式有三個相同的解時，兩者必定為同一多項式。
因此指定 $c_1,c_2,c_3$，即可表示所有二次方程式。

##### Exercise 4

執行以下程式碼。
其中 $B$ 為 $A$ 的反矩陣。
令 $S = \{{\bf u}_1,{\bf u}_2,{\bf u}_3\}$ 為 $A$ 的各行向量。
因為 $A$ 可逆﹐所以 $S$ 為 $\mathbb{R}^3$ 的一組基底。
也就是說﹐每一個 $\mathbb{R}^3$ 中的向量都可以用 $S$ 中的向量組合出來﹐而且組合方法唯一。

### code
set_random_seed(0)
A = random_good_matrix(3,3,3)
B = A.inverse()
print("A =")
show(A)
print("B =")
show(B)

令`set_random_seed(0)`得

$A = \begin{bmatrix}
1 & 3 & 5\\
-5 & -14 & -30\\
-15 & -42 & -89
\end{bmatrix}，B = \begin{bmatrix}
-14 & 57 & -20\\
5 & -14 & 5\\
0 & -3 & 1
\end{bmatrix}$。

##### Exercise 4(a)

令 ${\bf e}_1,{\bf e}_2,{\bf e}_3$ 分別為 $I_3$ 的三個行向量。
對每一個 $i = 1,2,3$﹐求出 ${\bf e}_i$ 寫成 $S$ 的線性組合的表示法。

$Ans$:
因為 $B$ 是 $A$ 的反矩陣，所以

$$
\begin{aligned}
AB&=A\begin{bmatrix}
| & | & |\\
{\bf b}_1 & {\bf b}_2 & {\bf b}_3\\
| & | & |\\
\end{bmatrix}\\\\
&=\begin{bmatrix}
| & | & |\\
{\bf e}_1 & {\bf e}_2 & {\bf e}_3\\
| & | & |\\
\end{bmatrix}\\\\
&=I,\\
\end{aligned}
$$

所以 $A {\bf b}_i = {\bf e}_i$，

$$
\begin{cases}
{\bf e}_1 = -14{\bf u}_1 + 5{\bf u}_2,\\
{\bf e}_2 = 57{\bf u}_1 - 14{\bf u}_2 - 3{\bf u}_3,\\
{\bf e}_3 = -20{\bf u}_1 + 5{\bf u}_2 + {\bf u}_3.
\end{cases}
$$

##### Exercise 4(b)

令 ${\bf b} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$。
求出 ${\bf b}$ 寫成 $S$ 的線性組合的表示法。

:::success
Good.
我原本想的答案是 $B\bone = (23,-4,-2)$，不過意思一樣。
:::

$Ans$:

$$
\begin{aligned}
{\bf b}
&= {\bf e}_1 + {\bf e}_2 + {\bf e}_3\\
&= 23{\bf u}_1 - 4{\bf u}_2 - 2{\bf u}_3。
\end{aligned}
$$

:::info
很多答案想法都很好！
只有一些要改的

目前分數 6.5/5
:::