Note that here we crucially used the fact that the main reduction preserves the sparsity of the original matrix. This conditional hardness result is tight as the best algorithms for (exactly) solving linear equations run in time \(\tilde{O}(\text{nnz}(A) \cdot n)\)  [1]} which is equal to \(\tilde{O}(n^2)\)  for sparse matrices.
