Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm designing a unit-test for a matrix inversion function. Currently I make a random matrix as a test case by generating its elements with random numbers uniformly distributed in $[0,1)$. If I stopped here, there would be a small, but non-zero, chance that the resulting matrix will be numerically ill-conditioned for inversion.

I know that I can solve this problem by diagonal loading of the matrix, i.e. adding a value $c$ to the diagonal elements $M_{ii}$.

Is there an easy way to compute that amount of diagonal loading $c$ that I can add to such a random matrix to ensure that it is not (numerically) ill-conditioned for inversion?

My hunch is that the size of $c$ depends (at least) on the size of the matrix $N$, but I don't know how to derive the relationship. Also note, that I'm not trying to find a smallest $c$ for the specific matrix under consideration, but rather a general $c$ applicable to any of my random matrices.

share|improve this question
2  
Thank you for that interesting question. I wonder however if avoiding the numerically hard cases is the right approach. Those cases might happen in real world applications and it would be interesting to see how the routine reacts. If you check the condition number and it turns out large I would consider a "is not invertible" as an expected failure and thus good behaviour. –  mvw Sep 4 at 14:47

1 Answer 1

up vote 11 down vote accepted

It sounds like you want the Gershgorin circle theorem. Since all the off-diagonal matrix entries are at most $1$, you can guarantee that no eigenvalue of your matrix is too small by ensuring that all the diagonal entries are substantially larger than $N-1$.

That is, taking $c=N$ should suffice.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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