Tag 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

行列式公式的推導

本文的閱讀等級:中級 一個 階矩陣 的行列式存在多種不同的定義方式,目前最被廣泛採用的定義當屬萊布尼茲 (Gottfried Wilhelm Leibniz) 公式[1]: , 其中 是數組 的排列 (permutation,或稱置換),總共有 種可能。函數 是排列 的符號差 (sign) 或稱簽名 (signature)。任何一個排列 可以分解成換位 (transposition) 的複合運算,例如, 的換位分解是 ,排列 至自然排序 的換位過程如下 (見“特殊矩陣 (16):排列矩陣”): 我們定義 若 包含偶數個換位, 若 包含奇數個換位。本文從行列式的幾何定義出發,解說如何從三個設定的性質推導出萊布尼茲行列式公式 (二階行列式公式的推導請見“行列式的運算公式與性質”)。

Posted in 線性代數專欄, 行列式 | Tagged , , | 5 Comments

特殊矩陣 (16):排列矩陣

本文的閱讀等級:中級 一 階矩陣 稱為排列矩陣 (或稱置換矩陣,permutation matrix),若 的每一行和每一列恰有一個元為 ,其餘元為 ,例如: , 明顯地, 也是一排列矩陣。設 ,,則 , 。 左乘排列矩陣和右乘排列矩陣有不同的效果: 將 的列按 2, 4, 1, 3 排序, 則將 的行按 3, 1, 4, 2 排序。寫出 ,配合轉置運算,右乘排列矩陣 可表示為左乘排列矩陣 ,以下限定排列矩陣總是以左乘方式執行。既然每一 階排列矩陣 代表 個元素的一種特別排列,可知冪矩陣 表示連續執行 次排列,所以 也是一排列矩陣。考慮這個問題:試求一 階排列矩陣 … Continue reading

Posted in 特殊矩陣, 線性代數專欄 | Tagged , , , , | 13 Comments