9宫格翻游戏的简单思考
用线性代数证明
这是一个使用线性代数进行的证明。
设：
状态空间为二元域 $\mathbb{F}_2 = {0, 1}$ 上的9维向量空间 $V = \mathbb{F}_2^9$，网格的初始状态为向量 $\vec{s} \in V$，则我们的目标状态（全1）为向量 $\vec{t} = (1, 1, 1, 1, 1, 1, 1, 1)^T \in V$。
又记按键操作为向量 $\vec{x} \in V$，其中 $x_i = 1$ 表示按了第 $i$ 个格子， $x_i = 0$ 表示未按。
令操作矩阵 A 中 $A_{ij}=1$ 当且仅当按第 j 个格子会翻转第 i 个格子。（例如，按第5个格子（中心）会翻转2, 4, 5, 6, 8，所以 A 的第5列为 (0,1,0,1,1,1,0,1,0)T）。
于是我们有：对初始状态 $\vec{s}$ 执行操作 $\vec{x}$，得到的最终状态 $\vec{s}_{final}$ 为：
(所有运算均在 $\mathbb{F}_2$ 上，加法即异或)
要证：
对于任意的初始状态 $\vec{s} \in V$，都存在一个操作 $\vec{x} \in V$，使得 $\vec{s}_{final} = \vec{t}$ ，有：
移项（在 $\mathbb{F}_2$ 中 $a+b=c \iff a=c-b \iff a=c+b$）得：
接下来令 $\vec{b} = \vec{t} + \vec{s}$
由于 $\vec{s}$ 可以是 $V$ 中 $2^9$ 个向量中的任意一个，所以 $\vec{b}$ 也可以是 $V$ 中 $2^9$ 个向量中的任意一个（$\vec{s} \mapsto \vec{t} + \vec{s}$ 是一个双射）。
即证，对于任意的 $\vec{b} \in V$，方程 $A\vec{x} = \vec{b}$ 恒有解。
又根据线性代数基本定理，上述命题等价于：矩阵 $A$ 是可逆的（非奇异的）。
即证，矩阵 A 的零空间（Kernel）是平凡的，即齐次线性方程组 Ax=0 只有唯一解 x=0。
（注意这里x=0 的物理意义是“一个键都不按”，Ax=0 的物理意义是“操作后所有格子都未翻转”）。
证明：
我们有方程组 $A\vec{x} = \vec{0}$。我们将 $\vec{x}$ 的分量 $x_1, \dots, x_9$ 视为 $3 \times 3$ 的按键网格，$\vec{b} = A\vec{x}$ 的分量 $b_1, \dots, b_9$ 视为 $3 \times 3$ 的翻转结果网格。
若 $b_1 = \dots = b_9 = 0$。
考察第一行格子 ($b_1, b_2, b_3$)：
$b_1 = x_1 + x_2 + x_4 = 0 \implies x_4 = x_1 + x_2$ (式1)
$b_2 = x_1 + x_2 + x_3 + x_5 = 0 \implies x_5 = x_1 + x_2 + x_3$ (式2)
b3=x2+x3+x6=0⟹x6=x2+x3 (式3)
（这表明第二行的按键 x4,x5,x6 由第一行的按键 x1,x2,x3 唯一确定）
考察第二行格子 ($b_4, b_5, b_6$)：
b4=x1+x4+x5+x7=0⟹x7=x1+x4+x5
代入 (1), (2): x7=x1+(x1+x2)+(x1+x2+x3)=x1+x3 (式4)
b5=x2+x4+x5+x6+x8=0⟹x8=x2+x4+x5+x6
代入 (1), (2), (3): x8=x2+(x1+x2)+(x1+x2+x3)+(x2+x3)=0 (式5)
b6=x3+x5+x6+x9=0⟹x9=x3+x5+x6
代入 (2), (3): x9=x3+(x1+x2+x3)+(x2+x3)=x1+x3 (式6)
（这表明第三行的按键 x7,x8,x9 也由 x1,x2,x3 唯一确定）
考察第三行格子 ($b_7, b_8, b_9$)：
b7=x4+x7+x8=0
代入 (1), (4), (5): (x1+x2)+(x1+x3)+0=0⟹x2+x3=0 (A)
b8=x5+x7+x8+x9=0
代入 (2), (4), (5), (6): (x1+x2+x3)+(x1+x3)+0+(x1+x3)=0⟹x1+x2+x3=0 (B)
b9=x6+x8+x9=0
代入 (3), (5), (6): (x2+x3)+0+(x1+x3)=0⟹x1+x2=0 (C)
则我们必须同时解出 x1,x2,x3 满足以下约束条件：
(A) x2+x3=0
(B) x1+x2+x3=0
(C) x1+x2=0
- 将 (A) 代入 (B)得 $x_1 + (x_2 + x_3) = 0 \implies x_1 + 0 = 0 \implies x_1 = 0$
- 将 $x_1 = 0$ 代入 (C)得 $0 + x_2 = 0 \implies x_2 = 0$
- 将 $x_2 = 0$ 代入 (A)得 $0 + x_3 = 0 \implies x_3 = 0$
则 $x_1 = x_2 = x_3 = 0$。将它们代入 (式1) 至 (式6)，可得 $x_4=0, x_5=0, x_6=0, x_7=0, x_8=0, x_9=0$。
于是$A\vec{x} = \vec{0}$ 的唯一解是 $\vec{x} = \vec{0}$。
因此矩阵 $A$ 是可逆的，对于任意 $\vec{b} \in V$，方程 $A\vec{x} = \vec{b}$ 都有唯一解 $\vec{x} = A^{-1}\vec{b}$，且对于任意初始状态 $\vec{s}$，都存在唯一的操作 $\vec{x}$，使得 $A\vec{x} = \vec{t} + \vec{s}$ 成立。
故所有 $2^9$ 种初始情况都一定能转变为全1。证毕。
用群论证明
该状态群和操作群皆为阿贝尔群
我们记状态群 ($S$)为：
- 元素（$e_S$）：所有 $2^9$ 种可能的 $3 \times 3$ 网格状态。每个状态 $s$ 都是一个 $\mathbb{F}_2^9$ 中的向量。
- 运算 ($\oplus$)：对应格子逐个进行的异或（XOR）操作，即向量加法 $\vec{s}_1 + \vec{s}_2$（在 $\mathbb{F}_2$ 上）。
又记操作群 ($G$)：
- 元素（$e_G$）：所有 $2^9$ 种可能的“按键组合”。每个操作 $x$ 也是一个 $\mathbb{F}_2^9$ 中的向量，代表是否按下第 $i$ 个键。
- 运算 ($\oplus$)：两个操作组合的叠加，也是逐元素的 XOR 操作 $\vec{x}_1 + \vec{x}_2$。
接下来我们定义一个映射 $\phi: G \to S$，将操作群的元素（按键组合 $\vec{x}$）映射到状态群的元素（产生的翻转图样 $\vec{b}$），即：
其中 $A$ 是 $9 \times 9$ 的“操作矩阵”（如前所述）。
注意到这个映射 $\phi$ 是一个群同态：
（根据 $\mathbb{F}_2$ 上的矩阵乘法分配律，且加法即 $\oplus$ 运算。）
要证，对于任意初始状态 ，找到操作 ，使得最终状态为 即：
移项得：
令 。由于 可以是 中的任意元素， 也可以是 中的任意元素。
等价于证明， 同态 $\phi: G \to S$ 是满射（Surjective）
证明：
由于 ∣G∣=∣S∣=29，根据有限群同态的基本定理，对于 ϕ:G→S，有：
我们只需要证明 ϕ 的核（Kernel）是平凡的，即 $\ker(\phi) = {\vec{x} \in G \mid \phi(\vec{x}) = e_S }$ ，其中 $e_S = \vec{0}$（全 $0$ 网格）。
因此，我们需证明：
这完全回到了线性代数中证明齐次线性方程组 $A\vec{x} = \vec{0}$ 只有平凡解的问题。根据前一证明，我们已经严谨地推导出：
所以，$\ker(\phi) = {\vec{0}} = {\vec{e}_G}$，核是平凡的。
由于 ker(ϕ) 是平凡的，同态 ϕ 是单射，又因为 ∣G∣=∣S∣，故 ϕ 也是满射。满射性保证了对于 S 中的任意“所需翻转图样” b，都存在至少一个按键组合 x∈G 满足 ϕ(x)=b。
因此，无论初始状态 $\vec{s}_{initial}$ 是什么，总存在操作 $\vec{x}$ 能使网格达到全 $1$ 的目标状态。证毕。
