Solving Systems of Linear Equations Through Zero Forcing Set

Let \(\mathbb {F}\) be any field, we consider solving \(Ax=b\) for a matrix \(A\in \mathbb {F}^{n\times n}\) of m non-zero elements and \(b\in \mathbb {F}^{n}\) . If we are given a zero forcing set of A of size k, we can solve the linear equation in \(O(mk+k^\omega )\) time, where \(\omega \) is the matrix multiplication exponent. As an application, we show how the lights out game in an \(n\times n\) grid is solved in \(O(n^3)\) time, and then improve the running time to \(O(n^\omega \log n)\) by exploiting the repeated structure in grids.