14
$\begingroup$

$\newcommand{\A}{\mathcal A}\newcommand{\Tr}{\operatorname{tr}}$For $c$ and $C$ such that $0<c<C<\infty$, let $\A_{d;c,C}$ denote the set of all symmetric positive-definite real $d\times d$ matrices $A$ such that $$cI\le A\le CI,$$ where $I$ is the $d\times d$ identity matrix and $A\le B$ for $d\times d$ matrices $A$ and $B$ means that $B-A$ is positive semidefinite. Let $|A|$ denote the determinant of a square matrix $A$.

Proposition 1: For any $A_0$ and $A_1$ in $\A_{d;c,C}$ \begin{equation} |A_1|-|A_0|\le L\|A_1-A_0\|_F\le L\sqrt d\,\|A_1-A_0\|, \end{equation} where $L:=C^d\sqrt d/c$, $\|\cdot\|_F$ is the Frobenius norm, and $\|\cdot\|$ is the spectral norm.

A proof of Proposition 1 will be given at the end of this post.

Question 1: Is Proposition 1 known?

Question 2: Can Proposition 1 be improved?

A correct and complete answer to either one of these questions will be considered a correct and complete answer to this entire post.


Proof of Proposition 1: In view of the inequality $\|B\|_F\le\sqrt d\,\|B\|$ for any matrix $B$, it is enough to prove the first inequality in Proposition 1.

Note that the set $\A_{d;c,C}$ is convex. For $A\in\A_{d;c,C}$, \begin{equation} f(A):=\sqrt{|A|}=(2\pi)^{-d/2}\int_{\mathbb R^d}dx\,e^{-x^\top A^{-1}x/2}. \end{equation} Let $X_A$ stand for any zero-mean Gaussian random vector in $\mathbb R^d$ with covariance matrix $A\in\A_{d;c,C}$. Let $\Tr A$ denote the trace of a square matrix $A$. Then the derivative of $f$ at $A$ applied to any $d\times d$ real matrix $D$ is \begin{equation} \begin{aligned} f'(A)(D)&=(2\pi)^{-d/2}\int_{\mathbb R^d}dx\,e^{-x^\top A^{-1}x/2}x^\top A^{-1}DA^{-1}x/2 \\ &=\frac{f(A)}2\,E(X_A^\top A^{-1}DA^{-1}X_A) \\ &=\frac{f(A)}2\,E\Tr(X_AX_A^\top A^{-1}DA^{-1}) \\ &=\frac{f(A)}2\,\Tr(EX_AX_A^\top A^{-1}DA^{-1}) \\ &=\frac{f(A)}2\,\Tr(DA^{-1}) \\ &\le\frac{f(A)}2\,\|D\|_F \|A^{-1}\|_F \\ &\le\frac{f(A)}2\,\|D\|_F \sqrt d\,\|A^{-1}\| \\ &\le\frac{C^{d/2}}2\,\|D\|_F \sqrt d\,/c=K\|D\|_F, \end{aligned} \end{equation} with $K:=\frac{C^{d/2}}2\,\sqrt d\,/c$. So, for any $A_0$ and $A_1$ in $\A_{d;c,C}$ \begin{equation} \sqrt{|A_1|}-\sqrt{|A_0|}=f(A_1)-f(A_0) \le K\|A_1-A_0\|_F, \end{equation} whence \begin{equation} |A_1|-|A_0|=(\sqrt{|A_1|}+\sqrt{|A_0|})(\sqrt{|A_1|}-\sqrt{|A_0|}) \\ \le 2C^{d/2}K\|A_1-A_0\|_F=L\|A_1-A_0\|_F, \end{equation} which proves the first inequality in Proposition 1. $\quad\Box$

$\endgroup$
5
  • 2
    $\begingroup$ For what it's worth, this is new to me. $\endgroup$
    – Nik Weaver
    Commented May 17, 2023 at 19:03
  • $\begingroup$ @NikWeaver : Thank you for your comment. $\endgroup$ Commented May 17, 2023 at 19:05
  • 1
    $\begingroup$ A tiny improvement in the last line of the long inequality: if the eigenvalues of $A$ are $\lambda_1\leq\cdots\leq \lambda_d$, then $f(A)\|A^{-1}\|=\lambda_1^{-1}\prod_{i=1}^d \sqrt{\lambda_i}\leq c^{-1/2}C^{(d-1)/2}.$ $\endgroup$
    – m7e
    Commented May 18, 2023 at 8:04
  • 1
    $\begingroup$ Another tiny observation is that $C^{d-1}$ is a lower bound on $L$, choosing $A_0=C I$ and $A_1=CI-\varepsilon e_1^Te_1$, where $e_1=(1,0,\ldots,0)$. $\endgroup$
    – m7e
    Commented May 18, 2023 at 8:19
  • $\begingroup$ @m7e : Thank you for your comments. $\endgroup$ Commented May 18, 2023 at 16:23

1 Answer 1

7
$\begingroup$

The best constant is $C^{d-1}\sqrt{d}$.

Write $D(A)=\det A$. We can rephrase the inequality as the claim that $\|D'\|_F\le L$ for $c\le A\le C$. (It's perhaps best to think of the matrices as long column vectors and the Frobenius norm as the Euclidean norm, and then $D'$ can be viewed as the gradient of $D$.)

By Jacobi's formula for the derivative of a determinant, we have $$ \frac{\partial D}{\partial a_{jk}}= D(A)\;\textrm{tr}\: (A^{-1}E_{jk}) = D(A) (A^{-1})_{kj} ; $$ here $E_{jk}$ is the matrix with a $1$ in the $jk$ slot and zero entries otherwise.

So $\|D'(A)\|_F= D(A) \|A^{-1}\|_F$. (This immediately recovers the original inequality since $D\le C^d$, $\|A^{-1}\|^2_F\le d/c^2$.) To find the optimal constant, we write $$ D^2\|A^{-1}\|^2_F= \prod \lambda_j^2\cdot \sum \lambda_j^{-2} = \lambda_2^2\cdots\lambda_d^2 +\lambda_1^2\lambda_3^2\cdots \lambda^2_d +\ldots +\lambda_1^2\cdots \lambda^2_{d-1} $$ in terms of the eigenvalues of $A$. Clearly this is maximized at $A=C$, with value $C^{d-1}\sqrt{d}$, so this constant works.

It is also optimal as we can confirm by simply taking $A=C$, $B=C-\epsilon$: then $\|A-B\|^2_F=d\epsilon^2$, $D(A)-D(B)=C^d-(C-\epsilon)^d=dC^{d-1}\epsilon + O(\epsilon^2)$.

(The fact that the derivative does have this value $C^{d-1}\sqrt{d}$ does not immediately rule out still smaller constants since the derivative controls movements in arbitrary directions while we are dealing with positive definite matrices only. However, we can also observe, in more abstract style, that $D'(A)$ is symmetric, so we do stay inside positive definite matrices when following the direction of the largest change of $D(A)$.)

$\endgroup$
2
  • $\begingroup$ Thank you for your answer, and sorry for the delayed response. $\endgroup$ Commented May 21, 2023 at 16:42
  • $\begingroup$ @IosifPinelis: No problem of course, in fact I don't think there's any obligation to react quickly. $\endgroup$ Commented May 21, 2023 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.