圖論意義下的Laplace定理

1、 % 162 % 貴州大學學報 ( 自然科學版 第 18 卷 C 1 : v t1 . . . v i v C 2: v w 1 . . . v j v u t1 . . . u i u uw1 . . . uj u 而且 f B ( u i , u C 1、 C 2 對應在 C* 1 I ( i ( i (j ( i (j . . . vtm vt1 . . . v w m v w 1 我們注意到: 在 G B 中, 我們有如下對應回路 : . . . u t m u t1 . . . u w m u w 1 (j = aj ( i , f B ( uj , u u = ai (j G* B

2、 中被合成為如下一個回路 : (j (j : u t1 . . . u i J ( i . . . u w m u w 1 . . . u j u ( i . . . u tm u t 1 下圖很清楚地表示了上述合成關系 . 圖5 可見 : w ( C* 1 = w ( C 1 w ( C 2 , 而且 length ( C * 1 = lengt h( C 1 + sig n( C 2 + 2. 所以, * 如果 C 1 、 C 2 為偶回路 , 則 C * C 2 為奇回路, 則 C * 1 為偶回路. 偶回路總數(shù)減少 1. 如果 C 1 、 1 為 偶回路. 偶回路總數(shù)增加 1. 如果

3、C 1 和 C 2 不同奇偶, 則 C 1 為奇回路 . 偶回路總數(shù)減少 1. C* B 由如下回路構成: C* 1 , C 3, . . . . . . , Cl , Ik Ik ( I 由上述分析和 C B 的構造 : (- 1 * A k n, k ( i , J k J k ( 1 & k & n, k sig n( C B * ( j . sign( C w ( C A = (- 1 (- 1 w ( CB . * 綜上所述及公式 ( 2 : det( A = (- 1 det ( B . 證畢. 我們用同樣方法可以證明 : 兩列互換 , 行列式改變符號 . 由引理

4、1 和引理 2, 我們得到 引理 3. det ( A det ( A 0 i1 j1 0 in- k j n- k j n- k = det ( A i1 j1 ik jk (- 1 i + . . . + i + j + . . .+ j 1 k 1 k i1 j 1 i n - k 1 1 中 , 通過 i 1 + . . . + i k - 2 k ( k + 1 次兩行互換和 j 1 + . . . + j k - 2 k( k + 1 次兩列互換 , A 0 可以化為如下形式的矩陣 . 證明 : 在矩陣 A 第3期 許道云 : 圖論意義下的 L aplace 定理 % 163 %

5、i1 A ik i1 j 1 in- j1 jk k k A j n- 由引理 2, 即得結論. 證畢 . 引理 4. det ( A = j 1 j n證明 : 設 A = ( aij , G 為 A 的表示圖 . 由公式 ( 2 , 1& j < j < . . . < j & n 1 2 k det( A 0 i1 i n- k k ( 5 det ( A = C ! CC( G (- 1 sig n( C w ( C ( 6 由 A 和 G 的形式定義 , G 是一結點帶自回路的有向完全圖, 所以 G 中有 n! 個回路復 蓋, 即公式( 6 右端為

6、n! 項之和 . 設 C 為 G 的一回路復蓋, 且 , w ( C = a 1 an ( n , ( 1 a2 ( 2 . . . 為 1 , 2, . . . , n 上的一個 置換. 給定 1 & i 1 < i 2 < . . . . . . < i k & n . 記 j 1 = ( i 2 , . . . . . . , j k = ( i1 , j 2 = k ( i 1 , j 2 = in- ( ik . 不妨設 1 & j 1 < j 2 < . . . . . . < j k & n. 令 i1 , (

7、i2 , . . . . . . , j n- k = ( in- k . 同樣地, 不妨設 1 & j 1 i1 ik i2 , . . . . . . , in- k = 1, 2, . . . . . . n - i 1 , i 2 , . . . . . . ik , 假定 1 & i1 < i2 < . . . . . . < k & n, 記 j 1 = < j 2 < . . . . . . < j n- & n. ( i 2 . 若不 計 符 號 , ai 1 ( i 1 ai 2 a i1 ( i1 ai2

8、A 0 ( i . 2 . . . . . a ik ( i k 作 為 一 項 出 現(xiàn) 在 det ( A i1 j 1 . . . . . ain- k ( i n- k 作 為 一 項 出 現(xiàn) 在 det ( A 中, j1 jk in- k 中. 設 j n- k i1 j1 0 ik jk 的表示圖為 G . 則 G 中有兩個互不相交的回路集合 C、 C(, 使得 ( i 2 . w ( C = ai 1 ( i1 a i2 由A A i1 j1 ik jk i1 j 1 a i2 a2 . . . . . ai k in- k k w ( ik 、 ( C( = ai1 ( i1

9、ai2 ( i2 . . . . . . a in- k ( in- k . 的 結 構 知 道: G 由 兩 個 連 通 分 支 G 1、 G 2 構 成, 而 且 G 1 、 G2 分 別 同構 于 和A j n( i 2 . ( 2 . 的表示圖 H 1 、 H 2 . 顯然 , C 是 G 1 的一個回路復蓋, C ( 是 G 2 的一個回路復蓋. 從而 , H 1 中有一個回路復蓋 C 1 , H 2 中有一個回路復蓋 C 2 , 使得 w ( C 1 = ai 1 所以 , w ( C = a 1 sign ( C 2 . 不難看出, 公式 ( 5 的右端形如 ( ai 1 = a

10、1 ( 1 ( i1 ( i1 ( 1 . . . . . ai k w ( ik 、 ( C 2 = ai1( i1 a i2 ( i2 . . . . . . ain- k ( in- k . . . . . an ( n = w ( C 1 w ( C 2 , 而 且 sign( C = sig n( C 1 + a ik i1 j1 ( ik ( a i2 ( i 2 a i1 ( i1 a i2 ( i2 ain- k ( in- k a2 ( 2 an 1 ( n 的項共有 n ! 項 . det( A 0 綜上所述 : det ( A = i nj n- k k j < j

11、 < .< j & n 1 2 k . 證畢. 引理 1, 引理 2, 引理 3 , 引理 4 構成 Laplace 定理的證明 . % 164 % 貴州大學學報 ( 自然科學版 第 18 卷 5 結束語 本文介紹了 Valiant 將圖論方法應用于行列式計算的技術 . 依據(jù)圖論方法的行列式定 義, 給出了 Laplace 定理的一個新的證明. 證明中用到的方法 , 可以用于矩陣 A 的不變量 ( permanent per ( A = a ! S n 1 ( 1 a2 ( 2 an ( n 的分解計算. 參 1 Bondy J A and M urt y U S J 考

12、文 獻 Graph t heory w it h applicat ions, 1988 Springer- Verlag Berlin Heideberg, 2000 2 Burgisser P Completeness and reduct ion in algebraic complexity th eory M 3 M ahajan M and V inay V . Det erminant : O ld algorit hms, new insights J 490 S IA M J D iscret e M at hem at ics, 1999, 12( 4 : 474 4 M

13、inh Hoang T and T hierauf T . The complexit y of verif ying t he charact eristic polynominal and t est ing similarit y M ceedings of 15t h annual IEEE conf erence on comput at ional complexity, edit ed by M . T itsw ort h, 2000 87 95 5 Zeiberger D A combinat orial approach t o mat rix algebra J D iscret e M ath emat ics, 1985, 56 67 72 Pro Laplace Theorem by Graph Theory Xu Daoyun ( D epart ment of Comput e