# $A{\bf x} = {\bf b}$ 的解集合

Solution set of $A{\bf x} = {\bf b}$

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_int_list, random_ref

## Main idea

Let $A$ be an $m\times n$ matrix and $\bb$ a vector in $\mathbb{R}^n$.
Recall that $A\bx = \bb$ is equivalent to a system of linear equation.
When $\bb = \bzero$, the system is said to be homogeneous, and
$$\ker(A) = \{\bx\in\mathbb{R}^n : A\bx = \bzero\}.
$$

Let $U = \{\bx\in\mathbb{R}^n : A\bx = \bb\}$ be the set of all solutions.
Then $U$ is an affine subspace in $\mathbb{R}^n$.
In fact, $U$ can be written as $\bp + \ker(A)$, where $\bp$ can be any vector in $U$.

We call $U$ the set of **general solutions**.
When one element is chosen from $U$, it is called a **particular solution**.
And $\ker(A)$ is called the set of **homogeneous solutions**.

Equivalently, the solutions set of $A\bx = \bb$ is of the form:

general solutions = particular solution + homogeneous solutions
(a shifted space) (a vector) (a space)

## Side stories
- `A.nullspace()`

## Experiments

##### Exercise 1

執行下方程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False
A = random_ref(3,5,2)
p = vector(random_int_list(5))
b = A * p

h = A.right_kernel().basis()[0]
p1 = p + h

print("A =")
show(A)
print("b =", b)
print("p =", p)
print("h =", h)
print("p1 =", p1)

:::info

$$
A =
\begin{bmatrix}
1 & 0 & 3 & 5 & -5 \\
0 & 1 & -5 & 0 & 3 \\
0 & 0 & 0 & 0 & 0
\end{bmatrix}
$$

    b = (4, -26, 0)
    p = (-3, 3, 4, -4, -3)
    h = (1, 0, 0, -1/5, 0)
    p1 = (-2, 3, 4, -21/5, -3)

:::

##### Exercise 1(a)

利用題目給的向量及矩陣，
確認 $\bh$ 在 $\ker(A)$ 中。
計算 $\bp + \bh$ 並驗證它符合 $A(\bp + \bh) = \bb$。

<!-- eng start -->
Use the given vectors and matrix and double-check if $\bh$ is in $\ker(A)$. Then compute $\bp + \bh$ and verify $A(\bp + \bh) = \bb$.
<!-- eng end -->

:::warning

- [x] Before $A(\bp + \bh)$: add verify
- [x] In the end after $\bb$: add a period
:::

$A\bh = \begin{bmatrix}
1 & 0 & 3 & 5 & -5 \\
0 & 1 & -5 & 0 & 3 \\
0 & 0 & 0 & 0 & 0
\end{bmatrix}\begin{bmatrix}
1 \\
0 \\
0 \\
-1/5\\
0\end{bmatrix}=\begin{bmatrix}
0 \\
0 \\
0
\end{bmatrix}$

Therefore, we know $\bh$ is in $\ker(A)$.

Then we calculate

$\bp+\bh=\begin{bmatrix}
-3 \\
3 \\
4 \\
-4 \\
-3
\end{bmatrix}+
\begin{bmatrix}
1 \\
0 \\
0 \\
-1/5\\
0\end{bmatrix} =
\begin{bmatrix}
-2 \\
3 \\
4 \\
-21/5\\
-3\end{bmatrix}$

and verify

$A(\bp+\bh)=\begin{bmatrix}
1 & 0 & 3 & 5 & -5 \\
0 & 1 & -5 & 0 & 3 \\
0 & 0 & 0 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
-2 \\
3 \\
4 \\
-21/5\\
-3\end{bmatrix}=
\begin{bmatrix}
4 \\
-26 \\
0\end{bmatrix}=\bb$.

##### Exercise 1(b)

如果已知 $A\bp = \bb$。
證明對任意 $\ker(A)$ 中的向量 $\bh$﹐
都有 $A(\bp + \bh) = \bb$。

<!-- eng start -->
Suppose $A\bp = \bb$. Show that $A(\bp + \bh) = \bb$ for any $\bh\in\ker(A)$.
<!-- eng end -->

:::success
Good
:::

We know if $\bh\in\ker(A)$, $A\bh=0$.

Therefore,

$A(\bp + \bh) = A\bp + A\bh = \bb + 0 = \bb$.

##### Exercise 1(c)

利用題目給的向量及矩陣，
確認它符合 $A\bp_1 = \bb$。
計算 $\bp_1 - \bp$ 並驗證它在 $\ker(A)$ 中。

<!-- eng start -->
Use the given vectors and matrix and double-check if $A\bp_1 = \bb$. Then compute $\bp_1 - \bp$ and verify it is in $\ker(A)$.
<!-- eng end -->

:::warning

- [x] $\bb - \bb = \bzero$ and $A(\bp_1 - \bp) = \bzero$ (bold zero for a zero vector)
:::

We know $A\bp_1 = \bb$ and $A\bp = \bb$ from the above statement.

By substracting the two equations

$A\bp_1 - A\bp = A(\bp_1 - \bp) = \bb - \bb = \bzero$,

we can infer $\bp_1 - \bp$ is in $\ker(A)$ since $A(\bp_1 - \bp) = \bzero$.

##### Exercise 1(d)

如果已知 $A\bp = \bb$。
證明對任意符合 $A\bp_1 = \bb$ 的向量 $\bp_1$﹐
都有 $\bp_1 - \bp\in\ker(A)$。

<!-- eng start -->
Suppose $A\bp = \bb$. Show that $\bp_1 - \bp\in\ker(A)$ for any $\bp_1$ satisfying $A\bp_1 = \bb$.
<!-- eng end -->

:::warning

This one asks you to show $\bp_1 - \bp \in \ker(A)$, but your answer starts with "since $\bp_1 - \bp$ is in $\ker(A)$". In fact, your answer for 1(c) should be the answer here, while 1(c) only requires you to do some calculation.

- [x] We could know that --> We knew that
- [x] If $A\bp_1=\bb$, then $\bzero=\bb-\bb=A\bp_1-A\bp=A(\bp_1-\bp)$. (comma, then)
- [x] We can get the solution that for any $\bp_1-\bp$ is in $\ker(A)$. --> Thus, we get the result that $\bp_1-\bp$ is in $\ker(A)$ for any $\bp_1$ with $A\bp_1 = \bb$.
:::

Solution: We knew that $A\bp=\bb$. If $A\bp_1=\bb$, then $\bzero=\bb-\bb=A\bp_1-A\bp=A(\bp_1-\bp)$.
Thus, we get the result that $\bp_1-\bp$ is in $\ker(A)$ for any $\bp_1$ with $A\bp_1=\bb$.

## Exercises

##### Exercise 2

給定矩陣 $A$ 和向量 $\bb$。
令 $U = \{ \bx: A\bx = \bb \}$。
證明 $V = \{ \bp_1 - \bp_2 : \bp_1, \bp_2 \in U \}$ 是一個子空間。
（因此 $U$ 是一個仿射子空間。）

<!-- eng start -->
Let $A$ be a matrix and $\bb$ a vector. Let $U = \{ \bx: A\bx = \bb \}$. Show that $V = \{ \bp_1 - \bp_2 : \bp_1, \bp_2 \in U \}$ is a subspace. (Therefore, $U$ is an affine subspace.)
<!-- eng end -->

##### Exercise 3

執行以下程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

### code
set_random_seed(0)
A = random_ref(3,5,2)
b = vector(random_int_list(2) + [0])
b1 = b + vector([0,0,1])

print("A =")
show(A)
print("b =", b)
print("b1 =", b1)

:::warning
Paste the result of your $A$, $\bb$, and $\bb_1$ below.
:::

:::info
By running the code, we have

$$
A=\begin{bmatrix}
1 & 0 & 3 & 5 & -5 \\
0 & 1 & -5 & 0 & 3 \\
0 & 0 & 0 & 0 & 0
\end{bmatrix},
\bb = \begin{bmatrix}-3 \\ 3 \\ 0 \end{bmatrix}, \text{ and }
\bb_1 = \begin{bmatrix}-3 \\ 3 \\ 1 \end{bmatrix}.
$$
:::

##### Exercise 3(a)

湊出一個 $A\bx = \bb$ 的解，稱之作 $\bp$。

<!-- eng start -->
Try any method to find a solution to $A\bx = \bb$. Let's call it $\bp$.
<!-- eng end -->

:::warning
- [x] Record what is the matrix $A$. See the comments above.
- [x] ==Upper cases and lower cases are different.== So, $P$ and $p$ and $\bp$ are all different things. See the examples sentence here: Let $\bp = (-3,3,0,0,0)$. Then we may calculate $A\bp = \bb$, so $\bp$ is a solution to $A\bx = \bb$.
- [x] Math error: $\begin{bmatrix}
1 & 0 & 3 & 5 & -5 \\
0 & 1 & -5 & 0 & 3 \\
0 & 0 & 0 & 0 & 0
\end{bmatrix}\begin{bmatrix}
-3 \\
3 \\
0 \\
0\\
0\end{bmatrix} \neq \begin{bmatrix}-3 & 3 & 0 \end{bmatrix}$
:::

:::info
Template:

Suppose $\bp = (x_1, x_2, x_3, x_4, x_5)$. By setting, e.g., $x_3 = x_4 = x_5 = 0$, we have $\bp = ...$. We may verify that $A\bp = \bb$, so it is a solution to $A\bx = \bb$.
:::

Suppose $\bp = (x_1, x_2, x_3, x_4, x_5)$. By setting, e.g., $x_3 = x_4 = x_5 = 0$, we have

$\bp=\begin{bmatrix}
-3\\
3 \\
0 \\
0\\
0\end{bmatrix}$.
We may verify that $A\bp = \bb$, so it is a solution to $A\bx = \bb$.

$A\bp=\begin{bmatrix}
1 & 0 & 3 & 5 & -5 \\
0 & 1 & -5 & 0 & 3 \\
0 & 0 & 0 & 0 & 0
\end{bmatrix}\begin{bmatrix}
-3 \\
3 \\
0 \\
0\\
0\end{bmatrix}=\begin{bmatrix}-3 \\
3\\
0\end{bmatrix}=\bb$.

##### Exercise 3(b)

利用參數式的方法找出 $\bh_1$、$\bh_2$、$\bh_3$
使得 $\ker(A) = \vspan(\{\bh_1, \bh_2, \bh_3\})$。

<!-- eng start -->
Parametrize the equations to find $\bh_1$, $\bh_2$, and $\bh_3$ so that $\ker(A) = \vspan(\{\bh_1, \bh_2, \bh_3\})$.
<!-- eng end -->

:::warning

This one is far from being understandable.

- :x: polynomial = 多項式, and this problem is nothing to do with polynomials
- [x] The equation $A\bx = \bzero$ is equivalent to

$$
\begin{aligned}
1x + 0y + 3z + 5w - 5K &= 0, \\
0x + 1y - 5z + 0w + 3K &= 0.
\end{aligned}
$$
(I suggest using $x_1, \ldots, x_5$.) :warning: Check the source code and revise again.
- [x] Then we let X3,X4,X5 to be as free variables and then we solve the polynomials to get --> Observe that $x_3$, $x_4$, and $x_5$ are the free variables.
- [x] By setting $x_3 = 1$, $x_4 = 0$, and $x_5 = 0$, we get $\bh_1 = ...$. (Revise the rest of the part accordingly.) :warning: Add a period to the end of each sentence.

:::

The equation $A\bx = \bzero$ is equivalent to
$$
\begin{aligned}
1x_1 + 0x_2 + 3x_3 + 5x_4 - 5x_5 &= 0, \\
0x_1 + 1x_2 - 5x_3 + 0x_4 + 3x_5 &= 0.
\end{aligned}
$$

Observe that $x_3$, $x_4$, and $x_5$ are the free variables.
By setting $x_3 = 1$, $x_4 = 0$, and $x_5 = 0$, we get $\bh_1=\begin{bmatrix}
-3 \\
5 \\
1 \\
0\\
0\end{bmatrix}$.

By setting $x_3 = 0$, $x_4 = 1$, and $x_5 = 0$, we get $\bh_2=\begin{bmatrix}
-5 \\
0 \\
0 \\
1\\
0\end{bmatrix}$.

By setting $x_3 = 0$, $x_4 = 0$, and $x_5 = 1$, we get $\bh_3=\begin{bmatrix}
5 \\
-3 \\
0 \\
0\\
1\end{bmatrix}$.

##### Exercise 3(c)

求出 $A\bx = \bb$ 的所有解。

<!-- eng start -->
Find all solutions to $A\bx = \bb$.
<!-- eng end -->

**[Provided by 朱曼華]**
**Answer**
All solution of $A\bx = \bb$ is in the form of
$$
\{\bp + c_1\bh_1+ c_2\bh_2+ c_3\bh_3: c_1, c_2, c_3\in\mathbb{R}^n\}.$$

From the above, we know $A\bx = \bb$​ can be written as
$$
\begin{aligned}
1x_1 + 0x_2 + 3x_3 + 5x_4 - 5x_5 &= -3, \\
0x_1 + 1x_2 - 5x_3 + 0x_4 + 3x_5 &= 3.
\end{aligned}
$$

Thus, the free variables are $x_3, x_4, x_5$, and we can assume they are parameters $c_1, c_2, c_3$, respectively.

Let $c_1 = c_2 = c_3 = 0$ and solve $A\bx = \bb$. We get $x_1 = -3, x_2 = 3$, $\bp = \begin{bmatrix}
-3 \\
3 \\
0 \\
0 \\
0\end{bmatrix}$.

Let $c_2 = c_3 = 0, c_1 = 1$ and solve $A\bx = \bzero$. We get $x_1 = -3, x_2 = 5$, $\bh_1 = \begin{bmatrix}
-3 \\
5 \\
1 \\
0 \\
0\end{bmatrix}$.

Let $c_1 = c_3 = 0, c_2 = 1$ and solve $A\bx = \bzero$. We get $x_1 = -3, x_2 = 5$, $\bh_2 = \begin{bmatrix}
5 \\
0 \\
0 \\
1 \\
0\end{bmatrix}$.

Let $c_2 = c_3 = 0, c_1 = 1$ and solve $A\bx = \bzero$. We get $x_1 = -3, x_2 = 5$, $\bh_3 = \begin{bmatrix}
5 \\
3 \\
0 \\
0 \\
1\end{bmatrix}$.

Hence all solutions are
$$\left\{\begin{bmatrix}
-3 \\
3 \\
0 \\
0 \\
0\end{bmatrix} + c_1\begin{bmatrix}
-3 \\
5 \\
1 \\
0 \\
0\end{bmatrix}+ c_2\begin{bmatrix}
5 \\
0 \\
0 \\
1 \\
0\end{bmatrix}+ c_3\begin{bmatrix}
5 \\
3 \\
0 \\
0 \\
1\end{bmatrix}: c_1, c_2, c_3\in\mathbb{R}^n\right\}.
$$

##### Exercise 3(d)

說明 $A\bx = \bb_1$ 無解。
（儘管 $\ker(A)$ 中有很多向量。）

<!-- eng start -->
Explain why $A\bx = \bb_1$ has no solution, even if $\ker(A)$ has infinitely many vectors.
<!-- eng end -->

**[Provided by 朱曼華]**
**Answer**
The equation $A\bx = \bb_1$ can be written as
$$
\begin{aligned}
1x_1 + 0x_2 + 3x_3 + 5x_4 - 5x_5 &= -3, \\
0x_1 + 1x_2 - 5x_3 + 0x_4 + 3x_5 &= 3, \\
0x_1 + 0x_2 - 0x_3 + 0x_4 + 0x_5 &= 1.
\end{aligned}
$$
The left part of the last equation is equal to $0$; however, the right part is $1$.
Therefore, we know $A\bx = \bb_1$ has no solution.

##### Exercise4

我們現階段對解集合的理解
已經可以告訴我們一些有趣的性質。

<!-- eng start -->
Based on what we have so far, we have the following interesting properties.
<!-- eng end -->

##### Exercise 4(a)

令 $V$ 為一子空間。
若 $V$ 中至少有兩個向量，
$V$ 中向量的個數是否有可能是有限個？

<!-- eng start -->
Let $V$ be a subspace. If $V$ contains at least two vectors, is it possible that $V$ contains only finitely many vectors?
<!-- eng end -->

:::warning

- [x] Let $\bu$ and $\bv$ be in $V$ such that $\bu$ is not equal to $\bv$.
- [x] k$\bv$ --> $k\bv$
- [x] is in $V$ for any $k\in\mathbb{R}$.
:::

Solution: Let $\bu$ and $\bv$ be in $V$ such that $\bu$ is not equal to $\bv$.
At least one of them is not $\bzero$, say that is $\bv$.
Then $k\bv$ is in $V$ for any $k\in\mathbb{R}$.
So we could know that $V$ contains infinite vectors.

##### Exercise 4(b)

若 $A\bx = \bb$ 至少有兩個解，
全部解的個數是否有可能是有限個？

<!-- eng start -->
If $A\bx = \bb$ contains at least two vector, is it possible that the equation has only finitely many solutions?
<!-- eng end -->

:::warning

- [x] Let $\bu$ and $\bv$ be different solutions to $A\bx = \bb$, which means $A\bu=\bb$ and $A\bv=\bb$.
- [x] When we minus these two equations --> By taking the difference of the two equations
- [x] Since $\ker(A)$ is a subspace of $A$, k$(\bu-\bv)$ is in $\ker(A)$, k is one of the real numbers, $A$k$(\bu-\bv)=\bzero$. --> Thus, $Ak(\bu-\bv) = \bzero$ for any $k\in\mathbb{R}$.
- [x] By adding two equations ...
- [x] Put k and k+1 into the `$...$`
- [x] Since (k+1)$\bu-$k$\bv$ is equal to $\bx$, and k is one of the real numbers, $\bx$ contains infinite solutions. --> Since $(k+1)\bu-k\bv$ is a solution to $A\bx = \bb$, it has infinite solutions.
- [x] $A\bu+$$Ak(\bu-\bv)=\bb$ --> $A\bu+Ak(\bu-\bv)=\bb$ (no need to leave `$...$` and come back again)
- [x] $A$$((k+1)\bu-k\bv)=\bb=A\bx$ --> $A((k+1)\bu-k\bv)=\bb=A\bx$ (no need to leave `$...$` and come back again)
:::

Solution: Let $\bu$ and $\bv$ be different solutions to $A\bx=\bb$, which means $A\bu=\bb$ and $A\bv=\bb$.
By taking the difference of the two equations, we will get $A(\bu-\bv)=\bzero$, which means $\bu-\bv$ is in $\ker(A)$.
Thus, $Ak(\bu-\bv)=\bzero$ for any $k\in\mathbb{R}$.
By adding two equations $A\bu=\bb$ and $Ak(\bu-\bv)=\bzero$, we can get $A\bu+Ak(\bu-\bv)=\bb$, which is equal to $A((k+1)\bu-k\bv)=\bb=A\bx$.
Since $(k+1)\bu-k\bv$ is a solution to $A\bx=\bb$, it has infinite solutions.

:::info

collaboration: 2
3 problems: 3

1 extra problem: 0.5

moderator: 0.5
quality control: 0.5
:::