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
    Commented May 27, 2013 at 12:01
  • $\begingroup$ Even the inequality $(\star)$ is false; see below for another counterexample. $\endgroup$
    – Suvrit
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented May 27, 2013 at 0:27
  • $\begingroup$ Ups, my link disappeared: [1] en.wikipedia.org/wiki/Symmetric_matrix#Decomposition $\endgroup$
    – user34406
    Commented May 27, 2013 at 0:29

You must log in to answer this question.

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