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?
Best Answer
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.