0
$\begingroup$

I have a square matrix of the form:

$$M = X^T X + A$$

where $A$ is a diagonal matrix whose diagonal elements are positive, and $X$ is a rectangular matrix (assume that matrix dimensions in this equation are consistent). Then, $M$ is positive definite and symmetric. In particular, it is invertible.

Is the following inequality true in general?

$$(M^{-1})_{nn} < \frac{1}{a_{nn}}$$

where $a_{nn}$ denotes the diagonal entries of $A$. I've done some numerical simulations with random matrices and it seems to hold. But I have not been able to prove it in general.

$\endgroup$

migrated from mathoverflow.net Jun 4 '18 at 22:36

This question came from our site for professional mathematicians.

  • $\begingroup$ Let $B=X'X$. Then, $M=B+A$, and $M^{-1} = (B+A)^{-1}$. Intuitively, since $(b+a)^{-1} \le a^{-1}$ for positive scalars, your inequality is a matrix version of this idea. As noted by Mark below, the key idea here is to observe that $M \ge A$, and then conclude that $M^{-1} \le A^{-1}$, from which it follows that $e_n^TM^{-1}e_n=(M^{-1})_{nn} \le 1/a_{nn}$. This question is, however, not really a research question, and I feel it may be more suitable for M.SE. $\endgroup$ – suvrit Jun 4 '18 at 19:34
3
$\begingroup$

The claim as stated is trivially false. Choose $X =$ matrix of zeros. Then $(M^{-1})_{nn} = \frac{1}{a_{nn}}$

However, $(M^{-1})_{nn} \le \frac{1}{a_{nn}}$ is true, because $M - A$ is positive semidefinite. Therefore, $A^{-1} -M^{-1}$ is positive semidefinite (see derivation below), and thus has nonnegative diagonal elements.

Here is a derivation that $M \succeq A$ implies $M^{-1} \preceq A^{-1}$, given of course, as is the case here, that $M^{-1}$ and $A^{-1}$ exist.

By Schur complement on the identity matrix, $I$, in the below, we have that $M \succeq A$ implies $$\left[\begin{array}{l}I&A^{1/2}\\A^{1/2}&M\end{array}\right] \succeq 0$$. Now applying Schur complement on $M$, we have $$I - A^{1/2}M^{-1}A^{1/2} \succeq 0$$ Applying a similarity transform with $A^{-1/2}$ to the LHS, which leaves its eigenvalues unchanged, we have $A^{-1} - M^{-1} \succeq 0$

$\endgroup$
  • 1
    $\begingroup$ So if $X^T X$ is positive-definite then the strict equality holds. $\endgroup$ – becko Jun 4 '18 at 15:50
  • $\begingroup$ I did not understand the step where you claim that $A^{-1} - M^{-1}$ is positive semi-definite? How do you get to that? $\endgroup$ – becko Jun 4 '18 at 15:51
  • $\begingroup$ Although this proves the result, I feel like there should be a more "direct" derivation. I still don't feel like I see why it is true. $\endgroup$ – becko Jun 4 '18 at 16:46
  • $\begingroup$ For future reference, the Schur complementarity theorem needed is Theorem 1.12 of the book The Schur Complement and Its Applications, by Zhang, Fuzhen (Springer, 2005). $\endgroup$ – becko Jun 5 '18 at 0:11
  • 1
    $\begingroup$ Or section A5.5 of the freely available book in pdf form, "Convex Optimization" by Boyd and Vandenberghe web.stanford.edu/~boyd/cvxbook $\endgroup$ – Mark L. Stone Jun 5 '18 at 0:29

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.