If $A\succ0$ and $J$ is the matrix of ones, then $A \succeq J$ if and only if $\mathrm{trace}(A^{-1}J)\leq 1$

Question

I'm trying to prove that if $A \in \mathbb{R}^{n \times n}$ is positive definite, and $J$ is the $n \times n$ matrix of ones, then $A \succeq J$ if and only if $\mathrm{trace}(A^{-1}J) = \sum_{i,j} A^{-1}_{i,j} \leq 1$.

For the $\Rightarrow$ direction, I'm able to show that $A \succeq J \implies I - A^{-1}J \succeq 0 \implies \mathrm{trace}(I - A^{-1}J) \geq 0 \implies n \geq \mathrm{trace}(A^{-1}J)$, but this isn't the upper bound of 1 I was hoping for. I've also tried the using the eigendecomposition of $A$ but that didn't seem to get anywhere. For the $\Leftarrow$ direction I'm unsure where to start. Any pointers?

Answer 1

proof 1
$B:= A-J = A-\mathbf {11}^T$
then for any $\mathbf x\neq \mathbf 0$, such that $\mathbf x \perp\mathbf 1$

$\mathbf x^TB\mathbf x =\mathbf x^TA\mathbf x-\mathbf x^T\mathbf {11}^T\mathbf x=\mathbf x^TA\mathbf x \gt 0$

so there is an $n-1\times n-1$ subspace where $B$ is positive definite, i.e. $B$ has signature $\big(\geq n-1,\leq 1\big)$.

Put differently $B$ has at least $n-1$ positive eigenvalues. To check on the nth eigenvalue, compute the determinant by applying the matrix-determinant lemma

$\det\big(B\big)= \det\big( A +(-\mathbf {11}^T)\big)=\det\big(A\big)\cdot \big(1-\mathbf 1^TA^{-1}\mathbf 1\big) =\det\big(A\big)\cdot \big(1-\text{trace}(A^{-1}J)\big) $

which is $\geq 0$ iff $\text{trace}\big(A^{-1}J\leq 1\big)$ i.e. $B\succeq \mathbf 0$ iff $\text{trace}\big(A^{-1}J\big)\leq 1$

proof 2
Adapting what OP has done

This issue is that one gives up too much by directly taking the trace. A better way if going down such a path is to write

$A \succeq J \implies I - A^{-\frac{1}{2}}JA^{-\frac{1}{2}} \succeq 0$. Now we know $\big(A^{-\frac{1}{2}}JA^{-\frac{1}{2}}\big)$ is real symmetric PSD with rank one, so its trace is given by selecting a quadratic form associated with its dominant eigenpair $\lambda_1$, $\mathbf x_1$ (with unit length)

now for any $\big \Vert \mathbf x\big\Vert_2=1$ we have

$\mathbf x^T\big( I - A^{-\frac{1}{2}}JA^{-\frac{1}{2}}\big)\mathbf x$
$=1 -\mathbf x^T\big( A^{-\frac{1}{2}}JA^{-\frac{1}{2}}\big)\mathbf x$
$\geq 1 -\mathbf x_1^T\big( A^{-\frac{1}{2}}JA^{-\frac{1}{2}}\big)\mathbf x_1$
$=1 - \text{trace}\big(A^{-\frac{1}{2}}JA^{-\frac{1}{2}}\big)$
$=1 - \text{trace}\big(A^{-1}J\big)$

which shows positive semi-definiteness if $1 - \text{trace}\big(A^{-1}J\big)\geq 0$
and for the other leg the result is immediate, i.e. $\mathbf x_1^T\big( I - A^{-\frac{1}{2}}JA^{-\frac{1}{2}}\big)\mathbf x_1\lt 0$ implies indefiniteness

Answer 2

For those familiar with Schur complment, one quick way to see the equivalence is to observe that the block matrix $$ B=\pmatrix{A&\mathbf1\\ \mathbf1^T&1} $$ is congruent to both $A\oplus(1-\mathbf1^TA^{-1}\mathbf1)$ and $(A-\mathbf1\mathbf1^T)\oplus1$. Since $A$ and $1$ are positive definite, it follows that $1-\mathbf1^TA^{-1}\mathbf1=1-\operatorname{tr}(A^{-1}J)\ge0$ if and only if $A-\mathbf1\mathbf1^T=A-J\succeq0$, and both inequalities are equivalent to $B\succeq0$.