1
$\begingroup$

For a symmetric, invertible matrix $A=(a_{ij})\in \mathbb{R}^{n\times n}$ with (at least two) nonzero off-diagonal elements, is it possible to bound in absolute value the smallest entry of its inverse in terms of the $a_{ij}$? And if so how?

If this is difficult to answer in such a general setting, would assuming that $A$ is either positive definite or sparse help simplifying the problem? Are there other assumptions that could help simplifying the problem?

$\endgroup$
4
  • 3
    $\begingroup$ You get bounds from Cramers rule quite directly: en.wikipedia.org/wiki/Cramer%27s_rule The smallest entry is the smallest possible value in the adjugate matrix, divided by the determinant of the original matrix. $\endgroup$ Feb 27, 2014 at 16:07
  • $\begingroup$ @PerAlexandersson But how usable are these bounds? Evaluating the determinants is all too often a formidable task in itself. $\endgroup$ Feb 27, 2014 at 23:12
  • $\begingroup$ @FelixGoldberg: Oh, it is not easy; this is just an illustration on that the problem is as hard as computing determinants. $\endgroup$ Feb 28, 2014 at 12:52
  • $\begingroup$ @PerAlexandersson The exact evaluation problem is indeed hard; but bounds may be easier to obtain :) $\endgroup$ Feb 28, 2014 at 13:10

2 Answers 2

2
$\begingroup$

Well, you are asking for a lot, but with some assumptions there are results for this problem. There is also a big difference between diagonal entries and off-diagonal and lower and upper bounds. But it's not hopeless!

Have a look at these papers:

Robinson & Wathen, Variational bounds on the entries of the inverse of a matrix

Golub & Meurant, Matrices, Moments and Quadrature

Benzi & Golub, Bounds for the entries of matrix functions with applications to preconditioning

These papers mostly handle the positive definite case. Another kind of approach, which doesn't even require symmetry, assumes instead diagonal dominance of $A$. This kind of stuff is mostly embedded as lemmas in other things so one has to know where to look for it. For example, Lemma 2.1 here.

I had studied this subject in some detail so if you are interested, I can try to help more specifically as well.

$\endgroup$
1
  • $\begingroup$ Thank you very much! I will go through the papers and the link. $\endgroup$
    – user47575
    Mar 1, 2014 at 23:12
0
$\begingroup$

Note $$\pmatrix{1&1-\epsilon\cr1-\epsilon&1}^{-1}={1\over2\epsilon-\epsilon^2}\pmatrix{1&-1+\epsilon\cr-1+\epsilon&1\cr}$$ so the inverse has rather large entries (for small $\epsilon$) while the matrix has rather moderate-sized entries. $$\pmatrix{1&1-\epsilon&0\cr1-\epsilon&1&0\cr0&0&I\cr}$$ is a sparse example (here, $I$ is the identity matrix of whatever size you like).

$\endgroup$

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.