$n$ の順列（permutation） と言った場合 $[n](\coloneqq \{1,\dots,n\})\rightarrow [n]$ の全単射写像を意味する． また， $n$ が文脈から明らかな場合は単に順列と言うこともある．

順列を $[n]$ の要素を並び替えた数列として書く場合がある． この場合数列の $i$ 番目の要素が順列の $i$ の行き先を表す． 例えば $p = (2,3,1)$ と書いた場合， $p(1) = 2, p(2)=3,p(3)=1$ を意味する．

断りのない限りグラフの頂点数を $n$ ，辺数を $m$ とする．

行列式

行列式の３つの定義・性質・意味 | 高校数学の美しい物語

定義

$n$ 次正方行列 $A$ の行列式 $\det A$ を以下で定める．ただし perm. は $n$ の順列全体．

$$ \det A \coloneqq \sum_{p:\text{perm.}} \text{sgn}(p) \prod_{i=1}^n A_{i,p(i)} $$

ただし $\text{sgn}(p)$ は順列 $p$ の符号で，偶置換の時 $1$ 奇置換の時 $-1$．

• 偶置換・奇置換

直感的には「各行・各列からちょうど一つ要素を抜き出す」という操作を全て考え，各操作について，総積を取った後適切に符号を取って全部足している．

例

$$ A = \begin{pmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{pmatrix} $$

の時

$$ \det A = 1\cdot 5\cdot 9

• 1\cdot 6\cdot 8

• 2\cdot 6\cdot 7

• 2\cdot 4\cdot 9

• 3\cdot 4\cdot 8

• 3\cdot 5\cdot 7 $$

計算量

掃き出し法を用いて（四則演算が $O(1)$ で行える体において） $O(n^3)$ で求められる（詳細略）．

• コード

定義式は $n!$ 個の項の総和だったのに $O(n^3)$ で求められる値というのが重要で，いくつかの（普通に求めようとすると指数時間かかりそうな）値について，行列式を経由することで多項式時間で値が求まることが知られている．