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]。底下介紹一個精巧的證明。

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

半正定矩陣的偏序關係

本文的閱讀等級:高級 不等式是矩陣理論的重要主題之一,矩陣不等式的探討可以從矩陣與數系的對應關係切入。Hermitian 矩陣 滿足 ,可類比為實數 ;複半正定矩陣 對任意 都滿足 ,因此可類比為非負實數 (見“矩陣與複數的類比”)。自然地,讀者會問:Hermitian 矩陣之間是否可以如實數那樣比較「大小」?本文從回答此問題開始,通過新概念的制訂與聯繫,最終發掘出一系列半正定矩陣的不等性質。

Posted in 線性代數專欄, 二次型 | Tagged , , , , , | 1 Comment