axpokl 3年前写下了点灯游戏Flip Game的$O(n^3)$算法，感觉颇为神奇¹。文章的算法很巧妙，但是算法的正确性并不显然。想象整个算法抽象成为了两个矩阵$A$和$B$。 用了Light Chasing操作得到了$B$和$b^{\prime }$. 解方程找到$By=b^{\prime }$中的$y$. 然后对$y$进行light chasing操作获得$Ax=b$的解。

这个算法是否是正确的？原先以为这应该非常显然，但自己要解释给人听的时候发现自己没法马上证出来。而且我一度错误的以为矩阵$A$和$B$的秩都一样。 那么，是否有可能$Ax=b$存在解，我们找到了个$By=b^{\prime }$的解$y$, 对$y$进行操作之后得到的向量$z$却无法满足$Ax=b$？从一个高维空间映射到了一个低维空间，我们竟然没有丢失什么信息嘛？axpokl也并没有给出正式的证明。

点灯游戏和解$Ax=b$是同一个问题。自然也会思考这算法如何延伸到解。

找了一堆文献后，发现算法里使用的性质在图上叫做逼零集（zero forcing set）。图上初始有一些蓝色的点。如果有一个蓝色的点，有且仅有1个非蓝色的邻点，则染色这个邻点为蓝色。如果不断染色直到整个图都能被染为蓝色，则初始的那些顶点被称之为逼零集。逼零集自然也可以被定义在有向图上，也能定义在 矩阵上──如果把矩阵看成领接矩阵。逼零集满足一系列不错的属性，在物理和电网监测方面都有用途。不过认真的讨论用逼零集解方程，以及计算复杂度，我们并没有找到这样的文章。

为此，本校的研一学生王建波，数学科学学院的博士生周思芸和我做了点工作。证明了以下的定理。

文章可以这里看到。我们也顺便将点灯游戏的复杂度降到了$O(n^{\omega }\log n)$，这部分倒是非常显然。

我线性代数已经忘得差不多了，基本简单证明都不会搞。所以在这个问题上，两位学生做出了比我要多很多贡献。

为了解决这个问题，我终于知道了最general的解线性方程组的算法是使用LSP分解[1]（非常像LUP分解）。对于一个$r$秩$m\times n$矩阵，LSP分解的复杂度是$O(mn{r}^{\omega -2})$。

1 未解问题

1. 找到最小逼零集是NP-hard的。是否存在快速的近似算法？
2. $O(mk)$的部分是否可以提升到$O(n{k}^{\omega -1})$或者$O(n^{2}k\omega -2)$的算法？

References