Quod Erat Demonstrandum

2010/12/31

利用矩陣求最大公因式

Filed under: Pure Mathematics — johnmayhk @ 8:48 上午

修純數的同學,應熟知以輾轉相除法(Euclidean algorithm)求多項式的最大公因式(greatest common divisor)。

這裡介紹另一方法:用矩陣。

舉例:

6x^4 + 7x^3 - 9x - 42x^3 + x^2 + 6x + 3 的最大公因式。

算法:

依次把係數寫出,作矩陣如下:

\begin{pmatrix} 6 & 7 & 0 & -9 & -4\\ 0 & 2 & 1 & 6 & 3\end{pmatrix}

同學,還記得高斯消元法(Gaussian elimination)嗎?

我們用當中涉及的所謂行運算(row operations),使矩陣中每行最左零(leftmost zeros)的數目不斷增加。

如上例,第一行沒有 leftmost zero,第二行則有一個。

只把兩行互換,無法增加 leftmost zero 數目;其他的 row operation 似乎不能把第一行的 “6″ 變成 “0″。

遇這情形,我們可引入一種運算:

如果該行存在 leftmost zero(s),則該行的元可依次左移若干位置,例如:設 a,b,c 為非零數,

(0 0 0 a b c)

可變成

(0 0 a b c 0), (0 a b c 0 0) 或 (a b c 0 0 0)

但不能有諸如 (b c 0 0 0 a) 等。

逆向地,如果某行存在 rightmost zero(s),則該行的元可依次右移若干位置,例如:

(a b c 0 0 0)

可變成

(0 a b c 0 0), (0 0 a b c 0) 或 (0 0 0 a b c)

但不能有諸如 (c 0 0 0 a b) 等。

回看原題:我們把第二行「左移」,得

\begin{pmatrix} 6 & 7 & 0 & -9 & -4\\ 0 & 2 & 1 & 6 & 3\end{pmatrix}

\rightarrow \begin{pmatrix} 6 & 7 & 0 & -9 & -4\\ 2 & 1 & 6 & 3 & 0\end{pmatrix}

好了,可以進行行運算:把第二行乘以 -3 加進第一行,從而把第一行的 “6″ 變成 “0″,即

\begin{pmatrix} 0 & 4 & -18 & -18 & -4\\ 2 & 1 & 6 & 3 & 0\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 4 & -18 & -18 & -4\\ 0 & 2 & 1 & 6 & 3\end{pmatrix}

現在兩行皆有一個最左零,隨即再進行行運算,以增加最左零的數目;例如把第一行的 “4″ 變 “0″,即

\rightarrow \begin{pmatrix} 0 & 0 & -20 & -30 & -10\\ 0 & 2 & 1 & 6 & 3\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 2 & 3 & 1\\ 0 & 2 & 1 & 6 & 3\end{pmatrix}

第一行兩個最左零,第二行只有一個,故要增加第二行最左零,即

\rightarrow \begin{pmatrix} 0 & 2 & 3 & 1 & 0\\ 0 & 2 & 1 & 6 & 3\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 2 & 3 & 1 & 0\\ 0 & 0 & -2 & 5 & 3\end{pmatrix}

跟從程序,使其中一行所有元變成零為止,即

\rightarrow \begin{pmatrix} 0 & 0 & 2 & 3 & 1\\ 0 & 0 & -2 & 5 & 3\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 2 & 3 & 1\\ 0 & 0 & 0 & 8 & 4\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 2 & 3 & 1\\ 0 & 0 & 0 & 2 & 1\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 2 & 3 & 1\\ 0 & 0 & 2 & 1 & 0\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 0 & 2 & 1\\ 0 & 0 & 2 & 1 & 0\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 0 & 2 & 1\\ 0 & 0 & 0 & 2 & 1\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 0 & 2 & 1\\ 0 & 0 & 0 & 0 & 0\end{pmatrix}

算法終,看非零部分:即 (2 1),對應的多項式是 2x + 1

6x^4 + 7x^3 - 9x - 42x^3 + x^2 + 6x + 3 的最大公因式是 2x + 1。(或曰 k(2x + 1),其中 k \ne 0

類似地,我們可尋求三個或以上多項式的最大公因式,舉例:

2x^4 + 3x^3 - 15x^2 - 14x + 12
x^3 + 3x^2 - 5x - 15,及
3x^3 + 5x^2 - 19x - 21

的最大公因式。

\begin{pmatrix} 2 & 3 & -15 & -14 & 12\\ 0 & 1 & 3 & -5 & -15\\ 0 & 3 & 5 & -19 & -21\end{pmatrix}

\rightarrow \begin{pmatrix} 2 & 3 & -15 & -14 & 12\\ 0 & 1 & 3 & -5 & -15\\ 0 & 0 & -4 & -4 & 24\end{pmatrix}

\rightarrow \begin{pmatrix} 2 & 3 & -15 & -14 & 12\\ 1 & 3 & -5 & -15 & 0\\ 0 & 0 & 1 & 1 & -6\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & -3 & -5 & 16 & 12\\ 1 & 3 & -5 & -15 & 0\\ 0 & 0 & 1 & 1 & -6\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & -3 & -5 & 16 & 12\\ 0 & 1 & 3 & -5 & -15\\ 0 & 0 & 1 & 1 & -6\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 4 & 1 & -33\\ 0 & 1 & 3 & -5 & -15\\ 0 & 0 & 1 & 1 & -6\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 4 & 1 & -33\\ 0 & 1 & 3 & -5 & -15\\ 0 & 1 & 1 & -6 & 0\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 4 & 1 & -33\\ 0 & 0 & 2 & 1 & -15\\ 0 & 0 & 1 & 1 & -6\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 0 & -3 & -9\\ 0 & 0 & 0 & -1 & -3\\ 0 & 0 & 1 & 1 & -6\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 0 & 1 & 3\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & -6\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 1 & 3 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & -6\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 1 & 3 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & -2 & -6\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 0 & 1 & 3\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & -2 & -6\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 0 & 1 & 3\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\end{pmatrix}

2x^4 + 3x^3 - 15x^2 - 14x + 12
x^3 + 3x^2 - 5x - 15,及
3x^3 + 5x^2 - 19x - 21

的最大公因式是

x + 3

這裡要補充有關「右移」的動作。

如上例,若算法某步得

\rightarrow \begin{pmatrix} 0 & 0 & 1 & 3 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\end{pmatrix}

我們要把最右的非零元「右移到盡頭」,即

\rightarrow \begin{pmatrix} 0 & 0 & 0 & 1 & 3\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\end{pmatrix}

方得答案。

但要注意,比方說

x^4, x^3, x^2 的最大公因式是 x^2,用上法:

\begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\end{pmatrix}

當各行皆存在最右零,那麼各行的最右非零元,就不能「右移到盡頭」,最多只能右移到(如這例)x^2 對應位置,即

\begin{pmatrix} 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\end{pmatrix}

\rightarrow \begin{pmatrix} 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\end{pmatrix}

即答案是 x^2

習題:試用上法求

x^4 + x^3 + 3x^2 + x + 2x^3 - 2x^2 - x - 6 的最大公因式。

(答:x^2 + x + 2

利用矩陣也可解丟番圖方程(Diophantine Equations),希望有時間為同學介紹。

當然,授課員要教數學,而不是算法或算術云云;因為有電腦,這些算法就變得無聊,故背後原理才是重點。

發表迴響 »

仍無迴響。

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 位部落客按了讚: