图论意义下的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 为偶回路. 偶回路总数减少 1. 如果 C 1 、 1 为 偶回路. 偶回路总数增加 1. 如果

3、C 1 和 C 2 不同奇偶, 则 C 1 为奇回路 . 偶回路总数减少 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 . 证毕. 我们用同样方法可以证明 : 两列互换 , 行列式改变符号 . 由引理 1 和引理 2,

4、 我们得到 引理 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 % i1 A ik

5、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 右端为 n! 项之和 . 设 C 为 G 的一回路复盖, 且 , w

6、( 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 , ( i2 , . . . . . . , j n- k = ( in- k . 同样地, 不妨设 1 & j 1 i1 ik i2 , . . . . . .

7、 , 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 A 0 ( i . 2 . . . . . a ik ( i k 作 为 一 项 出 现 在 det ( A i1 j 1 . . . . . ain- k ( i n- k 作 为 一 项 出 现 在 det ( A 中, j1 jk in-

8、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 ai2 ( i2 . . . . . . a in- k ( in- k . 的 结 构 知 道: G 由 两 个 连 通 分 支 G 1、 G 2 构 成, 而 且 G 1 、 G2 分 别 同构 于 和A j n( i 2 . ( 2 . 的

9、表示图 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 = a1 ( 1 ( i1 ( i1 ( 1 . . . . . ai k w ( ik 、 ( C 2 = ai1( i1 a i2 ( i2 . . . . . . ain- k ( in- k . . . . . an ( n = w ( C 1

10、 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 . j & n 1 2 k . 证毕. 引理 1, 引理 2, 引理 3 , 引理 4 构成 Laplace 定理的证明 . % 164 % 贵州大学学报 ( 自然科学版 第 18 卷 5 结束语 本文介绍了 Valiant 将图论方法应用于行列式计算的

11、技术 . 依据图论方法的行列式定 义, 给出了 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 考 文 献 Graph t heory w it h applicat ions, 1988 Springer- Verlag Berlin Heideberg, 2000 2 Burgisser P Completeness and reduct ion in algebraic c

12、omplexity 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 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 er Scien