演習問題：シフトによる巡回群作用とBurnsideの補題
\(n\)次元ベクトル空間上で、各成分が\(0\)または\(1\)をとるベクトルの集合を\(\mathcal{X}_n\)とおく：
\[\mathcal{X}_n\coloneqq\left\{(x_1,x_2,\ldots,x_n)^\mathrm{T}\mid x_1,x_2,\ldots,x_n\in\{0,1\}\right\}\subset \mathbb{R}^n.\]
ここで、\(n\)次正方行列\(A_n\)を以下で定義する：
\[A_n \coloneqq
\begin{bmatrix}
0 & 1 0 & \cdots 0 \\
0 & 0 1 & \cdots 0 \\
\vdots & \vdots \ddots & \ddots \vdots \\
0 & 0 \cdots & 0 1 \\
1 & 0 \cdots & 0 0 \\
\end{bmatrix}
\in \mathbb{R}^{n \times n}\]
\(n\)次一般線形群の部分群として\(A_n\)で生成される巡回群\(C_n = \langle A_n \rangle\)による\(\mathcal{X}_n\)への群作用を通常の行列の積により定める： \[\forall \mathbf{x} \in \mathcal{X}_n,B\in \langle A_n \rangle,\quad B \cdot \mathbf{x}= B \mathbf{x}.\]
このとき、以下の問いに答えよ。
-
\(\mathbf{x}=(x_1, x_2, \ldots, x_n)^\mathrm{T}\in \mathcal{X}_n\)とする。任意の \(k \in \{0, \dots, n-1\}\) に対して、\(A_n^k\cdot \mathbf{x}\)を求めよ。
-
任意の \(k \in \{1, \dots, n\}\) に対して、\(A_n^k\) による固定点（\(A_n^k\cdot \mathbf{x}=\mathbf{x}\)を満たす\(\mathbf{x}\in \mathcal{X}_n\)）の個数 \(f_k\) を求める式を導出せよ。
-
\(\mathcal{X}_n\)における\(C_n\)-軌道の総数を求める式を導出せよ。
-
\(n=4,5,6\)のときの軌道数を具体的に計算せよ。
-
白玉と黒玉が無数にある。この中から合計\(n\)個の玉を取り出して円形に並べる方法は何通りあるか。ただし、玉は等間隔に並べ、回転させて同じになる並べ方は同一と見做す。
-
\(m\)色の玉がそれぞれ無数にある。この中から合計\(n\)個の玉を取り出して円形に並べる方法は何通りあるか。ただし、玉は等間隔に並べ、回転させて同じになる並べ方は同一と見做す。
略解
-
\(A_n \mathbf{x}\)は \(\mathbf{x}=(x_1, x_2, \ldots, x_n)^\mathrm{T}\) の成分を1つ巡回シフトさせたもの、すなわち\((x_2, x_3, \ldots, x_n, x_1)^\mathrm{T}\)である。よって、\(A_n^k \mathbf{x}\)は右に \(k\) ステップ巡回シフトさせたものである。 \[A_n^k \cdot \mathbf{x}=(x_{k+1},x_{k+2},\ldots,x_{n},x_1,x_2,\ldots,x_{k}).\]
-
\(\mathbf{x} \in \mathcal{X}_n\) が \(A_n^k\) によって不変であることは、成分を\(k\)ステップ巡回シフトさせたときに元と一致することを意味する。これは、\(\mathbf{x}\) が長さ \(d = \gcd(k, n)\) の周期を持つことを意味する。ここで、\(\gcd\)は最大公約数を表す。したがって、\(\mathbf{x}\) の全成分は長さ \(d\) のブロックの繰り返しである。1つのブロックの中での\(0,1\)の並べ方を考えることで、 \[f_k = 2^{\gcd(k, n)}.\]
-
Burnsideの補題より、軌道の個数 \(N_n\) は
\[N_n = \frac{1}{|C_n|}\sum_{k=1}^{n}f_k=\frac{1}{n} \sum_{k=1}^{n} 2^{\gcd(k, n)}.\]
-
-
\(n=4\): \[f_4=2^4=16,\quad f_1=2^1=2,\quad f_2=2^2=4,\quad, f_3=2^1=2.\] よって、 \[N_4 = \frac{1}{4}(16+2+4+2) = \frac{24}{4} = 6.\]
-
\(n=5\): \[f_5=2^5=32,\quad f_1=2^1=2,\quad f_2=2^1=2,\] \[f_3=2^1=2,\quad f_4=2^1=2.\] よって、 \[N_5 = \frac{1}{5}(32+2+2+2+2) = \frac{40}{5} = 8.\]
-
\(n=6\): \[f_6=2^6=64,\quad f_1=2^1=2,\quad f_2=2^2=4,\] \[f_3=2^3=8,\quad f_4=2^2=4,\quad f_5=2^1=2.\] よって、 \[N_6 = \frac{1}{6}(64+2+4+8+4+2) = \frac{84}{6} = 14.\]
-
-
白を0、黒を1に対応させると、1つの並べ方はいくつ分巡回シフトさせても変わらないような\(n\)桁のビット列1つに対応する。これは第3問で求めたものだから、\(N_n\)がそのまま答えとなる。
-
第3問と同様に、Burnsideの補題より、 \[N_{m,n}= \frac{1}{|C_n|}\sum_{k=1}^{n}m^{\gcd(k, n)}=\frac{1}{n} \sum_{k=1}^{n} m^{\gcd(k, n)}.\]