ライツアウトの数理（4年ゼミ）

ライツアウト行列の rank を巡って．
ノイマン近傍型にライトのon/offを切り替えるこのゲームの操作は，Lights Out行列
$A=\begin{pmatrix} T_d&E_d&O_d&O_d&\cdots&O_d\\ E_d&T_d&E_d&O_d&\cdots&O_d\\ O_d&E_d&T_d&E_d&\cdots&O_d\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ O_d&\cdots&E_d&T_d&E_d&O_d\\ O_d&\cdots&O_d&E_d&T_d&E_d\\ O_d&\cdots&O_d&O_d&E_d&T_d \end{pmatrix}$
と表される．求めたいのは ${\rm rank}(A)$ だ．ただし， $T_d$ は $\mathbb{F}_2$ 係数の三重対角行列
$T_d=\begin{pmatrix} 1&1&0&0&\cdots&0\\ 1&1&1&0&\cdots&0\\ 0&1&1&1&\cdots&0\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ 0&\cdots&1&1&1&0\\ 0&\cdots&0&1&1&1\\ 0&\cdots&0&0&1&1 \end{pmatrix},$
$E_d,O_d$ はそれぞれ， $d$ 次単位行列とゼロ行列である．
${\rm rank}(A)$ を求める代わりに，はじめの $d$ 行を最後に移動した，
$B=\begin{pmatrix} E_d&T_d&E_d&O_d&\cdots&O_d\\ O_d&E_d&T_d&E_d&\cdots&O_d\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\ O_d&\cdots&E_d&T_d&E_d&O_d\\ O_d&\cdots&O_d&E_d&T_d&E_d\\ O_d&\cdots&O_d&O_d&E_d&T_d\\ T_d&E_d&O_d&O_d&\cdots&O_d\\ \end{pmatrix}$
の rank を求めるほうが容易い．このその最下段を頭から順に消去していくわけだが，はじめの $d$ 行とラストの $d$ 行とで，
$\begin{pmatrix} E_d&T_d&E_d&O_d&\cdots\\ T_d&E_d&O_d&O_d&\cdots \end{pmatrix} \to \begin{pmatrix} E_d&T_d&E_d&O_d&\cdots\\ O_d&T_d^2+E_d&T_d&O_d&\cdots \end{pmatrix}$
と行基本変形でき，これを繰り返せば $(k+1)$ stepで
$\begin{pmatrix} \cdots&E_d&T_d&E_d&\cdots\\ \cdots&P_k&Q_k&O_d&\cdots \end{pmatrix} \to \begin{pmatrix} \cdots&E_d&T_d&E_d&\cdots\\ \cdots&O_d&P_{k+1}=T_dP_k+Q_k&Q_{k+1}=P_k&\cdots \end{pmatrix}$
と変形される．こうしてFibonacci多項式の漸化式
$\begin{pmatrix}P_{k+1}\\Q_{k+1}\end{pmatrix} =\begin{pmatrix}T_d&E_d\\E_d&O_d\end{pmatrix} \begin{pmatrix}P_{k}\\Q_{k}\end{pmatrix}$
が登場し，特に最後のステップによってラスト $d$ 行は
$\begin{pmatrix} O_d&\cdots&P_{d}=p_d(T_d)\end{pmatrix}$
と， Fibonacci多項式 $p_d(t)$ を用いて表示される．こうして，
${\rm rank}(A)={\rm rank}(B)=d(d-1)+{\rm rank}(p_d(T_d))$
となる所まで来た．次にすべきは， ${\rm rank}(p_d(T_d))$ を求めることであるが，今度は三重対角行列 $T_d$ の固有多項式が関わってくることになる．
okiraku-semi.hatenablog.jp

drive.google.com

ゼミの風景

おそらくお気楽はしのすけゼミの諸風景

ライツアウトの数理（4年ゼミ）