解線性不定方程

2011/02/09

解線性不定方程

Filed under: Pure Mathematics — johnmayhk @ 1:57 下午
Tags: matrix, number theory

所謂前言

不知從何時開始，「尋求最大公因／約數」成了政治術語，其意義大概是「尋求最大共識或妥協」之類。正本清源，大家還記否數學上是如何尋求最大公因數（Highest Common Factor, H.C.F.）？

比如，要尋求 51 和 390 的最大公因數，現在的小學生應懂用「列舉法」處理，即

$51=3 \times 17$

$390=2 \times 3 \times 5 \times 13$

可見，51 和 390 的最大公因數是 3。

有「玩」奧數的小學同學，應可進一步解以下的二元一次不定方程（或曰丟番圖方程 diophantine equation）

$51x+390y=3$

要求 $x, y$ 皆為整數。但相信一般同學，要到中六的純數課，才學到以輾轉相除法（歐幾里德算法 Euclidean Algorithm）處理。

輾轉相除法

承上例，即

$390= 51 \times 7+33$

$51=33 \times 1+18$

$33=18 \times 1+15$

$18=15 \times 1+3$

$15=3 \times 5$

前一行的餘數是 3，即 51 和 390 的最大公因數是 3。把上述式子的餘數寫成主項（Subject），即

$33=390-51 \times 7$

$18=51-33$

$15=33-18$

$3=18-15$

隨即由下而上，由 3 出發，即

$3$

$=18-15$

$=(51-33)-(33-18)$

$=51-2 \times 33+18$

$=51-2(390-51 \times 7)+(51-33)$

$=51 \times 16-390 \times 2-33$

$=51 \times 16-390 \times 2-(390-51 \times 7)$

$= 51(23)+390(-3)$

$= 51(23-\frac{390}{3}t)+390(-3+\frac{51}{3}t)$

$= 51(23-130t)+390(-3+17t)$

解出

$\left \{ \begin{array}{ll} x=23-130t\\y=-3+17t\end{array}\right.$

其中 $t$ 是任意整數。

注， $51x + 390y = 3$ 是等價於 $17x + 130y = 1$ ，即解後者也可。

上述有關整數的輾轉相除法，在純數課中只充當「踏腳石」，純粹為了過渡到尋找多項式的最大公因式（Greatest Common Divisor, G.C.D.）並解決

$f(x)u(x) + g(x)v(x) \equiv d(x)$

（其中 $d(x)$ 是 $f(x),g(x)$ 的 G.C.D.）

之類的問題。

更樸素的做法

如果不知輾轉相除法為何物，要解上述的不定方程，我們有更樸素的做法。就以

$17x+130y=1$

為例。

$17x=-130y+1$

$x=\frac{-130y+1}{17}=\frac{-(17 \times 7+11)y+1}{17}$

$x=-7y-\frac{11y-1}{17}$

因為要求的 $x, y$ 皆為整數，故此

$\frac{11y-1}{17}=t_1$ （其中 $t_1$ 是整數）

進而，

$11y=17t_1+1$

$y=\frac{17t_1+1}{11}=t_1+\frac{6t_1+1}{11}$

得

$\frac{6t_1+1}{11}=t_2$ （其中 $t_2$ 是整數）

進而，

$t_1=\frac{11t_2-1}{6}=t_2+\frac{5t_2-1}{6}$

得，

$\frac{5t_2-1}{6}=t_3$ （其中 $t_3$ 是整數）

進而，

$t_2=\frac{6t_3+1}{5}=t_3+\frac{t_3+1}{5}$

得

$\frac{t_3+1}{5}=t$ （其中 $t$ 是整數）

即

$t_3=5t-1$

現在由下而上，把所有變數以 $t$ 表達，即

$t_2=5t-1+\frac{5t-1+1}{5}=6t-1$

$t_1=6t-1+\frac{5(6t-1)-1}{6}=11t-2$

$y=11t-2+\frac{6(11t-2)+1}{11}=17t-3$

$x=-7(17t-3)-\frac{11(17t-3)-1}{17}=-130t+23$

正是之前的解。

上述算法本質不過是輾轉相除法，同學，你能看出當中的共通點嗎？

上述算法比較直觀，以下介紹兩個不太直接的方法，特別是第二個方法，更能延伸。

利用連分數

不詳述，看看便懂：

$\frac{390}{51}$

$=7+\frac{33}{51}$

$=7+\frac{1}{(51/33)}$

$=7+\frac{1}{1+\frac{18}{33}}$

$=7+\frac{1}{1+\frac{1}{(33/18)}}$

$=7+\frac{1}{1+\frac{1}{1+\frac{15}{18}}}$

$=7+\frac{1}{1+\frac{1}{1+\frac{1}{(18/15)}}}$

$=7+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{5}}}}$

現在把最後的 $\frac{1}{5}$ 「刪除」，即

$7+\frac{1}{1+\frac{1}{1+\frac{1}{1+0}}}$

並「還原」它為普通分數，即

$7+\frac{1}{1+\frac{1}{1+\frac{1}{1+0}}}$

$=7+\frac{1}{1+\frac{1}{1+1}}$

$=7+\frac{1}{1+\frac{1}{2}}$

$=7+\frac{1}{(3/2)}$

$=7+\frac{2}{3}$

$=\frac{23}{3}$

考慮它和原來分數的差，即

$\frac{23}{3}-\frac{390}{51}=\frac{23\times 17-390}{51}=\frac{1}{51}$

看看分子，關係已得：

$17(23)+390(-1)=1$

得

$51(23)+390(-3)=3$

進一步得之前的答案：

$51(23-130t)+390(-3+17t)=3$

其中 $t$ 是任意整數。

為何可以如此？這裡是用到連分數的特性，一些純數考題也建於這些構作，有機會再談。

利用矩陣

其實我最希望介紹這法，因為矩陣是「在課程內」，相信同學比較容易接受。

矩陣可以把輾轉相除法清楚表達出來。

對於整數 $a, b$ ，先寫出矩陣

$\left(\begin{array}{c|cc}a & 1 & 0\\b & 0 & 1\end{array}\right)$

大家看到「貼上」了一個恆等矩陣（identity matrix）嗎？

之後進行若干「特別」的行運算（unimodular row operation），使上述矩陣變成

$\left(\begin{array}{c|cc}d & m & n\\ 0 & m_1 & n_1\end{array}\right)$

那麼， $d$ 就是 $a, b$ 的最大公因數，且 $ax + by = d$ 的整數解為

$\left \{ \begin{array}{ll} x = m + m_1t\\y = n + n_1t\end{array}\right.$

修純數的同學，對 row operation 不會太陌生，「玩」高斯消元法（Gaussian Elimination）時，就是進行若干的 row operation ；而所謂 unimodular row operation，包括

– 某行乘以某整數後，加到另一行
– 某行乘以 $-1$
– 兩行互換

又讓我以解

$51x + 390y = 3$

為例

$\left(\begin{array}{c|cc}51 & 1 & 0\\390 & 0 & 1\end{array}\right)$

行動方向是看第一列（column）的兩個數，以「小數」滅「大數」，最終希望出現零。

$\left(\begin{array}{c|cc}51 & 1 & 0\\390 & 0 & 1\end{array}\right)$

$\rightarrow \left(\begin{array}{c|cc}51 & 1 & 0\\33 & -7 & 1\end{array}\right)$ 　（ $-7R_1 + R_2 \rightarrow R_2$ ）

$\rightarrow \left(\begin{array}{c|cc}18 & 8 & -1\\33 & -7 & 1\end{array}\right)$ 　（ $-R_2 + R_1 \rightarrow R_1$ ）

$\rightarrow \left(\begin{array}{c|cc}18 & 8 & -1\\15 & -15 & 2\end{array}\right)$ 　（ $-R_1 + R_2 \rightarrow R_2$ ）

$\rightarrow \left(\begin{array}{c|cc}3 & 23 & -3\\15 & -15 & 2\end{array}\right)$ 　（ $-R_2 + R_1 \rightarrow R_1$ ）

$\rightarrow \left(\begin{array}{c|cc}3 & 23 & -3\\ 0 & -130 & 17\end{array}\right)$ 　（ $-5R_1 + R_2 \rightarrow R_2$ ）

出現零，算法終。得出 3 就是 51 和 390 的最大公因數，且 $51x + 390y = 3$ 的解為

$\left \{ \begin{array}{ll} x=23-130t\\y=-3+17t\end{array}\right.$

同學，順道觀察一下上述出現過的方陣：

$\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ , $\begin{pmatrix} 1 & 0 \\ -7 & 1 \end{pmatrix}$ , $\begin{pmatrix} 8 & -1 \\ -7 & 1 \end{pmatrix}$ , $\begin{pmatrix} 8 & -1 \\ -15 & 2 \end{pmatrix}$ , $\begin{pmatrix} 23 & -3 \\ -15 & 2 \end{pmatrix}$ 和 $\begin{pmatrix} 23 & -3 \\ -130 & 17 \end{pmatrix}$

它們的行列式（Determinant）皆是 1。

這個現象容易解釋，因為進行 unimodular row operation，就是對應著乘以一個行列式為 1 或 -1 的方陣 $M$ 。

比如

$\left(\begin{array}{c|cc}a_1 & m_1 & n_1\\b_1 & s_1 & t_1\end{array}\right) \rightarrow \left(\begin{array}{c|cc}a_2 & m_2 & n_2\\b_2 & s_2 & t_2\end{array}\right)$

對應著

$M\left(\begin{array}{c|cc}a_1 & m_1 & n_1\\b_1 & s_1 & t_1\end{array}\right) = \left(\begin{array}{c|cc}a_2 & m_2 & n_2\\b_2 & s_2 & t_2\end{array}\right)$

或

$M\begin{pmatrix} m_1 & n_1\\ s_1 & t_1 \end{pmatrix} = \begin{pmatrix} m_2 & n_2 \\ s_2 & t_2 \end{pmatrix}$

當中的 $M$ 的情況見下：

– 對於行運算 $kR_1 + R_2 \rightarrow R_2$ ， $M = \begin{pmatrix} 1 & 0\\ k & 1 \end{pmatrix}$ 。

– 對於行運算 $kR_2 + R_1 \rightarrow R_1$ ， $M = \begin{pmatrix} 1 & k\\ 0 & 1 \end{pmatrix}$ 。

– 對於行運算 $R_1 \leftrightarrow R_2$ ， $M = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}$ 。

– 對於行運算 $-R_1 \rightarrow R_1$ ， $M = \begin{pmatrix} -1 & 0\\ 0 & 1 \end{pmatrix}$ 。

– 對於行運算 $-R_2 \rightarrow R_2$ ， $M = \begin{pmatrix} 1 & 0\\ 0 & -1 \end{pmatrix}$ 。

（注：非常容易得出 $M$ ，因為 $M$ 就是該種行運算作用在 $I$ 上的結果。）

不論上述哪種情況， $M$ 的行列式皆為 1 或 -1。於是，由 $\begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix}$ 出發，不斷左乘所謂的 $M$ ，最終得的方陣，其行列式就是 1 或 -1 了。

矩陣法之推廣

原來對於聯立多元一次不定方程，我們也可利用矩陣處理，舉例：

解

$\left \{ \begin{array}{ll} x+3y-z=16\\2x-y+3z=-12\end{array}\right.$

要求 $x, y, z$ 皆為整數。

做法：先把係數矩陣寫出，即

$A = \begin{pmatrix} 1 & 3 & -1\\ 2 & -1 & 3\end{pmatrix}$

把 $A$ 的轉置矩陣（Transpose） $A^T$ 「貼上」對應的恆等矩陣 $I$ ，即

$\left(\begin{array}{cc|ccc}1 & 2 & 1 & 0 & 0\\ 3 & -1 & 0 & 1 & 0\\ -1 & 3 & 0 & 0 & 1\end{array}\right)$

隨即利用 unimodular row operation，使上述矩陣

$\left(\begin{array}{c|c}A^T & I\end{array}\right)$

變成

$\left(\begin{array}{c|c}H & K\end{array}\right)$

其中 $H$ 是所謂梯矩陣（echelon matrix），即形如

$H = \begin{pmatrix} a & b\\ 0 & c\\ 0 & 0\end{pmatrix}$

（注，這裡的 $a$ 和 $c$ 不一定要是 1。）

這裡談的梯矩陣，一般地，是指零行（zero row）在矩陣底部，且每行非零行（non-zero row）的最左非零元，在它以上各行的最左非零元之右邊者。

好了，運算：

$\left(\begin{array}{cc|ccc}1 & 2 & 1 & 0 & 0\\ 3 & -1 & 0 & 1 & 0\\ -1 & 3 & 0 & 0 & 1\end{array}\right)$

$\rightarrow \left(\begin{array}{cc|ccc}1 & 2 & 1 & 0 & 0\\ 0 & -7 & -3 & 1 & 0\\ 0 & 5 & 1 & 0 & 1\end{array}\right)$ 　（ $-3R_1 + R_2 \rightarrow R_2$ , $R_1 + R_3 \rightarrow R_3$ ）

$\rightarrow \left(\begin{array}{cc|ccc}1 & 2 & 1 & 0 & 0\\ 0 & -2 & -2 & 1 & 1\\ 0 & 5 & 1 & 0 & 1\end{array}\right)$ 　（ $R_3 + R_2 \rightarrow R_2$ ）

$\rightarrow \left(\begin{array}{cc|ccc}1 & 2 & 1 & 0 & 0\\ 0 & -2 & -2 & 1 & 1\\ 0 & 1 & -3 & 2 & 3\end{array}\right)$ 　（ $2R_2 + R_3 \rightarrow R_3$ ）

$\rightarrow \left(\begin{array}{cc|ccc}1 & 2 & 1 & 0 & 0\\ 0 & 0 & -8 & 5 & 7\\ 0 & 1 & -3 & 2 & 3\end{array}\right)$ 　（ $2R_3 + R_2 \rightarrow R_2$ ）

$\rightarrow \left(\begin{array}{cc|ccc}1 & 2 & 1 & 0 & 0\\ 0 & 1 & -3 & 2 & 3\\ 0 & 0 & -8 & 5 & 7\end{array}\right)$ 　（ $R_2 \leftrightarrow R_3$ ）

好了，我們已得梯矩陣

$H = \begin{pmatrix} 1 & 2\\ 0 & 1\\ 0 & 0\end{pmatrix}$

及其對應的方陣

$K = \begin{pmatrix} 1 & 0 & 0\\ -3 & 2 & 3\\ -8 & 5 & 7\end{pmatrix}$

好了，我們透過以下兩個步驟完工，

步驟一：解

$H^T\begin{pmatrix} t_1\\ t_2\\ t_3\end{pmatrix} = \begin{pmatrix} b_1\\ b_2\end{pmatrix}$

其中 $b_1, b_2$ 就是原方程組，等號右邊的數字。如本例，即解

$\begin{pmatrix} 1 & 0 & 0\\ 2 & 1 & 0\end{pmatrix}\begin{pmatrix} t_1\\ t_2\\ t_3\end{pmatrix} = \begin{pmatrix} 16\\ -12\end{pmatrix}$

即

$\left \{ \begin{array}{lll} t_1 = 16\\t_2 = -44\\t_3 = t\end{array}\right.$

（其中 $t$ 是任意整數）

步驟二：計

$\begin{pmatrix} x\\ y\\ z\end{pmatrix} = K^T\begin{pmatrix} t_1\\ t_2\\ t_3\end{pmatrix}$

即答案是

$\begin{pmatrix} x\\ y\\ z\end{pmatrix} = \begin{pmatrix} 1 & -3 & 8\\ 0 & 2 & 5\\ 0 & 3 & 7\end{pmatrix}\begin{pmatrix} 16\\ -12\\ t\end{pmatrix} = \begin{pmatrix} 148-8t\\ -88+5t\\ -132+7t\end{pmatrix}$

（其中 $t$ 是任意整數）

同學，請驗算一下它是否滿足

$\left \{ \begin{array}{ll} x+3y-z=16\\2x-y+3z=-12\end{array}\right.$

再舉一例，解不定方程

$6x-14y+21z=11$

算法如下：

$\left(\begin{array}{c|ccc}6 & 1 & 0 & 0\\-14 & 0 & 1 & 0\\21 & 0 & 0 & 1\end{array}\right)$

$\rightarrow \left(\begin{array}{c|ccc}6 & 1 & 0 & 0\\14 & 0 & -1 & 0\\21 & 0 & 0 & 1\end{array}\right)$

$\rightarrow \left(\begin{array}{c|ccc}6 & 1 & 0 & 0\\2 & -2 & -1 & 0\\3 & -3 & 0 & 1\end{array}\right)$ 　（ $-2R_1+R_2\rightarrow R_2, -3R_1+R_3\rightarrow R_3$ ）

$\rightarrow \left(\begin{array}{c|ccc}6 & 1 & 0 & 0\\2 & -2 & -1 & 0\\1 & -1 & 1 & 1\end{array}\right)$ 　（ $-R_2+R_3\rightarrow R_3$ ）

$\rightarrow \left(\begin{array}{c|ccc}1 & -1 & 1 & 1\\2 & -2 & -1 & 0\\6 & 1 & 0 & 0\end{array}\right)$ 　（ $R_1 \leftrightarrow R_3$ ）

$\rightarrow \left(\begin{array}{c|ccc}1 & -1 & 1 & 1\\ 0 & 0 & -3 & -2\\ 0 & 7 & -6 & -6\end{array}\right)$ 　（ $-2R_1+R_2\rightarrow R_2, -6R_1+R_3\rightarrow R_3$ ）

解

$\begin{pmatrix} 1 & 0 & 0\end{pmatrix}\begin{pmatrix} t_1\\ t_2\\ t_3\end{pmatrix} = (11)$

即

$\left \{ \begin{array}{lll} t_1 = 11\\t_2 = s\\t_3 = t\end{array}\right.$

（其中 $s,t$ 是任意整數）

故

$\begin{pmatrix} x\\ y\\ z\end{pmatrix} = \begin{pmatrix} -1 & 0 & 7\\ 1 & -3 & -6\\ 1 & -2 & -6\end{pmatrix}\begin{pmatrix} 11\\ s\\ t\end{pmatrix} = \begin{pmatrix} -11+7t\\ 11-3s-6t\\ 11-2s-6t\end{pmatrix}$

（其中 $s,t$ 是任意整數）

（JOHN NG 寫於 2011-01-30）

Comments (4)

4 則迴響 »

=.=，雖然新高中有學matrix, 但從matrix開始，不太看的懂。看來新高中的matrix和pure maths 真的有點距離。

迴響由 jaychan — 2011/02/09 @ 6:37 下午 | 回應
- 本人讀pure maths
  都不太看得懂,2個課程距離應該不大
  
  迴響由 Carmen — 2011/02/09 @ 7:14 下午 | 回應
“更樸素的做法"那段運算好像有錯，第11行，應是t1 + (6t1 + 1)/11？，導致最終的equation of y，尾5行，y=17t-50/11也有錯？

迴響由 Handason Tam — 2014/01/21 @ 3:22 下午 | 回應
- 已改，非常感謝！
  
  迴響由 johnmayhk — 2014/01/21 @ 6:14 下午 | 回應

RSS feed for comments on this post. TrackBack URI

	Simon YAU 在唔打：唯一解與delta非零
	johnmayhk 在在葵盛村的童年
	Gabriel So 在在葵盛村的童年
	uprivateta 在長周素
	Phoebe 在 [FW] 給樂道中學同學的一封信
	johnmayhk 在在葵盛村的童年
	johnmayhk 在在葵盛村的童年
	johnmayhk 在在葵盛村的童年
	姓張在在葵盛村的童年
	姓張在在葵盛村的童年
	姓張在在葵盛村的童年
	johnmayhk 在正弦積
	sinredemption 在正弦積
	湯圓桑在卡塔蘭
	卡特蘭數 & LEETCODE… 在卡塔蘭

Quod Erat Demonstrandum

2011/02/09