5
$\begingroup$

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!

$\endgroup$
7
  • $\begingroup$ $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. $\endgroup$
    – user34406
    May 27, 2013 at 12:01
  • $\begingroup$ Even the inequality $(\star)$ is false; see below for another counterexample. $\endgroup$
    – Suvrit
    May 27, 2013 at 18:14
  • $\begingroup$ 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. $\endgroup$
    – user34406
    May 27, 2013 at 18:46
  • $\begingroup$ 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 ;-) $\endgroup$
    – Suvrit
    May 27, 2013 at 18:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Suvrit
    May 27, 2013 at 21:17

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user34406
    May 27, 2013 at 0:27
  • $\begingroup$ Ups, my link disappeared: [1] en.wikipedia.org/wiki/Symmetric_matrix#Decomposition $\endgroup$
    – user34406
    May 27, 2013 at 0:29

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.