Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
3  
Gaussian elimination (i.e, row-reduction). –  Brian M. Scott Nov 18 '12 at 5:02
    
Doesn't row reduction have arithmetic complexity $O(n^3)$? –  Isaac Solomon Nov 18 '12 at 5:05
1  
@Isaac: yes, but this is already substantially better than the naive complexity of computing the determinant, which first of all contains $n!$ terms... –  Qiaochu Yuan Nov 18 '12 at 5:07
3  
Note that over the field of two elements, computing the determinant is equivalent to determining singularity. –  Gerry Myerson Nov 18 '12 at 5:11
2  
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. –  Brian M. Scott Nov 18 '12 at 5:20

1 Answer 1

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?

share|improve this answer
    
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? –  Isaac Solomon Nov 18 '12 at 16:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.