解的個數

This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.

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}\).

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

答:

題目給定 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}\)
要嘛無解、要嘛無限多解。

證明：

已知 \(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.」。
這種雙重否定的敘述讓人混亂。
然而未來我們會學到「非奇異的」和「可逆的」這兩個述敘等價﹐
這樣就可以避免雙重否定的困擾。）

答:

經過 \(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.

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\)。

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\)。