# 零解

Finding the homogeneous 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, betak_solver

## Main idea

Let $A$ be an $m\times n$ matrix and $\bb$ a vector in $\mathbb{R}^n$.
Recall that the homogeneous solutions are the solutions to $A\bx = \bzero$, which is irrelavent to $\bb$.
That is, the homogeneous solutions form the set $\ker(A)$.

Let $R$ be the reduced echelon form of $A$.
Suppose $x_{i_1},\ldots, x_{i_k}$ are the free variables.
For each $s = 1,\ldots, k$, we obtained $\bh_s$ as follows:
1. Set $x_{i_s} = 1$ and the remaining free variables as $0$.
2. Under this settting, solve $A\bx = \bzero$ and call the solution $\bh_s$.

Then $\ker(A) = \vspan(\{\bh_1,\ldots,\bh_k\})$.

Since the set of solutions to $A\bx = \bb$ is $\bp + \ker(A)$ for some particular solution $\bp$,
$$\{ \bx\in\mathbb{R}^n : A\bx = \bb \} =
\{ \bp + c_1\bh_1 + \cdots + c_k\bh_k : c_1,\ldots,c_k\in\mathbb{R} \}.
$$

Suppose $\bb\in\Col(A)$.
The following are equivalent:
1. $A\bx = \bb$ has a unique solution.
2. The reduced echelon form of $A$ has no free variable.
3. The reduced echelon form of $A$ has $n$ pivots.
4. $\ker(A) = \{\bzero\}$.

Since $A\bx = \bzero$ always has a trivial solution $A\bzero = \bzero$, , the followin are equivalent:
1. $\bzero$ is the only solution to $A\bx = \bzero$.
2. The reduced echelon form of $A$ has no free variable.
3. The reduced echelon form of $A$ has $n$ pivots.
4. $\ker(A) = \{\bzero\}$.

## Side stories
- unique representation
- polynomial passing through given points

## Experiments

##### Exercise 1

執行下方程式碼。
矩陣 $R$ 是 $A$ 的最簡階梯形式矩陣。
利用 Main idea 中說明的方法找出 $\{\bh_1,\ldots,\bh_k\}$。

<!-- eng start -->
Run the code below. Let $R$ be the reduced echelon form of $A$. Use the instructions in Main ideato find $\{\bh_1,\ldots,\bh_k\}$.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False
A, R, pivots = random_good_matrix(3,5,2, return_answer=True)

print("A =")
show(A)
print("R =")
show(R)

if print_ans:
    free = [i for i in range(5) if i not in pivots]
    print("Free variables are xi with i =", free)
    for i in range(len(free)):
        hi = betak_solver(R, free, i+1)
        print("h%s ="%(i+1), vector(hi))

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

:::info
By running the code above, we obtain that

$$
A
=
\left[\begin{array}\
1 & -3 & 18 & 5 & -14 \\
3 & -8 & 49 & 15 & -39 \\
-8 & 20 & -124 & -40 & 100
\end{array}\right]
$$

and

$$
R
=
\left[\begin{array}\
1 & 0 & 3 & 5 & -5 \\
0 & 1 & -5 & 0 & 3 \\
0 & 0 & 0 & 0 & 0
\end{array}\right].
$$
:::

By observing the reduced row echelon form, we know that $x_1,x_2$ are leading variables, $x_3,x_4,x_5$ are free variables.

First, we set $x_3=1,x_4=0,x_5=0$, then we solve $A\bx=\bzero$ and get

$$
\bh_1=
\left[\begin{array}\
-3 \\
5 \\
1 \\
0 \\
0
\end{array}\right].
$$

Second, we set $x_3=0,x_4=1,x_5=0$, then we solve $A\bx=\bzero$ and get

$$
\bh_2=
\left[\begin{array}\
-5 \\
0 \\
0 \\
1 \\
0
\end{array}\right].
$$

Finally, we set $x_3=0,x_4=0,x_5=1$, then we solve $A\bx=\bzero$ and get

$$
\bh_3=
\left[\begin{array}\
5 \\
-3 \\
0 \\
0 \\
1
\end{array}\right].
$$

Thus,
$$
\ker(A)=\vspan\left\{
\left[\begin{array}\
-3 \\
5 \\
1 \\
0 \\
0
\end{array}\right],
\left[\begin{array}\
-5 \\
0 \\
0 \\
1 \\
0
\end{array}\right],
\left[\begin{array}\
5 \\
-3 \\
0 \\
0 \\
1
\end{array}\right]
\right\}.
$$

## Exercises

##### Exercise 2

令 $A$ 為一 $m\times n$ 矩陣而 $R$ 為其最簡階梯形式矩陣。
考慮方程式 $A\bx = \bzero$。
若 $R$ 有 $r$ 個軸﹐則可以算出 $\ker(A)$ 的生成集 $S = \{\bh_1,\ldots,\bh_{n-r}\}$。
令 $H$ 為一 $n\times (n-r)$ 矩陣其和行向量依序為 $S$ 中的各項量。

可以執行以下程式碼看例子。

<!-- eng start -->
Let $A$ be an $m\times n$ matrix and $R$ its reduced echelon form. Consider the equation $A\bx = \bzero$. Suppose $R$ has $r$ pivots. Then $\ker(A)$ can be spanned by a set $S = \{\bh_1,\ldots,\bh_{n-r}\}$. Let $H$ be the $n\times (n-r)$ matrix whose columns are vectors in $S$.

See some examples by running the code below.
<!-- eng end -->

### code
set_random_seed(0)
A, R, pivots = random_good_matrix(5,7,4,return_answer=True)

free = [i for i in range(7) if i not in pivots]
H = zero_matrix(QQ, 7, 3)
for i in range(3):
    H[:,i] = betak_solver(R, free, i+1)
    
print("A =")
show(A)
print("R =")
show(R)
print("H =")
show(H)

##### Exercise 2(a)

把 $R$ 中的前 $r$ 列取出來
（也就是那些非零的列向量）、
再從中把對應到領導變數的那些行向量拿出來﹐
組成一個 $r\times r$ 矩陣。
這個矩陣長什麼樣子？說明為什麼？

<!-- eng start -->
Obtain the $r\times r$ matrix from $R$ by taking the first $r$ rows (i.e., those nonzero rows) and those columns corresponding to the leading variables. How does this matrix look like? Provide your reasons.
<!-- eng end -->

##### Exercise 2(b)

把 $H$ 對應到自由變數的那些列向量拿出來﹐
組成一個 $(n-r)\times (n-r)$ 矩陣。
這個矩陣長什麼樣子？說明為什麼？

<!-- eng start -->
Obtain the $(n-r)\times (n-r)$ matrix from $H$ by taking those rows corresponding to the free variables. How does this matrix look like? Provide your reasons.
<!-- eng end -->

##### Exercise 2(c)

把 $R$ 中的前 $r$ 列取出來
（也就是那些非零的列向量）、
再從中把對應到自由變數的那些行向量拿出來﹐
組成一個 $r\times (n-r)$ 矩陣、稱作 $R'$。

另一方面，把 $H$ 中對應到領導變數的列向量拿出來﹐
組成一個 $r\times (n-r)$ 矩陣、稱作 $H'$。

這兩個矩陣 $R'$ 和 $H'$ 有什麼關係？說明為什麼？

<!-- eng start -->
Let $R'$ be the $r\times (n-r)$ matrix obtained from $R$ by taking the first $r$ rows (i.e., those nonzero rows) and those columns corresponding to the free variables.

Let $H'$ be the $r\times (n-r)$ matrix obtained from $H$ by taking those rows corresponding to the leading variables.

Is there any relation between $R'$ and $H'$? Provide your reasons.
<!-- eng end -->

##### Exercise 3

執行以下程式碼。
已知 $\bb\in\Col(A)$。
驗證以下關於唯一解的問題。

<!-- eng start -->
Run the code below. Suppose $\bb\in\Col(A)$. Verify the following statements regarding the uniqueness.
<!-- eng end -->

### code
set_random_seed(0)
A = random_good_matrix(5,3,3)
b = A * vector([1,1,1])
print("A =")
show(A)
print("b =", b)

##### Exercise 3(a)

說明 $A\bx = \bb$ 有唯一解。

<!-- eng start -->
Explain why $A\bx = \bb$ has a unique solution.
<!-- eng end -->

**[由鄭宗祐提供]**
**Answer**
By set `seed = 0`, we get
$$A = \begin{bmatrix} 1 & 3 & 5 \\
-5& -14 & -30 \\
-15 & -42 & -89\\28 & 79
& 162\\ -13 & -37 & -73 \end{bmatrix},
$$

$$
\bb= ( 9,-49,-146,269,-123 ).
$$
$A\bx=\bb$ is
$$\left[\begin{array}{ccc|c}
1 & 3 & 5 & 9\\
-5 & -14 & -30 & -49\\
-15 & -42 & -89 & -146\\
28 & 79 & 162 & 269\\
-13 & -37 & -73 & -123
\end{array}\right],
$$
and its reduce row echelon form is $$\left[\begin{array}{ccc|c}
1 & 0 & 0 & 1\\
0 & 1 & 0 & 1\\
0 & 0 & 1 & 1\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0
\end{array}\right].$$
Thus, we can know $x$ has a unique solution $\begin{bmatrix}1\\1\\1\end{bmatrix}.$

##### Exercise 3(b)

說明 $A\bx = \bzero$ 有唯一解。

<!-- eng start -->
Explain why $A\bx = \bzero$ has a unique solution.
<!-- eng end -->

**[由鄭宗祐提供]**
**Answer**
The augmented matrix for $A\bx= \bzero$ is
$$
\left[\begin{array}{ccc|c}
1 & 3 & 5 & 0\\
-5 & -14 & -30 & 0\\
-15 & -42 & -89 & 0\\
28 & 79 & 162 & 0\\
-13 & -37 & -73 & 0
\end{array}\right],
$$
and its rref is
$$
\left[\begin{array}{ccc|c}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0
\end{array}\right].
$$
Thus, we can know $A\bx=\bzero$ has a unique solution $\begin{bmatrix}0\\0\\0\end{bmatrix}.$

##### Exercise 3(c)

若 $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 -->
Let $f(x) = c_0 + c_1 x + c_2 x^2$. Suppose $f(1) = b_1$, $f(2) = b_2$, and $f(3) = b_3$. Explain why $c_0$, $c_1$, and $c_2$ are solvable annd unique regardless the choice of $b_1$, $b_2$, and $b_3$.
<!-- eng end -->

##### Exercise 3(d)

若 $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 -->
Let $f(x) = c_0 + c_1 x + c_2 x^2$. Suppose $x_1$, $x_2$, and $x_3$ are distinct real numbers and $f(1) = b_1$, $f(2) = b_2$, and $f(3) = b_3$. Explain why $c_0$, $c_1$, and $c_2$ are solvable annd unique regardless the choice of $b_1$, $b_2$, and $b_3$.
<!-- eng end -->