# 特解

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 $A$ be an $m\times n$ matrix and ${\bf b}$ a vector in $\mathbb{R}^n$.
Recall that the augmented matrix of $A{\bf x} = {\bf b}$ is the $m\times (n+1)$ matrix $\left[\begin{array}{c|c}A&{\bf b}\end{array}\right]$.
We may perform row operations on $\left[\begin{array}{c|c}A&{\bf b}\end{array}\right]$ to get its reduced echelon form $\left[\begin{array}{c|c}R&{\bf r}\end{array}\right]$.
The equation $R{\bf x} = {\bf r}$ has a solution if and only if the $i$-th entry of ${\bf r}$ is zero whenever the $i$-th row of $R$ is zero.

Let ${\bf x} = (x_1, \ldots, x_n)$.
The variables $x_i$ correponding to a pivot $i$ of $R$ are called **leading variables**.
The other variables are called **free variables**.
Suppose the $i$-th entry of ${\bf r}$ is zero whenever the $i$-th row of $R$ is zero.
One may set each free variable as an arbitrary number (e.g., all zeros).
Then there is a solution ${\bf x}$ satisfying the setting.

Therefore, the following are equivalent:
1. $A{\bf x} = {\bf b}$ has a solution.
2. The reduced echelon form of $\left[\begin{array}{c|c}A&{\bf b}\end{array}\right]$ does not contain a row where the last entry is nonzero but the other entries are zero.
3. ${\bf b} \in \operatorname{Col}(A)$.

On the other hand, if $R$ has no zero row, then $R{\bf x} = {\bf r}$ has a solution regardless the choice of ${\bf r}$.
Therefore, the following are equivalent:
1. $A{\bf x} = {\bf b}$ has a solution for any ${\bf b}\in\mathbb{R}^m$.
2. The reduced echelon form of $A$ contains no zero row.
3. The reduced echelon form of $A$ has $m$ pivots.
4. $\operatorname{Col}(A) = \mathbb{R}^m$.

## Side stories
- constraint
- polynomial passing through given points

## Experiments

##### Exercise 1
執行下方程式碼。
矩陣 $\left[\begin{array}{c|c}R&{\bf r}\end{array}\right]$ 是 $\left[\begin{array}{c|c}A&{\bf b}\end{array}\right]$ 的最簡階梯形式矩陣。
考慮方程組 $A{\bf x} = {\bf b}$ 且 ${\bf x} = (x_1,\ldots,x_5)$。

### code
set_random_seed(0)
print_ans = False
Ab, R, pivots = random_good_matrix(3,6,3, return_answer=True)
A = Ab[:,:5]
b = vector(Ab[:,5])
Ab = A.augment(b, subdivide=True)
Rr = Ab.rref()

print("[ A | b ] =")
show(Ab)
print("[ R | r ] =")
show(Rr)

if print_ans:
    has_sol = False if 5 in pivots else True
    leading = [i+1 for i in pivots if i != 5]
    free = [i for i in range(1,6) if i not in leading]
    print("Has a solution?", has_sol)
    print("Leading variables are xi with i =", leading)
    print("Free variables are xi with i =", free)
    if has_sol:
        x = vector([0]*5)
        for i in range(3):
            x[pivots[i]] = Rr[i,5]
        print("By setting free variables as zeros, x =", x)

##### Exercise 1(a)
在 $x_1,\ldots,x_5$ 中﹐
哪些是領導變數、
哪些是自由變數？

:::warning

- [x] $seed(0)$ --> `set_random_seed(0)`
- [x] 把向量改粗體，如 $b$ --> $\bb$, $r$ --> $\br$
:::

$Ans:$
令 `set_random_seed(0)`，
則 $$ \left[\begin{array}{c|c}
A & \bb
\end{array}\right] =
\left[\begin{array}{ccccc|c}
1 & 4 & 23 & -4 & 7 & -5\\
2 & 9 & 51 & -11 & 23 & -16\\
-4 & -20 & -112 & 29 & -67 & 47
\end{array}\right]$$
經矩陣列運算後，

$$ \left[\begin{array}{c|c}
R & \br
\end{array}\right] =
\left[\begin{array}{ccccc|c}
1 & 0 & 3 & 0 & -5 & -5\\
0 & 1 & 5 & 0 & 0 & 3\\
0 & 0 & 0 & 1 & -3 & 3
\end{array}\right].
$$
故在 $x_1,\ldots,x_5$ 中﹐
領導變數為 $x_1,x_2,x_4$，
自由變數為 $x_3,x_5$。

##### Exercise 1(b)

方程式是否有解？
若有解﹐繼續前往下一題。
若無解﹐忽略以下題目。

$Ans:$
因為 $R$ 沒有一列為零向量，
所以此方程式有解。

##### Exercise 1(c)

將所有自由變數設成 $0$ 求解。

:::warning
- [x] 描述一下怎麼解的，比如說：令自由變數 $x_3 = x_5 = 0$。由 $x_4 - 3x_5 = 3$ 得知 $x_4 = 3$。 ...
:::

$Ans:$
令自由變數 $x_3 = x_5 = 0$。
由 $x_4 - 3x_5 = 3$ 得知 $x_4 = 3$。
由 $x_2 + 5x_3 = 3$ 得知 $x_2 = 3$。
由 $x_1 + 3x_3 - 5x_5= -5$ 得知 $x_1 = -5$。
最後得到 $x_1=-5,x_2=3,x_3=0,x_4=3,x_5=0$ 。

##### Exercise 1(d)

隨意將自由變數設成任意數字求解。

:::warning

- [x] $x_1=0,x_2=-2,x_3=1,x_4=6,x_5=1$ 。 --> 前面加"可以得到"，最後面句點前不用空格
:::

$Ans:$
設自由變數皆為 1,
可以得到 $x_1=0,x_2=-2,x_3=1,x_4=6,x_5=1$。

## Exercises

##### Exercise 2

以下類型的問題通稱為反問題﹐可以加深對數學概念的理解。

##### Exercise 2(a)

找一個 $5\times 3$ 的最簡階梯形式矩陣﹐它的軸落在 $1,3,5$ 的位置。

:::warning

水，簡單明瞭！

- [x] 數學式裡可以加一個半形句點
:::

$Ans:$
令
$$A = \begin{bmatrix}
1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1
\end{bmatrix}.
$$

##### Exercise 2(b)

找一個 $5\times 3$ 的矩陣﹐
它的所有項皆不是零﹐
且它的最簡階梯形式的軸落在 $1,3,5$ 的位置

:::warning
Great!

- [x] 但一樣數學式後要有標點
- [x] 減 --> 簡
:::

$Ans:$
令
$$A = \begin{bmatrix}
1 & 1 & 1 & 1 & 1 \\
1 & 1 & 2 & 2 & 2 \\
1 & 1 & 1 & 1 & 2
\end{bmatrix}.
$$
則經矩陣列運算後，$A$ 之最簡階梯形式 $A'$ 為
$$A' = \begin{bmatrix}
1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 1
\end{bmatrix}.
$$

##### Exercise 3

給定一個矩陣 $A$﹐
依照以下步驟求出 ${\bf b}\in\operatorname{Col}(A)$ 的等價條件。

##### Exercise 3(a)

執行下以程式碼。
令 ${\bf b} = (b_1,b_2,b_3,b_4)$。
令 $A'$ 為 $A{\bf x} = {\bf b}$ 的增廣矩陣。

把 ${\bf b}$ 的各項當作變數處理﹐經過列運把 $A'$ 中的 $A$ 消成階梯形式矩陣。
如果左側有一列零向量﹐則右側對應到的項必須要是零才有解。
利用這個性質給出 ${\bf b}\in\operatorname{Col}(A)$ 的等價條件。

:::warning

- [x] $seed(0)$ --> `set_random_seed(0)` 然後後面加全型句點
- [x] 數學式後的標點
- [x] 排版一下
$$\begin{aligned}
c_1 &= 6b_1 + 5b_2, \\
c_2 &= 5b_1 + b_2, \\
c_3 &= 3b_2 + b_3, \\
c_4 &= - 3b_1 - 3b_2 + b_4,
\end{aligned}
$$

:::

$Ans:$
令 `set_random_seed(0)`。
經過列運把 $A'$ 中的 $A$ 消成階梯形式矩陣，
得到 $$ A'' = \left[\begin{array}{ccc|c}
1 & 0 & 3 & 6b_1 + 5b_2\\
0 & 1 & 5 & 5b_1 + b_2\\
0 & 0 & 0 & 3b_2 + b_3\\
0 & 0 & 0 & - 3b_1 - 3b_2 + b_4
\end{array}\right].
$$
設 $$\begin{aligned}
c_1 &= 6b_1 + 5b_2, \\
c_2 &= 5b_1 + b_2, \\
c_3 &= 3b_2 + b_3, \\
c_4 &= - 3b_1 - 3b_2 + b_4,
\end{aligned}
$$
則有下列兩種情況：

:::warning

- [x] $c_3,c_4 = 0$ --> $c_3 = c_4 = 0$ （只是寫法習慣問題）
- [x] 變數 $x$ 不用粗體
:::

1. 若 $A''$ 有解，則 $c_3 = c_4 = 0$。
$A''$ 可表示為：
$$A'' =\begin{bmatrix}
1 & 0 & 3\\
0 & 1 & 5\\
0 & 0 & 0\\
0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
x_1\\
x_2\\
x_3
\end{bmatrix} =
\begin{bmatrix}
c_1\\
c_2\\
c_3\\
c_4
\end{bmatrix}$$
展開矩陣可得：
$$A'' = \begin{cases}
1x_1 + 0x_2 + 3x_3 = c_1,\\
0x_1 + 1x_2 + 5x_3 = c_2,\\
0x_1 + 0x_2 + 0x_3 = c_3,\\
0x_1 + 0x_2 + 0x_3 = c_4.
\end{cases}$$
令自由變數 $x_3$ = 0
及領導變數 $x_1 = c_1,x_2 = c_2$,
則方程式有解，
等價於 ${\bf b}\in\operatorname{Col}(A)$。

2. 若 $A''$ 無解，則 $c_3 ≠ 0$ 或 $c_4 ≠ 0$。
$A''$ 可表示為：
$$A'' =\begin{bmatrix}
1 & 0 & 3\\
0 & 1 & 5\\
0 & 0 & 0\\
0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
x_1\\
x_2\\
x_3
\end{bmatrix} =
\begin{bmatrix}
c_1\\
c_2\\
c_3\\
c_4
\end{bmatrix}$$
展開矩陣可得：
$$A'' = \begin{cases}
1x_1 + 0x_2 + 3x_3 = c_1,\\
0x_1 + 1x_2 + 5x_3 = c_2,\\
0x_1 + 0x_2 + 0x_3 = c_3,\\
0x_1 + 0x_2 + 0x_3 = c_4.
\end{cases}
$$
由於 $c_3 ≠ 0$ 或 $c_4 ≠ 0$，
故方程式無解，
等價於 ${\bf b}\notin\operatorname{Col}(A)$。

### code
set_random_seed(0)
A = random_good_matrix(4,3,2)
var('b1 b2 b3 b4')
b = vector([b1, b2, b3, b4])

Ab = A.change_ring(SR).augment(b, subdivide=True)
print("A' =")
show(Ab)

### do something here to get the echelon form on the A side
# Ab.swap_rows(...)
# Ab.rescale_row(...)
# Ab.add_multiple_of_row(...)

print("After reduction:")
show(Ab)

##### Exercise 3(b)

每個線性方程式都對應到一些法向量﹐
找到一些向量 $\{{\bf u}_1,\ldots,{\bf u}_k\}$
（以這題的設定 $k = 2$ 就足夠）
使得以下敘述等價：
1. $\langle{\bf u}_i,{\bf b}\rangle = 0$ if $i = 1,\ldots,k$.
2. ${\bf b}\in\operatorname{Col}(A)$.

:::warning
這題可能題意沒有說清楚。因為是題組，這題的意思是說，依照上一題的 $A$ 及 $\bb\in\Col(A)$ 的條件，找到一些 $\bu_1,\ldots,\bu_k$ 使得上述敘述等價。建議的答案大概是：

令 $\bu_1 = (0,3,1,0)$ 及 $\bu_2 = (-3,-3,0,1)$。
由先前的答案我們知道 $\bb\in\Col(A)$ 和
$$\left\{\begin{aligned}
??? & = 0, \\
??? & = 0,
\end{aligned}\right.
$$
等價。
由於 $\inp{\bu_1}{\bb} = ???$ 且 $\inp{\bu_2}{\bb} = ???$，題目所寫的兩敘述等價。

PS 先不用動你們的答案，我之後會把它註解掉。
:::

$Ans:$
令 `set_random_seed(0)`。
經過列運把 $A'$ 中的 $A$ 消成階梯形式矩陣，
得到 $$ A'' = \left[\begin{array}{ccc|c}
1 & 0 & 3 & 6b_1 + 5b_2\\
0 & 1 & 5 & 5b_1 + b_2\\
0 & 0 & 0 & 3b_2 + b_3\\
0 & 0 & 0 & - 3b_1 - 3b_2 + b_4
\end{array}\right].
$$

令 $\bu_1 = (0,3,1,0)$ 及 $\bu_2 = (-3,-3,0,1)$。
由先前的答案我們知道 $\bb\in\Col(A)$ 和
$$\left\{\begin{aligned}
3b_2 + b_3 &= 0, \\
-3b_1 - 3b_2 + b_4 &= 0,
\end{aligned}\right.
$$
等價。
由於 $\inp{\bu_1}{\bb} = 3b_2 + b_3$ 且 $\inp{\bu_2}{\bb} = -3b_1 - 3b_2 + b_4$，題目所寫的兩敘述等價。

<!--
$<i>$ 證：若 1. 成立，則 2. 成立。
若 $\langle{\bf u}_i,{\bf b}\rangle = 0$ if $i = 1,\ldots,k$ 成立，
則 $u_i\in\operatorname{ker}(A\trans) = \operatorname{Row}(A\trans)^\perp$，
所以 $b\in\operatorname{ker}(A\trans)^\perp = \operatorname{Row}(A\trans) = \operatorname{Col}(A)$.

$<ii>$ 證：若 2. 成立，則 1. 成立。
若將 $A$ 化減成階梯形式 $A'$ 後，則會有以下形式 ：
$$ A = \left[\begin{array}{ccc|c}
| & ~ & | & b_1\\
{\bf v}_1 & \cdots & {\bf v}_n & \vdots\\
| & ~ & | & b_n\\
\end{array}\right]$$
$$ A' = \left[\begin{array}{ccc|ccc}
| & ~ & | & u_{11}b_{1} + & \cdots & + u_{n1}b_{n}\\
{\bf v'}_1 & \cdots & {\bf v'}_n & \vdots & & \vdots\\
| & ~ & | & u_{1m}b_{1} + & \cdots & + u_{nm}b_{n}\\
\end{array}\right]$$
對於所有 $u_{ij}$，當 $i = 1,\ldots,n$ 及 $j = 1,\ldots,m$ 時，$u_{ij}\in \mathbb{R}$。
若 ${\bf b}\in\operatorname{Col}(A)$ 成立。
1. 若 $A'$ 中有至少一列為零向量，
則可以找到：
$$\begin{cases}
u_{1k}b_{1} + & \cdots & + u_{nk}b_{n} = 0 ,\\
& \vdots & \\
u_{1m}b_{1} + & \cdots & + u_{nm}b_{n} = 0.
\end{cases}
$$
對於所有 $u_{ij}$，當 $i = 1,\ldots,n$ 及 $j = (1,m]$ 時，$u_{ij}\in \mathbb{R}$。
所以可以找到 $\langle{\bf u}_{ij},{\bf b}\rangle = 0$ 成立。
2. 若 $A'$ 中沒有一列為零向量，
則 $\operatorname{Col}(A)\in \mathbb{R}^m$ ,
所以 $\langle{\bf u}_{ij},{\bf b}\rangle = 0$ 任意成立。

總結上述，得到下述等價：
1. $\langle{\bf u}_i,{\bf b}\rangle = 0$ if $i = 1,\ldots,k$.
2. ${\bf b}\in\operatorname{Col}(A)$.
-->

##### Exercise 4(a)

執行以下程式碼。
說明 $\operatorname{Col}(A) = \mathbb{R}^3$。

### code
set_random_seed(0)
A = random_good_matrix(3,5,3)
print("A =")
show(A)

$Ans:$
$$\begin{bmatrix}
1 & -3 & 3 & 18 & 29 \\
-4 & 13 & -8 & -77 & -109 \\
-11 & 35 & -24 & -208 & -302
\end{bmatrix}⟹ \begin{bmatrix}
1 & -3 & 3 & 18 & 29 \\
0 & 1 & 4 & -5 & 7 \\
0 & 3 & 9 & -10 & 17
\end{bmatrix}⟹ \begin{bmatrix}
1 & -3 & 3 & 18 & 29 \\
0 & 1 & 4 & -5 & 7 \\
0 & 0 & -3 & 5 & -4
\end{bmatrix}$$
因為此矩陣擁有三個軸，所以可得 $\Col(A)=\mathbb{R}^3$

##### Exercise 4(b)

若 $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$ 都有解。

:::warning

- [x] 說明一下第一個矩陣怎麼來的，比如說：我們首先觀察
$$\begin{aligned}
f(1) = ?c_0 + ?c_1 + ?c_2 &= b_1, \\
f(2) = ?c_0 + ?c_1 + ?c_2 &= b_2, \\
f(3) = ?c_0 + ?c_1 + ?c_2 &= b_3, \\
\end{aligned}
$$
而這個方程組等同於
$$\begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix}
\begin{bmatrix} c_0 \\ c_1 \\ c_2 \end{bmatrix}
=
\begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix}.
$$
- [x] 且皆不為零向量 --> 且每列皆不為零向量
- [x] 所以 $c_0,c_1,c_2$ 都有解 --> 所以對任意 $b_1,b_2,b_3$ 來說，$c_0,c_1,c_2$ 都有解
:::

$Ans:$
我們首先觀察
$$\begin{aligned}
f(1) = 1c_0 + 1c_1 + 1c_2 &= b_1, \\
f(2) = 1c_0 + 2c_1 + 4c_2 &= b_2, \\
f(3) = 1c_0 + 3c_1 + 9c_2 &= b_3, \\
\end{aligned}
$$
而這個方程組等同於
$$\begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix}
\begin{bmatrix} c_0 \\ c_1 \\ c_2 \end{bmatrix} =
\begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix}.
$$

執行以下列運算：
$$\begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix}⟹\begin{bmatrix}
1 & 1 & 1 \\
0 & 1 & 3 \\
0 & 2 & 7
\end{bmatrix}⟹\begin{bmatrix}
1 & 1 & 1 \\
0 & 1 & 3 \\
0 & 0 & 1
\end{bmatrix}
$$
因為此矩陣為階梯型矩陣，
且每列皆不為零向量，
所以對任意 $b_1,b_2,b_3$ 來說，$c_0,c_1,c_2$ 都有解

##### Exercise 4(c)

若 $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_2 - x_1$ 和 $x_3 - x_1$ 都不等於零，可以用列運算把它們提出來，再多做一兩步
$$⟹
\begin{bmatrix}
1 & x_1 & x_1^2 \\
0 & 1 & x_2+x_1 \\
0 & 1 & x_3+x_1
\end{bmatrix}
⟹ ???
$$
- [x] 因為第二列和第三列不成比例，<-- 改完上一點後這句就不用了
- [x] 因此列運算後呈階梯型不存在零向量， --> 因此列運算後呈階梯型，且各列不存在零向量，
:::

$Ans:$
跟前一題的方法一樣，對以下矩陣執行列運算：
$$\begin{aligned}
\begin{bmatrix}
1 & x_1 & x_1^2 \\
1 & x_2 & x_2^2 \\
1 & x_3 & x_3^2
\end{bmatrix} &⟹ \begin{bmatrix}
1 & x_1 & x_1^2 \\
0 & x_2-x_1 & x_2^2-x_1^2 \\
0 & x_3-x_1 & x_3^2-x_1^2
\end{bmatrix} \\
&⟹ \begin{bmatrix}
1 & x_1 & x_1^2 \\
0 & x_2-x_1 & (x_2+x_1)(x_2-x_1) \\
0 & x_3-x_1 & (x_3+x_1)(x_3-x_1)
\end{bmatrix} \\
&⟹
\begin{bmatrix}
1 & x_1 & x_1^2 \\
0 & 1 & x_2+x_1 \\
0 & 1 & x_3+x_1
\end{bmatrix} \\
&⟹ \begin{bmatrix}
1 & x_1 & x_1^2 \\
0 & 1 & x_2+x_1 \\
0 & 0 & x_3-x_2
\end{bmatrix} \\
&⟹ \begin{bmatrix}
1 & x_1 & x_1^2 \\
0 & 1 & x_2+x_1 \\
0 & 0 & 1
\end{bmatrix}
\end{aligned}
$$
因此列運算後呈階梯型，且各列不存在零向量，
所以不論 $b_1,b_2,b_3$ 給的是多少，$c_1,c_2,c_3$ 都有解。

:::info
非常完整，數學幾乎沒問題
排版完就很完美了

目前分數：6/5
:::