<p>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.</p>

<p>References:</p>

<p>Ibarra, O. , Moran, S. , and Hui, R. 1982. <a href="http://www.sciencedirect.com/science/article/pii/0196677482900074">A generalization of the fast LUP matrix decomposition algorithm and applications</a>. Journal of Algorithms 3 , 45{56.</p>

<p>Jeannerod, C.-P. , Pernet, C. , and Storjohann, A. 2011. <a href="https://cs.uwaterloo.ca/~astorjoh/ple.pdf">Rank profile revealing Gaussain
elimination and the CUP matrix decomposition</a>.</p>

CC BY-SA 3.0
2014-07-29T14:52:26.187Z
2014-07-29T14:52:26.187Z
R B
<p>I’m not sure this is a research-level question, however solving linear systems over $\mathbb F_p$ is a <a href="http://link.springer.com/article/10.1007%2FBF01374526">$\mathrm{Mod}_p\mathrm L$-complete</a> 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.</p>

CC BY-SA 3.0
2014-07-29T14:53:00.587Z
2014-07-29T15:00:11.230Z
2014-07-29T15:00:11.230Z
Emil Jeřábek
<p>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?</p>

<cc.complexity-theory><linear-equations>
Complexity of solving linear equations
Alan
# Complexity of solving linear equations

(Asked by: username_0 on 2014-07-29)

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?

**Tags:** cc.complexity-theory, linear-equations

---

## 2 answers

### Answer by username_2 on 2014-07-29. Score: 12 | Accepted answer

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](http://link.springer.com/article/10.1007%2FBF01374526) 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.


---

### Answer by username_1 on 2014-07-29. Score: 7

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](http://www.sciencedirect.com/science/article/pii/0196677482900074). 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](https://cs.uwaterloo.ca/~astorjoh/ple.pdf).


---

