9
$\begingroup$

While reading a paper An Arithmetic Proof of John’s Ellipsoid Theorem by Gruber and Schuster, I have a question on their proof.


Consider an $n\times n$ real symmetric and positive definite matrix $\mathbf A$.

  1. As this kind of matrix is symmetric, its $n(n+1)/2$ upper diagonal terms are enough to represent it. Hence, we can consider such a matrix as a point in $\mathbb R^{n(n+1)/2}$.
  2. A conical combination of two positive definite matrices is also positive definite. Hence, the set of all symmetric positive definite matrices forms an open convex cone $\mathcal P\in\mathbb R^{n(n+1)/2}$ with apex on the origin.

Now they claim the following theorem without proving it.

Theorem: The set $\ \mathcal D = \{\mathbf A \in \mathcal P: \det \mathbf A \geq 1\}$ is a closed, smooth, strictly convex set in $\mathcal P$ with non-empty interior.

They just gave some hint that we can use Implicit Function Theorem and Minkowski's Determinant Inequality which states that

For two $n\times n$ positive semidefinite Hermitian matrices $\mathbf X$ and $\mathbf Y$, $$\det (\mathbf X + \mathbf Y)^{1/n}\geq \det(\mathbf X)^{1/n} + \det(\mathbf Y)^{1/n} $$

Any hint or suggestion on how to prove the above theorem about the set $\mathcal D$?

$\endgroup$
  • 3
    $\begingroup$ Use simultaneous diagonalization to reduce the problem to the case of diagonal matrices. $\endgroup$ – Misha Nov 8 '13 at 12:49
  • $\begingroup$ @Misha I don't understand your comment. Tow matrices can be simultaneously diagonalizable if and only if they commute. I don't see any reason why two positive definite matrices must commute. Would you please be more specific? $\endgroup$ – Federico Magallanez Nov 8 '13 at 13:05
  • $\begingroup$ write X=aT, Y=(1-a)S where T,S belong to P. Then use the inequality together with a^{1/n}+(1-a)^{1/n}>1 $\endgroup$ – ofer zeitouni Nov 8 '13 at 13:08
  • 1
    $\begingroup$ @FedericoMagallanez: This is the unitary diagonalization (not the conjugation); you should think of the quadratic forms defined via the Hermitian matrices and make a simultaneous change of variables to make both forms diagonal. $\endgroup$ – Misha Nov 8 '13 at 13:12
  • $\begingroup$ What are your attempts up to now? What is the part where you are stuck? Closed, smooth, convex or non-empty interior? $\endgroup$ – Federico Poloni Nov 8 '13 at 13:41
10
$\begingroup$

Here is a textbook level description of the above. I assume you know what a convex set and convex function on this set are. Given that, let us know prove that the determinant is strictly log-concave on hermitian positive definite matrices.

Claim. Let $A, B > 0$. Then, $\det\left(\frac{A+B}{2}\right) \ge \sqrt{\det(AB)}$

Proof Consider $\phi(A) := \log\det(A)$. The first derivative of this is $A^{-1}$, while the second derivative may be identified with $-A^{-1}\otimes A^{-1}$, which is clearly negative definite if $A > 0$. This proves the desired concavity of $\phi(A)$, and therewith the claim above.

Note: Minkowski's determinant inequality is not the same as the above log-concavity. It is stronger, and enjoys a variety of different proof attempts. For a great list of these, have a look at the following much older MO question.

$\endgroup$
8
$\begingroup$

$-\log \det$ is a smooth convex function on the PSD cone (this is a standard fact , and follows from the Chandler Davis theorem -- see, e.g., my arXiv preprint on "another proof of the Davis theorem", or see Boyd and Vanderberghe's convex optimization for deep significance of this fact in convex programming), so the set $\log \det X > a$ is a smooth convex set.

$\endgroup$
  • $\begingroup$ That'a a bit of overkill. Misha's answer in the comments is the basic one. However, all publicity for the Chandler Davis theorem is good in my book :-). $\endgroup$ – alvarezpaiva Nov 8 '13 at 15:10
  • 1
    $\begingroup$ I'm a little confused. According to page 73 of Convex Optimization by Boyd and Vandenberghe, The function $f(\mathbf X) = \log \det \mathbf X$ is concave on $\mathsf{dom} f =S^n_{++}$ where $S_{++}^n$ denotes the set of symmetric positive definite $n\times n$ matrices. Am I missing something here? $\endgroup$ – Federico Magallanez Nov 8 '13 at 15:10
  • 4
    $\begingroup$ No, concave up/concave down is too confusing for us peasants, I just call them both convex. $\endgroup$ – Igor Rivin Nov 8 '13 at 16:48
3
$\begingroup$

I'm not sure if you are asking for the proof of the theorem assuming Minkowski's inequality or if you are asking for the proof including a proof of Minkowski's inequality.

If you assume Minkowski's inequality there is nothing to prove: the sup-level sets of a concave function are convex. In this case, if you take two positive definite Hermitian matrices $A$ and $B$ with determinant greater or equal to $1$, then $$ \det((A + B)/2)^{1/n} \geq (\det(A)^{1/n} + \det(B)^{1/n})/2 \geq 1 . $$

Now, the proof of Minkowski's inequality is just the arithmetic-geometric mean inequality once you follows Misha's line of thought in the comments to the OP.

$\endgroup$
  • 1
    $\begingroup$ You don't have to simultaneously diagonalize $A$ and $B$: $\det(A + B) = \det(C(A + B)C^{-1})$ for any invertible $C$ and now choose $C$ so that $CAC^{-1} = I$. This leaves you with having to prove the case where $A = I$. $\endgroup$ – alvarezpaiva Nov 8 '13 at 15:48
  • 1
    $\begingroup$ $CAC^{-1}=I \implies CA=C \implies C^{-1}CA=C^{-1}C=I$, i.e., $A=I$. Perhaps I'm being really silly here... $\endgroup$ – Suvrit Nov 8 '13 at 16:59
  • 1
    $\begingroup$ The $C^{-1}$ should be $C^t$. In fact, you can take $C$ to be the square root of $A$ (positive symmetric matrices can be raised to any real power). Then the rest follows. $\endgroup$ – Deane Yang Nov 8 '13 at 19:15
  • 1
    $\begingroup$ @Deane: That's what I meant by "simultaneous congruence" :-), though it suffices to just turn $A$ into $I$, as you note. $\endgroup$ – Suvrit Nov 8 '13 at 19:18
  • 2
    $\begingroup$ Yes Deane. Sorry I was being sloppy. I felt the person who proposed the question had to do some work in answering it. $\endgroup$ – alvarezpaiva Nov 8 '13 at 19:20

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.