# 特解

Finding a particular solution

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

Let $\bx = (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 $\br$ 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 $\bx$ satisfying the setting.

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

On the other hand, if $R$ has no zero row, then $R\bx = \br$ has a solution regardless the choice of $\br$.
Therefore, the following are equivalent:
1. $A\bx = \bb$ has a solution for any $\bb\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. $\Col(A) = \mathbb{R}^m$.

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

## 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$ 且 $\bx = (x_1,\ldots,x_5)$。

<!-- eng start -->
Run the code below. The matrix $\left[\begin{array}{c|c}R&\br\end{array}\right]$ is the reduced echelon form of $\left[\begin{array}{c|c}A&\bb\end{array}\right]$. Consider the system of linear equations $A\bx = \bb$ with $\bx = (x_1,\ldots,x_5)$.
<!-- eng end -->

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

:::info
By running the code above with `seed = 0`, we obtain that

$$
\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]
$$

and

$$
\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].
$$
:::

##### Exercise 1(a)

在 $x_1,\ldots,x_5$ 中，
哪些是領導變數、
哪些是自由變數？

<!-- eng start -->
Among $x_1,\ldots,x_5$, which are the leading variables, and which are the free variables?
<!-- eng end -->

**[由張永賦提供]**
**Answer**
From main idea, we know that:

> Let $\bx = (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**.

Thus, $x_1, x_2, x_4$ are leading variables, and $x_3, x_5$ are free variables.

##### Exercise 1(b)

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

<!-- eng start -->
Is there a solution to the system of linear equations? If yes, go to the next problem. If not, ignore the following problems.
<!-- eng end -->

**[由張永賦提供]**
**Answer**
Yes!

##### Exercise 1(c)

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

<!-- eng start -->
Find a solution by setting every free variable as $0$.
<!-- eng end -->

**[由張永賦提供]**
**Answer**
By setting $x_3=x_5=0$, solve the equation

$$
\begin{cases}
1x_1+0x_2+3x_3+0x_4+5x_5= -5, \\
0x_1+1x_2+5x_3+0x_4+0x_5= 3, \\
0x_1+0x_2+0x_3+1x_4-3x_5= 3.
\end{cases}
$$

Therefore, we get $\bx=(-5,3,0,3,0)$.

##### Exercise 1(d)

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

<!-- eng start -->
Find a solution by setting the free variables as any numbers you like.
<!-- eng end -->

**[由張永賦提供]**
**Answer**
By setting $x_3=1,x_5=0$, solve the equation
$$
\begin{cases}
1x_1+0x_2+3x_3+0x_4+5x_5= -5, \\
0x_1+1x_2+5x_3+0x_4+0x_5= 3, \\
0x_1+0x_2+0x_3+1x_4-3x_5= 3.
\end{cases}
$$

Therefore, we get $\bx=(-8,-2,1,3,0)$.

## Exercises

##### Exercise 2

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

<!-- eng start -->
The following problems are examples of inverse problems. They help us to understand a mathematical notion better.
<!-- eng end -->

##### Exercise 2(a)

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

<!-- eng start -->
Find a $3\times 5$ matrix such that it is in the reduced echelon form and its pivots are at $1$, $3$, and $5$.
<!-- eng end -->

**[由張永賦提供]**
**Solution:**
$$
\begin{bmatrix}\
1 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1
\end{bmatrix}.
$$

##### Exercise 2(b)

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

<!-- eng start -->
Find a $3\times 5$ matrix whose entries are all nonzero such that the pivots of its reduced echelon form are at $1$, $3$, and $5$.
<!-- eng end -->

**[由張永賦提供]**
**Solution:**
We find a $3\times 5$ matrix $A$ by doing the row operation in the matrix $R$ that the pivots of its reduced echelon form are at $1$, $3$, and $5$.

Assume

$$
R=
\begin{bmatrix}\
1 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1
\end{bmatrix}
=
\begin{bmatrix}\
- & \br_1 & - \\
- & \br_2 & - \\
- & \br_3 & - \\
\end{bmatrix}.
$$
Let
$$
\br'_1=5\br_1+3\br_2+2\br_3,\\
\br'_2=5\br_1+4\br_2+2\br_3,\\
\br'_3=5\br_1+3\br_2+3\br_3.
$$
Thus, we get
$$
A=
\begin{bmatrix}\
- & \br'_1 & - \\
- & \br'_2 & - \\
- & \br'_3 & - \\
\end{bmatrix}=
\begin{bmatrix}\
5 & 5 & 3 & 5 & 2 \\
5 & 5 & 4 & 5 & 2 \\
5 & 5 & 3 & 5 & 3
\end{bmatrix}.
$$

##### Exercise 3

給定一個矩陣 $A$，
依照以下步驟求出 $\bb\in\Col(A)$ 的等價條件。

<!-- eng start -->
Let $A$ be a matrix. Use the given instruction to find some equivalent conditions for $\bb\in\Col(A)$.
<!-- eng end -->

##### Exercise 3(a)

執行下以程式碼。
令 $\bb = (b_1,b_2,b_3,b_4)$。
令 $A'$ 為 $A\bx = \bb$ 的增廣矩陣。

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

<!-- eng start -->
Run the code below. Let $\bb = (b_1,b_2,b_3,b_4)$. Let $A'$ be the augmented matrix of $A\bx = \bb$.

Write a variable for each entry of $\bb$. Then apply some row operations to $A'$ so that the part of $A$ is in its reduced echelon form. If there is a zero row on the left hand side, the the value of the same row on the right hand side must be zero. Use this fact to give an equivalent condition for $\bb\in\Col(A)$.
<!-- eng end -->

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

上題找到的條件應該都是一些線性方程，
而每個線性方程式都對應到一個法向量，
找到一些向量 $\{\bu_1,\ldots,\bu_k\}$
（以這題的設定 $k = 2$ 就足夠）
使得以下敘述等價：

1. $\inp{\bu_i}{\bb} = 0$ if $i = 1,\ldots,k$.
2. $\bb\in\Col(A)$.

<!-- eng start -->
All the conditions we found in the previous problem are linear equation, while we know each linear equation correspond to a hyperplane defined by its normal vector. Find some vectors $\{\bu_1, \ldots,\bu_k\}$ so that the following are equivalent: (Under the settings in the code, $k = 2$ is enough in our case.)

1. $\inp{\bu_i}{\bb} = 0$ if $i = 1,\ldots,k$.
2. $\bb\in\Col(A)$.
<!-- eng end -->

##### Exercise 4(a)

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

<!-- eng start -->
Run the code below. Explain why $\Col(A) = \mathbb{R}^3$.
<!-- eng end -->

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

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

<!-- eng start -->
Suppose $f(x) = c_0 + c_1 x + c_2 x^2$, $f(1) = b_1$, $f(2) = b_2$, and $f(3) = b_3$. Show that there is a solution of﹐$c_0$、$c_1$、$c_2$ regardless the choice of $b_1$, $b_2$, and $b_3$.
<!-- eng end -->

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

<!-- eng start -->
Suppose $f(x) = c_0 + c_1 x + c_2 x^2$. Suppose for some distinct real numbers $x_1$, $x_2$, and $x_3$, we know $f(1) = b_1$, $f(2) = b_2$, and $f(3) = b_3$. Show that there is a solution of﹐$c_0$、$c_1$、$c_2$ regardless the choice of $b_1$, $b_2$, and $b_3$.
<!-- eng end -->