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!


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?

  • $\begingroup$ 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. $\endgroup$ – Denis Serre Nov 6 '10 at 19:49
  • $\begingroup$ 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). $\endgroup$ – Aaron Meyerowitz Nov 6 '10 at 20:34
  • $\begingroup$ I restricted $A$ to be "strictly positive definite", so all eigenvalues are strictly bigger than zero, so $A$ is not singular. $\endgroup$ – Suvrit Nov 6 '10 at 20:57
  • $\begingroup$ @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. $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Suvrit Nov 8 '10 at 10:32
  • $\begingroup$ @Suvrit. Yes, this is an interesting question. $\endgroup$ – Denis Serre Nov 8 '10 at 14:04

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


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.