Subject: Checking for matrix non-singularity

From: Tom Sundius U of Helsinki +358 0 1918339 <[email-masked]>
Date: Thu, 10 Mar 1994 12:01:54 +0200 (EET)

Recently there has been some discussion about how to check if a
matrix is non-singular. According to definition, a (square) matrix is
non-singular if it has an inverse, but there are several other definitions,
which are equivalent (a non-zero determinant and linearly independent
rows or columns). The determinant can be used to check for singularity,
but a direct calculation of the determinant is often unstable (and
timeconsuming). Using the LU decomposition method, the determinant can
be calculated as the product of the diagonal element of the U-matrix
(but one has to arrange the calculation to avoid over- or underflow).

A better method to check the condition of a matrix is to use the
"condition number", which is discussed (for instance) in the book by
Kahaner, Moler & Nash : Numerical methods and software. The condition
number of a matrix can be defined as the ratio of the norm of the matrix
and the norm of its inverse. If one performs a singular value decomposition
(SVD) of the matrix, the condition number can be calculated as the ratio
of the largest and the smallest singular value. Since a singular matrix
will have (at least) one singular value = 0, it follows that the 
condition number of a matrix close to singularity will be very large.