6
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\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
    Commented Nov 6, 2010 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
    Commented Nov 6, 2010 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
    Commented Nov 6, 2010 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
    Commented Nov 6, 2010 at 21:16
  • $\begingroup$ I am looking for the same thing, the upper bound of the sum of entries of the inverse convariance matrix. From the current answer, I cannot see a solution for this question (an approximation for $\gamma(n)$). Did you find something so far? $\endgroup$
    – Maryam Bahrami
    Commented Aug 23, 2021 at 14:18

2 Answers 2

Reset to default
7
$\begingroup$

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

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

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

Improve this answer
$\endgroup$

You must log in to answer this question.

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