changed 4 years ago
Linked with GitHub

零解

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

\(\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 \({\bf b}\) a vector in \(\mathbb{R}^n\).
Recall that the homogeneous solutions are the solutions to \(A{\bf x} = {\bf 0}\), which is irrelavent to \({\bf b}\).
That is, the homogeneous solutions form the set \(\operatorname{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 \({\bf h}_s\) as follows:

  1. Set \(x_{i_s} = 1\) and the remaining free variables as \(0\).
  2. Under this settting, solve \(A{\bf x} = {\bf 0}\) and call the solution \({\bf h}_s\).

Then \(\operatorname{ker}(A) = \operatorname{span}(\{{\bf h}_1,\ldots,{\bf h}_k\})\).

Since the set of solutions to \(A{\bf x} = {\bf b}\) is \({\bf p} + \operatorname{ker}(A)\) for some particular solution \({\bf p}\), \[\{ {\bf x}\in\mathbb{R}^n : A{\bf x} = {\bf b} \} = \{ {\bf p} + c_1{\bf h}_1 + \cdots + c_k{\bf h}_k : c_1,\ldots,c_k\in\mathbb{R} \}. \]

Suppose \({\bf b}\in\operatorname{ker}(A)\).
The following are equivalent:

  1. \(A{\bf x} = {\bf b}\) 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. \(\operatorname{ker}(A) = \{{\bf 0}\}\).

Since \(A{\bf x} = {\bf 0}\) always has a trivial solution \(A{\bf 0} = {\bf 0}\), , the followin are equivalent:

  1. \({\bf 0}\) is the only solution to \(A{\bf x} = {\bf 0}\).
  2. The reduced echelon form of \(A\) has no free variable.
  3. The reduced echelon form of \(A\) has \(n\) pivots.
  4. \(\operatorname{ker}(A) = \{{\bf 0}\}\).

Side stories

  • unique representation
  • polynomial passing through given points

Experiments

Exercise 1

執行下方程式碼。
矩陣 \(R\)\(A\) 的最簡階梯形式矩陣。
利用 Main idea 中說明的方法找出 \(\{{\bf h}_1,\ldots,{\bf h}_k\}\)

### 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))
  • \(x_3,x_4,x_5\) 的值有寫錯
  • \({\bf h_1}\) > \(\bh_1\) 數字不要粗體

\(Ans:\)

題目給定 seed=0

\[A =\begin{bmatrix} 1 & -3 & 18 & 5 & -14 \\ 3 & -8 & 49 & 15 & -39 \\ -8 & 20 & -120 & -40 & 1000 \end{bmatrix} \]
以及 \[R = \begin{bmatrix} 1 & 0 & 3 & 5 & -5 \\ 0 & 1 & -5 & 0 & 3 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}. \]

\(R\)\(A\) 的最簡階梯形式矩陣。
\(R\) 可知 \(x_1 , x_2\) 為領導變數 , \(x_3 , x_4 , x_5\) 則為自由變數。
\(x_3=1 , x_4=0 , x_5=0\) 時可得到 \[\bh_1 = (-3,5,1,0,0)。 \]

\(x_4=1 , x_3=0 , x_5=0\) 時可得到 \[\bh_2 = (-5,0,0,1,0)。 \] \(x_5=1 , x_3=0 , x_4=0\) 時可得到 \[\bh_3= (5,-3,0,0,1)。\]

Exercises

Exercise 2

\(A\) 為一 \(m\times n\) 矩陣而 \(R\) 為其最簡階梯形式矩陣。
考慮方程式 \(A{\bf x} = {\bf 0}\)
\(R\)\(r\) 個軸﹐則可以算出 \(\operatorname{ker}(A)\) 的生成集 \(S = \{{\bf h}_1,\ldots,{\bf h}_{n-r}\}\)
\(H\) 為一 \(n\times (n-r)\) 矩陣其和行向量依序為 \(S\) 中的各向量。

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

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

藉由 seed = 0 得到 \[A = \begin{bmatrix} 1 & -4 & -3 & 32 & -4 & -29 & 4 \\ -3 & 13 & 11 &-107 & 18 & 98 & -16 \\ 6 & -27 & -23 & 222 & -39 & -203 & 35\\4 & -20 & -18& 166 & -34& -154 & 31\\-10 & 39 & 30 & -315 & 40 & 287 & -37\end{bmatrix}, \] \[R = \begin{bmatrix} 1 & 0 & 0 & 3 & 5 & -5 & 0 \\ 0 & 1 & 0 &-5 & 0 & 3 & 0 \\ 0 & 0 & 1 & -3 & 3 & 4 & 0\\0 & 0 & 0& 0 & 0& 0 & 1\\0 & 0& 0 & 0 & 0 & 0 & 0\end{bmatrix}, \] \[H = \begin{bmatrix} -3 & -5 & 5 \\ 5 & 0 & -3 \\ 3& -3 & -4 \\1 & 0 & 0\\ 0 & 1& 0 \\0& 0& 1 \\ 0 & 0 & 0 \end{bmatrix}. \]

Exercise 2(a)

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

\(Ans:\)

首先,把 \(R\) 中的前 \(r\) 列取出來,得到 \[\begin{bmatrix} 1 & 0 & 0 & 3 & 5 & -5 & 0 \\ 0 & 1 & 0 &-5 & 0 & 3 & 0 \\ 0 & 0 & 1 & -3 & 3 & 4 & 0\\0 & 0 & 0& 0 & 0& 0 & 1\end{bmatrix}. \] 其次,從中把對應到領導變數的那些行向量列舉出來 \[{\bf n}_1 = \begin{bmatrix} 1\\0\\0\\0\end{bmatrix} , {\bf n}_2 = \begin{bmatrix} 0\\1\\0\\0\end{bmatrix} , {\bf n}_3 = \begin{bmatrix} 0\\0\\1\\0\end{bmatrix} , {\bf n}_7 = \begin{bmatrix} 0\\0\\0\\1\end{bmatrix} , \] 再將這些行向列組成一個 \(r\times r\) 矩陣,得到 \[\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0\\0 & 0 & 0& 1\end{bmatrix}. \] 因為 \(R\) 為最簡階梯形式矩陣,所以滿足以下條件:

  1. 所有非零列在所有全零列上面。
  2. 非零列最左的非零元素(即軸元),嚴格地比上一列的軸元更靠右。
  3. 非零列的軸元等於 \(1\) ,且是其所在行的唯一非零元素。

根據以上性質,取非零列的軸元所在的行向量組成的 \(r\times r\) 矩陣,就是單位矩陣。

Exercise 2(b)

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

可能題目沒講清楚,因為 \(H\) 的每一個列都對應到原本的 \(x_1\) ~ \(x_7\),所以這裡說的 "自由變數" 指的是 \(R\) 上的自由變數 \(x_4,x_5,x_6\),所以把 \(H\) 中對應到 \(x_4,x_5,x_6\) 的列拿出來,看看會得到什麼。(你們目前的答案是拿 \(R\) 的行)

\(Ans:\)

首先,把 \(H\) 對應到自由變數的那些列向量拿出來: 因為領導變數位於 \(x_1\),\(x_2\),\(x_3\),\(x_7\),由此可知自由變數所在位置為 \(x_4\)~\(x_6\) 可得: \(H\) 的第 \(i\) 列都會對應到 \(x_i\), 題目要的就是 \(H\) 內的第 \(4\)~\(6\) 列 (對應到 \(x_4\)~\(x_6\) \[{\bf h}_4 = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} , {\bf h}_5 = \begin{bmatrix} 0 & 1 & 0 \end{bmatrix} , {\bf h}_6 = \begin{bmatrix} 0 & 0 & 1\end{bmatrix} \] 組成一個 \((n-r)\times (n-r)\) 的矩陣。 所以這個矩陣就是:

\[{\bf I}_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\\\end{bmatrix} \] 而這個矩陣也就是單位矩陣,其中每列的第 \(k\) 行元素就是表示第 \(k\) 個自由變數設為 \(1\) ,其他為 \(0\) 故若有 \(n\) 個自由變數,代表就會做 \(n\) 次上述的動作,使得該矩陣就是個 \(n\times n\) 的單位矩陣。

Exercise 2©

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

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

這兩個矩陣 \(R'\)\(H'\) 有什麼關係?說明為什麼?

Nice!

  • \({\bf O_{r,n-r}}\) > \(O_{r,n-r}\) 向量才要粗體
  • 數學式後半型句點

\(Ans:\)

\[R'=\begin{bmatrix} 3 & 5 & -5\\ -5 & 0 & 3\\ -3 & 3 & 4\\ 0 & 0 & 0 \end{bmatrix}, H'=\begin{bmatrix} -3 & -5 & 5\\ 5 & 0 & -3\\ 3 & -3 & -4\\ 0 & 0 & 0 \end{bmatrix},R'+H'=O_{r,n-r}. \]

\(R'\) 的第 \(k\) 個列向量為 \((c_1,\ldots,c_{n-r})\) ,可以與所有自由變數組成的向量內積後加上第 \(k\) 個領導變數會等於 \(0\)

\[x_{l,k}+c_1\cdot x_{f,1}+\cdots+c_{n-r}\cdot x_{f,n-r}=0 \] 其中 \(x_{l,k}\) 為第 \(k\) 個領導變數、而 \(x_{f,i}\) 為第 \(i\) 個自由變數。

\(H'\) 的第 \(k\) 個列向量為 \((x_{k,1},\dots x_{k,i},\dots x_{k,n-r})\)
其中 \(x_{k,i}\) 即第 \(i\) 個自由變數等於 \(1\),其他自由變數等於 \(0\) 時的第 \(k\) 個領導變數, 結合 \(R'\)\(x_{k,i}+c_i\cdot 1=0\)
因此 \(H'\)\(k\) 個列向量可以看成 \((-c_1,\ldots,-c_{n-r})\)

\[R'+H'=O_{r,n-r}. \]

Exercise 3

執行以下程式碼。
已知 \({\bf b}\in\operatorname{Col}(A)\)
驗證以下關於唯一解的問題。

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

藉由 seed = 0 得到 \[A = \begin{bmatrix} 1 & 3 & 5 \\ -5& -14 & -30 \\ -15 & -42 & -89\\28 & 79 & 162\\ -13 & -37 & -73 \end{bmatrix}. \] \[ b= ( 9,-49,-146,269,-123 ) \]

Exercise 3(a)

說明 \(A{\bf x} = {\bf b}\) 有唯一解。

\(Ans:\)

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

\[\xrightarrow[-28\rho_1+\rho_4,13\rho_1+\rho_5]{5\rho_1+\rho_2,15\rho_1+\rho_3}\left[\begin{array}{ccc|c} 1 & 3 & 5 & 9\\ 0 & 1 & -5 & -4\\ 0 & 3 & -14 & -11\\ 0 & -5 & 22 & 17\\ 0 & 2 & -8 & -6 \end{array}\right]\]

\[\xrightarrow[5\rho_2+\rho_4,-2\rho_2+\rho_5]{-3\rho_2+\rho_1,-3\rho_2+\rho_3}\left[\begin{array}{ccc|c} 1 & 0 & 20 & 21\\ 0 & 1 & -5 & -4\\ 0 & 0 & 1 & 1\\ 0 & 0 & -3 & -3\\ 0 & 0 & 2 & 2 \end{array}\right]\]

\[\xrightarrow[3\rho_3+\rho_4,-2\rho_3+\rho_5]{-20\rho_3+\rho_1,5\rho_3+\rho_2}\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]\] 由最簡階梯形式矩陣得知, \(x_1=x_2=x_3=1\),有唯一解。

Exercise 3(b)

說明 \(A{\bf x} = {\bf 0}\) 有唯一解。

\(Ans:\) \[\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]\]

\[\xrightarrow[-28\rho_1+\rho_4,13\rho_1+\rho_5]{5\rho_1+\rho_2,15\rho_1+\rho_3}\left[\begin{array}{ccc|c} 1 & 3 & 5 & 0\\ 0 & 1 & -5 & 0\\ 0 & 3 & -14 & 0\\ 0 & -5 & 22 & 0\\ 0 & 2 & -8 & 0 \end{array}\right]\]

\[\xrightarrow[5\rho_2+\rho_4,-2\rho_2+\rho_5]{-3\rho_2+\rho_1,-3\rho_2+\rho_3}\left[\begin{array}{ccc|c} 1 & 0 & 20 & 0\\ 0 & 1 & -5 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & -3 & 0\\ 0 & 0 & 2 & 0 \end{array}\right]\]

\[\xrightarrow[3\rho_3+\rho_4,-2\rho_3+\rho_5]{-20\rho_3+\rho_1,5\rho_3+\rho_2}\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]=R\]

\(x_1=x_2=x_3=0\) ,有解。
\(A\)\(5\times 3\) 矩陣,且最簡階梯形式矩陣後的 \(R\)\(3\) 個軸,沒有自由變數,所以 \(\ker(A)=\{{\bf 0}\}\)\(A{\bf x} = {\bf 0}\) 有唯一解。

Exercise 3©

\(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\) 都有唯一解。

\(Ans:\)

\[\begin{cases} c_0+c_1+c_2=b_1\\ c_0+2c_1+4c_2=b_2\\ c_0+3c_1+9c_2=b_3 \end{cases}\]

可以看成

\[\left[\begin{array}{ccc|c} 1 & 1 & 1 & b_1\\ 1 & 2 & 4 & b_2\\ 1 & 3 & 9 & b_3 \end{array}\right]\] 的解。

\[\xrightarrow[-\rho_1+\rho_3]{-\rho_1+\rho_2}\left[\begin{array}{ccc|c} 1 & 1 & 1 & b_1\\ 0 & 1 & 3 & -b_1+b_2\\ 0 & 2 & 8 & -b_1+b_3 \end{array}\right]\]

\[\xrightarrow[-2\rho_2+\rho_3]{-\rho_2+\rho_1}\left[\begin{array}{ccc|c} 1 & 0 & -2 & 2b_1-b_2\\ 0 & 1 & 3 & -b_1+b_2\\ 0 & 0 & 2 & -3b_1-2b_2+b_3 \end{array}\right]\]

\[\xrightarrow[]{\rho_3\times\frac{1}{2}}\left[\begin{array}{ccc|c} 1 & 0 & -2 & 2b_1-b_2\\ 0 & 1 & 3 & -b_1+b_2\\ 0 & 0 & 2 & -\frac{3}{2}b_1-b_2+\frac{1}{2}b_3 \end{array}\right] \]

\[\xrightarrow[-3\rho_3+\rho_2]{2\rho_3+\rho_1}\left[\begin{array}{ccc|c} 1 & 0 & 0 & -b_1-3b_2+b_3\\ 0 & 1 & 0 & \frac{7}{2}b_1+4b_2-\frac{3}{2}b_3\\ 0 & 0 & 1 & -\frac{3}{2}b_1-b_2+\frac{1}{2}b_3 \end{array}\right] \]

\[ c_0=-b_1-3b_2+b_3 \]

\[ c_1=\frac{7}{2}b_1+4b_2-\frac{3}{2}b_3 \]

\[ c_2=-\frac{3}{2}b_1-b_2+\frac{1}{2}b_3 \] 所以不論 \(b_1\)\(b_2\)\(b_3\) 給的是多少﹐\(c_0\)\(c_1\)\(c_2\) 都有唯一解。

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\) 都有唯一解。

  • 因為 \(x_1\neq x_2\neq x_3\) > 因為 \(x_1,x_2,x_3\) 彼此相異(原本的式子 \(x_1\neq x_2\neq x_3\) 不是一個好的數學式,看起來也許 \(x_1\) 可能和 \(x_3\) 相等)
  • 列運算可以把第二列同乘 \(\frac{1}{-x_1+x_2}\) 之類的會比較好算;參考 109 4©

\(Ans:\) \[\begin{cases} c_0+c_1x_1+c_2{x_1}^2=b_1\\ c_0+c_1x_2+c_2{x_2}^2=b_2\\ c_0+c_1x_3+c_2{x_3}^2=b_3 \end{cases}\]

可以看成

\[\left[\begin{array}{ccc|c} 1 & x_1 & {x_1}^2 & b_1\\ 1 & x_2 & {x_2}^2 & b_2\\ 1 & x_3 & {x_3}^2 & b_3 \end{array}\right] \] 的解。

因為 \(x_1,x_2,x_3\) 彼此相異,所以可以有以下運算:

\[\left[\begin{array}{ccc|c} 1 & x_1 & {x_1}^2 & b_1\\ 1 & x_2 & {x_2}^2 & b_2\\ 1 & x_3 & {x_3}^2 & b_3 \end{array}\right]\]

\[\xrightarrow[-\rho_1+\rho_3]{-\rho_1+\rho_2}\begin{bmatrix} 1 & x_1 & {x_1}^2\\ 0 & -x_1+x_2 & -{x_1}^2+{x_2}^2 &\\ 0 & -x_1+x_3 & -{x_1}^2+{x_3}^2 \end{bmatrix}\]

\[\xrightarrow[\rho_3\times \frac{1}{-x_1+x_3}]{\rho_2\times \frac{1}{-x_1+x_2}}\begin{bmatrix} 1 & x_1 & {x_1}^2\\ 0 & 1 & x_1+x_2\\ 0 & 1 & x_1+x_3 \end{bmatrix}\]

\[\xrightarrow[-\rho_2+\rho_3]{\rho_2\times (-x_1)+\rho_1}\begin{bmatrix} 1 & 0 & -x_1x_2\\ 0 & 1 & x_1+x_2\\ 0 & 0 & -x_2+x_3 \end{bmatrix}\]

\[\xrightarrow[]{\rho_3\times \frac{1}{-x_2+x_3}}\begin{bmatrix} 1 & 0 & -x_1x_2\\ 0 & 1 & x_1+x_2\\ 0 & 0 & 1 \end{bmatrix}\]

\[\xrightarrow[\rho_3\times (-x_1-x_2)]{\rho_3\times(x_1x_2)+\rho_1}\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}\]

由運算結果得到最簡階梯形式矩陣,則可知道只有唯一解。

答案清晰乾淨:)
除了 2(b) 以外數學都沒問題
只有格式要改

目前分數 6/5

Select a repo