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$ – Per Alexandersson Feb 27 '14 at 16:07
  • $\begingroup$ @PerAlexandersson But how usable are these bounds? Evaluating the determinants is all too often a formidable task in itself. $\endgroup$ – Felix Goldberg Feb 27 '14 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$ – Per Alexandersson Feb 28 '14 at 12:52
  • $\begingroup$ @PerAlexandersson The exact evaluation problem is indeed hard; but bounds may be easier to obtain :) $\endgroup$ – Felix Goldberg Feb 28 '14 at 13:10
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 '14 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, privacy policy and cookie policy

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