# Tight bound for sum of entries of the inverse of a nonnegative matrix

While playing around with certain non-negative matrices, I got stuck at the following question.

Let $A$ be a strictly positive-definite $n \times n$ matrix ($n \ge 3$), with ones on the diagonal, and all other entries in the range $[0,1]$. How should I go about proving a tight bound on the sum of the entries of $A^{-1}$. In symbols, how should I go about trying to compute the smallest number $\gamma(n)$ such that $$1^TA^{-1}1 \le \gamma(n).$$

Any pointers to related work, or some possible ways to attack the problem will be very useful. Of course, if you think this question is not well-formulated, please help me improve it!

Remarks:

a. Notice that for the special case where $A$ is the identity matrix, we have equality, and $\gamma(n)=n.$

b. If the vector of all ones, i.e., $1$, happens to be an eigenvector of $A$, then also we have an instant answer.

More background

The reason I reached the above bounding problem was that I was looking at the matrix $$\begin{bmatrix} A & 1\\\\ 1^T & n\end{bmatrix},$$ and trying to prove that it is positive semidefinite. So, either I could show that $A-11^T/n \succeq 0$, or $1^TA^{-1}1 \le n$. Now, since the bound with $n$ might not always hold, I started searching for a $\gamma(n)$ that holds. Perhaps, I need to further cleanup my question?

• Your assumptions allow $A$ to be singular (not invertible). Therefore it is likely that there is no finite upper bound $\gamma(n)$ without additional information. – Denis Serre Nov 6 '10 at 19:49
• AT least for the 2x2 case near singularity is not a problem and it appears that the identity matrix gives the maximum. Dod you want the maximum as A runs over all such n by n matrices or a formula for a particular A? In the latter case there is a symbolic expression for the inverse and hence for the whole sum (albeit not a nice one). – Aaron Meyerowitz Nov 6 '10 at 20:34
• I restricted $A$ to be "strictly positive definite", so all eigenvalues are strictly bigger than zero, so $A$ is not singular. – Suvrit Nov 6 '10 at 20:57
• @Aaron: oops, I forgot to add, that I am looking at $n \ge 3$ (though, even for this case, I guess, one can write out (a messy) explicit formula. – Suvrit Nov 6 '10 at 21:16

When $n\ge3$, there does not exist such a bound. To see this, take $n=3$ and the following matrix $$A=\begin{pmatrix} 1 & a & 0 \\\\ a & 1 & a \\\\ 0 & a & 1 \end{pmatrix}.$$ If $a< 1/\sqrt2$, it is positive definite with non-negative entries. However $$1^TA^{-1}1=\frac{3-4a}{1-2a^2}$$ is not bounded as $a\rightarrow1/\sqrt2$.
• So in light of this answer, instead of looking for bounds of this form, ask my original question (I think I should make a new question): to describe the class of matrices for which $1^TA^{-1}1 \le n$ holds. – Suvrit Nov 8 '10 at 10:32
Let $M$ be a zero/one random symmetric matrix with zero diagonal. Presumably the eigenvector $v$ corresponding to the smallest eigenvalue of $M$ is not perpendicular to the all-ones vector 1 with high probability. Choose $v$ to be normalized so that $d = 1^T v > 0$ and $v^T v = 1$. Then choose $\alpha>0$ so that $A=I+\alpha M$ has smallest eigenvalue (with eigenvector $v$ obviously) of $d^2 / (2n)$. Now $v^T(A-1\cdot 1^T/n)^v = v^T A v -v^T 1\cdot 1^T v / n = d^2/(2n) - d^2/n<0$, so $A - 1 \cdot 1^T / n \not \succeq 0$.