この記事は木 Advent Calendar 2025 の 13 日目の記事です。
「木材と人材」というタイトルで何か書く予定でしたが、急遽予定を変更してお届けします。
外積代数
#
今月 10 日、外積代数 in 競プロ という記事が公開されました。見たことがないテクニックで興味深い記事でした。
これを見て、そういえば外積代数を使う組合せ論の論文があったなあ、ということを思い出したのでその論文を読みました。その内容を軽く紹介していきます。
まずは外積代数を復習します。ベクトル空間 V V V { e 1 , … , e n } \{e_1,\ldots,e_n\} { e 1 , … , e n } ⋀ ( V ) \bigwedge(V) ⋀ ( V ) e i 1 ∧ e i 2 ∧ ⋯ ∧ e i k e_{i_1}\wedge e_{i_2}\wedge\cdots \wedge e_{i_k} e i 1 ∧ e i 2 ∧ ⋯ ∧ e i k 1 ≤ i 1 < ⋯ < i k ≤ n 1\le i_1<\cdots<i_k\le n 1 ≤ i 1 < ⋯ < i k ≤ n ∧ \wedge ∧
v ∧ v = 0 v\wedge v=0 v ∧ v = 0 v ∧ w = − w ∧ v v\wedge w=-w\wedge v v ∧ w = − w ∧ v
などの性質をみたします。外積代数はグラスマン代数とも呼ばれるようです。
以下、ウェッジを省略して v ∧ w = v w v\wedge w=vw v ∧ w = v w ∏ \prod ∏ e i e_i e i ψ 1 , … , ψ n \psi_1,\ldots,\psi_n ψ 1 , … , ψ n ψ ˉ 1 , … , ψ ˉ n \bar{\psi}_1,\ldots,\bar{\psi}_n ψ ˉ 1 , … , ψ ˉ n
ψ i ψ j = − ψ j ψ i \psi_i\psi_j=-\psi_j\psi_i ψ i ψ j = − ψ j ψ i ψ ˉ i ψ j ˉ = − ψ ˉ j ψ ˉ i \bar{\psi}_i\bar{\psi_j}=-\bar{\psi}_j\bar{\psi}_i ψ ˉ i ψ j ˉ = − ψ ˉ j ψ ˉ i ψ i ψ ˉ j = ψ ˉ j ψ i \psi_i\bar{\psi}_j=\bar{\psi}_j\psi_i ψ i ψ ˉ j = ψ ˉ j ψ i
をみたすとします。特に ψ i 2 = ψ ˉ i 2 = 0 \psi_i^2=\bar{\psi}_i^2=0 ψ i 2 = ψ ˉ i 2 = 0
外積代数と行列式
#
n n n A = ( A i j ) A=(A_{ij}) A = ( A ij )
∏ i , j = 1 n ( 1 + ψ ˉ i ψ j A i j ) = ∑ I , J ⊂ [ n ] ψ ˉ I ψ J det ( A I , J )
\prod_{i,j=1}^n(1+\bar{\psi}_i\psi_jA_{ij})=\sum_{I,J\subset [n]}\bar{\psi}_I\psi_J\det(A_{I,J})
i , j = 1 ∏ n ( 1 + ψ ˉ i ψ j A ij ) = I , J ⊂ [ n ] ∑ ψ ˉ I ψ J det ( A I , J ) が成り立ちます。ここで ψ ˉ I \bar{\psi}_I ψ ˉ I i ∈ I i\in I i ∈ I ψ ˉ i \bar{\psi}_i ψ ˉ i ψ J \psi_J ψ J j ∈ J j\in J j ∈ J ψ j \psi_j ψ j A I , J A_{I,J} A I , J I I I J J J
A A A
外積代数と行列木定理
#
グラフ G G G L = D − A L=D-A L = D − A 2 日目の記事 でも解説したのでここでは解説しません。
定理 (行列木定理)
グラフ G G G L L L
det ( t I n + L ) \det(tI_n+L) det ( t I n + L ) t t t c 1 c_1 c 1 1 n c 1 \frac{1}{n}c_1 n 1 c 1 L L L λ 1 , … , λ n \lambda_1,\ldots,\lambda_n λ 1 , … , λ n λ 1 = 0 \lambda_1=0 λ 1 = 0 1 n λ 2 λ 3 ⋯ λ n \frac{1}{n}\lambda_2\lambda_3\cdots \lambda_n n 1 λ 2 λ 3 ⋯ λ n
j j j
∏ i = 1 n ( 1 + ψ ˉ i ψ j A i j ) = ∏ i = 1 n ( 1 + ( ψ ˉ i − ψ ˉ j ) ψ j A i j + ψ ˉ j ψ j A i j ) = ∏ i = 1 n ( 1 + ( ψ ˉ i − ψ ˉ j ) ψ j A i j ) ∏ i = 1 n ( 1 + ψ ˉ j ψ j A i j ) = ∏ i ∈ [ n ] ∖ { j } ( 1 − ( ψ ˉ j − ψ ˉ i ) ψ j A i j ) ⋅ ( 1 + ψ ˉ j ψ j ∑ i = 1 n A i j )
\begin{align*}
\prod_{i=1}^n(1+\bar{\psi}_i\psi_jA_{ij}) &= \prod_{i=1}^n(1+(\bar{\psi}_i-\bar{\psi}_j)\psi_jA_{ij}+\bar{\psi}_j\psi_jA_{ij}) \\
&= \prod_{i=1}^n(1+(\bar{\psi}_i-\bar{\psi}_j)\psi_jA_{ij})\prod_{i=1}^n(1+\bar{\psi}_j\psi_jA_{ij}) \\
&= \prod_{i\in [n]\setminus\{j\}}(1-(\bar{\psi}_j-\bar{\psi}_i)\psi_jA_{ij})\cdot \left(1+\bar{\psi}_j\psi_j\sum_{i=1}^n A_{ij}\right)
\end{align*}
i = 1 ∏ n ( 1 + ψ ˉ i ψ j A ij ) = i = 1 ∏ n ( 1 + ( ψ ˉ i − ψ ˉ j ) ψ j A ij + ψ ˉ j ψ j A ij ) = i = 1 ∏ n ( 1 + ( ψ ˉ i − ψ ˉ j ) ψ j A ij ) i = 1 ∏ n ( 1 + ψ ˉ j ψ j A ij ) = i ∈ [ n ] ∖ { j } ∏ ( 1 − ( ψ ˉ j − ψ ˉ i ) ψ j A ij ) ⋅ ( 1 + ψ ˉ j ψ j i = 1 ∑ n A ij ) となります。ここで ψ j 2 = 0 \psi_j^2=0 ψ j 2 = 0
B j = ∑ i A i j B_j=\sum_i A_{ij} B j = ∑ i A ij
w ( i , j ) = { − A i j i ≠ j B j i = j
w(i,j)=\begin{cases}
-A_{ij} & i\ne j \\
B_j & i=j
\end{cases}
w ( i , j ) = { − A ij B j i = j i = j Ψ ( i , j ) = { ( ψ ˉ j − ψ ˉ i ) ψ j i ≠ j ψ ˉ j ψ j i = j
\Psi(i,j)=\begin{cases}
(\bar{\psi}_j-\bar{\psi}_i)\psi_j & i\ne j \\
\bar{\psi}_j\psi_j & i=j
\end{cases}
Ψ ( i , j ) = { ( ψ ˉ j − ψ ˉ i ) ψ j ψ ˉ j ψ j i = j i = j とおきます。すると
∏ i , j = 1 n ( 1 + ψ ˉ i ψ j A i j ) = ∏ i , j = 1 n ( 1 + Ψ ( i , j ) w ( i , j ) )
\prod_{i,j=1}^n(1+\bar{\psi}_i\psi_jA_{ij})=\prod_{i,j=1}^n(1+\Psi(i,j)w(i,j))
i , j = 1 ∏ n ( 1 + ψ ˉ i ψ j A ij ) = i , j = 1 ∏ n ( 1 + Ψ ( i , j ) w ( i , j )) が得られます。
辺 ( i , j ) (i,j) ( i , j ) w ( i , j ) w(i,j) w ( i , j ) G G G G G G
辺集合 H H H w ( H ) , Ψ ( H ) w(H), \Psi(H) w ( H ) , Ψ ( H ) H H H ( i , j ) (i,j) ( i , j ) w ( i , j ) , Ψ ( i , j ) w(i,j), \Psi(i,j) w ( i , j ) , Ψ ( i , j ) Ψ ( i , j ) Ψ ( i ′ , j ′ ) = Ψ ( i ′ , j ′ ) Ψ ( i , j ) \Psi(i,j)\Psi(i',j')=\Psi(i',j')\Psi(i,j) Ψ ( i , j ) Ψ ( i ′ , j ′ ) = Ψ ( i ′ , j ′ ) Ψ ( i , j ) ψ \psi ψ ψ ˉ \bar{\psi} ψ ˉ
このとき、右辺を展開することで
∏ i , j = 1 n ( 1 + ψ ˉ i ψ j A i j ) = ∑ H ⊂ E ( G ) Ψ ( H ) w ( H )
\prod_{i,j=1}^n(1+\bar{\psi}_i\psi_jA_{ij})=\sum_{H\subset E(G)}\Psi(H)w(H)
i , j = 1 ∏ n ( 1 + ψ ˉ i ψ j A ij ) = H ⊂ E ( G ) ∑ Ψ ( H ) w ( H ) となるので
∑ I , J ⊂ [ n ] ψ ˉ I ψ J det ( A I , J ) = ∑ H ⊂ E ( G ) Ψ ( H ) w ( H )
\sum_{I,J\subset [n]}\bar{\psi}_I\psi_J\det(A_{I,J})=\sum_{H\subset E(G)}\Psi(H)w(H)
I , J ⊂ [ n ] ∑ ψ ˉ I ψ J det ( A I , J ) = H ⊂ E ( G ) ∑ Ψ ( H ) w ( H ) が成り立ちます。
終点が等しい 2 辺 ( i 1 , j ) , ( i 2 , j ) (i_1,j),(i_2,j) ( i 1 , j ) , ( i 2 , j ) Ψ ( i 1 , j ) Ψ ( i 2 , j ) \Psi(i_1,j)\Psi(i_2,j) Ψ ( i 1 , j ) Ψ ( i 2 , j ) ψ j 2 = 0 \psi_j^2=0 ψ j 2 = 0 H H H
入次数が 1 以下のグラフの連結成分は、次の 3 種類です。
木型：根付き木であって辺が根から遠ざかる向きなもの。2 頂点以上。
ループ型：木タイプのグラフの根にループを加えたもの。1 頂点でもよい。
サイクル型：サイクルを含むもの。
まずサイクル型を考えましょう。1 → 2 → ⋯ → k → 1 1\to 2\to\cdots\to k\to 1 1 → 2 → ⋯ → k → 1 k ≥ 2 k\ge 2 k ≥ 2
Ψ ( 1 , 2 ) Ψ ( 2 , 3 ) ⋯ Ψ ( k − 1 , k ) Ψ ( k , 1 ) = ( ψ ˉ 2 − ψ ˉ 1 ) ψ 2 ( ψ ˉ 3 − ψ ˉ 2 ) ψ 3 ⋯ ( ψ ˉ k − ψ ˉ k − 1 ) ψ k ( ψ ˉ 1 − ψ ˉ k ) ψ 1 = ( ψ ˉ 2 ψ ˉ 3 ⋯ ψ ˉ k ψ ˉ 1 + ( − 1 ) k ψ ˉ 1 ψ ˉ 2 ⋯ ψ ˉ k ) ψ 2 ψ 3 ⋯ ψ k ψ 1 = ( ( − 1 ) k − 1 + ( − 1 ) k ) ψ ˉ 1 ψ ˉ 2 ⋯ ψ ˉ k ψ 2 ψ 3 ⋯ ψ k ψ 1 = 0
\begin{align*}
& \Psi(1,2)\Psi(2,3)\cdots\Psi(k-1,k)\Psi(k,1) \\
&= (\bar{\psi}_2-\bar{\psi}_1)\psi_2(\bar{\psi}_3-\bar{\psi}_2)\psi_3\cdots(\bar{\psi}_k-\bar{\psi}_{k-1})\psi_k(\bar{\psi}_1-\bar{\psi}_k)\psi_1 \\
&= (\bar{\psi}_2\bar{\psi}_3\cdots \bar{\psi}_k\bar{\psi}_1+(-1)^k\bar{\psi}_1\bar{\psi}_2\cdots \bar{\psi}_k)\psi_2\psi_3\cdots \psi_k\psi_1 \\
&= ((-1)^{k-1}+(-1)^k)\bar{\psi}_1\bar{\psi}_2\cdots \bar{\psi}_k\psi_2\psi_3\cdots \psi_k\psi_1 \\
&= 0
\end{align*}
Ψ ( 1 , 2 ) Ψ ( 2 , 3 ) ⋯ Ψ ( k − 1 , k ) Ψ ( k , 1 ) = ( ψ ˉ 2 − ψ ˉ 1 ) ψ 2 ( ψ ˉ 3 − ψ ˉ 2 ) ψ 3 ⋯ ( ψ ˉ k − ψ ˉ k − 1 ) ψ k ( ψ ˉ 1 − ψ ˉ k ) ψ 1 = ( ψ ˉ 2 ψ ˉ 3 ⋯ ψ ˉ k ψ ˉ 1 + ( − 1 ) k ψ ˉ 1 ψ ˉ 2 ⋯ ψ ˉ k ) ψ 2 ψ 3 ⋯ ψ k ψ 1 = (( − 1 ) k − 1 + ( − 1 ) k ) ψ ˉ 1 ψ ˉ 2 ⋯ ψ ˉ k ψ 2 ψ 3 ⋯ ψ k ψ 1 = 0 となるので、サイクル型は考えなくてよいことになります。
木型は、根を r r r ψ r \psi_r ψ r det ( A ) \det(A) det ( A )
最後にループ型ですが、Ψ ( H ) = ψ ˉ V ( H ) ψ V ( H ) \Psi(H)=\bar{\psi}_{V(H)}\psi_{V(H)} Ψ ( H ) = ψ ˉ V ( H ) ψ V ( H )
さて、行列木定理に戻ります。A = L A=L A = L ( n , n ) (n,n) ( n , n ) det ( A [ n − 1 ] , [ n − 1 ] ) \det(A_{[n-1],[n-1]}) det ( A [ n − 1 ] , [ n − 1 ] )
∑ H ⊂ E Ψ ( H ) w ( H )
\sum_{H\subset E}\Psi(H)w(H)
H ⊂ E ∑ Ψ ( H ) w ( H ) における ψ ˉ 1 ⋯ ψ ˉ n − 1 ψ 1 ⋯ ψ n − 1 \bar{\psi}_1\cdots \bar{\psi}_{n-1}\psi_1\cdots \psi_{n-1} ψ ˉ 1 ⋯ ψ ˉ n − 1 ψ 1 ⋯ ψ n − 1 B j = 0 B_j=0 B j = 0 H H H ψ n \psi_n ψ n H H H n n n
2 も証明しましょう。A = t I n + L A=tI_n+L A = t I n + L t t t ψ ˉ 1 ⋯ ψ ˉ n ψ 1 ⋯ ψ n \bar{\psi}_1\cdots \bar{\psi}_n\psi_1\cdots \psi_n ψ ˉ 1 ⋯ ψ ˉ n ψ 1 ⋯ ψ n det ( A ) \det(A) det ( A ) det ( A ) \det(A) det ( A ) n n n n n n
より一般に t k t^k t k k k k
おまけ
#
数え上げと行列式といえば、行列木定理の他に LGV 公式を思い浮かべる人も多いでしょう。なんと LGV 公式も外積代数から導出できるようです。
外積代数、奥が深そうですね。競技プログラミングの世界に新たな知見をもたらして、いずれは典型になるかもしれません。
参考文献
#
Curtin, Eugene; Lee, Junu; Lu, Andrew; Sun, Sophia. A modified Grassmann algebra approach to theorems on permanents and determinants. Linear Algebra Appl. 581, 20-35 (2019).
Abdesselam, Abdelmalek. The Grassmann-Berezin calculus and theorems of the matrix-tree type. Adv. Appl. Math. 33, No. 1, 51-70 (2004).
Carrozza, S.; Tanasa, A. Pfaffians and nonintersecting paths in graphs with cycles: Grassmann algebra methods. Adv. Appl. Math. 93, 108-120 (2018).
