1
$\begingroup$

I'd like to find a condition that allows me to determine if a matrix is invertible or not. naively, I computed the determinant to see if it was zero. but then I realized that even for very small values (1e-100), lapack is still able to find an invert matrix.

I read here that a $QR$ factorization can be used to compute the rank of a matrix.

Is a $QR$ factorization the best way to check if a matrix is invertible? will it take into account the numerical errors ? is there a more efficient way ?

I also found this link that gives a reciprocal condition number $\kappa$. What does this number mean ? I know that if $\kappa=\infty$ then the matrix is singular ! But what is the cutoff, what is $\infty$ for a computer ?

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ For rank estimation/measuring closeness to singularity, in the prescence of fuzzy data or roundoff, the singular value decomposition is probably the most reliable calculation. Lapack provides routines to compute it (dgesvd, for instance). Wikipedia page has an SVD page, see the subsections regarding "Range, null space and rank" and "Low-rank matrix approximation". Golub and van Loan have good material as well, see section 2.5 entitled "Orthogonality and the SVD" (it deals with the intepretation of the SVD, actually calculating it requires more machinery and appears much later in the book). $\endgroup$
    – rchilton1980
    Commented Jul 5, 2013 at 14:09
  • 2
    $\begingroup$ The condition number (ratio of largest to smallest singular values from the SVD) is normally used as a measure of closeness to singularity. For double precision matrices, any condition number bigger than 1.0e15 is effectively singular just due to the limits of double precision floating point. However, much smaller condition numbers can be problematic if the data in your problem are not very precise. $\endgroup$
    – Brian Borchers
    Commented Jul 5, 2013 at 15:51
  • 1
    $\begingroup$ Are you solving a system of equations that involves measured data? If they're only accurate to one part in $10^4$, then your solutions will not be trustworthy as soon as the condition number reaches $10^4$. $\endgroup$
    – Brian Borchers
    Commented Jul 5, 2013 at 17:13
  • 1
    $\begingroup$ LAPACK provides a condition number estimate along with the LU factorization, but this estimate is not very precise at all (in my experience, it can easily be off by a factor of 10 or more.) However, it often doesn't matter exactly how big the condition number is (e.g. it's "way too large!") so this might be entirely adequate for your purposes. $\endgroup$
    – Brian Borchers
    Commented Jul 5, 2013 at 17:16
  • 1
    $\begingroup$ The condition number provides an upper bound on the error in the computation of a solution to your system of equations (or the computation of an inverse) with respect to any noise on the right hand side or in the matrix elements. It doesn't follow that you will necessarily see an error that large. $\endgroup$
    – Brian Borchers
    Commented Jul 12, 2013 at 1:16

1 Answer 1

Reset to default
-1
$\begingroup$

LU factorization exists only if the matrix is invertible (Not LUP). A common way to do this in Lapack is to try to obtain the LU decomposition. Many Lapack libraries will throw you an info code, stating the reason of failure. If your matrix is not invertible LU decomposition output "info" will not be 0 and you can check this flag to decide if your matrix is invertible or not.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "LU factorization exists only if the matrix is invertible (Not LUP)". No. $\begin{bmatrix}1 & 0\\ 0 & 1\end{bmatrix}\begin{bmatrix}1 & 0\\ 0 & 0\end{bmatrix}$ is a LU decomposition. $\endgroup$
    – Federico Poloni
    Commented Jan 9, 2014 at 14:00
  • $\begingroup$ You are right that it depends on singularities of principal minors, I skipped this part. $\endgroup$
    – Tolga Birdal
    Commented Jan 9, 2014 at 14:37
  • $\begingroup$ On the other hand, if matrix is symmetric, checking Cholesky decomposition the same way is an approach. $\endgroup$
    – Tolga Birdal
    Commented Jan 9, 2014 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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