本文的閱讀等級：初級
考慮下面這個問題：設 $$A$$ 和 $$B$$ 為 $$n\times n$$ 階矩陣且 $$A+B$$ 是可逆的，證明
$$A(A+B)^{-1}B=B(A+B)^{-1}A$$
此題令人頭疼的地方在於 $$(A+B)^{-1}$$ 夾在兩個矩陣之間，要將它消去似乎不是一件容易的事。先檢查一下我們手邊的可用工具，矩陣運算遵守下列基本性質：
(1) 分配律 $$A(B+C)=AB+AC$$，$$(A+B)C=AC+BC$$
(2) 結合律 $$A(BC)=(AB)C$$
(3) 矩陣乘法交換律不總是成立，但若 $$A$$ 可逆，則存在 $$B$$ 使得 $$AB=BA=I$$，交換律成立。
理論上，運用這些性質便足以應付多數的問題，但我們也不諱言矩陣運算確實要善用一些技巧，複雜一點的問題更需要巧思和洞察力。
2010年9月11日 星期六
矩陣鏈乘積的最佳計算順序
本文的閱讀等級：初級
給定一序列的可乘矩陣，這些矩陣的乘積稱為矩陣鏈乘積。我們知道矩陣乘法有結合律，所以不論採用何種相乘順序，最後的結果總是一樣的。例如，$$A$$ 是 $$3\times 5$$，$$B$$ 是 $$5\times 2$$，$$C$$ 是 $$2\times 4$$，$$D$$ 是 $$4\times 6$$ 階矩陣，總計有 $$5$$ 種方式刮號乘積，如下：
$$((AB)C)D$$，$$(A(BC))D$$，$$(AB)(CD)$$，$$A((BC)D)$$，$$A(B(CD))$$
雖然矩陣鏈乘積相同，但不同的乘法順序所耗費的運算量並不相同。例如，若以乘法運算為計數單位，$$A(BC)$$ 需要 $$(5\times 2\times 4)+(3\times 5\times 4)=40+60=100$$ 個運算，而 $$(AB)C$$ 只使用 $$(3\times 5\times 2)+(3\times 2\times 4)=30+24=54$$ 個運算，第二種計算方式明顯優於第一種方式。考慮一般情況，如果有 $$n$$ 個矩陣相乘，如何決定最佳的矩陣乘法執行順序？這個問題不存在一般公式解。最直接的方法是比較每一種順序的運算量，不過，這僅適用於小 $$n$$ 的情況。當 $$n=10$$，刮號乘積有 $$16,796$$ 種可能，而當 $$n=20$$ 時，總共有 $$6,564,120,420\approx 6\times 10^9$$ 種可能！對於長矩陣鏈，不難理解蠻力檢查是絕對不可行的。
給定一序列的可乘矩陣，這些矩陣的乘積稱為矩陣鏈乘積。我們知道矩陣乘法有結合律，所以不論採用何種相乘順序，最後的結果總是一樣的。例如，$$A$$ 是 $$3\times 5$$，$$B$$ 是 $$5\times 2$$，$$C$$ 是 $$2\times 4$$，$$D$$ 是 $$4\times 6$$ 階矩陣，總計有 $$5$$ 種方式刮號乘積，如下：
$$((AB)C)D$$，$$(A(BC))D$$，$$(AB)(CD)$$，$$A((BC)D)$$，$$A(B(CD))$$
雖然矩陣鏈乘積相同，但不同的乘法順序所耗費的運算量並不相同。例如，若以乘法運算為計數單位，$$A(BC)$$ 需要 $$(5\times 2\times 4)+(3\times 5\times 4)=40+60=100$$ 個運算，而 $$(AB)C$$ 只使用 $$(3\times 5\times 2)+(3\times 2\times 4)=30+24=54$$ 個運算，第二種計算方式明顯優於第一種方式。考慮一般情況，如果有 $$n$$ 個矩陣相乘，如何決定最佳的矩陣乘法執行順序？這個問題不存在一般公式解。最直接的方法是比較每一種順序的運算量，不過，這僅適用於小 $$n$$ 的情況。當 $$n=10$$，刮號乘積有 $$16,796$$ 種可能，而當 $$n=20$$ 時，總共有 $$6,564,120,420\approx 6\times 10^9$$ 種可能！對於長矩陣鏈，不難理解蠻力檢查是絕對不可行的。
2010年8月2日 星期一
分塊矩陣的解題案例
本文的閱讀等級：中級
數學解題像是一門具歸納性質的實驗科學活動，學者不僅試圖了解各種解答，還希望能明白這些解答背後的動機和過程。美國數學家 G. Polya (1887-1985) 在其名著“How to Solve it”（中譯《怎樣解題》，天下文化出版，2006）主張數學解題過程可分為四個階段。第一、了解問題：要知道未知數是什麼？已知數是什麼？條件是什麼？第二、擬定計畫：找出已知數和未知數之間的關係。如果這個關係不是很明確，可以嘗試考慮類似的問題。最後，我們應該能想出解題的計畫。第三、執行計畫：將解題計畫付諸實現，仔細檢查每一個步驟。第四、驗算與回顧：驗算所得的解答，檢驗每個論證步驟是否正確。Polya 並以“啟發法”（heuristic）為基礎，舉出一連串提示問題引領讀者朝著解答方向前進。本文就以矩陣分析常使用的分塊矩陣為例，跟隨 Polya 的腳步，學習透過有效的提問來激發想法，從而構思解題計畫，跨越障礙直達問題核心。
數學解題像是一門具歸納性質的實驗科學活動，學者不僅試圖了解各種解答，還希望能明白這些解答背後的動機和過程。美國數學家 G. Polya (1887-1985) 在其名著“How to Solve it”（中譯《怎樣解題》，天下文化出版，2006）主張數學解題過程可分為四個階段。第一、了解問題：要知道未知數是什麼？已知數是什麼？條件是什麼？第二、擬定計畫：找出已知數和未知數之間的關係。如果這個關係不是很明確，可以嘗試考慮類似的問題。最後，我們應該能想出解題的計畫。第三、執行計畫：將解題計畫付諸實現，仔細檢查每一個步驟。第四、驗算與回顧：驗算所得的解答，檢驗每個論證步驟是否正確。Polya 並以“啟發法”（heuristic）為基礎，舉出一連串提示問題引領讀者朝著解答方向前進。本文就以矩陣分析常使用的分塊矩陣為例，跟隨 Polya 的腳步，學習透過有效的提問來激發想法，從而構思解題計畫，跨越障礙直達問題核心。
2010年6月18日 星期五
線性代數的第一堂課——矩陣乘法的定義
本文的閱讀等級：初級
美國數學家 Morris Kline (1908-1992) 說[1]：「矩陣理論在被創造前就已發展完善（the subject of matrix theory was well developed before it was created）。」這句話讓人聽得一頭霧水，要弄清楚這話的意思必須從矩陣的發展歷史說起。西元十七至十九世紀中葉，數學活動在歐洲以快速的步伐朝各領域繁盛發展，此時關於陣列（array）運算的研究全部集中於行列式理論，令人不解的是矩陣代數並未隨著行列式進行，矩陣理論足足落後行列式兩百年之久。西元 1850年，英國數學家 James Joseph Sylvester (1814-1897) 將矩形陣列命名為矩陣（matrix），但他並未定義矩陣乘法。1857 年，英國數學家 Arthur Cayley (1821-1895) 發表 A Memoir on the Theory of Matrices，他將矩陣從行列式抽離出來，視之為單獨數學物件，並定義完備的矩陣代數運算，此篇論文被後世公認為近代矩陣理論和線性代數的基石。這段歷史顯示矩陣乘法——矩陣理論最重要的一個代數運算——絕對不是如數學課本所述那般理所當然；矩陣乘法定義隱含深層的意涵，否則為何眾多優秀數學家竟然看不出矩陣理當如此相乘。今天我們事後諸葛，已然明瞭矩陣代數之所以遲至十九世紀中葉才誕生的最主要原因在於人們一直無法確定矩陣的內涵和本質究竟為何。
美國數學家 Morris Kline (1908-1992) 說[1]：「矩陣理論在被創造前就已發展完善（the subject of matrix theory was well developed before it was created）。」這句話讓人聽得一頭霧水，要弄清楚這話的意思必須從矩陣的發展歷史說起。西元十七至十九世紀中葉，數學活動在歐洲以快速的步伐朝各領域繁盛發展，此時關於陣列（array）運算的研究全部集中於行列式理論，令人不解的是矩陣代數並未隨著行列式進行，矩陣理論足足落後行列式兩百年之久。西元 1850年，英國數學家 James Joseph Sylvester (1814-1897) 將矩形陣列命名為矩陣（matrix），但他並未定義矩陣乘法。1857 年，英國數學家 Arthur Cayley (1821-1895) 發表 A Memoir on the Theory of Matrices，他將矩陣從行列式抽離出來，視之為單獨數學物件，並定義完備的矩陣代數運算，此篇論文被後世公認為近代矩陣理論和線性代數的基石。這段歷史顯示矩陣乘法——矩陣理論最重要的一個代數運算——絕對不是如數學課本所述那般理所當然；矩陣乘法定義隱含深層的意涵，否則為何眾多優秀數學家竟然看不出矩陣理當如此相乘。今天我們事後諸葛，已然明瞭矩陣代數之所以遲至十九世紀中葉才誕生的最主要原因在於人們一直無法確定矩陣的內涵和本質究竟為何。
2010年5月17日 星期一
2010年3月19日 星期五
特殊矩陣 (12)：對角佔優矩陣
本文的閱讀等級：初級
如果一 $$n\times n$$ 階矩陣 $$A=[a_{ij}]$$ 每一列其主對角元的絕對值大於該列非主對角元絕對值之和，也就是說，對於 $$i=1,2,\ldots,n$$，滿足
$$\vert a_{ii}\vert>\sum_{j\neq i}\vert a_{ij}\vert$$
我們稱 $$A$$ 為對角佔優（diagonally dominant）。例如，
$$B=\begin{bmatrix}
-4&-2&1\\
1&2&0\\
3&1&5
\end{bmatrix}$$
是對角佔優矩陣因為
$$\vert b_{11}\vert=4>\vert b_{12}\vert+\vert b_{13}\vert=2+1=3$$
$$\vert b_{22}\vert=2>\vert b_{21}\vert+\vert b_{23}\vert=1+0=1$$
$$\vert b_{33}\vert=5>\vert b_{31}\vert+\vert b_{32}\vert=3+1=4$$
如果一 $$n\times n$$ 階矩陣 $$A=[a_{ij}]$$ 每一列其主對角元的絕對值大於該列非主對角元絕對值之和，也就是說，對於 $$i=1,2,\ldots,n$$，滿足
$$\vert a_{ii}\vert>\sum_{j\neq i}\vert a_{ij}\vert$$
我們稱 $$A$$ 為對角佔優（diagonally dominant）。例如，
$$B=\begin{bmatrix}
-4&-2&1\\
1&2&0\\
3&1&5
\end{bmatrix}$$
是對角佔優矩陣因為
$$\vert b_{11}\vert=4>\vert b_{12}\vert+\vert b_{13}\vert=2+1=3$$
$$\vert b_{22}\vert=2>\vert b_{21}\vert+\vert b_{23}\vert=1+0=1$$
$$\vert b_{33}\vert=5>\vert b_{31}\vert+\vert b_{32}\vert=3+1=4$$
2010年3月12日 星期五
2010年2月21日 星期日
特殊矩陣 (11)：三對角矩陣
本文的閱讀等級：初級
如果 $$n$$ 階方陣 $$A=[a_{ij}]$$ 除了主對角線元以及比主對角線低一列和高一列的對角線之外，其餘皆為零元，我們稱它為三對角（tridiagonal）矩陣，也就是說，當 $$\vert i-j\vert>1$$，$$a_{ij}=0$$；如下例，
$$A=\begin{bmatrix}
1&2&0&0\\
3&2&3&0\\
0&2&1&1\\
0&0&3&2
\end{bmatrix}$$
三對角矩陣常出現於數值分析問題，本文僅介紹三對角矩陣的幾個基本性質，包括行列式計算、相似變換的應用以及求解線性方程式。
如果 $$n$$ 階方陣 $$A=[a_{ij}]$$ 除了主對角線元以及比主對角線低一列和高一列的對角線之外，其餘皆為零元，我們稱它為三對角（tridiagonal）矩陣，也就是說，當 $$\vert i-j\vert>1$$，$$a_{ij}=0$$；如下例，
$$A=\begin{bmatrix}
1&2&0&0\\
3&2&3&0\\
0&2&1&1\\
0&0&3&2
\end{bmatrix}$$
三對角矩陣常出現於數值分析問題，本文僅介紹三對角矩陣的幾個基本性質，包括行列式計算、相似變換的應用以及求解線性方程式。
2010年2月3日 星期三
最簡列梯形陣式的唯一性
本文的閱讀等級：高級
高斯---約當法（Gauss-Jordan method）是線性代數中最常使用的演算法之一，它的功用是將給定矩陣化約至最簡列梯形陣式（reduced row echelon form）。透過最簡列梯形矩陣，不但可以解出線性方程組還能回答許多有關矩陣的基本問題，如矩陣秩、列空間基底、行空間基底以及零空間基底。從高斯---約當法的演算過程，我們憑直覺推斷 $$A$$ 的最簡列梯形矩陣是唯一的，於是理所當然地將它視為事實。本文介紹一個運用排列矩陣和分塊矩陣的代數證明方法，透徹瞭解這整個論證過程對提昇邏輯推理能力有很大的幫助。
高斯---約當法（Gauss-Jordan method）是線性代數中最常使用的演算法之一，它的功用是將給定矩陣化約至最簡列梯形陣式（reduced row echelon form）。透過最簡列梯形矩陣，不但可以解出線性方程組還能回答許多有關矩陣的基本問題，如矩陣秩、列空間基底、行空間基底以及零空間基底。從高斯---約當法的演算過程，我們憑直覺推斷 $$A$$ 的最簡列梯形矩陣是唯一的，於是理所當然地將它視為事實。本文介紹一個運用排列矩陣和分塊矩陣的代數證明方法，透徹瞭解這整個論證過程對提昇邏輯推理能力有很大的幫助。
2010年2月2日 星期二
特殊矩陣 (十)：基本矩陣
本文的閱讀等級：初級
數百年來，化約主義（reductionism）強力主導科學和工程研究方法論，基本思想是將複雜的系統或現象化解為各部分的組合，透過分析各組件從而理解並描述原來的複雜系統或現象。線性代數也是如此，例如，類似對多項式因式分解，高斯消去法可將任意可逆矩陣分解為一組基本矩陣的乘積。這篇短文介紹基本矩陣的一般形式，證明基本矩陣是可逆的，且其逆矩陣也為基本矩陣。
數百年來，化約主義（reductionism）強力主導科學和工程研究方法論，基本思想是將複雜的系統或現象化解為各部分的組合，透過分析各組件從而理解並描述原來的複雜系統或現象。線性代數也是如此，例如，類似對多項式因式分解，高斯消去法可將任意可逆矩陣分解為一組基本矩陣的乘積。這篇短文介紹基本矩陣的一般形式，證明基本矩陣是可逆的，且其逆矩陣也為基本矩陣。
訂閱：
文章 (Atom)