21
$\begingroup$

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?

$\endgroup$
5
  • 3
    $\begingroup$ The n! way is by cofactor expansion, which is probably the slowest algorithm you could use. $\endgroup$
    – Larry Wang
    Jul 23, 2010 at 18:04
  • 2
    $\begingroup$ This question is more appropriate to go onto Stackoverflow.com $\endgroup$
    – Jason S
    Jul 23, 2010 at 18:08
  • 3
    $\begingroup$ @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) $\endgroup$
    – Larry Wang
    Jul 23, 2010 at 18:21
  • $\begingroup$ An SO question, stackoverflow.com/questions/1886280/…, gives a good summary of efficient algorithms for finding determinants of potentially large matrics. $\endgroup$ Jul 23, 2010 at 20:39
  • 2
    $\begingroup$ Note that if your matrix is fully symbolic, then the size of the 'answer' for the determinant is indeed O(n!). $\endgroup$ Aug 4, 2010 at 1:40

3 Answers 3

17
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks. I imagine that proving that is quite an enormous amount of work. $\endgroup$ Jul 23, 2010 at 17:51
  • 2
    $\begingroup$ Actually it's one of the first things you learn in introductory linear algebra classes. $\endgroup$ Jul 23, 2010 at 18:21
  • $\begingroup$ Well, I haven't learned the proof yet... I don't think he even mentioned how it is done... $\endgroup$ Jul 23, 2010 at 18:29
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 23, 2010 at 18:42
  • 5
    $\begingroup$ 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$]. $\endgroup$ Aug 4, 2010 at 1:36
14
$\begingroup$

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

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

$\endgroup$
5
  • 3
    $\begingroup$ 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.) $\endgroup$ Jul 23, 2010 at 20:13
  • 1
    $\begingroup$ 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 . $\endgroup$ Jul 30, 2010 at 17:33
  • $\begingroup$ @Jitse: Yes, as Noah notes, they all rely on the fastest algorithm to multiply matrices. $\endgroup$ Jul 30, 2010 at 17:38
  • 1
    $\begingroup$ 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) $\endgroup$ Aug 4, 2010 at 1:03
  • 4
    $\begingroup$ 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). $\endgroup$ Aug 4, 2010 at 1:38
6
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .