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) ?

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

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