Twitterで出した問題の解説（マス目の入れ替え）
今回は, Twitterで出題した以下の問題の解説をしようと思います.
${}$
以下のようなマス目がある. 16マスから1つ以上のマスを選び, それらに書かれた数の和を「スコア」と呼ぶことにする. 次の操作をどのように繰り返してもスコアが不変であるような, マスの選び方は何通りか.
操作：$1\leq i< j\leq4$を満たす整数$i,j$をとり, 上から$i$行目と$j$行目の数を入れ替え, 左から$i$列目と$j$列目の数を入れ替える.
$$\begin{bmatrix}2&2&0&0\\2&2&0&0\\5&5&2&2\\5&5&2&2\end{bmatrix}$$
${}$
実験
例えば$(i,j)=(2,3),(1,2),(3,4)$で順に操作すると
$\begin{bmatrix}\two&\two&\zero&\zero\\\two&\two&\zero&\zero\\\five&\five&\two&\two\\\five&\five&\two&\two\end{bmatrix} \to \begin{bmatrix}\two&\zero&\two&\zero\\\five&\two&\five&\two\\\two&\zero&\two&\zero\\\five&\two&\five&\two\end{bmatrix} \to \begin{bmatrix}\two&\five&\five&\two\\\zero&\two&\two&\zero\\\zero&\two&\two&\zero\\\two&\five&\five&\two\end{bmatrix} \to \begin{bmatrix}\two&\five&\two&\five\\\zero&\two&\zero&\two\\\two&\five&\two&\five\\\zero&\two&\zero&\two\end{bmatrix} $
のようにいくらかの対称性があることが見えてきますが, 全て言葉にすることは難しそうです.
${}$
方針
マス目の状態を$16$次元$\C$線型空間の元とみる.（以下の議論は実際は$\Q$係数でも問題なく行えるが, 念の為に$\C$にしておく.）すると, 問題文の操作によって$\S_4$の作用が導かれ, これは$\S_4$の表現とみなせる.
一方で, $V=\C^4$を成分入れ替えによる$\S_4$の表現とし, そのTensor積$V\otimes V$を考えると, 基底$e_i\otimes e_j$の係数をマス目の$i$行$j$列成分と対応させることにより, 上記の$16$次表現と$V\otimes V$は表現として同じものである.
さらに表記上の都合から, $V\otimes V\cong \mathrm{M}_4(\C)$によりマス目を$4\times4$行列と対応させる. また, $M=\begin{pmatrix}2&2&0&0\\2&2&0&0\\5&5&2&2\\5&5&2&2\end{pmatrix}$とおく.
これで問題は, 以下のように言い換えられた.
$\S_4$の$\mathrm{M}_4(\C)$への作用および$M$を上のとおりとする.
いくつかの成分を足し合わせるという形の線型写像$f:\mathrm{M}_4(\C)\to\C$であって, $\forall \sigma\in\S_4,\ f(\sigma M)=f(M)$を満たすものの個数を求めよ,
${}$
解答
さらに言い換える
$\forall \sigma\in\S_4,\ f(\sigma M)=f(M)$
$\iff \forall \sigma\in\S_4,\ \sigma M-M\in\Ker f$
$\iff \langle \sigma M-M\ |\ \sigma \in\S_4\rangle \subset \Ker f$
この左辺を$W$とおく. これは$\sigma M-M$たちの貼る部分空間を指す.（$M$に依存することに注意）
$\tau(\sigma M-M)=(\tau\sigma M-M)-(\tau M-M)\in W$ より$W$は$\S_4$安定なので, 部分表現になっている. $W$を特定したい.
${}$
$\mathrm{M}_4(\C)$の自明表現成分への射影を$p$とおくと, $W=\Ker\,p\ \cap \langle\sigma M\ |\ \sigma \in \S_4\rangle$である.
つまり$W$は, $M$が表現として（$\C[\S_4]$加群として）生成する空間$\langle\sigma M\rangle$の, 自明表現成分を落としたものに等しい.
右辺を$W'$とおく. $W\subset W'$は明らかである. そこで商空間$W'/W$を考えると, その中では$\sigma M=M$なのでこれは自明表現である. しかし$W'$は定め方から自明な部分表現を持たないので, $W'/W=0$となるしかない.
従って, $\C[\S_4]M=\langle\sigma M\rangle$を特定すれば良いことがわかった.
${}$
既約分解する
そのためにまず, $\mathrm{M}_4(\C)$の既約分解を求める.
$\S_4$の共役類は5つより既約表現は5つである. 1次表現を$\mathrm{triv},\mathrm{sgn}$とおく. $V=\C^4=\mathrm{triv}\oplus\mathrm{Std_3}$なる標準表現$\mathrm{Std}_3$は既約である. これらを用いて, $\S_4$の既約表現の指標表は以下のようになる.
| $e$ | $(12)$ | $(123)$ | $(1234)$ | $(12)(34)$ | |
|---|---|---|---|---|---|
| $\mathrm{triv}$ | $1$ | $1$ | $1$ | $1$ | $1$ |
| $\mathrm{sgn}$ | $1$ | $-1$ | $1$ | $-1$ | $1$ |
| $\mathrm{Std}_3$ | $3$ | $1$ | $0$ | $-1$ | $-1$ |
| $\mathrm{Std}_3'$ | $3$ | $-1$ | $0$ | $1$ | $-1$ |
| $\rho_2$ | $2$ | $0$ | $-1$ | $0$ | $2$ |
ここで$\mathrm{Std}_3'=\mathrm{Std_3}\otimes\mathrm{sgn}$であり, $\rho_2$は2次既約表現である.
次に, $V=\C^4=\mathrm{triv}\oplus\mathrm{Std_3}$の指標を$\chi$とすると, $V\otimes V=\mathrm{M}_4(\C)$の指標は$\chi^2$となる.
さらに表現のTensor積の一般論より, $V\otimes V=\mathrm{Sym}(V)\oplus\mathrm{Alt}(V)$と, 対称積と外積に直和分解でき, $\mathrm{Sym}$の指標は$\frac12(\chi(g)^2+\chi(g^2))$, $\mathrm{Alt}$の指標は$\frac12(\chi(g)^2-\chi(g^2))$で計算できる.
${}$
| $e$ | $(12)$ | $(123)$ | $(1234)$ | $(12)(34)$ | |
|---|---|---|---|---|---|
| $V$ | $4$ | $2$ | $1$ | $0$ | $0$ |
| $\mathrm{M}_4(\C)$ | $16$ | $4$ | $1$ | $0$ | $0$ |
| $\mathrm{Sym}$ | $10$ | $4$ | $1$ | $0$ | $2$ |
| $\mathrm{Alt}$ | $6$ | $0$ | $0$ | $0$ | $-2$ |
2つの表を見比べて,
$$ \mathrm{Sym}=\mathrm{triv}^{\oplus2}\oplus\mathrm{Std_3}^{\oplus2}\oplus\rho_2,\quad \mathrm{Alt}=\mathrm{Std}_3\oplus\mathrm{Std}_3'$$
を得る.
また, 分解$V\otimes V=\mathrm{M}_4(\C)=\mathrm{Sym}\oplus\mathrm{Alt}$は, 行列空間の, 対称行列と反対称行列への直和分解に一致することに注意する.
さらに, $\mathrm{Sym}$はさらに対角行列とそれ以外に分解でき, 対角部分が$V=\mathrm{triv}\oplus\mathrm{Std_3}$に同型で, 残りが$\mathrm{triv}\oplus\mathrm{Std_3}\oplus\rho_2$となっている.
${}$
生成する表現を特定する
以上を踏まえて$\C[\S_4]M$を特定する. まず$M$を, 対角行列, 対称行列（の非対角部分）, 反対称行列に分解すると
$$ M=\begin{pmatrix}2&2&0&0\\2&2&0&0\\5&5&2&2\\5&5&2&2\end{pmatrix}=\begin{pmatrix}2&0&0&0\\0&2&0&0\\0&0&2&0\\0&0&0&2\end{pmatrix}+\frac12\begin{pmatrix}0&4&5&5\\4&0&5&5\\5&5&0&4\\5&5&4&0\end{pmatrix}-\frac52\begin{pmatrix}0&0&1&1\\0&0&1&1\\-1&-1&0&0\\-1&-1&0&0\end{pmatrix}$$
となるので,
$M_{\mathrm{Sym}}=\begin{pmatrix}0&4&5&5\\4&0&5&5\\5&5&0&4\\5&5&4&0\end{pmatrix},\quad M_{\mathrm{Alt}}=\begin{pmatrix}0&0&1&1\\0&0&1&1\\-1&-1&0&0\\-1&-1&0&0\end{pmatrix}$が生成する$\C[\S_4]M_{\mathrm{Sym}},\ \C[\S_4]M_{\mathrm{Alt}}$（これらはそれぞれ$\mathrm{Sym},\mathrm{Alt}$の部分表現である）を特定すればよい. 対角行列成分が生成するのは自明表現である.
${}$
$M_{\mathrm{Sym}}$の生成する部分表現
$(12),(23),(34)$が$\S_4$を$M_{\mathrm{Sym}}$に色々と作用させれば,
$$ \C[\S_4]M_{\mathrm{Sym}}=\left\{\begin{pmatrix}0&a&b&c\\a&0&c&b\\b&c&0&a\\c&b&a&0\end{pmatrix}\mid a,b,c\in\C\right\}$$
であることがすぐにわかる. しかしこれは既約ではなく, $a=b=c$の場合が自明部分表現になっている. これによる商は$a+b+c=0$を条件とした2次元表現になるが, これは1次部分表現を持たないことから（指標を計算してもよい）, $\rho_2$に等しいことがわかる. 従って $\C[\S_4]M_{\mathrm{Sym}}=\mathrm{triv}\oplus\rho_2$である.
$M_{\mathrm{Alt}}$の生成する部分表現
同様に$(12),(23),(34)$を作用させれば,
$$ \C[\S_4]M_{\mathrm{Alt}}=\left\{\begin{pmatrix}0&x+y&y+z&z+x\\-x-y&0&z-x&z-y\\-y-z&x-z&0&x-y\\-z-x&y-z&y-x&0\end{pmatrix}\mid x,y,z\in\C\right\}$$
となる. $\mathrm{Alt}$の既約分解よりこれは$\mathrm{Std_3},\ \mathrm{Std}_3'$のどちらかに等しい. 実際に指標を計算すると$\mathrm{Std}_3$だとわかる（が, 実はどちらだったとしても以下の議論には関係ない）.
$M$の生成する部分表現
以上より,
$$ \C[\S_4]M=\mathrm{triv}^{\oplus2}\oplus\rho_2\oplus\mathrm{Std}_3$$
従って補題より,
$$ W=\langle \sigma M-M\ |\ \sigma \in\S_4\rangle =\rho_2\oplus\mathrm{Std}_3 $$
となる. （正確には$\C[\S_4]M$の自明成分は, $\mathrm{triv}^{\oplus2}$の1次元部分空間かもしれないが, どちらにしろ無視するので関係ない.）
${}$
$f$を決定する
$W=\rho_2\oplus\mathrm{Std}_3\subset\Ker f$となればよかったのだから,
$\begin{pmatrix}0&a&b&c\\a&0&c&b\\b&c&0&a\\c&b&a&0\end{pmatrix}+\begin{pmatrix}0&x+y&y+z&z+x\\-x-y&0&z-x&z-y\\-y-z&x-z&0&x-y\\-z-x&y-z&y-x&0\end{pmatrix}$
の, 16マスのうち何マスかを足したものが, $a,b,c,x,y,z$の式として（$a+b+c=0$のもとで）$0$になればよい.
${}$
対角成分はいくつ選んでも良い. 対角成分以外は, $a,b,c$を同じ個数ずつ選ぶしかないので0,3,6,9,12個選ぶしかない. 9個選ぶことは, 選ばないマスを3個選ぶことと同じなので, 以下では非対角成分を3,6個選ぶ方法を数える.
・非対角成分3つの場合
$a$ブロック（$\pm x\pm y$）, $b$ブロック（$\pm y\pm z$）, $c$ブロック（$\pm z\pm x$）から1つずつ選んだ和が$x,y,z$の式として$0$になる場合の数を数えればよい.
これは, $a$ブロックから1つ決めると$b,c$ブロックからの選び方はちょうど2通りあるので, 合計8通りである.
・非対角成分6つの場合
$a$ブロックから2つ選んだ和は$0,\pm 2x,\pm2y$があり得, 他も同様である. すると, 各ブロックでの和は「$0,0,0$」か「$2x,-2x,0$」のようであるかしかない. それぞれ8通り, 12通りの合計20通りである.
${}$
以上より, 非対角成分の選び方は$1+8+20+8+1=38$通りである. また, 対角成分の選び方は$2^4=16$通りである. 最後に, ひとつもマスを選ばないというパターンを除いて, $38\times 16-1=$$607$通りが答えである.
${}$
確認
実際に, 条件を満たすようなマス目の選び方を確認してみましょう.
上の, 非対角成分6つの場合の「$2x,-2x,0$」パターンは,
$$ \begin{pmatrix}0&\color{red}{x+y}&\color{red}y+z&z+x\\-x-y&0&\color{red}z-x&z-y\\\color{red}-y-z&x-z&0&\color{red}x-y\\\color{red}-z-x&y-z&y-x&0\end{pmatrix}$$
の赤文字の6つを選ぶことに対応します. 実際にこの6つでスコアが不変なことを見てみましょう. 一番最初に挙げた盤面の遷移に対して確かめてみると,
$\begin{bmatrix}2&\colorbox{pink}2&\colorbox{pink}0&0\\2&2&\colorbox{pink}0&0\\\colorbox{pink}5&5&2&\colorbox{pink}2\\\colorbox{pink}5&5&2&2\end{bmatrix} \to \begin{bmatrix}2&\colorbox{pink}0&\colorbox{pink}2&0\\5&2&\colorbox{pink}5&2\\\colorbox{pink}2&0&2&\colorbox{pink}0\\\colorbox{pink}5&2&5&2\end{bmatrix} \to \begin{bmatrix}2&\colorbox{pink}5&\colorbox{pink}5&2\\0&2&\colorbox{pink}2&0\\\colorbox{pink}0&2&2&\colorbox{pink}0\\\colorbox{pink}2&5&5&2\end{bmatrix} \to \begin{bmatrix}2&\colorbox{pink}5&\colorbox{pink}2&5\\0&2&\colorbox{pink}0&2\\\colorbox{pink}2&5&2&\colorbox{pink}5\\\colorbox{pink}0&2&0&2\end{bmatrix} $
と, どの場合も和が14になっているので, 確かにスコア不変条件を満たしていそうです. 非自明で面白いですね.
${}$
それでは, ここまで読んでくださった方, ありがとうございました.
${}$
${}$
