Determinant and Condition Number

The determinant of a matrix a_ij is given by

where the a_ii⁽ⁱ⁾ come from the LU (link). If it is a very large or very small number, it can be divided or multiplied by 10 to retain accuracy in the computer; the scale factor is then accumulated separately. The condition number can be defined in terms of the singular value decomposition (link) The condition number is then ratio of the largest w_i to the smallest w_i (link). It can also be expressed in terms of the norm of the matrix.

where the norm is defined as

If this number is infinite the set of equations is singular. If the number is too large the matrix is said to be ill-conditioned. The definition of "large" refers to the accuracy of the computer being used; the criterion is the inverse of the floating point precision. If the machine's floating point precision is 10^-6 then 10⁶ is large; if double precsion is used then the precision is 10^-12 and 10¹² is large. The calculation of the condition number can be lengthy so that another criterion is also useful. Compute the ratio of largest to smallest pivot and make judgments on the ill-conditioning based on that.

Another empirical test is the quantity V defined below; when V is small the matrix is ill-conditioned.

When a matrix is ill-conditioned it is important to perform the LU decomposition using pivoting (or use the singular value decompostion (link)). With pivoting one just rearranges the order of the elimination. At each stage one looks for the largest element (in magnitude) and makes that the next row-column to be processed. The largest element can be obtained only from the diagonal entries (partial pivoting) or from all the remaining entries. If the matrix is non-singular then Gaussian elimination (or LU decomposition) could fail if a zero value were to occur along the diagonal and were to be a pivot. With full pivoting, though, the Gaussian elimination (or LU decomposition) cannot fail if the matrix is non-singular.