Category Archives: 應用之道

有向無環圖與 (0,1) 矩陣的特徵值

本文的閱讀等級:中級 若一個矩陣 的每一元 為 或 ,我們稱之為 (0,1) 矩陣。2003年任職 Wolfram 研究中心的韋斯坦 (Eric W. Weisstein) 在計算 階 (0,1) 矩陣,,的特徵值時,發現所有特徵值皆為正實數[1]的 (0,1) 矩陣總數為下列序列: 在圖論中,若一個有向圖無法從某個頂點出發經過若干條邊回到該點,則稱之為有向無環圖 (directed acyclic graph,簡稱DAG)。韋斯坦得到的序列恰巧與包含 個標記頂點的有向無環圖數的前五項相等[2]: 自然地,韋斯坦猜想這兩個數列完全相同。圖一顯示 的所有標記有向無環圖。2004年麥凱 (Brendan D. McKay) 等人證明了韋斯坦猜想:包含 個標記頂點的有向無環圖與特徵值皆為正實數的 階 矩陣存在一對一的關係[3]。底下介紹一個精巧的證明。 Advertisements

Posted in 線性代數專欄, 圖論, 應用之道 | Tagged , , , , , , , , | 7 Comments

線性規劃 (四):單形法

本文的閱讀等級:中級 美國數學家丹齊格 (George Dantzig) 於1947年提出第一個有效的線性規劃算法──單形法,或稱單純形法 (simplex method),被後人譽為線性規劃之父。1946年丹齊格從加州大學柏克萊分校取得博士學位,次年他以數學顧問身分為美國空軍工作,經常他被要求解決一些與規劃相關的問題,譬如,如何配置預算、人力、飛機,及其他資源使達到最佳的成本效益。因為這些問題多少與經濟學有關,丹齊格跑去徵詢經濟學家科普斯曼 (Tjalling Koopmans,1975年諾貝爾經濟學獎得主)。丹齊格設想經濟學家應當早已發展出解線性規劃問題的技術,出乎意料之外,科普斯曼告訴他經濟學家也沒有線性規劃問題的系統化解法。於是在1947年的暑假,丹齊格決定自己著手尋找一個方法[1]。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , , | 9 Comments

希爾密碼

本文的閱讀等級:初級 希爾密碼 (Hill cipher) 由美國數學家希爾 (Lester S. Hill) 於1929年發明,它是線性代數於密碼學的一個經典應用。希爾密碼是一種替換式密碼,加密一方按照特定規律將明文取代為密文,密文接收者解密時必須使用相反規律才能取得原文本[1]。舉例來說,凱撒密碼是最廣為人知的一種簡易替換式密碼,加密方式係將明文訊息的每一個字母替換為循環移位後的對應字母,位移量即為密鑰 (key)。以英文為例,除了26個字母,還可加入標點符號和空格以方便閱讀。譬如,若移位量為3,則29個明文字母 (含句號「.」,問號「?」與空格「」) 與對應的密文字母如下所示: 明文字母表:ABCDEFGHIJKLMNOPQRSTUVWXYZ .? 密文字母表:DEFGHIJKLMNOPQRSTUVWXYZ .?ABC 為便利計算,我們將29個字母以數字 0, 1, 2,…, 28 依序編碼,即 A0,B1,C2,以此類推。簡單講,每一個字母可視為二十九進制的數字。設非零整數 表示密鑰,凱撒密碼的加密公式為 ,解密公式為 。不同於凱撒密碼的簡易加密法,希爾密碼採用表格式 (polygraphic) 加密,我們不再單獨替換個別字母,而是替換一組字母。首先將明文訊息切割為相同大小的單元,稱為組,每一組包含 () 個字母,接著使用矩陣乘法將每組明文轉換成密文,所乘矩陣即為密鑰。解密同樣使用矩陣乘法,惟所乘矩陣為密鑰的逆矩陣。希爾密碼其實是由 階密鑰矩陣表達的一線性變換, 維明文向量形成定義域, 維密文向量形成到達域,矩陣乘法實現加密與解密程序。下面我們說明希爾密碼的加密與解密過程以及破解方法,模算術是必要的預備知識 (見“利用模算術判定可逆矩陣”)。

Posted in 線性代數專欄, 應用之道 | Tagged , , , | Leave a comment

線性代數在數值分析的應用 (二):Dirichlet 問題

本文的閱讀等級:中級 在物理學中,等方向均勻介質的一點的溫度變化由熱傳導方程 (heat equation) 所描述[1]: , 其中 是點 於時間 的溫度, 是一正數,稱為熱擴散率 (thermal diffusivity), 是 Laplace 算子 (或稱 Laplacian),定義如下: 。 淺白地說,Laplace 算子度量一點的函數值與其鄰近點的差異。若點 處於穩態,即該點溫度不隨時間改變,則 滿足 Laplace 方程 。如果二階連續可導函數 ( 為一開集) 滿足 Laplace 方程,我們稱之為調和函數 (harmonic function)。本文將探討簡化後的二維 Dirichlet 問題[2]:尋找一調和函數 ,使其在一正方形區域內所有點皆滿足 ,且邊界滿足給定條件 。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , , , | 3 Comments

線性代數在圖論的應用 (二):關聯矩陣

本文的閱讀等級:初級 線性代數在圖論的應用建立於圖的矩陣表達。我們曾在“線性代數在圖論的應用 (一):鄰接矩陣”討論了鄰接矩陣 (adjacency matrix),本文將介紹另一個重要的矩陣表達──關聯矩陣 (incidence matrix)。令 為一個有向圖,其中 是頂點集合, 是有向邊集合。我們以 和 分別表示頂點和邊的總數,即 ,。有序對 表示邊 的起始頂點是 ,終止頂點是 ,即 。我們定義關聯矩陣 為一 階矩陣,其中 且 若 ,其餘元為零[1]。見下例: 此圖的關聯矩陣為 。

Posted in 線性代數專欄, 圖論, 應用之道 | Tagged , , , , , , , , , | Leave a comment

線性規劃 (三):最佳基可行解定理

Continue reading

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , , , | Leave a comment

線性微分方程解的存在性與唯一性

本文的閱讀等級:中級 考慮一物理系統,在任意時間 ,該系統的狀態完全由 個函數 描述。在任意時間 ,假設這些函數的變化率由它們的函數值所決定,表示如下: , 並給定初始條件 ,。如果數組 滿足 , 我們稱系統處在均衡狀態 (equilibrium state)。除非受到外力干擾,否則系統不會離開均衡狀態。我們對於均衡狀態附近的系統行為特別感興趣,精確地說,我們想瞭解系統在微小擾動下是否具備穩定性。若系統受到擾動後最終可以返回均衡狀態,便稱此系統是穩定的,否則稱為不穩定。為了探討這個問題,設定 , 其中 是微小擾動量。將上式代入前面的微分式,寫出泰勒展開式, 當 ,,令 。如果忽略高階項,物理系統在均衡狀態 附近的行為可以用下列線性微分方程近似: , 或表示為矩陣形式 。 令 是一 維向量且 是一 階矩陣。定義 ,可得簡明的向量微分方程式 。 我們研習常微分方程的一個強烈動機即在解出 ,,以確定系統的漸近行為 (當 )。本文採用矩陣分析證明線性微分方程解的存在性與唯一性,給出齊次常微分方程的解並定義矩陣指數,最後討論矩陣微分方程解的可逆性 (線性代數與微分方程的一般關聯性討論請見“從線性代數看微分方程”)。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , | Leave a comment

線性規劃 (二):端點與基解

本文的閱讀等級:中級 線性規劃的標準型問題具有下列形式: 其中 是一個 階矩陣, 是 維向量, 是 維向量, 是 維未知向量 (見“線性規劃 (一):標準型問題”)。如果 無解,線性規劃問題即不成立。因為這個緣故,我們要求 ,即約束等式的數目不多於未知數的數目。如果 有線性相關的列向量 (row vector),表示系統存在冗餘的約束條件 (可將多餘條件刪除),譬如,,,或約束條件彼此矛盾 (此時系統無解),譬如,,。為了避免捲入這些無謂的情況,以下假設 有 個線性獨立的列向量,即 ,且 (若 ,則 有唯一解)。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , | 5 Comments

圓錐曲線

本文的閱讀等級:初級 任意二元二次方程式可表示為 , 其中 是實數且 不全為零 (否則二次方程退化為一次方程)。在卡氏座標系統中,二元二次方程的軌跡稱為圓錐曲線[1](conic section,也稱二次曲線)。本文介紹如何通過旋轉與平移,將任一圓錐曲線化簡至典型表達式。圓錐曲線共可區分為9種類別,根據典型表達式的推演結果,我們設計一組建立於行列式的判別式 (discriminant)。

Posted in 線性代數專欄, 應用之道 | Tagged , , , | 11 Comments

線性規劃 (一):標準型問題

本文的閱讀等級:中級 線性規劃 (linear programming) 是一種最佳化問題。顧名思義,線性規劃的目標函數 (objective function) 是未知變數的線性函數,約束條件 (constraints) 則是包含未知變數的線性等式或不等式。儘管最佳化目標與約束條件可能因問題而有所不同,所有的線性規劃問題都可以轉換成下列標準型: 其中 ,,,是給定的實數, 是待決定的未知數。我們之所以將問題寫成標準型,主要的原因是為了執行消去法以化簡線性方程組 (消去法不適用於線性不等式)。針對標準型問題,所謂最佳化是指在滿足 (subject to) 給定的線性方程組,以及未知變數必須為非負值的條件下,尋找可使目標函數最小化的未知變數。因為約束等式可乘以 ,為便利分析,我們假設每一 。線性規劃標準型問題可以用矩陣與向量簡明地表達如下: 上式中, 是一 階矩陣, 是一 維向量, 是一 維向量, 是一 維未知向量。不等式 表示 的每一元皆非負值。本文介紹一些典型的線性規劃問題,並說明如何將給定的問題轉換成標準型。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , | 1 Comment