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$
7
  • 3
    $\begingroup$ Use simultaneous diagonalization to reduce the problem to the case of diagonal matrices. $\endgroup$
    – Misha
    Commented Nov 8, 2013 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$ Commented Nov 8, 2013 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$ Commented Nov 8, 2013 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
    Commented Nov 8, 2013 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$ Commented Nov 8, 2013 at 13:41

3 Answers 3

11
$\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$
3
  • $\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$ Commented Nov 8, 2013 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$ Commented Nov 8, 2013 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
    Commented Nov 8, 2013 at 16:48
4
$\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$
7
  • 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$ Commented Nov 8, 2013 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
    Commented Nov 8, 2013 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
    Commented Nov 8, 2013 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
    Commented Nov 8, 2013 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$ Commented Nov 8, 2013 at 19:20

You must log in to answer this question.

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