# Bound on smallest entry of inverse matrix

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?

• 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. – Per Alexandersson Feb 27 '14 at 16:07
• @PerAlexandersson But how usable are these bounds? Evaluating the determinants is all too often a formidable task in itself. – Felix Goldberg Feb 27 '14 at 23:12
• @FelixGoldberg: Oh, it is not easy; this is just an illustration on that the problem is as hard as computing determinants. – Per Alexandersson Feb 28 '14 at 12:52
• @PerAlexandersson The exact evaluation problem is indeed hard; but bounds may be easier to obtain :) – Felix Goldberg Feb 28 '14 at 13:10

## 2 Answers

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

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.

• Thank you very much! I will go through the papers and the link. – user47575 Mar 1 '14 at 23:12

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).