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?

Improve this question
$\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
    Commented 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$
    – Felix Goldberg
    Commented 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$
    – Per Alexandersson
    Commented Feb 28, 2014 at 12:52
  • $\begingroup$ @PerAlexandersson The exact evaluation problem is indeed hard; but bounds may be easier to obtain :) $\endgroup$
    – Felix Goldberg
    Commented Feb 28, 2014 at 13:10

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much! I will go through the papers and the link. $\endgroup$
    – user47575
    Commented 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).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .