# What is the most efficient way to determine if a matrix is invertible?

I'm learning Linear Algebra using MIT's Open Courseware Course 18.06

Quite often, the professor says "... assuming that the matrix is invertible ...".

Somewhere in the lecture he says that using a determinant on an $n \times n$ matrix is on the order of $O(n!)$ operations, where an operation is a multiplication and a subtraction.

Is there a more efficient way? If the aim is to get the inverse, rather than just determine the invertibility, what is the most effecient way to do this?

-
The n! way is by cofactor expansion, which is probably the slowest algorithm you could use. –  Larry Wang Jul 23 '10 at 18:04
This question is more appropriate to go onto Stackoverflow.com –  Jason S Jul 23 '10 at 18:08
@Jason: It would be an appropriate question for stackoverflow, but it's also a good question here. Linear algebra and algorithmic complexity are math. (Also, on stackoverflow it would get instantly closed as an exact duplicate) –  Larry Wang Jul 23 '10 at 18:21
An SO question, stackoverflow.com/questions/1886280/…, gives a good summary of efficient algorithms for finding determinants of potentially large matrics. –  Charles Stewart Jul 23 '10 at 20:39
Note that if your matrix is fully symbolic, then the size of the 'answer' for the determinant is indeed O(n!). –  Jacques Carette Aug 4 '10 at 1:40

Gauss-Jordan elimination can be used to determine when a matrix is invertible and can be done in polynomial (in fact, cubic) time. The same method (when you apply the opposite row operation to identity matrix) works to calculate the inverse in polynomial time as wel.

-
Thanks. I imagine that proving that is quite an enormous amount of work. –  John Gietzen Jul 23 '10 at 17:51
Actually it's one of the first things you learn in introductory linear algebra classes. –  BlueRaja - Danny Pflughoeft Jul 23 '10 at 18:21
Well, I haven't learned the proof yet... I don't think he even mentioned how it is done... –  John Gietzen Jul 23 '10 at 18:29
@John: If you've learned how to solve a system of linear equations (represented by a matrix), or equivalently, how to find the inverse of a matrix, you know Gauss-Jordan elimination. If this process results in a row of all 0's, it means the matrix can't be inverted. However, this is not the most efficient method of determining if a matrix can be inverted; see my answer for that. –  BlueRaja - Danny Pflughoeft Jul 23 '10 at 18:42
That assumes that the matrix coefficients are of uniformly bounded size and do not grow at all when doing GJ. This is false for most rings! In other words, you are assuming that coefficient operations are O(1), which is almost always false in bit-complexity [exception: $Z_q$]. –  Jacques Carette Aug 4 '10 at 1:36

A matrix is invertible iff its determinant is non-zero.

There are algorithms which find the determinant in slightly worse than O(n2)

-
Conjecturally one should be able to get to O(n^{2+\epsilon}) but as your link says the current record is around 2.376. Interestingly enough there are now two completely different ways to get to 2.376, which might suggest that that's actually as good as you can do. (It's also worth noting that nearly all problems in linear algebra have the same complexity, e.g. matrix multiplication and taking determinants.) –  Noah Snyder Jul 23 '10 at 20:13
The theoretical complexity of LU-decomposition, which is basically the same as Gauss-Jordan elimination, is precisely the same: en.wikipedia.org/wiki/LU_decomposition#Theoretical_complexity . –  Jitse Niesen Jul 30 '10 at 17:33
@Jitse: Yes, as Noah notes, they all rely on the fastest algorithm to multiply matrices. –  BlueRaja - Danny Pflughoeft Jul 30 '10 at 17:38
Finding the determinant is not necessarily of the same complexity as deciding whether it is zero (for example, you can get rid of denominators if you are working over rational numbers) –  Mariano Suárez-Alvarez Aug 4 '10 at 1:03
See my comment on Akhil Matthew's answer -- these are not bit-complexity results, these are results assuming O(1) coefficient operations. For example, this does not work for random integer matrices (because of coefficient growth). –  Jacques Carette Aug 4 '10 at 1:38

Computing the determinant and Gaussian elimination are both fine if you are using exact computations, for instance if the entries of your matrix are rational numbers and you are using only rational numbers during the computations. The disadvantage is that the numerator and denominator can get very large indeed. So the number of operations may indeed be O(n2.376) or O(n3), but the cost of every addition and multiplication gets bigger as n grows because the numbers get bigger.

This is not an issue if you are using floating point numbers, but then you have the problem that floating point computations are not exact. Some methods are more sensitive to this than others. In particular, checking invertibility by computing the determinant is a bad idea in this setting. Gaussian elimination is better. Even better is to use the singular value decomposition, which will be treated towards the end of the MIT course.

-