Quod Erat Demonstrandum

2011/02/09

解線性不定方程

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

所謂前言

不知從何時開始,「尋求最大公因/約數」成了政治術語,其意義大概是「尋求最大共識或妥協」之類。正本清源,大家還記否數學上是如何尋求最大公因數(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_2M = \begin{pmatrix} 1 & 0\\ k & 1 \end{pmatrix}

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

– 對於行運算 R_1 \leftrightarrow R_2M = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}

– 對於行運算 -R_1 \rightarrow R_1M = \begin{pmatrix} -1 & 0\\ 0 & 1 \end{pmatrix}

– 對於行運算 -R_2 \rightarrow R_2M = \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}

(注,這裡的 ac 不一定要是 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)

4 則迴響 »

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

    迴響 由 jaychan — 2011/02/09 @ 6:37 下午 | 回覆

    • 本人讀pure maths
      都不太看得懂,2個課程距離應該不大

      迴響 由 Carmen — 2011/02/09 @ 7:14 下午 | 回覆

  2. “更樸素的做法"那段運算好像有錯,第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

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: