# In terms of complexity, is there a quicker way of checking if a matrix is nonsingular than computing the determinant?

To repeat the question, let $A$ be a square matrix. We wish to determine if $A$ is nonsingular, that is, invertible. One way is compute its determinant and check if it is nonzero. However, if $A$ is invertible, calculating its determinant gives us strictly more information that knowing that it is nonzero.

Although the naive complexity for calculating the determinant is $O(n!)$, faster $O(n^3)$ algorithms exist. It does not seem unreasonable to suppose that their might be an algorithm that checks for nonsingularity that has strictly lower complexity than the fastest algorithms known for computing the determinant. Is such an algorithm known to exist? Can such an algorithm exist? (I am quite ignorant in these areas of computational complexity)

I am primarily interested in the case where $A$ is a real or complex matrix, but the case of rational matrices, or matrices over finite fields are also of interest. Feel free to discuss matrices over an arbitrary ring if you think it can clarify this discussion.

Thanks in advance for any insight you can spare!

• Gaussian elimination (i.e, row-reduction). Commented Nov 18, 2012 at 5:02
• Doesn't row reduction have arithmetic complexity $O(n^3)$? Commented Nov 18, 2012 at 5:05
• @Isaac: yes, but this is already substantially better than the naive complexity of computing the determinant, which first of all contains $n!$ terms... Commented Nov 18, 2012 at 5:07
• Note that over the field of two elements, computing the determinant is equivalent to determining singularity. Commented Nov 18, 2012 at 5:11
• Of course. When I made my original comment, I wasn’t paying attention to who posted the question, so I wasn’t assuming awareness of that fact: in my experience many undergraduates know only cofactors. Had I noticed who was asking, I’d not have bothered. Commented Nov 18, 2012 at 5:20

There are two methods that are quite good methods to check for singularity:

1. As pointed out in comments, Gaussian elimination is a very efficient method for checking it.

2. Another way is using conditional number of the matrix. As we know, If conditional number is $\infty$ then matrix is non singular. So calculate the condition number of your matrix and compare with $\frac {1}{\text{e.p.s.}}$ . Now the problem reduces to finding condition number. As far as I know, finding conditional number is easier than finding determinants.

EDIT:

All I know about finding Condition number...

1. If your matrix is triangular, you can approximate condition number by $\kappa(A) \geq \frac{\max_i(|a_{ii}|)}{\min_i(|a_{ii}|)}$, it is a reasonable approximation but gives some wrong results. Note that if we use QR factorisation, we can say that $\kappa (A)=\kappa(Q) \text{ if } A=QR$. Though for upper triangular matrix, we can find conditional no. in $O(n)$.

2. For tridiagonal matrix it can be found in $O(n). 3. For other matrices either first perform QR, then use 1, or try to find the singular values for the matrix as condition number is the ratio of largest singular value to smallest. Now one way of doing is to use SVD decomposition or directly finding the singular values. Though SVD decomposition takes$O(n^3)$. I think algorithms for just finding singular values exist and (should be) faster. You'll have to search for them.. Remaining is my personal view and you are free to disagree, hence I've hidden it :-) Also I think that practicality of algorithms should be taken in consideration. Yes, it is true that we can find determinant in$O(n^3)$, same as Gaussian elimination, but Gaussian elimination is easy to implement whereas determinant is not so easy to implement. (For example, I can implement Gaussian elimination but I don't even know what the algorithm for determinant in$O(n^3)$is? • Thanks for the answer. Do you know what the complexity of finding the condition number is, or where I might be able to read up on such a question? Commented Nov 18, 2012 at 16:44 • For the record, the$O(n^3)\$ algorithm for the determinant is essentially: (1) perform Gaussian elimination, keeping track of sign changes in the determinant whenever you swap rows (2) once you are done, you have obtained a triangular matrix with the same determinant as the initial one (up to those sign changes); its determinant is then the product of its diagonal entries. Commented Sep 18, 2021 at 8:30

I asked this question recently on Twitter, and did some digging and found what might be a better answer than these two.

Volker Strassen in 1969 showed that matrix inversion, calculating the determinant, gaussian elimination and matrix multiplication are all equally fast / slow. Currently the fastest algorithm is O(n^2.3728596)

However, figuring out if a square matrix can be inverted is (perhaps) a simpler problem: a square matrix is invertible if its rank = its dimension.

There seem to be faster algorithms to calculate rank if the matrix is sparse:

This does seem to suggest that in a typical / random dense square matrix, determining invertibility is basically as hard as inverting it. I'd love to know if this is clearly proven.

Note: There might be additional fanciness possible if the matrix only has small integers