Fast method to check if a Matrix is singular? (non-invertible, det = 0)

Question

What is the fastest algorithm (a link to C or C++ example would be cool) to check if a small square matrix (<16*16 elements) is singular (non-invertible, det = 0) ?

Solution 1

Best way is to compute the condition number via SVD and check if it is greater than 1 / epsilon, where epsilon is the machine precision.

If you allow false negatives (ie. a matrix is defective, but your algorithm may not detect it), you can use the max(a_ii) / min(a_ii) formula from the Wikipedia article as a proxy for the condition number, but you have to compute the QR decomposition first (the formula applies to triangular matrices): A = QR with R orthogonal, then cond(A) = cond(Q). There are also techniques to compute the condition number of Q with O(N) operations, but there are more complex.

Solution 2

I agree with Gaussian elimination. http://math.nist.gov/javanumerics/jama/doc/Jama/LUDecomposition.html documents LU decomposition - after constructing the LU decomposition from a matrix you can call a method on it to get the determinant. My guess is that it is at least worth timing this to compare it with any more specialised scheme.

Comments

[phs]

An epsilon distance check from zero is in order for floating point matrices.

[nhahtdh]

He will need a meta-program to generate the hard-code formula.

[Alexandre C.]

For n=16 this may well be quite cumbersome to write.

[Alexandre C.]

LU decomposition is the standard way to compute determinants. Determinants are just not the standard way to test defectiveness of a matrix.

[BlueRaja - Danny Pflughoeft]

-1 For n=15 Leibniz's formula will have 1.3 trillion summands. This is not a realistic answer.

[Michael Conlen]

Using LAPACK we can use DGECON/SGECON for double/single precision general matrices or one of the similar routines for matrices with usable structure (banded, symmetric, etc). This uses LU factorization

[RandomSort]

-1, the issue is not how to generate the code effectively. The issue is with the general time complexity of the problem.