# 解的個數

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
$$\{ {\bf x}\in\mathbb{R}^n : A{\bf x} = {\bf b} \} = {\bf p} + \operatorname{ker}(A).
$$

Since $\operatorname{ker}(A)$ is a subspace in $\mathbb{R}^n$, it either contains
1. only one vector, which is ${\bf 0}$, or
2. infintely many vectors.

In the first case, we say the homogeneous equation only has the **trivial solution**.
In the second case, we say the homogeneous equation has **nontrivial solutions**.

On the other hand, we know
1. a particular solution exists if ${\bf b}\in\operatorname{Col}(A)$, and
2. a particular solution does not exists if ${\bf b}\notin\operatorname{Col}(A)$.

In the first case, we say the equation $A{\bf x} = {\bf b}$ is **consistent**.
In the second case, we say the equation $A{\bf x} = {\bf b}$ is **inconsistent**.

Therefore, a system of linear equations $A{\bf x} = {\bf b}$ either have $0$, $1$, or infinitely solutions.
This table summarizes the number of solutions of $A{\bf x} = {\bf b}$.

hom \ par | consistent | inconsistent
--------- | ---------- | ------------
trivial | one | none
nontrivial | infinite | none

Note that whether its homogeneous equation only has the trivial solution or not depends only on $A$.

Let $r$ be the number of pivots in the reduced echelon form of $A$.
Here we summarize some facts that we have learnt:
1. If $r = m$, then $\operatorname{Col}(A) = \mathbb{R}^m$.
2. If $r = n$, then $\operatorname{ker}(A) = \{{\bf 0}\}$.

Since $r\leq\min\{m,n\}$, the two conditions happen together only when $r = m = n$.

Let $A$ be an $n\times n$ matrix and $r$ its number of pivots in its reduced echelon form.
We say $A$ is **singular** if $r < n$ and is **nonsingular** if $r = n$.
The following are equivalent:
1. $A$ is nonsingular.
2. $\operatorname{Col}(A) = \mathbb{R}^n$.
3. $\operatorname{ker}(A) = \{{\bf 0}\}$.
4. For any ${\bf b}\in\mathbb{R}^n$, the equation $A{\bf x} = {\bf b}$ has a unique solution.

## Side stories
- determinant and nonsingularity for small matrices

## 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}$ 解的個數
（零個、一個、或是無限多個）。

:::warning

- [x] $、$ --> 、（頓號不用進數學模式）
- [x] $x_1=0、x_2=3、x_3=-3、x_4=3、x_5=4$ --> $x_1=0$、$x_2=3$、$x_3=-3$、$x_4=3$、$x_5=4$ （一樣是頓號的問題）
:::

答:

題目給定 `seed=0`、

$\left[\begin{array}{c|c}A&{\bf b}\end{array}\right]=\left[\begin{array}{ccccc|c}
1 & -4 & -3 & 4 & -3 & -3 \\
-3 & 13 & 11 & -16 & 6 & -18 \\
2 & -8 & -5 & 7 & -8 & -20 \\
-4 & 17 & 12 & -17 & 8 & -4 \\
-19 & 82 & 60 & -86 & 33 & -60
\end{array}\right]$、

$\left[\begin{array}{c|c}R&{\bf r}\end{array}\right]=\left[\begin{array}{ccccc|c}
1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 3 \\
0 & 0 & 1 & 0 & 0 & -3 \\
0 & 0 & 0 & 1 & 0 & 3 \\
0 & 0 & 0 & 0 & 1 & 4
\end{array}\right]$ 。

令 ${ \bx}=(x_1 , x_2 , x_3 , x_4 , x_5)$，考慮方程式 $R{\bf x} = {\bf r}$ 。

此方程式可看成
$$\begin{cases}1x_1+0x_2+0x_3+0x_4+0x_5=0 ,\\ 0x_1+1x_2+0x_3+0x_4+0x_5=3 ,\\ 0x_1+0x_2+1x_3+0x_4+0x_5=-3 ,\\ 0x_1+0x_2+0x_3+1x_4+0x_5=3 ,\\ 0x_1+0x_2+0x_3+0x_4+1x_5=4 ,\end{cases}
$$

得 $x_1=0$、$x_2=3$、$x_3=-3$、$x_4=3$、$x_5=4$ 僅此一解，

故 $A{\bf x} = {\bf b}$ 只有一組解。

### code
set_random_seed(0)
print_ans = False
has_sol = choice([True, False])
tri_ker = choice([True, False])
r = 5 if tri_ker else 4
while True:
    Ab, R, pivots = random_good_matrix(5,6,r, return_answer=True)
    if (5 not in pivots) == has_sol:
        break
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]
    num_sol = 0 if not has_sol else (1 if len(free) == 0 else oo)
    print("Number of solutions?", num_sol)

## Exercises

##### Exercise 2

令 $A$ 為一 $m\times n$ 矩陣而 ${\bf b}\in\mathbb{R}^m$。

##### Exercise 2(a)

說明若 $m < n$ 則 $A{\bf x} = {\bf b}$
要嘛無解、要嘛無限多解。

:::warning

- [x] 中英數之間空格 [S01](https://sagelabtw.github.io/LA-Tea/)
- [x] $b$ --> $\bb$ 向量用粗體
- [x] 兩個"若"可以合在一起：當 $b\in\Col(A)$ 時，因為 $r\leq m < n$，所以會有無限多解。這裡 $r$ 是 $A$ 的軸數。
:::

證明：

已知 $A$ 為一 $m\times n$ 矩陣而 $\bb\in\mathbb{R}^m$。
當 ${\bf b}\notin\Col(A)$ 時，則無解。
當 ${\bf b}\in\Col(A)$ 時，因為 $r\leq m < n$ ，所以會有無限多解。這裡 $r$ 是 $A$ 的軸數。

##### Exercise 2(b)

說明若 $m > n$ 則 $A{\bf x} = {\bf b}$
要嘛無解、要嘛有唯一解。
**[Jephian: 這題怪怪的，先忽略這題。]**

##### Exercise 3

Singular 這個字是意思是「奇異的」。
執行以下的程式碼。
這段程式請電腦隨機產生一個矩陣 $A$
其每一項都是從 $-5$ 到 $5$ 中機率相同地取出一個整數。
試試看出現 singular 的機會高不高。

（因為大部份的矩陣都不奇異的﹐所以一開始才把這類 $r < n$ 的矩陣稱為奇異的。
然而在數學上「非奇異的」是一個重要的性質﹐
課本和學術論文上一直會用到「The matrix is nonsingular.」這種句子﹐
甚至時常使用「The matrix is not nonsingular.」。
這種雙重否定的敘述讓人混亂。
然而未來我們會學到「非奇異的」和「可逆的」這兩個述敘等價﹐
這樣就可以避免雙重否定的困擾。）

:::success
Nice!
:::

答:

經過 $5000$ 次的執行程式，所得出現 singular 次數為 $6$。

### code
l = [choice(list(range(-5,6))) for _ in range(25)]
A = matrix(5, l)
show(A)
print("Is A singular?", A.is_singular())

##### Exercise 4

對於小的矩陣﹐證明以下敘述等價：
1. $\det(A) \neq 0$.
2. $A$ is nonsingular.

##### Exercise 4(a)

若 $A$ 是 $2\times 2$ 矩陣﹐證明以下敘述等價：
1. $\det(A) \neq 0$.
2. $A$ is nonsingular.

<!--
:::warning

- [ ] We know that $A$ is nonsingular, $n = 2$ in this case, if pivot $r = n$. $\rightarrow$ Let $n = 2$. We know that $A$ is nonsingular if the number of pivots is $r = n$.
- [ ] Suppose $\det(A) \neq 0$, $\rightarrow$ Suppose $\det(A) \neq 0$.
- [ ] We have $\rightarrow$ We may let
- [ ] Where $\rightarrow$ where
- [ ] , and $a\neq 0$ <-- 拿掉這句
- [ ] 在 By Gaussian 前面加上： If $a = 0$, then $\det(A) = -bc \neq 0$ implies $b$ and $c$ are nonzero. Thus,
$$A = \begin{bmatrix}
0 & b \\
c & d
\end{bmatrix} \rightarrow \begin{bmatrix}
c & d \\
0 & b
\end{bmatrix} \rightarrow \begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix}
$$
leads to the conclusion that $A$ has $2$ pivots, so $A$ is nonsingular.
- [ ] By Gaussian Elimination $\rightarrow$ On the other hand, if $a \neq 0$, then by the Gaussian Elimination
- [ ] And we have $\rightarrow$ Since
- [ ] Which means $\rightarrow$ we have
- [ ] the pivot $r = 2 = n$ $\rightarrow$ $A$ has $r = 2$ pivots, which means $A$ is nonsingular.
- [ ] $\therefore \det(A) \neq 0 \equiv A$ is nonsingular. 不要用邏輯符號
- [ ] 沒有證明 $A$ is nonsingular 則 $\det(A)\neq 0$
:::
-->

Solution:

回顧一下，$A$ 是 nonsingular 等價於 $A$ 有 $n = 2$ 個軸。
我們考慮兩個狀況：$a \neq 0$ 及 $a = 0$。

**Case 1:** $a \neq 0$.
在這個情況下我們可以執行列運算得到：
$$
A = \begin{bmatrix}
a & b \\
c & d
\end{bmatrix} \rightarrow \begin{bmatrix}
1 & \frac{b}{a} \\
c & d
\end{bmatrix} \rightarrow \begin{bmatrix}
1 & \frac{b}{a} \\
0 & d-\frac{bc}{a}
\end{bmatrix}
$$

若 $\det(A) \neq 0$，則
$$d-\frac{bc}{a} = \frac{ad-bc}{a} \neq 0,
$$
因此 $A$ 有 $2 = n$ 個軸。

反之，若 $A$ 是 nonsingular，則
$$d-\frac{bc}{a} = \frac{ad-bc}{a} \neq 0,
$$
這表示
$$ad-bc = \det(A) \neq 0.
$$

**Case 2:** $a = 0$.
在這個情況下我們可以執行列運算得到：
$$
A = \begin{bmatrix}
0 & b \\
c & d
\end{bmatrix} \rightarrow \begin{bmatrix}
c & d \\
0 & b
\end{bmatrix}
$$

若 $\det(A) \neq 0$，則 $ad-bc=-bc\neq 0$，所以 $b\neq 0$ 且 $c\neq 0$，
因此 $A$ 仍有 $2 = n$ 個軸。

反之，若 $A$ 是 nonsingular，則 $b\neq 0$ 且 $c\neq 0$，
故 $-bc = ad-bc\neq 0$。
這表示 $ad-bc= \det(A) \neq 0$。

<!--
We know that $A$ is nonsingular, $n = 2$ in this case, if pivot $r = n$.

Suppose $\det(A) \neq 0$, We have
$A = \begin{bmatrix}
a & b \\
c & d
\end{bmatrix},$
Where $a,b,c,d\in\mathbb{R}$, and $a\neq 0$.

By Gaussian Elimination
$$A = \begin{bmatrix}
a & b \\
c & d
\end{bmatrix} \rightarrow \begin{bmatrix}
1 & \frac{b}{a} \\
c & d
\end{bmatrix} \rightarrow \begin{bmatrix}
1 & \frac{b}{a} \\
0 & d-\frac{bc}{a}
\end{bmatrix},
$$
where $$d-\frac{bc}{a} = \frac{ad-bc}{a}.
$$
And we have
$$\det(A) = ad-bc \neq 0 .
$$
Which means
$$\frac{ad-bc}{a} \neq 0
$$
, so the pivot $r = 2 = n$.

$\therefore \det(A) \neq 0 \equiv A$ is nonsingular.
-->

##### Exercise 4(b)

若 $A$ 是 $3\times 3$ 矩陣﹐證明以下敘述等價：
1. $\det(A) \neq 0$.
2. $A$ is nonsingular.

以下論證實際上證明了 $n\times n$ 的版本：
**[由廖緯程同學提供]**
**1.證明一個矩陣的某列有公因子，則它的行列式等於公因子可以提出來：**
令

$$
M_2 = \begin{bmatrix}
a & b\\
c & d
\end{bmatrix}，
{M_2}' = \begin{bmatrix}
a & b\\
kc & kd
\end{bmatrix}，
$$

計算可以得 $k \times \det(M_2) = k(ad - bc) = kad - kbc = \det({M_2}')$。

令

$$
M_n =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n}\\
\vdots & & \vdots\\
a_{n,1} & \ldots & a_{n,n}
\end{bmatrix}，
{M_n}' =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n}\\
\vdots & & \vdots\\
ka_{i,1} & \ldots & ka_{i,n}\\
\vdots & & \vdots\\
a_{n,1} & \ldots & a_{n,n}
\end{bmatrix}.
$$

假設 $k \times \det(M_n) = \det({M_n}')$，

令

$$
M_{n+1} =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n+1}\\
\vdots & & \vdots\\
a_{n+1,1} & \ldots & a_{n+1,n+1}
\end{bmatrix}，
{M_{n+1}}' =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n+1}\\
\vdots & & \vdots\\
ka_{i,1} & \ldots & ka_{i,n+1}\\
\vdots & & \vdots\\
a_{n+1,1} & \ldots & a_{n+1,n+1}
\end{bmatrix}.
$$

令 $M_{(i,j)}$ 為 $M$ 矩陣去掉第 $i$ 列 與第 $j$ 行。
對最後一列展開得，

$$
\det(M_{n+1}) = \sum_{i=1}^{n+1}(-1)^{i+1} a_{n+1,i} \det({M_{n+1}}_{(n+1,i)})，\\
\begin{aligned}
\det({M_{n+1}}') &= \sum_{i=1}^{n+1} (-1)^{i+1} a_{n+1,i} \det({M_{n+1}'}_{(n+1,i)})\\
&= k \sum_{i=1}^{n+1} (-1)^{i+1} a_{n+1,i} \det({M_{n+1}}_{(n+1,i)})\\
&= k \times \det(M_{n+1})，
\end{aligned}
$$

根據數學歸納法，得證。

**2.證明一個矩陣如果有兩列一樣，則它的行列式為** $0$ **：**
令

$$
M_2 = \begin{bmatrix}
a & b\\
a & b\\
\end{bmatrix}，
$$

則 $\det(M_2) = ab - ab = 0$，
令

$$
M_n =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n}\\
\vdots & & \vdots\\
a_{n,1} & \ldots & a_{n,n}
\end{bmatrix}，M_{n+1} =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n+1}\\
\vdots & & \vdots\\
a_{n+1,1} & \ldots & a_{n+1,n+1}
\end{bmatrix}，
$$

並且 $M_n,M_{n+1}$ 的第 $i$ 列與第 $j$ 列相等，$i \neq j$，假設 $\det(M_n) = 0$，
把最後一列展開計算得，

$$
\begin{aligned}
\det(M_{n+1}) &= \sum_{i=1}^{n+1}(-1)^{i+1} a_{n+1,i} \det({M_{n+1}}_{(n+1,i)})\\
&= \sum_{i=1}^{n+1}(-1)^{i+1} a_{n+1,i} \times 0\\
&= 0，
\end{aligned}
$$

根據數學歸納法，得證。

**3.證明一個矩陣的某列的所有元素為兩數之和，則它的行列式可以拆分為兩個相加的行列式：**
令

$$
M_2 = \begin{bmatrix}
a+k_1 & b + k_2\\
c & d
\end{bmatrix},
{M_2}' = \begin{bmatrix}
a & b\\
c & d
\end{bmatrix},
K_2 = \begin{bmatrix}
k_1 & k_2\\
c & d
\end{bmatrix}.
$$

計算 $M_2$ 的行列式，$\det(M_2) = (a+k_1)d - c(b+k_2) = ad + k_1d - bc - k_2c$，
計算 ${M_2}'$ 的行列式，$\det({M_2}') = ad - bc$，
計算 $K_2$ 的行列式，$\det(K_2) = k_1d - k_2c$，
可以觀察到 $\det(M_2) = \det({M_2}') + \det(K_2)$。
令

$$
M_n =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n}\\
\vdots & & \vdots\\
a_{i,1}+k_1 & \ldots & a_{i,n}+k_n\\
\vdots & & \vdots\\
a_{n,1} & \ldots & a_{n,n}
\end{bmatrix}，
{M_n}' =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n}\\
\vdots & & \vdots\\
a_{n,1} & \ldots & a_{n,n}
\end{bmatrix}，
K_n =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n+1}\\
\vdots & & \vdots\\
k_1 & \ldots & k_{n+1}\\
\vdots & & \vdots\\
a_{n,1} & \ldots & a_{n,n}
\end{bmatrix}，
$$

其中 $K_n$ 的第 $i$ 列為 $(k_1, \ldots ,k_n)$，假設 $\det(M_n) = \det({M_n}') + \det(K_n)$，
令

$$
M_{n+1} =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n+1}\\
\vdots & & \vdots\\
a_{i,1}+k_1 & \ldots & a_{i,n+1}+k_{n+1}\\
\vdots & & \vdots\\
a_{n+1,1} & \ldots & a_{n+1,n+1}
\end{bmatrix}，
{M_{n+1}}' =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n+1}\\
\vdots & & \vdots\\
a_{n+1,1} & \ldots & a_{n+1,n+1}
\end{bmatrix}，
K_{n+1} =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n+1}\\
\vdots & & \vdots\\
k_1 & \ldots & k_{n+1}\\
\vdots & & \vdots\\
a_{n+1,1} & \ldots & a_{n+1,n+1}
\end{bmatrix}，
$$

其中 $K_{n+1}$ 的第 $i$ 列為 $(k_1,\ldots,k_{n+1})$，對最後一列展開計算 $M_{n+1}$ 的行列式，

$$
\begin{aligned}
\det(M_{n+1}) &= \sum_{i=1}^{n+1} (-1)^{i+1} a_{n+1,i} \times \det({M_{n+1}}_{(n+1,i)})\\
&= \sum_{i=1}^{n+1} (-1)^{i+1} a_{n+1,i} \times (\det({{M_{n+1}}'}_{(n+1,i)}) + \det({K_{n+1}}_{(n+1,i)}))\\
&= \sum_{i=1}^{n+1} (-1)^{i+1} a_{n+1,i} \times \det({{M_{n+1}}'}_{(n+1,i)}) + \sum_{i=1}^{n+1} (-1)^{i+1} a_{n+1,i} \times \det({K_{n+1}}_{(n+1,i)})\\
&= \det({M_{n+1}}') + \det(K_{n+1})
\end{aligned}
$$

根據數學歸納法，得證。

**4.證明一個矩陣經過列運算** $\rho_i : + k\rho_j$ **後，行列式值不變：**
令

$$
M =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n}\\
\vdots & & \vdots\\
a_{n,1} & \ldots & a_{n,n}
\end{bmatrix}，
$$

做任意列運算 $\rho_i : + k\rho_j$ 後

$$
M' =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n}\\
\vdots & & \vdots\\
a_{i,1} + ka_{j,1} & \ldots & a_{i,n} + ka_{j,n}\\
\vdots & & \vdots\\
a_{n,1} & \ldots & a_{n,n}
\end{bmatrix}
$$

利用**1,2,3**計算 $M'$ 的行列式，

$$
\begin{aligned}
\det(M') &= \det(M) + \det(\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n}\\
\vdots & & \vdots\\
ka_{j,1} & \ldots & ka_{j,n}\\
\vdots & & \vdots\\
a_{n,1} & \ldots & a_{n,n}
\end{bmatrix})\\
&= \det(M) + k\det(\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n}\\
\vdots & & \vdots\\
a_{j,1} & \ldots & a_{j,n}\\
\vdots & & \vdots\\
a_{n,1} & \ldots & a_{n,n}
\end{bmatrix})\\
&= \det(M) + k \times 0\\
&= \det(M)
\end{aligned}
$$

得證。

**5.**
根據**4**，計算任意矩陣的行列式時，可以用列運算 $\rho_i : + k\rho_j$ 算出它的階梯形式，使得對角線下方的元素都為 $0$。
接下來不斷對第一行展開就可以得到行列式。
令 $A$ 是任意方陣，$R$ 是它的階梯形式，

$$
A =
\begin{bmatrix}
a_{1,1} & \ldots & a_{1,n}\\
\vdots & & \vdots\\
a_{n,1} & \ldots & a_{n,n}
\end{bmatrix}，R =
\begin{bmatrix}
a_{1,1} & \ldots & r_{1,n}\\
\vdots & \ddots & r_{2, n}\\
0 &&\vdots\\
\vdots && \vdots\\
0 & \ldots & r_{n,n}
\end{bmatrix}
$$

$\det(A)$ 等於 $R$ 對角線上的元素相乘，所以如果 $R$ 的對角線上沒有 $0$，$\det(A) \neq 0$，
$R$ 的對角線上沒有 $0$，代表它的軸數目與行數一樣，即 $A$ 是非奇異的。

所以 $A$ 是非奇異的等價於 $\det(A) \neq 0$。

:::success
目前分數： 5.5/5
:::