patternModerate
Complexity class of Matrix Inversion
Viewed 0 times
inversionmatrixclasscomplexity
Problem
Is inverting a matrix in the Complexity class $\text{P}$ ?
From the runtime I would say yes $\mathcal{O}(n^3)$ but the inverted matrix can contain entries where the size is not polynomially bounded by the input?
From the runtime I would say yes $\mathcal{O}(n^3)$ but the inverted matrix can contain entries where the size is not polynomially bounded by the input?
Solution
Yes, it can be done in polynomial time, but the proof is quite subtle. It's not simply $\mathcal{O}(n^3)$ time, because Gaussian elimination involves multiplying and adding numbers, and the time to perform each of those arithmetic operations is dependent on how large they are. For some matrices, the intermediate values can become extremely large, so Gaussian elimination doesn't necessarily run in polynomial time.
Fortunately, there are algorithms that do run in polynomial time. They require quite a bit more care in the design of the algorithm and the analysis of the algorithm to prove that the running time is polynomial, but it can be done. For instance, the running time of Bareiss's algorithm is something like $\mathcal{O}(n^5 (\log n)^2)$ [actually it is more complex than that, but take that as a simplification for now].
For lots more details, see Dick Lipton's blog entry Forgetting Results and What is the actual time complexity of Gaussian elimination? and Wikipedia's summary.
Finally, a word of caution. The precise running time depends upon exactly what field you are working over. The above discussion applies if you are working with rational numbers. On the other hand, if, for instance, you are working over the finite field $\mathrm{GF}(2)$ (the integers modulo 2), then naive Gaussian elimination does run in $\mathcal{O}(n^3)$ time. If you don't understand what this means, you can likely ignore this last paragraph.
Fortunately, there are algorithms that do run in polynomial time. They require quite a bit more care in the design of the algorithm and the analysis of the algorithm to prove that the running time is polynomial, but it can be done. For instance, the running time of Bareiss's algorithm is something like $\mathcal{O}(n^5 (\log n)^2)$ [actually it is more complex than that, but take that as a simplification for now].
For lots more details, see Dick Lipton's blog entry Forgetting Results and What is the actual time complexity of Gaussian elimination? and Wikipedia's summary.
Finally, a word of caution. The precise running time depends upon exactly what field you are working over. The above discussion applies if you are working with rational numbers. On the other hand, if, for instance, you are working over the finite field $\mathrm{GF}(2)$ (the integers modulo 2), then naive Gaussian elimination does run in $\mathcal{O}(n^3)$ time. If you don't understand what this means, you can likely ignore this last paragraph.
Context
StackExchange Computer Science Q#38353, answer score: 14
Revisions (0)
No revisions yet.