Question

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?

Answer 1

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

Answer 2

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