Solving systems of linear equations through zero forcing set and application to lights out
share
Let 𝔽 be any field, we consider solving Ax=b repeatedly for a matrix A∈𝔽^n× n of m non-zero elements, and multiple different b∈𝔽^n. If we are given a zero forcing set of A of size k, we can then build a data structure in O(mk) time, such that each instance of Ax=b can be solved in O(k^2+m) time. As an application, we show how the lights out game in an n× n grid is solved in O(n^3) time, and then improve the running time to O(n^ωlog n) by exploiting the repeated structure in grids.
READ FULL TEXT