Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given three real, symmetric matrices $A\succ0$ and $B$, $C⪰ 0$.

How can it be shown that: $$\det(A^2+AB+AC) \leq \det(A^2 +BA +AC+BC) ? \qquad (\star)$$

Where $A^2$ is symmetric and positive definite. Eigenvalues of $BA$, $AC$, and $BC$ are all $> 0$, but symmetry is lost.

Thank you!

share|improve this question
    
$det(A^2+AB+AC) = det (A^2+A^{1/2}BA^{1/2} + A^{1/2}CA^{1/2})$, which are then all symmetric positive semi definite matrices. –  user34406 May 27 '13 at 12:01
    
Even the inequality $(\star)$ is false; see below for another counterexample. –  Suvrit May 27 '13 at 18:14
    
Thank you very much for your answers. Your counterexample is for the case where $A$ in $(\star)$ has a zero eigenvalue. My apologies, I hadn't made this clear in my initial question, but $A$ should be positive definite. I've edited my question to be more specific. –  user34406 May 27 '13 at 18:46
    
It still will not hold! even though $A$ turned out to be semidefinite in my example, you can see that a trivial epsilon perturbation will make it positive definite, but still yield a counterexample. I've included another explicit counterexample, including for the case where all three matrices are positive definite, so that you feel more convinced ;-) –  Suvrit May 27 '13 at 18:58
1  
The fixed version with $BA$ does hold. The proof is interesting. If I get time, I'll type it out; otherwise someone else may want to do it. –  Suvrit May 27 '13 at 21:17
show 2 more comments

2 Answers

up vote 6 down vote accepted

Because the original question has changed so much, I am writing a new answer.

The key point to recognize is that you are trying to prove a submodularity property. Indeed, we see that we may equivalently prove \begin{equation*} \log\det(A) + \log\det(A+B+C) \le \log\det(A+B) +\log\det(A+C). \end{equation*} One common way to verify submodularity is to prove the diminishing marginals property: in our case, it amounts to showing that for a fixed $B \succeq 0$, the function \begin{equation*} f(A) := \log\det(A+B)-\log\det(A) \end{equation*} is monotonically decreasing (since we are dealing with hermitian positive definite matrices, this means $f(A) \le f(C)$ if $C \succeq A$ in the semidefinite order).

To verify this, simply check if $\nabla f(A) \preceq 0$ for all $A$. But this is easy since

\begin{equation*} \nabla f(A) = (A+B)^{-1} - A^{-1} \preceq 0, \end{equation*} where the latter inequality follows as the map $X \mapsto X^{-1}$ is well-known to be (operator) decreasing.

share|improve this answer
    
Thank you kindly. –  user34406 May 28 '13 at 7:35
add comment

None of the conjectured inequalities hold.

This answer contains three counterexamples. The first one is to $(\star)$, while the second and third ones (below the line) refer to previous inequalities conjectured by the OP.

\begin{equation*} A=\begin{bmatrix} 5 & 5\\\\ 5 & 5\end{bmatrix},\quad B=\begin{bmatrix} 8 &4 \\\\ 4 & 2\end{bmatrix},\quad C=\begin{bmatrix} 8 &6 \\\\ 6 & 5\end{bmatrix}. \end{equation*}

Then $A^2+AB+AC$ is a rank-1 matrix, so its determinant is zero, while $A^2+AB+AC+BC=\begin{bmatrix}268 & 203\\\\ 224 & 169\end{bmatrix}$, so its determinant is $-180$.

The structure of this counterexample and of the other ones below is to setup matrices so that the left hand side becomes a rank-1 matrix, which will have determinant zero. Then, one can adjust the other terms to violate inequalities in any direction.

EDIT I'm adding explicit matrices where $A,B,C \succ 0$, but still we have a counterexample to quell the OP's insistence ;-)

\begin{equation*} A=\begin{bmatrix}11&12&7\\\\ 12 & 14 & 8\\\\ 7 & 8 & 11\end{bmatrix},\ B=\begin{bmatrix}19 &14&7\\\\ 14& 14&6\\\\ 7&6&3\end{bmatrix},\ C=\begin{bmatrix}17&17&16\\\\ 17&19&17\\\\ 16&17&17\end{bmatrix} \end{equation*}

For these matrices, $\det(A^2+AB+AC) \approx 2.35\times 10^5$, while $\det(A^2+AB+AC+BC) \approx 4.67 \times 10^4$.


A particularly cute counterexample for your last question (edit: where $\det(A+B) \ge \det(A)+\det(B)$ holds for non symmetric matrices with positive eigenvalues) is the following:

\begin{equation*} A = \begin{bmatrix} 0.5 & 0 & 0& 0\\\\ 1 & 0.5 & 0 & 0\\\\ 1 & 1 & 0.5 & 0\\\\ 1 & 1 & 1 & 0.5 \end{bmatrix},\quad B = A^T. \end{equation*}

Then, $\det(A+B)=0$, but $\det(A)+\det(B) = 1/8$.

The updated question, whether $\det(XY+YZ) \ge \det(XY)+\det(YZ)$ holds is also false. Here is a nice counterexample.

\begin{eqnarray*} X = \begin{bmatrix} 2 & 2\\\\ 2 & 2 \end{bmatrix},\quad Y = \begin{bmatrix} 5 & 5\\\\ 5 & 10 \end{bmatrix},\quad Z = \begin{bmatrix} 10 & 4\\\\ 4 & 2 \end{bmatrix}. \end{eqnarray*} With this choice, $\det(XY+YZ) = -300$, while $\det(XY)+\det(YZ)=100$.

share|improve this answer
    
I see, so clearly $\det(A+B)\geq\det(A)+det(B)$ does not hold in general. Nevertheless, decomposing your $A$ matrix using the [Jordan normal form][1] such that $A=BC$ yields $B$ and $C$ with both positive and negative eigenvalues. Doing the same for a matrix $A=XY$ with $X$,$Y\succeq 0$ yields $B$,$C$ with positive eigenvalues (at least for the ones I tested). Therefore I'd still suspect that the inequality $\det(XY+YZ)\geq\det(XY)+det(YZ)$ with $X$,$Y$,$Z\succeq 0$ holds. But how to (dis-)prove it? Tahnks. –  user34406 May 27 '13 at 0:27
    
Ups, my link disappeared: [1] en.wikipedia.org/wiki/Symmetric_matrix#Decomposition –  user34406 May 27 '13 at 0:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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