# Complexity of solving linear equations

What is known about the complexity of solving a system of linear equations over some finite field? I know that there exists an $O(n^3)$ algorithm (Gauss) that computes a solution and that for sparse systems there are even better algorithms. However, I was wondering if there was some comlexity-theoretic characterization of this problem. For example, is the corresponding decision problem in $\mathbf{NC}$? Is it complete for any complexity class?

-

I’m not sure this is a research-level question, however solving linear systems over $\mathbb F_p$ is a $\mathrm{Mod}_p\mathrm L$-complete problem, hence in particular it is in $\mathrm{NC}^2$. More generally, linear algebra over $\mathbb F_{p^k}$ (at least for $k$ fixed) can be reduced to the $\mathbb F_p$ case.

-

A result known for over 30 years is that Guassian Elimination over $\mathbb F_2$ can be done by a various decompositions which takes $O(n^\omega)$, where $\omega$ is the matrix multiplication constant.

References:

Ibarra, O. , Moran, S. , and Hui, R. 1982. A generalization of the fast LUP matrix decomposition algorithm and applications. Journal of Algorithms 3 , 45{56.

Jeannerod, C.-P. , Pernet, C. , and Storjohann, A. 2011. Rank profile revealing Gaussain elimination and the CUP matrix decomposition.

-