共役類ごとにまとめたバーンサイドの補題

$S_{m} \times S_{n}$ による $m \times n$ 行列の行・列の並べ替えのように、作用する群が直積（や転置を加えた拡大）で与えられるとき、群の位数を求め、固定点の個数が共役類（巡回型の組）ごとに一定であることを使って $\frac{1}{∣ G ∣} \sum_{C} ∣ C ∣ ∣ Fix (g_{C}) ∣$ を計算できる。巡回型 $(a_{i})$ , $(b_{j})$ の組が成分に引き起こす巡回の個数 $\sum_{i, j} g cd (a_{i}, b_{j})$ から固定される $0, 1$ 行列の個数を求められる。正方行列で転置を加えたときは、転置を含む元 $(σ, τ) \circ T : (i, j) \mapsto (σ (j), τ (i))$ の成分の巡回の個数が $σ τ$ の巡回型だけで決まることを使える（例: $2 \times 2$ の $0, 1$ 行列の行・列の並べ替えによる類は $7$ 個、 $3 \times 3$ で転置も加えると $26$ 個）

前提

バーンサイドの補題（大学数学離散数学・組合せ論）
対称群の共役類（大学数学代数学）

この技能までの道筋（25 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

約数の見つけ方（算数整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
群の位数と元の位数（大学数学代数学）
置換の巡回置換分解と位数（大学数学代数学）
バーンサイドの補題（大学数学離散数学・組合せ論）
順列・円順列・重複順列（数学A 場合の数と確率）
対称群の共役類（大学数学代数学）

説明

$m \times n$ の $0, 1$ 行列を「行の並べ替え・列の並べ替えで移り合うものは同じ」とみなして数えるように、作用する群が $S_{m} \times S_{n}$ のような直積（正方行列なら転置も加えたもの）であるとき、バーンサイドの補題の和を群の元 1 つずつではなく共役類ごとにまとめて計算できるようになります。各類について「類の元の個数 $\times$ 代表元の固定点の個数」を足し、群の位数で割れば答えが出ます。固定点の個数は、行と列の巡回型から $\sum_{i, j} g cd (a_{i}, b_{j})$ で求めた「成分の巡回の個数」で決まります。

なぜそうしてよいのか

まず、固定点の個数が共役類の上で一定である理由です。 $h \in G$ に対し、 $x$ が $g$ で固定されることと $h x$ が $h g h^{- 1}$ で固定されることは同値なので（ $h g h^{- 1} (h x) = h (g x)$ ）、 $x \mapsto h x$ は $Fix (g)$ から $Fix (h g h^{- 1})$ への全単射です。よって $∣ Fix (g) ∣$ は共役な元で等しく、 $\frac{1}{∣ G ∣} \sum_{g} ∣ Fix (g) ∣ = \frac{1}{∣ G ∣} \sum_{C} ∣ C ∣ ∣ Fix (g_{C}) ∣$ （ $C$ は共役類、 $g_{C}$ はその代表）とまとめられます。直積 $S_{m} \times S_{n}$ では $(α, β) (σ, τ) (α, β)^{- 1} = (α σ α^{- 1}, β τ β^{- 1})$ なので、共役類は「 $S_{m}$ の類と $S_{n}$ の類の組」、つまり巡回型の組で、その元の個数は 2 つの類の大きさの積です。また $∣ S_{m} \times S_{n} ∣ = m! n!$ です。

次に固定点の数え方です。 $(σ, τ)$ は成分の位置 $(i, j)$ を $(σ (i), τ (j))$ に移します。行列がこの並べ替えで変わらないのは、成分の位置の置換の各巡回の上で値が一定のときなので、巡回が $c$ 個あれば固定される $0, 1$ 行列は $2^{c}$ 個です。 $σ$ の長さ $a$ の巡回に属する行と、 $τ$ の長さ $b$ の巡回に属する列が交わる $ab$ 個の位置は互いの間で移り合い、 $(σ, τ)^{k}$ で $(i, j)$ が元に戻るのは $a ∣ k$ かつ $b ∣ k$ 、すなわち $lcm (a, b) ∣ k$ のときです。したがってこの $ab$ 個は長さ $lcm (a, b)$ の巡回に分かれ、その個数は $ab / lcm (a, b) = g cd (a, b)$ です。行の巡回型 $(a_{i})$ 、列の巡回型 $(b_{j})$ のすべての組で足して $c = \sum_{i, j} g cd (a_{i}, b_{j})$ を得ます。

正方行列（ $m = n$ ）で転置 $T$ も加えると群の位数は $2 (n!)^{2}$ になり、転置を含む元 $f = (σ, τ) \circ T : (i, j) \mapsto (σ (j), τ (i))$ が新たに $(n!)^{2}$ 個加わります。行・列の並べ替え $(α, β)$ で共役をとると $(α, β) f (α, β)^{- 1} = (α σ β^{- 1}, β τ α^{- 1}) \circ T$ となり、 $α = e, β = σ$ とすれば $(e, σ τ) \circ T$ に共役です。さらに $α$ を動かすと $σ τ$ は $α (σ τ) α^{- 1}$ に変わるだけなので、 $f$ の成分の巡回の個数は $σ τ$ の巡回型だけで決まり、代表 $(e, ρ) \circ T : (i, j) \mapsto (j, ρ (i))$ で数えれば足ります（ $σ τ$ がある巡回型の類に入る組 $(σ, τ)$ は、その類の大きさの $n!$ 倍あります）。

手順

群とその位数を確定する：行・列の並べ替えだけなら $G = S_{m} \times S_{n}$ , $∣ G ∣ = m! n!$ 。正方行列で転置も加えるなら $∣ G ∣ = 2 (n!)^{2}$
共役類を列挙する： $S_{m}$ の巡回型と $S_{n}$ の巡回型の組ごとに、元の個数（各類の大きさ $\frac{k !}{\prod _{l} l ^{m_{l}} m _{l} !}$ の積）を書く。転置を含む元は $σ τ$ の巡回型ごとに分け、個数は（その類の大きさ） $\times n!$
各類の代表について成分の巡回の個数を求める： $c = \sum_{i, j} g cd (a_{i}, b_{j})$ 。転置を含む元は代表 $(e, ρ) \circ T$ で直接巡回をたどる
固定される行列の個数を $2^{c}$ （ $k$ 色なら $k^{c}$ ）とし、 $∣ C ∣ \cdot 2^{c}$ を表にまとめる
すべての類について足し、 $∣ G ∣$ で割る。結果が整数になることで検算する

例題

成分が $0$ または $1$ の $2 \times 3$ 行列全体に、行の並べ替えと列の並べ替えの群 $S_{2} \times S_{3}$ が作用している。行の並べ替えと列の並べ替えを組み合わせて互いに移り合う行列を同じものとみなすとき、異なる行列は何通りあるか求めよ。

例題の解答

手順 1： $G = S_{2} \times S_{3}$ , $∣ G ∣ = 2! \cdot 3! = 12$ 。

手順 2： $S_{2}$ の巡回型は $1^{2}$ （1 個）と $2$ （1 個）、 $S_{3}$ の巡回型は $1^{3}$ （1 個）、 $1 \cdot 2$ （3 個）、 $3$ （2 個）。組は 6 通りで、元の個数はそれぞれ大きさの積。

手順 3・4：各組で $c = \sum g cd (a_{i}, b_{j})$ と $∣ C ∣ \cdot 2^{c}$ を求める。
- $(1^{2}, 1^{3})$ ： $c = 2 \cdot 3 = 6$ 、 $1 \cdot 2^{6} = 64$
- $(1^{2}, 1 \cdot 2)$ ：各行で $g cd (1, 1) + g cd (1, 2) = 2$ 、 $c = 4$ 、 $3 \cdot 2^{4} = 48$
- $(1^{2}, 3)$ ：各行で $g cd (1, 3) = 1$ 、 $c = 2$ 、 $2 \cdot 2^{2} = 8$
- $(2, 1^{3})$ ： $g cd (2, 1) \cdot 3 = 3$ 、 $c = 3$ 、 $1 \cdot 2^{3} = 8$
- $(2, 1 \cdot 2)$ ： $g cd (2, 1) + g cd (2, 2) = 3$ 、 $c = 3$ 、 $3 \cdot 2^{3} = 24$
- $(2, 3)$ ： $g cd (2, 3) = 1$ 、 $c = 1$ 、 $2 \cdot 2^{1} = 4$
（元の個数の合計 $1 + 3 + 2 + 1 + 3 + 2 = 12 = ∣ G ∣$ で、類の取りこぼしがないことも確認できる。）

手順 5： $\frac{64 + 48 + 8 + 8 + 24 + 4}{12} = \frac{156}{12} = 13.$

答え： $13$ 通り

答え: $13$

よくある誤り

行の巡回と列の巡回が作る成分の巡回の個数を $lcm (a, b)$ としてしまう誤り。 $lcm (a, b)$ は 1 つの巡回の長さで、個数は $ab / lcm (a, b) = g cd (a, b)$ 。例えば $a = b = 2$ なら 4 つの位置は長さ 2 の巡回 2 個に分かれ、 $c = g cd (2, 2) = 2$
成分の巡回の個数を、行の巡回の個数と列の巡回の個数の積 $c (σ) c (τ)$ としてしまう誤り。それは各組を 1 個と数えたもので、正しくは $\sum_{i, j} g cd (a_{i}, b_{j})$ 。例えば $σ = (12)$ , $τ = (12)$ （ $2 \times 2$ ）では積は 1 だが、正しくは $c = 2$
類ごとにまとめるときに類の元の個数 $∣ C ∣$ を掛け忘れ、代表元の固定点の個数をそのまま足してしまう誤り。正しくは $\frac{1}{∣ G ∣} \sum_{C} ∣ C ∣ ∣ Fix (g_{C}) ∣$ で、 $∣ C ∣$ の合計が $∣ G ∣$ になることを確かめる
転置を加えたとき、転置を含む元の固定点を $σ$ と $τ$ の巡回型の組で分類しようとする、または群の位数を $(n!)^{2}$ のままにしてしまう誤り。正しくは $∣ G ∣ = 2 (n!)^{2}$ で、転置を含む元 $(σ, τ) \circ T$ は $σ τ$ の巡回型ごとに $(e, σ τ) \circ T$ を代表にして数える

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
各成分が $0$ または $1$ である $2 \times 3$ 行列全体の集合を $X$ とする。群 $G = S_{2} \times S_{3}$ を、 $(σ, τ) \in G$ が行列 $A = (a_{ij})$ の行を $σ$ で、列を $τ$ で並べ替える作用
$((σ, τ) \cdot A)_{σ (i) τ (j)} = a_{ij}$
によって $X$ に作用させる。この作用による軌道の個数（行の並べ替えと列の並べ替えで移り合う行列を同じとみなしたときの行列の種類の数）を求めよ。

この技能を使う問題

難易度 4（大学院入試の難問レベル）
成分がすべて $0$ または $1$ である $3 \times 3$ 行列全体の集合を $X$ とする（ $∣ X ∣ = 2^{9}$ ）。 $A, B \in X$ について、 $A$ に「行の並べ替え」「列の並べ替え」「転置」の操作を有限回（ $0$ 回も含む）くり返して $B$ が得られるとき、 $A$ と $B$ は同値であるという。この同値関係による $X$ の同値類の個数を求めよ。