Unit-Weight Laplacians are Complete for Linear Systems Modulo $p$

In this paper, we prove that over finite fields modulo primes, solving general linear systems is as hard as solving unit-weight Laplacian linear systems. We give a reduction of solving a general linear system $\mathbf{A} \boldsymbol{x} = \boldsymbol{b}$ over $\mathbb{Z}_{p}$ to solving a unit-weight Laplacian system $\bar{\mathbf{L}}$ of size $O\left(\mathrm{nnz}(\mathbf{A})\log^2p/\log\log p\right)$. Our result indicates that unlike problems over reals, graph-like structure such as Laplacians may not offer too many additional properties over finite fields. We also formalize the role of Schur complement as a tool for making reductions between problems on systems of linear equations.