# 零解

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, betak_solver

## Main idea

Let $A$ be an $m\times n$ matrix and ${\bf b}$ a vector in $\mathbb{R}^n$.
Recall that the homogeneous solutions are the solutions to $A{\bf x} = {\bf 0}$, which is irrelavent to ${\bf b}$.
That is, the homogeneous solutions form the set $\operatorname{ker}(A)$.

Let $R$ be the reduced echelon form of $A$.
Suppose $x_{i_1},\ldots, x_{i_k}$ are the free variables.
For each $s = 1,\ldots, k$, we obtained ${\bf h}_s$ as follows:
1. Set $x_{i_s} = 1$ and the remaining free variables as $0$.
2. Under this settting, solve $A{\bf x} = {\bf 0}$ and call the solution ${\bf h}_s$.

Then $\operatorname{ker}(A) = \operatorname{span}(\{{\bf h}_1,\ldots,{\bf h}_k\})$.

Since the set of solutions to $A{\bf x} = {\bf b}$ is ${\bf p} + \operatorname{ker}(A)$ for some particular solution ${\bf p}$,
$$\{ {\bf x}\in\mathbb{R}^n : A{\bf x} = {\bf b} \} =
\{ {\bf p} + c_1{\bf h}_1 + \cdots + c_k{\bf h}_k : c_1,\ldots,c_k\in\mathbb{R} \}.
$$

Suppose ${\bf b}\in\operatorname{ker}(A)$.
The following are equivalent:
1. $A{\bf x} = {\bf b}$ has a unique solution.
2. The reduced echelon form of $A$ has no free variable.
3. The reduced echelon form of $A$ has $n$ pivots.
4. $\operatorname{ker}(A) = \{{\bf 0}\}$.

Since $A{\bf x} = {\bf 0}$ always has a trivial solution $A{\bf 0} = {\bf 0}$, , the followin are equivalent:
1. ${\bf 0}$ is the only solution to $A{\bf x} = {\bf 0}$.
2. The reduced echelon form of $A$ has no free variable.
3. The reduced echelon form of $A$ has $n$ pivots.
4. $\operatorname{ker}(A) = \{{\bf 0}\}$.

## Side stories
- unique representation
- polynomial passing through given points

## Experiments

##### Exercise 1

執行下方程式碼。
矩陣 $R$ 是 $A$ 的最簡階梯形式矩陣。
利用 Main idea 中說明的方法找出 $\{{\bf h}_1,\ldots,{\bf h}_k\}$。

### code
set_random_seed(0)
print_ans = False
A, R, pivots = random_good_matrix(3,5,2, return_answer=True)

print("A =")
show(A)
print("R =")
show(R)

if print_ans:
    free = [i for i in range(5) if i not in pivots]
    print("Free variables are xi with i =", free)
    for i in range(len(free)):
        hi = betak_solver(R, free, i+1)
        print("h%s ="%(i+1), vector(hi))

:::warning

- [x] $x_3,x_4,x_5$ 的值有寫錯
- [x] ${\bf h_1}$ --> $\bh_1$ 數字不要粗體
:::

$Ans:$

題目給定 `seed=0`、

$$A =\begin{bmatrix}
1 & -3 & 18 & 5 & -14 \\
3 & -8 & 49 & 15 & -39 \\
-8 & 20 & -120 & -40 & 1000
\end{bmatrix}
$$
以及
$$R = \begin{bmatrix}
1 & 0 & 3 & 5 & -5 \\
0 & 1 & -5 & 0 & 3 \\
0 & 0 & 0 & 0 & 0
\end{bmatrix}.
$$

$R$ 為 $A$ 的最簡階梯形式矩陣。
由 $R$ 可知 $x_1 , x_2$ 為領導變數 , $x_3 , x_4 , x_5$ 則為自由變數。
令 $x_3=1 , x_4=0 , x_5=0$ 時可得到 $$\bh_1 = (-3,5,1,0,0)。 $$

令 $x_4=1 , x_3=0 , x_5=0$ 時可得到 $$\bh_2 = (-5,0,0,1,0)。 $$
令 $x_5=1 , x_3=0 , x_4=0$ 時可得到 $$\bh_3= (5,-3,0,0,1)。$$

## Exercises

##### Exercise 2

令 $A$ 為一 $m\times n$ 矩陣而 $R$ 為其最簡階梯形式矩陣。
考慮方程式 $A{\bf x} = {\bf 0}$。
若 $R$ 有 $r$ 個軸﹐則可以算出 $\operatorname{ker}(A)$ 的生成集 $S = \{{\bf h}_1,\ldots,{\bf h}_{n-r}\}$。
令 $H$ 為一 $n\times (n-r)$ 矩陣其和行向量依序為 $S$ 中的各向量。

可以執行以下程式碼看例子。

### code
set_random_seed(0)
A, R, pivots = random_good_matrix(5,7,4,return_answer=True)

free = [i for i in range(7) if i not in pivots]
H = zero_matrix(QQ, 7, 3)
for i in range(3):
    H[:,i] = betak_solver(R, free, i+1)
    
print("A =")
show(A)
print("R =")
show(R)
print("H =")
show(H)

藉由 `seed = 0` 得到
$$A = \begin{bmatrix} 1 & -4 & -3 & 32 & -4 & -29 & 4 \\
-3 & 13 & 11 &-107 & 18 & 98 & -16 \\
6 & -27 & -23 & 222 & -39 & -203 & 35\\4 & -20
& -18& 166 & -34& -154 & 31\\-10 & 39 & 30 & -315 & 40 & 287 & -37\end{bmatrix},
$$
$$R = \begin{bmatrix} 1 & 0 & 0 & 3 & 5 & -5 & 0 \\
0 & 1 & 0 &-5 & 0 & 3 & 0 \\
0 & 0 & 1 & -3 & 3 & 4 & 0\\0 & 0
& 0& 0 & 0& 0 & 1\\0 & 0& 0 & 0 & 0 & 0 & 0\end{bmatrix},
$$
$$H = \begin{bmatrix} -3 & -5 & 5 \\
5 & 0 & -3 \\
3& -3 & -4 \\1 & 0
& 0\\ 0 & 1& 0 \\0& 0& 1 \\ 0 & 0 & 0 \end{bmatrix}.
$$

##### Exercise 2(a)

把 $R$ 中的前 $r$ 列取出來
（也就是那些非零的列向量）、
再從中把對應到領導變數的那些行向量拿出來﹐
組成一個 $r\times r$ 矩陣。
這個矩陣長什麼樣子？說明為什麼？

$Ans:$

首先，把 $R$ 中的前 $r$ 列取出來，得到
$$\begin{bmatrix} 1 & 0 & 0 & 3 & 5 & -5 & 0 \\
0 & 1 & 0 &-5 & 0 & 3 & 0 \\
0 & 0 & 1 & -3 & 3 & 4 & 0\\0 & 0
& 0& 0 & 0& 0 & 1\end{bmatrix}.
$$
其次，從中把對應到領導變數的那些行向量列舉出來
$${\bf n}_1 = \begin{bmatrix} 1\\0\\0\\0\end{bmatrix} , {\bf n}_2 = \begin{bmatrix} 0\\1\\0\\0\end{bmatrix} ,
{\bf n}_3 = \begin{bmatrix} 0\\0\\1\\0\end{bmatrix} , {\bf n}_7 = \begin{bmatrix} 0\\0\\0\\1\end{bmatrix} ,
$$
再將這些行向列組成一個 $r\times r$ 矩陣，得到
$$\begin{bmatrix} 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0\\0 & 0
& 0& 1\end{bmatrix}.
$$
因為 $R$ 為最簡階梯形式矩陣，所以滿足以下條件：

1. 所有非零列在所有全零列上面。
2. 非零列最左的非零元素(即軸元)，嚴格地比上一列的軸元更靠右。
3. 非零列的軸元等於 $1$ ，且是其所在行的唯一非零元素。

根據以上性質，取非零列的軸元所在的行向量組成的 $r\times r$ 矩陣，就是單位矩陣。

##### Exercise 2(b)

把 $H$ 對應到自由變數的那些列向量拿出來﹐
組成一個 $(n-r)\times (n-r)$ 矩陣。
這個矩陣長什麼樣子？說明為什麼？

:::warning
可能題目沒講清楚，因為 $H$ 的每一個列都對應到原本的 $x_1$ ~ $x_7$，所以這裡說的 "自由變數" 指的是 $R$ 上的自由變數 $x_4,x_5,x_6$，所以把 $H$ 中對應到 $x_4,x_5,x_6$ 的列拿出來，看看會得到什麼。（你們目前的答案是拿 $R$ 的行）
:::

$Ans:$

首先，把 $H$ 對應到自由變數的那些列向量拿出來:
因為領導變數位於 $x_1$,$x_2$,$x_3$,$x_7$，由此可知自由變數所在位置為 $x_4$~$x_6$ 可得：
而 $H$ 的第 $i$ 列都會對應到 $x_i$， 題目要的就是 $H$ 內的第 $4$~$6$ 列 （對應到 $x_4$~$x_6$ ）
$${\bf h}_4 = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} , {\bf h}_5 = \begin{bmatrix} 0 & 1 & 0 \end{bmatrix} , {\bf h}_6 = \begin{bmatrix} 0 & 0 & 1\end{bmatrix}
$$
組成一個 $(n-r)\times (n-r)$ 的矩陣。
所以這個矩陣就是：

$${\bf I}_3 = \begin{bmatrix} 1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1\\\end{bmatrix}
$$
而這個矩陣也就是單位矩陣，其中每列的第 $k$ 行元素就是表示第 $k$ 個自由變數設為 $1$ ，其他為 $0$。
故若有 $n$ 個自由變數，代表就會做 $n$ 次上述的動作，使得該矩陣就是個 $n\times n$ 的單位矩陣。

##### Exercise 2(c)

把 $R$ 中的前 $r$ 列取出來
（也就是那些非零的列向量）、
再從中把對應到自由變數的那些行向量拿出來﹐
組成一個 $r\times (n-r)$ 矩陣、稱作 $R'$。

另一方面，把 $H$ 中對應到領導變數的列向量拿出來﹐
組成一個 $r\times (n-r)$ 矩陣、稱作 $H'$。

這兩個矩陣 $R'$ 和 $H'$ 有什麼關係？說明為什麼？

:::warning
Nice!

- [x] ${\bf O_{r,n-r}}$ --> $O_{r,n-r}$ 向量才要粗體
- [x] 數學式後半型句點
:::

$Ans:$

$$R'=\begin{bmatrix}
3 & 5 & -5\\
-5 & 0 & 3\\
-3 & 3 & 4\\
0 & 0 & 0
\end{bmatrix},
H'=\begin{bmatrix}
-3 & -5 & 5\\
5 & 0 & -3\\
3 & -3 & -4\\
0 & 0 & 0
\end{bmatrix},R'+H'=O_{r,n-r}.
$$

令 $R'$ 的第 $k$ 個列向量為 $(c_1,\ldots,c_{n-r})$ ，可以與所有自由變數組成的向量內積後加上第 $k$ 個領導變數會等於 $0$
即
$$x_{l,k}+c_1\cdot x_{f,1}+\cdots+c_{n-r}\cdot x_{f,n-r}=0
$$
其中 $x_{l,k}$ 為第 $k$ 個領導變數、而 $x_{f,i}$ 為第 $i$ 個自由變數。

令 $H'$ 的第 $k$ 個列向量為 $(x_{k,1},\dots x_{k,i},\dots x_{k,n-r})$，
其中 $x_{k,i}$ 即第 $i$ 個自由變數等於 $1$，其他自由變數等於 $0$ 時的第 $k$ 個領導變數，
結合 $R'$ 得 $x_{k,i}+c_i\cdot 1=0$
因此 $H'$ 第 $k$ 個列向量可以看成 $(-c_1,\ldots,-c_{n-r})$
得

$$R'+H'=O_{r,n-r}.
$$

##### Exercise 3

執行以下程式碼。
已知 ${\bf b}\in\operatorname{Col}(A)$。
驗證以下關於唯一解的問題。

### code
set_random_seed(0)
A = ran2dom_good_matrix(5,3,3)
b = A * vector([1,1,1])
print("A =")
show(A)
print("b =", b)

藉由 `seed = 0` 得到
$$A = \begin{bmatrix} 1 & 3 & 5 \\
-5& -14 & -30 \\
-15 & -42 & -89\\28 & 79
& 162\\ -13 & -37 & -73 \end{bmatrix}.
$$
$$
b= ( 9,-49,-146,269,-123 )
$$

##### Exercise 3(a)

說明 $A{\bf x} = {\bf b}$ 有唯一解。

$Ans:$

$$\left[\begin{array}{ccc|c}
1 & 3 & 5 & 9\\
-5 & -14 & -30 & -49\\
-15 & -42 & -89 & -146\\
28 & 79 & 162 & 269\\
-13 & -37 & -73 & -123
\end{array}\right]$$

$$\xrightarrow[-28\rho_1+\rho_4，13\rho_1+\rho_5]{5\rho_1+\rho_2，15\rho_1+\rho_3}\left[\begin{array}{ccc|c}
1 & 3 & 5 & 9\\
0 & 1 & -5 & -4\\
0 & 3 & -14 & -11\\
0 & -5 & 22 & 17\\
0 & 2 & -8 & -6
\end{array}\right]$$

$$\xrightarrow[5\rho_2+\rho_4，-2\rho_2+\rho_5]{-3\rho_2+\rho_1，-3\rho_2+\rho_3}\left[\begin{array}{ccc|c}
1 & 0 & 20 & 21\\
0 & 1 & -5 & -4\\
0 & 0 & 1 & 1\\
0 & 0 & -3 & -3\\
0 & 0 & 2 & 2
\end{array}\right]$$

$$\xrightarrow[3\rho_3+\rho_4，-2\rho_3+\rho_5]{-20\rho_3+\rho_1，5\rho_3+\rho_2}\left[\begin{array}{ccc|c}
1 & 0 & 0 & 1\\
0 & 1 & 0 & 1\\
0 & 0 & 1 & 1\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0
\end{array}\right]$$
由最簡階梯形式矩陣得知，
$x_1=x_2=x_3=1$，有唯一解。

##### Exercise 3(b)

說明 $A{\bf x} = {\bf 0}$ 有唯一解。

$Ans:$
$$\left[\begin{array}{ccc|c}
1 & 3 & 5 & 0\\
-5 & -14 & -30 & 0\\
-15 & -42 & -89 & 0\\
28 & 79 & 162 & 0\\
-13 & -37 & -73 & 0
\end{array}\right]$$

$$\xrightarrow[-28\rho_1+\rho_4，13\rho_1+\rho_5]{5\rho_1+\rho_2，15\rho_1+\rho_3}\left[\begin{array}{ccc|c}
1 & 3 & 5 & 0\\
0 & 1 & -5 & 0\\
0 & 3 & -14 & 0\\
0 & -5 & 22 & 0\\
0 & 2 & -8 & 0
\end{array}\right]$$

$$\xrightarrow[5\rho_2+\rho_4，-2\rho_2+\rho_5]{-3\rho_2+\rho_1，-3\rho_2+\rho_3}\left[\begin{array}{ccc|c}
1 & 0 & 20 & 0\\
0 & 1 & -5 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & -3 & 0\\
0 & 0 & 2 & 0
\end{array}\right]$$

$$\xrightarrow[3\rho_3+\rho_4，-2\rho_3+\rho_5]{-20\rho_3+\rho_1，5\rho_3+\rho_2}\left[\begin{array}{ccc|c}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0
\end{array}\right]=R$$

$x_1=x_2=x_3=0$ ，有解。
$A$ 是 $5\times 3$ 矩陣，且最簡階梯形式矩陣後的 $R$ 有 $3$ 個軸，沒有自由變數，所以 $\ker(A)=\{{\bf 0}\}$ ， $A{\bf x} = {\bf 0}$ 有唯一解。

##### Exercise 3(c)

若 $f(x) = c_0 + c_1 x + c_2 x^2$。
若 $f(1) = b_1$、
$f(2) = b_2$、
$f(3) = b_3$。
說明不論 $b_1$、$b_2$、$b_3$ 給的是多少﹐$c_0$、$c_1$、$c_2$ 都有唯一解。

$Ans:$

$$\begin{cases}
c_0+c_1+c_2=b_1\\
c_0+2c_1+4c_2=b_2\\
c_0+3c_1+9c_2=b_3
\end{cases}$$

可以看成

$$\left[\begin{array}{ccc|c}
1 & 1 & 1 & b_1\\
1 & 2 & 4 & b_2\\
1 & 3 & 9 & b_3
\end{array}\right]$$
的解。

$$\xrightarrow[-\rho_1+\rho_3]{-\rho_1+\rho_2}\left[\begin{array}{ccc|c}
1 & 1 & 1 & b_1\\
0 & 1 & 3 & -b_1+b_2\\
0 & 2 & 8 & -b_1+b_3
\end{array}\right]$$

$$\xrightarrow[-2\rho_2+\rho_3]{-\rho_2+\rho_1}\left[\begin{array}{ccc|c}
1 & 0 & -2 & 2b_1-b_2\\
0 & 1 & 3 & -b_1+b_2\\
0 & 0 & 2 & -3b_1-2b_2+b_3
\end{array}\right]$$

$$\xrightarrow[]{\rho_3\times\frac{1}{2}}\left[\begin{array}{ccc|c}
1 & 0 & -2 & 2b_1-b_2\\
0 & 1 & 3 & -b_1+b_2\\
0 & 0 & 2 & -\frac{3}{2}b_1-b_2+\frac{1}{2}b_3
\end{array}\right]
$$

$$\xrightarrow[-3\rho_3+\rho_2]{2\rho_3+\rho_1}\left[\begin{array}{ccc|c}
1 & 0 & 0 & -b_1-3b_2+b_3\\
0 & 1 & 0 & \frac{7}{2}b_1+4b_2-\frac{3}{2}b_3\\
0 & 0 & 1 & -\frac{3}{2}b_1-b_2+\frac{1}{2}b_3
\end{array}\right]
$$

$$
c_0=-b_1-3b_2+b_3
$$

$$
c_1=\frac{7}{2}b_1+4b_2-\frac{3}{2}b_3
$$

$$
c_2=-\frac{3}{2}b_1-b_2+\frac{1}{2}b_3
$$
所以不論 $b_1$、$b_2$、$b_3$ 給的是多少﹐$c_0$、$c_1$、$c_2$ 都有唯一解。

##### Exercise 3(d)

若 $f(x) = c_0 + c_1 x + c_2 x^2$。
若 $x_1$、$x_2$、$x_3$ 為三相異實數且
$f(x_1) = b_1$、
$f(x_2) = b_2$、
$f(x_3) = b_3$。
說明不論 $b_1$、$b_2$、$b_3$ 給的是多少﹐$c_0$、$c_1$、$c_2$ 都有唯一解。

:::warning

- [x] 因為 $x_1\neq x_2\neq x_3$ --> 因為 $x_1,x_2,x_3$ 彼此相異（原本的式子 $x_1\neq x_2\neq x_3$ 不是一個好的數學式，看起來也許 $x_1$ 可能和 $x_3$ 相等）
- [x] 列運算可以把第二列同乘 $\frac{1}{-x_1+x_2}$ 之類的會比較好算；參考 109 4(c)
:::

$Ans:$
$$\begin{cases}
c_0+c_1x_1+c_2{x_1}^2=b_1\\
c_0+c_1x_2+c_2{x_2}^2=b_2\\
c_0+c_1x_3+c_2{x_3}^2=b_3
\end{cases}$$

可以看成

$$\left[\begin{array}{ccc|c}
1 & x_1 & {x_1}^2 & b_1\\
1 & x_2 & {x_2}^2 & b_2\\
1 & x_3 & {x_3}^2 & b_3
\end{array}\right]
$$
的解。

因為 $x_1,x_2,x_3$ 彼此相異，所以可以有以下運算:

$$\left[\begin{array}{ccc|c}
1 & x_1 & {x_1}^2 & b_1\\
1 & x_2 & {x_2}^2 & b_2\\
1 & x_3 & {x_3}^2 & b_3
\end{array}\right]$$

$$\xrightarrow[-\rho_1+\rho_3]{-\rho_1+\rho_2}\begin{bmatrix}
1 & x_1 & {x_1}^2\\
0 & -x_1+x_2 & -{x_1}^2+{x_2}^2 &\\
0 & -x_1+x_3 & -{x_1}^2+{x_3}^2
\end{bmatrix}$$

$$\xrightarrow[\rho_3\times \frac{1}{-x_1+x_3}]{\rho_2\times \frac{1}{-x_1+x_2}}\begin{bmatrix}
1 & x_1 & {x_1}^2\\
0 & 1 & x_1+x_2\\
0 & 1 & x_1+x_3
\end{bmatrix}$$

$$\xrightarrow[-\rho_2+\rho_3]{\rho_2\times (-x_1)+\rho_1}\begin{bmatrix}
1 & 0 & -x_1x_2\\
0 & 1 & x_1+x_2\\
0 & 0 & -x_2+x_3
\end{bmatrix}$$

$$\xrightarrow[]{\rho_3\times \frac{1}{-x_2+x_3}}\begin{bmatrix}
1 & 0 & -x_1x_2\\
0 & 1 & x_1+x_2\\
0 & 0 & 1
\end{bmatrix}$$

$$\xrightarrow[\rho_3\times (-x_1-x_2)]{\rho_3\times(x_1x_2)+\rho_1}\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{bmatrix}$$

由運算結果得到最簡階梯形式矩陣，則可知道只有唯一解。

:::info
答案清晰乾淨：）
除了 2(b) 以外數學都沒問題
只有格式要改

目前分數 6/5
:::