文献あり

置換行列についての覚書

142

定義

$n$ 次対称群 $S_{n}$ の元 $σ$ に対して，線型変換 $p_{σ} : C^{n} \to C^{n}$ を
$p_{σ} ϵ_{j} : = ϵ_{σ (j)}$
で定め， $C^{n}$ の標準基底に関する $p_{σ}$ の表現行列を $P_{σ}$ で表わす：
$P_{σ} (i, j) = δ_{i, σ (j)} = {\begin{cases} 1 & i = σ (j) \\ 0 & i \neq σ (j) \end{cases} .$
明らかに $p_{σ}$ は全単射であるから， $P_{σ}$ は可逆行列である．したがって，写像 $P : S_{n} \to GL (n, C)$ を
$P (σ) : = P_{σ}$
で定めることができる．

$P$ は単射群準同型である．

$σ, τ \in S_{n}$ とする．このとき
$\begin{aligned} p_{σ \circ τ} ϵ_{j} & = ϵ_{(σ \circ τ) (j)} \\ = ϵ_{σ (τ (j))} \\ = p_{σ} ϵ_{τ (j)} \\ = p_{σ} p_{τ} ϵ_{j} \end{aligned}$
より $p_{σ \circ τ} = p_{σ} \circ p_{τ}$ となるので，（行列の積の定義（cf. [5]例13）より）
$P (σ \circ τ) = P_{σ \circ τ} = P_{σ} P_{τ} = P (σ) P (τ)$
が成り立つ．
$σ \in S_{n}$ とし， $P_{σ} = I_{n}$ とする．このとき， $p_{σ} = {id}_{C^{n}}$ より，任意の $j \in {1, \dots, n}$ に対して
$ϵ_{σ (j)} = p_{σ} ϵ_{j} = ϵ_{j} ⇝ σ (j) = j$
が成り立つので， $σ = id$ を得る．

命題1より
$S_{n} ≅ Perm (n) := Im (P) < GL (n, C)$
が成り立つ． $Perm (n)$ の元を（ $n$ 次）置換行列という．

置換 $σ \in S_{n}$ に対して，
$\begin{aligned} \det p_{σ} & = \det P_{σ} \\ = \sum_{τ \in S_{n}} sgn (τ) \cdot P_{σ} (1, τ (1)) \dots P_{σ} (n, τ (n)) \\ = \sum_{τ \in S_{n}} sgn (τ) \cdot δ_{1, σ (τ (1))} \dots δ_{n, σ (τ (n))} \\ = sgn (σ^{- 1}) \\ = sgn (σ) \end{aligned}$
が成り立つ．また，
$tr p_{σ} = tr P_{σ} = \sum_{i = 1}^{n} δ_{i, σ (i)} = # {i \in {1, \dots, n} : σ (i) = i}$
が成り立つ．

直交性

置換行列は直交行列である：
$Perm (n) < O (n) .$

$σ \in S_{n}$ とする．このとき
$P_{σ}^{T} (i, j) = P_{σ} (j, i) = δ_{j, σ (i)} = δ_{i, σ^{- 1} (j)} = P_{σ^{- 1}} (i, j)$
より，
$P_{σ}^{T} = P_{σ^{- 1}} = P (σ^{- 1}) = P (σ)^{- 1} = P_{σ}^{- 1}$
が成り立つ．

作用

$σ \in S_{n}$ とする．

$x = \sum_{i} ϵ_{i} x_{i} \in C^{n}$ に対して
$p_{σ} x = \sum_{i = 1}^{n} (p_{σ} ϵ_{i}) x_{i} = \sum_{i = 1}^{n} ϵ_{σ (i)} x_{i} = \sum_{i = 1}^{n} ϵ_{i} x_{σ^{- 1} (i)}$
が成り立つので，置換行列 $P_{σ}$ による列ベクトルへの作用は
$P_{σ} [\begin{matrix} x_{1} \\ ⋮ \\ x_{n} \end{matrix}] = [\begin{matrix} x_{σ^{- 1} (1)} \\ ⋮ \\ x_{σ^{- 1} (n)} \end{matrix}]$
で与えられる（cf. [7]例11）．したがって
$P_{σ^{- 1}} [\begin{matrix} a_{1, 1} & \dots & a_{1, m} \\ ⋮ & ⋱ & ⋮ \\ a_{n, 1} & \dots & a_{n, m} \end{matrix}] = [\begin{matrix} a_{σ (1), 1} & \dots & a_{σ (1), m} \\ ⋮ & ⋱ & ⋮ \\ a_{σ (n), 1} & \dots & a_{σ (n), m} \end{matrix}]$
が成り立つ（行ベクトルの入れ替え）．

$A \in Mat (m, n; C)$ に対して
$\begin{aligned} (A P_{σ}) (i, j) & = \sum_{k = 1}^{n} A (i, k) P_{σ} (k, j) \\ = \sum_{k = 1}^{n} A (i, k) δ_{k, σ (j)} \\ = A (i, σ (j)) \end{aligned}$
が成り立つ．したがって， $\cdot P_{σ}$ は $A$ の列ベクトルを入れ替える：
$A = [\begin{matrix} \hat{A} (1) & \dots & \hat{A} (n) \end{matrix}] ⟹ A P_{σ} = [\begin{matrix} \hat{A} (σ (1)) & \dots & \hat{A} (σ (n)) \end{matrix}] .$

固有多項式

置換 $σ \in S_{n}$ の巡回置換分解に現れる長さ $ℓ \in {2, \dots, n}$ の巡回置換の個数を $N_{ℓ} \in {0, \dots, n}$ とおくと，線型変換 $p_{σ}$ の固有多項式 $f_{σ}$ は
$f_{σ} (t) = (t - 1)^{tr p_{σ}} \cdot \prod_{ℓ = 2}^{n} (t^{ℓ} - 1)^{N_{ℓ}}$
で与えられる．

“長さ $1$ の巡回置換”も考えて
$N_{1} : = # {i \in {1, \dots, n} : σ (i) = i}$
とおくと， $N_{1} = tr p_{σ}$ であったから，
$f_{σ} (t) = \prod_{ℓ = 1}^{n} (t^{ℓ} - 1)^{N_{ℓ}}$
とまとめられる．

Step 1.

正整数 $ℓ \in N_{> 0}$ に対して $ℓ$ 次置換行列 $C_{ℓ} \in Perm (ℓ)$ を
$C_{ℓ} : = P ((12 \dots ℓ)) = [\begin{matrix} 0 & 0 & \dots & 0 & 1 \\ 1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 0 & 0 & \dots & 1 & 0 \end{matrix}]$
で定めると，
$\begin{aligned} \det (t I_{ℓ} - C_{ℓ}) & = \det [\begin{array}{c} t & 0 & \dots & 0 & - 1 \\ - 1 & t & \dots & 0 & 0 \\ 0 & - 1 & \dots & 0 & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 0 & 0 & \dots & - 1 & t \end{array}] \\ = t \cdot \det [\begin{array}{c} t & \dots & 0 & 0 \\ - 1 & \dots & 0 & 0 \\ ⋮ & ⋱ & ⋮ & ⋮ \\ 0 & \dots & - 1 & t \end{array}] + (- 1)^{1 + ℓ} (- 1) \cdot \det [\begin{array}{c} - 1 & t & \dots & 0 \\ 0 & - 1 & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & - 1 \end{array}] \\ = t \cdot t^{ℓ - 1} + (- 1)^{1 + ℓ} (- 1) \cdot (- 1)^{ℓ - 1} \\ = t^{ℓ} - 1 \end{aligned}$
が成り立つ．

Step 2.

置換 $σ \in S_{n}$ の“広義”巡回置換分解を
$σ = σ_{ℓ_{1}} \dots σ_{ℓ_{m}}$
とする：
$σ_{ℓ_{j}} : = (i_{1, j} \dots i_{ℓ_{j}, j}), 1 \leq j \leq m, 1 \leq ℓ_{j} \leq n .$
このとき， $C^{n}$ の基底 $(ϵ_{i_{1, 1}}, \dots, ϵ_{i_{ℓ_{1}, 1}}, \dots, ϵ_{i_{1, m}}, \dots, ϵ_{i_{ℓ_{m}, m}})$ に関する $p_{σ}$ の表現行列は
$C_{ℓ_{1}} \oplus \dots \oplus C_{ℓ_{m}}$
となる．したがって
$\begin{aligned} f_{σ} (t) & = \det (t I_{n} - (C_{ℓ_{1}} \oplus \dots \oplus C_{ℓ_{m}})) \\ = \det ((t I_{ℓ_{1}} - C_{ℓ_{1}}) \oplus \dots \oplus (t I_{ℓ_{m}} - C_{ℓ_{m}})) \\ = \prod_{j = 1}^{m} \det (t I_{ℓ_{j}} - C_{ℓ_{j}}) \\ = \prod_{j = 1}^{m} (t^{ℓ_{j}} - 1) \\ = \prod_{ℓ = 1}^{n} (t^{ℓ} - 1)^{# {j \in {1, \dots, m} : ℓ_{j} = ℓ}} \\ = \prod_{ℓ = 1}^{n} (t^{ℓ} - 1)^{N_{ℓ}} \end{aligned}$
が成り立つ．

$σ : = (13) (24) \in S_{4}$ とおく．このとき
$P_{σ} = [\begin{matrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{matrix}]$
より
$\begin{aligned} f_{σ} (t) & = \det [\begin{array}{c} t & 0 & - 1 & 0 \\ 0 & t & 0 & - 1 \\ - 1 & 0 & t & 0 \\ 0 & - 1 & 0 & t \end{array}] \\ = t \cdot \det [\begin{array}{c} t & 0 & - 1 \\ 0 & t & 0 \\ - 1 & 0 & t \end{array}] + (- 1) \cdot \det [\begin{array}{c} 0 & t & - 1 \\ - 1 & 0 & 0 \\ 0 & - 1 & t \end{array}] \\ = t (t^{3} - t) - (- 1 + t^{2}) \\ = t^{4} - 2 t^{2} + 1 \\ = (t^{2} - 1)^{2} \end{aligned}$
となるので，確かに
$f_{σ} (t) = \prod_{ℓ = 1}^{4} (t^{ℓ} - 1)^{N_{ℓ}}$
が成り立っている．

最小多項式

置換 $σ \in S_{n}$ の巡回置換分解を
$σ = σ_{ℓ_{1}} \dots σ_{ℓ_{m}}$
とすると，線型変換 $p_{σ}$ の最小多項式 $μ_{σ}$ は
$μ_{σ} = \prod {Φ_{k} : \exists j \in {1, \dots, m}, k ∣ ℓ_{j}}$
で与えられる．ただし $Φ_{k}$ は $k$ 番目の円分多項式である．

Step 1.

$ℓ$ 次置換行列 $C_{ℓ} \in Perm (ℓ)$ の最小多項式 $μ_{ℓ} : = μ_{(12 \dots ℓ)}$ は
$μ_{ℓ} (t) = t^{ℓ} - 1 = \prod_{k ∣ ℓ} Φ_{k} (t)$
で与えられる．実際，

$C_{ℓ}^{ℓ} = I_{ℓ}$ より $μ_{ℓ} (t) ∣ t^{ℓ} - 1$ を得る．
$\deg μ_{ℓ} \leq ℓ - 1$ として
$μ_{ℓ} (t) = a_{ℓ - 1} t^{ℓ - 1} + \dots + a_{1} t + a_{0}$
とおくと，
$\begin{aligned} 0 & = μ_{ℓ} (C_{ℓ}) ϵ_{1} \\ = (a_{ℓ - 1} C_{ℓ}^{ℓ - 1} + \dots + a_{1} C_{ℓ} + a_{0} I_{ℓ}) ϵ_{1} \\ = a_{ℓ - 1} ϵ_{ℓ} + \dots + a_{1} ϵ_{2} + a_{0} ϵ_{1} \end{aligned}$
より
$a_{ℓ - 1} = \dots = a_{1} = a_{0} = 0$
が得られるが，これは不合理である．

Step 2.

$C^{n}$ の適当な基底に関する $p_{σ}$ の表現行列は
$I_{ℓ_{0}} \oplus C_{ℓ_{1}} \oplus \dots \oplus C_{ℓ_{m}}$
となる（のだった）．よって
$\begin{aligned} μ_{σ} & = LCM {μ_{1}, μ_{ℓ_{1}}, \dots, μ_{ℓ_{m}}} \\ = LCM {Φ_{1}, \prod_{k_{1} ∣ ℓ_{1}} Φ_{k_{1}}, \dots, \prod_{k_{m} ∣ ℓ_{m}} Φ_{k_{m}}} \\ = \prod {Φ_{k} : \exists j \in {1, \dots, m}, k ∣ ℓ_{j}} \end{aligned}$
が成り立つ．

$σ : = (23) (456) \in S_{6}$ とおく．このとき，
$\begin{aligned} P_{σ} & = I_{1} \oplus C_{2} \oplus C_{3}; \\ P_{σ}^{2} & = I_{1} \oplus I_{2} \oplus C_{3}^{2}; \\ P_{σ}^{3} & = I_{1} \oplus C_{2} \oplus I_{3}; \\ P_{σ}^{4} & = I_{1} \oplus I_{2} \oplus C_{3}; \end{aligned}$
より
$P_{σ}^{4} + P_{σ}^{3} = P_{σ} + I_{6}$
が成り立つので
$μ_{σ} (t) ∣ t^{4} + t^{3} - t - 1$
を得る．ここで， $\deg μ_{σ} \leq 3$ として
$μ_{σ} (t) : = a t^{3} + b t^{2} + c t + d$
とおくと，
$O_{6} = μ_{σ} (P_{σ}) = a P_{σ}^{3} + b P_{σ}^{2} + c P_{σ} + d I_{6}$
であるから，
$\begin{aligned} 0 & = (a P_{σ}^{3} + b P_{σ}^{2} + c P_{σ} + d I_{6}) ϵ_{4} \\ = a ϵ_{4} + b ϵ_{6} + c ϵ_{5} + d ϵ_{4} \end{aligned}$
より $b = c = 0$ が得られ，
$0 = (a P_{σ}^{3} + d I_{6}) ϵ_{2} = a ϵ_{3} + d ϵ_{2}$
より $a = d = 0$ が得られるが，これは不合理である．ところで
$Φ_{1} (t) Φ_{2} (t) Φ_{3} (t) = (t - 1) (t + 1) (t^{2} + t + 1) = t^{4} + t^{3} - t - 1$
であるから，確かに
$μ_{σ} = Φ_{1} Φ_{2} Φ_{3}$
が成り立っている．

任意の置換行列は $C$ 上対角化可能である．
置換行列 $P_{σ}$ が $R$ 上対角化可能であるためには， $σ^{2} = id$ が成り立つことが必要かつ十分である．

固有値と固有ベクトル

置換 $σ \in S_{n}$ の巡回置換分解を
$σ = σ_{ℓ_{1}} \dots σ_{ℓ_{m}}$
とすると，線型変換 $p_{σ}$ の固有値全体のなす集合は
${1 の原始 k 乗根 : \exists j \in {1, \dots, m}, k ∣ ℓ_{j}}$
に一致する．

$ζ_{ℓ} \in C$ を $1$ の原始 $ℓ$ 乗根（のひとつ）とし，
$v_{ℓ}^{k} : = [\begin{matrix} ζ_{ℓ}^{ℓ k} \\ ζ_{ℓ}^{(ℓ - 1) k} \\ ⋮ \\ ζ_{ℓ}^{2 k} \\ ζ_{ℓ}^{k} \end{matrix}] \in C^{ℓ}, 1 \leq k \leq ℓ$
とおくと，
$C_{ℓ} v_{ℓ}^{k} = [\begin{matrix} ζ_{ℓ}^{k} \\ ζ_{ℓ}^{ℓ k} \\ ζ_{ℓ}^{(ℓ - 1) k} \\ ⋮ \\ ζ_{ℓ}^{2 k} \end{matrix}] = ζ_{ℓ}^{k} v_{ℓ}^{k}$
が成り立つ．したがって $v_{ℓ}^{1}, v_{ℓ}^{2}, \dots, v_{ℓ}^{ℓ}$ はそれぞれ相異なる固有値 $ζ_{ℓ}, ζ_{ℓ}^{2}, \dots, ζ_{ℓ}^{ℓ} = 1$ に属する $C_{ℓ}$ の固有ベクトルであるから， $(v_{ℓ}^{1}, v_{ℓ}^{2}, \dots, v_{ℓ}^{ℓ})$ は（ $C$ 上）線型独立である（ヴァンデルモンドの行列式からもわかる）．
$σ \in S_{n}$ の（“広義”）巡回置換分解を
$σ = σ_{ℓ_{1}} \dots σ_{ℓ_{m}}, σ_{ℓ_{j}} : = (i_{1, j} \dots i_{ℓ_{j}, j})$
とする．このとき
$w_{σ_{ℓ_{j}}}^{k} : = ϵ_{i_{1, j}} ζ_{ℓ_{j}}^{ℓ_{j} k} + ϵ_{i_{2, j}} ζ_{ℓ_{j}}^{(ℓ_{j} - 1) k} + \dots + ϵ_{i_{ℓ_{j} - 1}, j} ζ_{ℓ_{j}}^{2 k} + ϵ_{i_{ℓ_{j}, j}} ζ_{ℓ_{j}}^{k} \in C^{n}$
とおくと，
$\begin{aligned} p_{σ} w_{σ_{ℓ_{j}}}^{k} & = (p_{σ} ϵ_{i_{1, j}}) ζ_{ℓ_{j}}^{ℓ_{j} k} + (p_{σ} ϵ_{i_{2, j}}) ζ_{ℓ_{j}}^{(ℓ_{j} - 1) k} + \dots + (p_{σ} ϵ_{i_{ℓ_{j} - 1}, j}) ζ_{ℓ_{j}}^{2 k} + (p_{σ} ϵ_{i_{ℓ_{j}, j}}) ζ_{ℓ_{j}}^{k} \\ = ϵ_{i_{2, j}} ζ_{ℓ_{j}}^{ℓ_{j} k} + ϵ_{i_{3, j}} ζ_{ℓ_{j}}^{(ℓ_{j} - 1) k} + \dots + ϵ_{i_{ℓ_{j}, j}} ζ_{ℓ_{j}}^{2 k} + ϵ_{i_{1, j}} ζ_{ℓ_{j}}^{k} \\ = ζ_{ℓ_{j}}^{k} (ϵ_{i_{1, j}} ζ_{ℓ_{j}}^{ℓ_{j} k} + ϵ_{i_{2, j}} ζ_{ℓ_{j}}^{(ℓ_{j} - 1) k} + \dots + ϵ_{i_{ℓ_{j} - 1}, j} ζ_{ℓ_{j}}^{2 k} + ϵ_{i_{ℓ_{j}, j}} ζ_{ℓ_{j}}^{k}) \\ = ζ_{ℓ_{j}}^{k} w_{σ_{ℓ_{j}}}^{k} \end{aligned}$
が成り立つ．

$σ_{1} : = (23) (465) \in S_{6}$ とおく．このとき
$\begin{aligned} p_{σ_{1}} ϵ_{1} & = ϵ_{1}; \\ p_{σ_{1}} (ϵ_{2} - ϵ_{3}) & = ϵ_{3} - ϵ_{2} = - (ϵ_{2} - ϵ_{3}); \\ p_{σ_{1}} (ϵ_{2} + ϵ_{3}) & = ϵ_{2} + ϵ_{3}; \\ p_{σ_{1}} (ϵ_{4} + ω^{2} ϵ_{6} + ω ϵ_{5}) & = ϵ_{6} + ω^{2} ϵ_{5} + ω ϵ_{4} = ω (ϵ_{4} + ω^{2} ϵ_{6} + ω ϵ_{5}); \\ p_{σ_{1}} (ϵ_{4} + ω ϵ_{6} + ω^{2} ϵ_{5}) & = ϵ_{6} + ω ϵ_{5} + ω^{2} ϵ_{4} = ω^{2} (ϵ_{4} + ω ϵ_{6} + ω^{2} ϵ_{5}); \\ p_{σ_{1}} (ϵ_{4} + ϵ_{6} + ϵ_{5}) & = ϵ_{4} + ϵ_{6} + ϵ_{5}; \end{aligned}$
が成り立つ（ただし $ω : = ζ_{3}$ である）．そこで
$A_{1} : = [\begin{matrix} 1 \\ 1 & 1 \\ - 1 & 1 \\ 1 & 1 & 1 \\ ω & ω^{2} & 1 \\ ω^{2} & ω & 1 \end{matrix}]$
とおくと， $A_{1} \in GL (6, C)$ であって
$P_{σ_{1}} A_{1} = A_{1} [\begin{matrix} 1 \\ - 1 \\ 1 \\ ω \\ ω^{2} \\ 1 \end{matrix}]$
が成り立つ．
$σ_{2} : = (13) (24) \in S_{4}$ とおく．このとき
$\begin{aligned} p_{σ_{2}} (ϵ_{1} - ϵ_{3}) & = ϵ_{3} - ϵ_{1} = - (ϵ_{1} - ϵ_{3}); \\ p_{σ_{2}} (ϵ_{1} + ϵ_{3}) & = ϵ_{1} + ϵ_{3}; \\ p_{σ_{2}} (ϵ_{2} - ϵ_{4}) & = ϵ_{4} - ϵ_{2} = - (ϵ_{2} - ϵ_{4}); \\ p_{σ_{2}} (ϵ_{2} + ϵ_{4}) & = ϵ_{2} + ϵ_{4}; \end{aligned}$
が成り立つ．そこで
$\begin{array}{r} A_{2} : = [\begin{array}{c} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ - 1 & 1 & 0 & 0 \\ 0 & 0 & - 1 & 1 \end{array}] \end{array}$
とおくと， $A_{2} \in GL (4, R)$ であって
$P_{σ_{2}} A_{2} = A_{2} [\begin{matrix} - 1 \\ 1 \\ - 1 \\ 1 \end{matrix}]$
が成り立つ．
$σ_{3} : = (12) (3456) \in S_{6}$ とおく．このとき
$\begin{aligned} p_{σ_{3}} (ϵ_{1} - ϵ_{2}) & = - (ϵ_{1} - ϵ_{2}); \\ p_{σ_{3}} (ϵ_{1} + ϵ_{2}) & = ϵ_{1} + ϵ_{2}; \\ p_{σ_{3}} (ϵ_{3} - \sqrt{- 1} ϵ_{4} - ϵ_{5} + \sqrt{- 1} ϵ_{6}) & = \sqrt{- 1} (ϵ_{3} - \sqrt{- 1} ϵ_{4} - ϵ_{5} + \sqrt{- 1} ϵ_{6}); \\ p_{σ_{3}} (ϵ_{3} - ϵ_{4} + ϵ_{5} - ϵ_{6}) & = - (ϵ_{3} - ϵ_{4} + ϵ_{5} - ϵ_{6}); \\ p_{σ_{3}} (ϵ_{3} + \sqrt{- 1} ϵ_{4} - ϵ_{5} - \sqrt{- 1} ϵ_{6}) & = - \sqrt{- 1} (ϵ_{3} + \sqrt{- 1} ϵ_{4} - ϵ_{5} - \sqrt{- 1} ϵ_{6}); \\ p_{σ_{3}} (ϵ_{3} + ϵ_{4} + ϵ_{5} + ϵ_{6}) & = ϵ_{3} + ϵ_{4} + ϵ_{5} + ϵ_{6}; \end{aligned}$
が成り立つ．そこで
$A_{3} : = [\begin{matrix} 1 & 1 \\ - 1 & 1 \\ 1 & 1 & 1 & 1 \\ - \sqrt{- 1} & - 1 & \sqrt{- 1} & 1 \\ - 1 & 1 & - 1 & 1 \\ \sqrt{- 1} & - 1 & - \sqrt{- 1} & 1 \end{matrix}]$
とおくと， $A_{3} \in GL (6, C)$ であって
$P_{σ_{3}} A_{3} = A_{3} [\begin{matrix} - 1 \\ 1 \\ \sqrt{- 1} \\ - 1 \\ - \sqrt{- 1} \\ 1 \end{matrix}]$
が成り立つ．

附：巡回行列

$a = \sum_{i} ϵ_{i} a_{i - 1} \in C^{n}$ に対して，多項式
$Γ_{a} (t) : = a_{0} + a_{1} t + \dots + a_{n - 1} t^{n - 1}$
に置換行列 $C_{n}$ を代入して得られる $n$ 次正方行列
$Γ_{a} (C_{n}) = a_{0} I_{n} + a_{1} C_{n} + \dots + a_{n - 1} C_{n}^{n - 1} = [\begin{matrix} a_{0} & a_{n - 1} & \dots & a_{2} & a_{1} \\ a_{1} & a_{0} & ⋱ & a_{2} \\ a_{2} & ⋱ & ⋱ & ⋱ & ⋮ \\ ⋮ & ⋱ & ⋱ & ⋱ & a_{n - 1} \\ a_{n - 1} & \dots & a_{2} & a_{1} & a_{0} \end{matrix}]$
を， $a$ から定まる巡回行列という．

$a = \sum_{i} ϵ_{i} a_{i - 1} \in C^{n}$ から定まる巡回行列 $Γ_{a} (C_{n})$ のディターミナントは
$Γ_{a} (1) Γ_{a} (ζ_{n}) \dots Γ_{a} (ζ_{n}^{n - 1})$
に等しい．

可逆行列 $Z \in GL (n, C)$ を
$Z (j, k) : = ζ_{n}^{(n - j + 1) k} ⇝ \hat{Z} (k) = [\begin{matrix} ζ_{n}^{n k} \\ ζ_{n}^{(n - 1) k} \\ ⋮ \\ ζ_{n}^{2 k} \\ ζ_{n}^{k} \end{matrix}] = v_{n}^{k}$
で定める．このとき
$\begin{aligned} Γ_{a} (C_{n}) \hat{Z} (k) & = (a_{0} I_{n} + a_{1} C_{n} + \dots + a_{n - 1} C_{n}^{n - 1}) v_{n}^{k} \\ = a_{0} v_{n}^{k} + a_{1} ζ_{n}^{k} v_{n}^{k} + \dots + a_{n - 1} (ζ_{n}^{k})^{n - 1} v_{n}^{k} \\ = (a_{0} + a_{1} ζ_{n}^{k} + \dots + a_{n - 1} (ζ_{n}^{k})^{n - 1}) v_{n}^{k} \\ = Γ_{a} (ζ_{n}^{k}) v_{n}^{k} \\ = Γ_{a} (ζ_{n}^{k}) \hat{Z} (k) \end{aligned}$
より
$Γ_{a} (C_{n}) Z = Z [\begin{matrix} Γ_{a} (ζ_{n}) \\ ⋱ \\ Γ_{a} (ζ_{n}^{n - 1}) \\ Γ_{a} (ζ_{n}^{n}) \end{matrix}]$
となるので，
$\det Γ_{a} (C_{n}) = Γ_{a} (1) Γ_{a} (ζ_{n}) \dots Γ_{a} (ζ_{n}^{n - 1})$
が成り立つ．

巡回行列 $Γ_{a} (C_{n})$ の固有値は
$Γ_{a} (1), Γ_{a} (ζ_{n}), \dots, Γ_{a} (ζ_{n}^{n - 1})$
であり，固有値 $Γ_{a} (ζ_{n}^{k}), 0 \leq k \leq n - 1,$ に属する固有ベクトル（のひとつ）は
$[\begin{matrix} 1 \\ ζ_{n}^{(n - 1) k} \\ ⋮ \\ ζ_{n}^{2 k} \\ ζ_{n}^{k} \end{matrix}]$
である．

$Γ_{a} (ζ_{n}^{k})$ は相異なるとは限らない．たとえば $a : = (1, 1, ω)$ とおくと，
$Γ_{a} (1) = 1 + 1 \cdot 1^{1} + ω \cdot 1^{2} = 2 + ω = 1 + 1 \cdot ω^{1} + ω \cdot ω^{2} = Γ_{a} (ω)$
が成り立つ．

$a : = ϵ_{1} x + ϵ_{2} y \in C^{2}$ とおくと， $Γ_{a} (t) = x + y t$ より
$\det Γ_{a} (C_{2}) = Γ_{a} (1) Γ_{a} (- 1) = (x + y) (x - y)$
となるが，一方
$\det Γ_{a} (C_{2}) = \det [\begin{matrix} x & y \\ y & x \end{matrix}] = x^{2} - y^{2}$
であるから，
$x^{2} - y^{2} = (x + y) (x - y)$
が成り立つ．
$b : = ϵ_{1} x + ϵ_{2} y + ϵ_{3} z \in C^{3}$ とおくと， $Γ_{b} (t) = x + y t + z t^{2}$ より
$\det Γ_{b} (C_{3}) = Γ_{b} (1) Γ_{b} (ω) Γ_{b} (ω^{2}) = (x + y + z) (x + y ω + z ω^{2}) (x + y ω^{2} + z ω)$
となるが，一方
$\det Γ_{b} (C_{3}) = \det [\begin{matrix} x & z & y \\ y & x & z \\ z & y & x \end{matrix}] = x^{3} + y^{3} + z^{3} - 3 x y z$
であるから，
$\begin{aligned} x^{3} + y^{3} + z^{3} - 3 x y z & = (x + y + z) (x + y ω + z ω^{2}) (x + y ω^{2} + z ω) \\ = (x + y + z) (x^{2} + y^{2} + z^{2} + (ω + ω^{2}) (x y + y z + z x)) \\ = (x + y + z) (x^{2} + y^{2} + z^{2} - x y - y z - z x) \end{aligned}$
が成り立つ．

附：二重確率行列

$n \in N_{> 0}$ とし $ϵ : = \sum_{j} ϵ_{j} \in R^{n}$ とおく．このとき，集合
$DS (n) : = {S \in Mat (n, n; R) : S (i, j) \geq 0, S ϵ = ϵ = S^{T} ϵ}$
の元を二重確率行列という．

単位行列は二重確率行列である．
二重確率行列の積は二重確率行列である．実際， $S, T \in DS (n)$ とすると，
$\begin{aligned} (S T) (i, j) & = \sum_{k = 1}^{n} S (i, k) T (k, j) \geq 0; \\ (S T) ϵ & = S (T ϵ) = S ϵ = ϵ; \\ (S T)^{T} ϵ & = T^{T} (S^{T} ϵ) = T^{T} ϵ = ϵ; \end{aligned}$
が成り立つので， $S T \in DS (n)$ を得る．

置換行列 $P_{σ} \in Perm (n)$ は二重確率行列である．実際，明らかに
$P_{σ} (i, j) = δ_{i, σ (j)} \geq 0, P_{σ} ϵ = \sum_{j = 1}^{n} ϵ_{σ (j)} = ϵ$
が成り立ち，さらに
$P_{σ}^{T} ϵ = P_{σ^{- 1}} ϵ = ϵ$
も成り立つ．

置換行列の凸結合は二重確率行列である：
$\forall (a_{σ})_{σ} \in [0, 1]^{S_{n}}, \sum_{σ \in S_{n}} a_{σ} = 1 ⟹ S : = \sum_{σ \in S_{n}} a_{σ} P_{σ} \in DS (n) .$
実際，明らかに $S (i, j) \geq 0$ であり，例10より
$S ϵ = \sum_{σ \in S_{n}} a_{σ} P_{σ} ϵ = \sum_{σ \in S_{n}} a_{σ} ϵ = (\sum_{σ \in S_{n}} a_{σ}) ϵ = ϵ,$
および
$S^{T} ϵ = \sum_{σ \in S_{n}} a_{σ} P_{σ}^{T} ϵ = \sum_{σ \in S_{n}} a_{σ} ϵ = (\sum_{σ \in S_{n}} a_{σ}) ϵ = ϵ$
が成り立つ．

$S \in Mat (n, n; R)$ とする．このとき次は同値である：

$S$ は置換行列の凸結合で書ける；
任意の $A \in Mat (n, n; R)$ に対して
$\sum_{i, j = 1}^{n} A (i, j) S (i, j) \leq max_{σ \in S_{n}} \sum_{i = 1}^{n} A (i, σ (i)) (= max_{σ \in S_{n}} tr (A P_{σ}))$
が成り立つ．

不等式の左辺は $A$ と $S$ とのFrobenius内積である（cf. [6]例7）：
$\sum_{i, j = 1}^{n} A (i, j) S (i, j) = tr (A S^{T}) = ⟨ A ∣ S ⟩ .$

まづ
$Conv (Perm (n)) : = {X \in Mat (n, n; R) : \exists (a_{σ})_{σ} \in [0, 1]^{S_{n}}, \sum_{σ \in S_{n}} a_{σ} = 1, X = \sum_{σ \in S_{n}} a_{σ} P_{σ}}$
とおき，写像 $h : Mat (n, n; R) \to R$ を
$h (A) : = max_{σ \in S_{n}} ⟨ A ∣ P_{σ} ⟩ = sup {⟨ A ∣ X ⟩ : X \in Conv (Perm (n))}$
で定める（これを $Conv (Perm (n))$ の支持函数（support function）という）．このとき
$Conv (Perm (n)) = {S \in Mat (n, n; R) : \forall A \in Mat (n, n; R), ⟨ A ∣ S ⟩ \leq h (A)}$
が成り立つことを示せばよい．

$S \in Conv (Perm (n))$ とすると， $S = \sum_{σ \in S_{n}} a_{σ} P_{σ}, a_{σ} \in [0, 1], \sum_{σ \in S_{n}} a_{σ} = 1$
と書けるので，任意の $A \in Mat (n, n; R)$ に対して
$⟨ A ∣ S ⟩ = \sum_{σ \in S_{n}} a_{σ} ⟨ A ∣ P_{σ} ⟩ \leq \sum_{σ \in S_{n}} a_{σ} h (A) = h (A)$
が成り立つ．
$S \notin Conv (Perm (n))$ とする．いま $Conv (Perm (n))$ は $R^{n!}$ から $Mat (n, n; R)$ への連続写像
$(a_{σ})_{σ} \mapsto \sum_{σ \in S_{n}} a_{σ} P_{σ}$
による $(n! - 1)$ 単体の像なのでコンパクトであり，したがって $X_{0} \in Conv (Perm (n))$ であって
$∥ S - X_{0} ∥ = dist (S, Conv (Perm (n))) > 0$
を満たすものが存在する．そこで $A_{0} : = S - X_{0} (\neq O_{n})$ とおくと，
$⟨ A_{0} ∣ S ⟩ - ⟨ A_{0} ∣ X_{0} ⟩ = ⟨ A_{0} ∣ S - X_{0} ⟩ = ∥ S - X_{0} ∥^{2} > 0 ⇝ ⟨ A_{0} ∣ S ⟩ > ⟨ A_{0} ∣ X_{0} ⟩$
が成り立つ．あとは任意の $σ \in S_{n}$ に対して
$⟨ A_{0} ∣ X_{0} ⟩ \geq ⟨ A_{0} ∣ P_{σ} ⟩$
が成り立つことを示せばよい．ところで $σ \in S_{n}$ とすると，任意の $r \in] 0, 1]$ に対して， $(1 - r) X_{0} + r P_{σ} \in Conv (Perm (n))$ より，
$\begin{aligned} ∥ A_{0} ∥^{2} & = ∥ S - X_{0} ∥^{2} \\ \leq ∥ S - ((1 - r) X_{0} + r P_{σ}) ∥^{2} \\ = ∥ A_{0} - r (P_{σ} - X_{0}) ∥^{2} \\ = ∥ A_{0} ∥^{2} - 2 r ⟨ A_{0} ∣ P_{σ} - X_{0} ⟩ + r^{2} ∥ P_{σ} - X_{0} ∥^{2} \end{aligned}$
が成り立つので，
$⟨ A_{0} ∣ P_{σ} ⟩ - ⟨ A_{0} ∣ X_{0} ⟩ \leq \frac{r}{2} ∥ P_{σ} - X_{0} ∥^{2} \to 0 (r \to 0)$
を得る．

Birkhoff–von Neumann

任意の二重確率行列は置換行列の凸結合で書ける．

[1]

Step 1.

任意の $S \in DS (n) ∖ {I_{n}}$ に対して， $σ_{S} \in S_{n} ∖ {id}$ であって
$0 \notin {S (i, σ_{S} (i)) : 1 \leq i \leq n, i \neq σ_{S} (i)}$
なるものが存在することを示す．

$n = 1$ のときは自明に成り立つ．
$S \in DS (n + 1) ∖ {I_{n + 1}}$ とし，
$\forall σ \in S_{n + 1} ∖ {id}, 0 \in {S (i, σ (i)) : 1 \leq i \leq n + 1, i \neq σ (i)}$
が成り立ったと仮定する．このとき， $S$ の固有多項式 $f_{S}$ は
$f_{S} (t) = (t - S (1, 1)) \dots (t - S (n + 1, n + 1)) + \sum_{σ \in S_{n + 1} ∖ {id}} sgn (σ) \cdot (t δ_{1, σ (1)} - S (1, σ (1))) \dots (t δ_{n + 1, σ (n + 1)} - S (n + 1, σ (n + 1)))$
で与えられるが，各 $σ \in S_{n + 1} ∖ {id}$ に対して， $i_{σ} \in {1, \dots, n + 1}$ であって
$i_{σ} \neq σ (i_{σ}), S (i_{σ}, σ (i_{σ})) = 0 ⇝ t δ_{i_{σ}, σ (i_{σ})} - S (i_{σ}, σ (i_{σ})) = 0$
なるものが存在するので，上式第 $2$ 項は $0$ となり，
$f_{S} (t) = (t - S (1, 1)) \dots (t - S (n + 1, n + 1))$
が成り立つ．ところで，二重確率行列 $S$ は固有値 $1$ を持つので， $i_{0} \in {1, \dots, n + 1}$ であって $S (i_{0}, i_{0}) = 1$ なるものが存在し，したがって
$S = [\begin{matrix} 0 \\ ⋮ \\ 0 \\ 0 & \dots & 0 & 1 & 0 & \dots & 0 \\ 0 \\ ⋮ \\ 0 \end{matrix}]$
となる．よって $S$ の第 $i_{0}$ 行と第 $i_{0}$ 列を取り除いてできる $n$ 次正方行列を $S_{0}$ とおくと， $S_{0} \in DS (n) ∖ {I_{n}}$ であるから，数学的帰納法の仮定より $σ_{0} \in S_{n + 1} ∖ {id}$ であって
$σ_{0} (i_{0}) = i_{0}, 0 \notin {S (i, σ_{0} (i)) : 1 \leq i \leq n + 1, i \neq i_{0}, i \neq σ_{0} (i)},$
すなわち
$0 \notin {S (i, σ_{0} (i)) : 1 \leq i \leq n + 1, i \neq σ_{0} (i)}$
を満たすものが存在するが，これは不合理である．

Step 2.

$S \in DS (n)$ とする．このとき任意の $A \in Mat (n, n; R)$ に対して
$\sum_{i, j = 1}^{n} A (i, j) S (i, j) \leq max_{σ \in S_{n}} \sum_{i = 1}^{n} A (i, σ (i))$
が成り立つことを示せばよい（cf. 補題1）．

そこで $A \in Mat (n, n; R)$ とし $τ \in S_{n}$ であって
$max_{σ \in S_{n}} \sum_{i = 1}^{n} A (i, σ (i)) = \sum_{i = 1}^{n} A (i, τ (i)) = tr (A P_{τ})$
なるものを取る．いま $S P_{τ} \in DS (n)$ であり，系1より
$⟨ A ∣ S ⟩ = tr (A S^{T}) = tr ((A P_{τ}) (P_{τ}^{T} S^{T})) = tr ((A P_{τ}) (S P_{τ})^{T}) = ⟨ A P_{τ} ∣ S P_{τ} ⟩$
であるから， $τ = id$ としてよい：
$\forall σ \in S_{n}, tr (A P_{σ}) \leq tr A .$
さて， $r \in R_{> 0}$ とし
$A_{r} : = A + r I_{n} \in Mat (n, n; R)$
とおく．このとき，任意の $σ \in S_{n} ∖ {id}$ に対して
$\begin{aligned} tr A_{r} - tr (A_{r} P_{σ}) & = (tr A - tr (A P_{σ})) + r n - r tr P_{σ} \\ \geq r n - r (n - 1) \\ = r \end{aligned}$
が成り立つ．
つぎに， $r \in R_{> 0}$ とし， $T_{0} \in DS (n)$ であって
$sup_{T \in DS (n)} ⟨ A_{r} ∣ T ⟩ = ⟨ A_{r} ∣ T_{0} ⟩$
を満たすものを考える（注意： $DS (n) \subset Mat (n, n; R)$ は有界閉集合なので，このような $T_{0}$ は存在する）．もし $T_{0} \neq I_{n}$ であるとすると，前段より $τ_{0} \in S_{n} ∖ {id}$ であって
$0 \notin {T_{0} (i, τ_{0} (i)) : 1 \leq i \leq n, i \neq τ_{0} (i)}$
を満たすものが存在する．そこで
$r^{'} : = min {T_{0} (i, τ_{0} (i)) : 1 \leq i \leq n, i \neq τ_{0} (i)} \in R_{> 0}$
とおいて $T_{r^{'}} \in Mat (n, n; R)$ を
$T_{r^{'}} : = T_{0} + r^{'} I_{n} - r^{'} P_{τ_{0}^{- 1}}$
で定めると，
$T_{r^{'}} (i, j) = T_{0} (i, j) + r^{'} δ_{i, j} - r^{'} δ_{τ_{0} (i), j} = {\begin{cases} T_{0} (i, i) + r^{'} & τ_{0} (i) \neq i = j \\ T_{0} (i, τ_{0} (i)) - r^{'} & i \neq τ_{0} (i) = j \\ T_{0} (i, j) & otherwise \end{cases}$
より $T_{r^{'}} (i, j) \geq 0$ であって，
$T_{r^{'}} ϵ = T_{0} ϵ + r^{'} I_{n} ϵ - r^{'} P_{τ_{0}^{- 1}} ϵ = ϵ + r^{'} ϵ - r^{'} ϵ = ϵ = T_{r^{'}}^{T} ϵ$
が成り立つので， $T_{r^{'}} \in DS (n)$ である．ところがこのとき
$\begin{aligned} ⟨ A_{r} ∣ T_{r^{'}} ⟩ - ⟨ A_{r} ∣ T_{0} ⟩ & = ⟨ A_{r} ∣ T_{r^{'}} - T_{0} ⟩ \\ = ⟨ A_{r} ∣ r^{'} I_{n} - r^{'} P_{τ_{0}^{- 1}} ⟩ \\ = r^{'} (⟨ A_{r} ∣ I_{n} ⟩ - ⟨ A_{r} ∣ P_{τ_{0}}^{T} ⟩) \\ = r^{'} (tr A_{r} - tr (A P_{τ_{0}})) \\ \geq r^{'} r \\ > 0 \end{aligned}$
となって $T_{0}$ の取り方に反する．
よって任意の $r \in R_{> 0}$ に対して
$⟨ A ∣ S ⟩ \leq ⟨ A_{r} ∣ S ⟩ \leq ⟨ A_{r} ∣ T_{0} ⟩ = ⟨ A_{r} ∣ I_{n} ⟩ = tr A_{r} = tr A + r n$
が成り立つ．
以上より
$\sum_{i, j = 1}^{n} A (i, j) S (i, j) = ⟨ A ∣ S ⟩ \leq tr A = max_{σ \in S_{n}} \sum_{i = 1}^{n} A (i, σ (i))$
を得る．

正方行列 $A \in Mat (n, n; R)$ に対して
$per A : = \sum_{σ \in S_{n}} A (1, σ (1)) \dots A (n, σ (n))$
を $A$ のパーマネントという．二重確率行列 $S = \sum_{τ} a_{τ} P_{τ} \in DS (n)$ のパーマネントについて，
$S (i, σ (i)) = \sum_{τ \in S_{n}} a_{τ} δ_{i, τ (σ (i))} \geq a_{σ^{- 1}}$
より，
$per S = \sum_{σ \in S_{n}} S (1, σ (1)) \dots S (n, σ (n)) \geq \sum_{σ \in S_{n}} a_{σ^{- 1}} \dots a_{σ^{- 1}} = \sum_{σ \in S_{n}} a_{σ}^{n} > 0$
が成り立つ．よって $σ_{S} \in S_{n}$ であって
$0 \notin {S (1, σ_{S} (1)), \dots, S (n, σ_{S} (n))}$
を満たすもの（すなわち $S P_{σ_{S}}$ の対角成分がすべて正となるもの）が存在する．