# 解的個數

Number of solutions

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

from lingeo import random_good_matrix

## Main idea

Let $A$ be an $m\times n$ matrix and $\bb$ a vector in $\mathbb{R}^n$.
Recall that
$$\{ \bx\in\mathbb{R}^n : A\bx = \bb \} = \bp + \ker(A).$$

Since $\ker(A)$ is a subspace in $\mathbb{R}^n$, it either contains
1. only one vector, which is $\bzero$, 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 $\bb\in\Col(A)$, and
2. a particular solution does not exists if $\bb\notin\Col(A)$.

In the first case, we say the equation $A\bx = \bb$ is **consistent**.
In the second case, we say the equation $A\bx = \bb$ is **inconsistent**.

Therefore, a system of linear equations $A\bx = \bb$ either have $0$, $1$, or infinitely solutions.
This table summarizes the number of solutions of $A\bx = \bb$.

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 $\Col(A) = \mathbb{R}^m$.
2. If $r = n$, then $\ker(A) = \{\bzero\}$.

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. $\Col(A) = \mathbb{R}^n$.
3. $\ker(A) = \{\bzero\}$.
4. For any $\bb\in\mathbb{R}^n$, the equation $A\bx = \bb$ has a unique solution.

## Side stories
- determinant and nonsingularity for small matrices

## Experiments

##### Exercise 1

執行下方程式碼。
矩陣 $\left[\begin{array}{c|c}R&\br\end{array}\right]$ 是 $\left[\begin{array}{c|c}A&\bb\end{array}\right]$ 的最簡階梯形式矩陣。
判斷方程式 $A\bx = \bb$ 解的個數
（零個、一個、或是無限多個）。

<!-- eng start -->
Run the code below. Let $\left[\begin{array}{c|c}R&\br\end{array}\right]$ be the reduced echelon form of $\left[\begin{array}{c|c}A&\bb\end{array}\right]$. Determine the number of solutions to $A\bx = \bb$. (None, one solution, or infinitely many solutions.)
<!-- eng end -->

### 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$ 矩陣而 $\bb\in\mathbb{R}^m$。
說明若 $m < n$ 則 $A\bx = \bb$
要嘛無解、要嘛無限多解。

<!-- eng start -->
Let $A$ be an $m\times n$ matrix and $\bb\in\mathbb{R}^m$. Show that if $m < n$, then $A\bx = \bb$ has either no solution or infinitely many solutions.
<!-- eng end -->

##### Exercise 3

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

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

<!-- eng start -->
The term "singular" indicates that it is a special case. Run the code below. The code generates a random matrix $A$, where each entry is a random integer between $-5$ and $5$ with evenly distributed probabilty. Try a few times and describe how likely you can get a singular matrix.

Note: Since most of matrices are not singular, so the matrices with rank $r < n$ are named singular. However, the term "nonsingular" is an important concept in mathematics, and it is quite common to see some sentences like "The matrix is nonsingular." Even worse, sentences like "The matrix is not nonsingular" are also very common. Such statements with double negation is confusing. Fortunately, we will later learn that "nonsingular" is equivalent to "invertible", so we can always avoid sentences with double negation.
<!-- eng end -->

### 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.

<!-- eng start -->
For small matrices, show the following are equivalent.

1. $\det(A) \neq 0$.
2. $A$ is nonsingular.
<!-- eng end -->

##### Exercise 4(a)

若 $A$ 是 $2\times 2$ 矩陣﹐證明以下敘述等價：

1. $\det(A) \neq 0$.
2. $A$ is nonsingular.

<!-- eng start -->
Let $A$ be a $2\times 2$ matrix. Show the following are equivalent.

1. $\det(A) \neq 0$.
2. $A$ is nonsingular.
<!-- eng end -->

##### Exercise 4(b)

若 $A$ 是 $3\times 3$ 矩陣﹐證明以下敘述等價：

1. $\det(A) \neq 0$.
2. $A$ is nonsingular.

<!-- eng start -->
Let $A$ be a $3\times 3$ matrix. Show the following are equivalent.

1. $\det(A) \neq 0$.
2. $A$ is nonsingular.
<!-- eng end -->