前回の（その１）で求めた行列A = makeA(5,5) を使い、今回もこの論文を参考に解答を見つけるアルゴリズムをSagemathを使って書いて行きます。
階段行列 (echelon form) Eと変換行列Rを求める
まずAの階数を求めると23（正則なら25）なので、正則ではないことが分かります。
print(A.rank())
#23
そこでこれを階段行列（echelon form）$E$とその変換行列$R$を求めます。$R$は1行目の式で求まると思ったのですが、うまく行かず色々調べた結果2-4行目を使いました。
#E0, R = A.echelon_form(transformation=True)
E0, R0 = map(lambda t: matrix(GF(2),t), matrix(ZZ,A).echelon_form(transformation=True))
R = E0*R0
E = R*A
print(R)
# [0 1 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0]
#[0 1 1 1 0 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 0 1 0 1]
# : :
#[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
#[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
直交基底ベクトルV1,V2をEから求める
直交基底ベクトルV1, V2はEの右の2列から以下のように求まります。（固有ベクトルを使っても求まりそうです）
V1 = vector(GF(2),[0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0])
V2 = vector(GF(2),[1,0,1,0,1,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,0,1,0,1])
V1,V2を使って解ける問題かどうかを判定する
例えばこの問題をベクトル化すると以下のようになります。
f = vector(GF(2),[0,0,1,0,0, 0,1,1,1,0, 0,0,1,0,0, 0,0,1,0,0, 0,0,1,0,0])
問題が解ける条件は
fがV1,V2と直行する \\
すなわち \\
内積 f \cdot V1 = 0 かつ f \cdot V1 = 0
内積をチェックすると解けるということが分かります。
print("f*V1=",f*V1,", f*V2=",f*V2)
# f*V1= 0 , f*V2= 0
Lights Outの解答の1つを求める
上で求めた$R$を使うと以下の式から簡単に答えの1つが求まります。
x_1 = Rf \ \ \ \
従ってこの解答の1つは以下のようなり。分かりやすいように5 x 5のマトリクスに戻して表示しています。また検算として$A*x1$で元に戻ることも確認できました。
x1 = R*f
print("---Answer #1 , --")
print(matrix(GF(2),m,n,x1))
print(".verification .")
print(matrix(GF(2),m,n,A*x1))
#---Answer #1 --
#[0 0 1 1 1]
#[0 1 1 1 0]
#[1 1 1 0 0]
#[0 0 0 0 0]
#[1 1 0 0 0]
#-verification-
#[0 0 1 0 0]
#[0 1 1 1 0]
#[0 0 1 0 0]
#[0 0 1 0 0]
#[0 0 1 0 0]
Lights Outの最適解を求める
上記論文によると5 x 5の場合は解ける場合は4つの答えがあります。（行列の自由度=$25-23=2$なので$2^2=4$）
x_1 = Rf \\
x_2 = Rf + V1 \\
x_3 = Rf + V2 \\
x_4 = Rf + V1 + V2 \\
これらを各々求めて手数の数えて最小のものを選びます。一見ベクトルの要素のsumをとれば良さそうですがそのままだと剰余２の計算になってしまうのでlift() プロパティを使って整数に戻す必要があります。
この問題の場合には手数が11の$x_1$が最適解だと言う事が分かりました。
x1 = R*f
x2 = R*f+V1
x3 = R*f+V2
x4 = R*f+V1+V2
print(f"Steps: x1={sum(x1.lift())},x2={sum(x2.lift())},x3={sum(x2.lift())},x4={sum(x2.lift())}")
# Steps: x1=11,x2=15,x3=15,x4=15
解答を見るのは最初の1行でよい
この論文の最後に面白いことが書いてあります
解答の最初の1行のボタンを押したら2行目からは上の行の点灯しているものの下のボタンを押して行けばよい
これは例えば今回の例題の場合1行目の答えは右の3つなので、まずこれを押して、2行目からは答えを見なくても上の行の点灯している下のボタンを押して行けばクリアできるということです。もしよければ試してみてください。
#[0 0 1 1 1]
次のステップ
今回は5 x 5の問題に関して解くことができるかどうかの判定とその解き方を紹介しました。次回は一般にm x nの問題が必ず解けるのかどうかを調べてみたいと思います。
（開発環境：Cocalc Sage Worksheet）