POTW Inequality of Determinants

[Euge]

Let $M$ be a real $n \times n$ matrix. If $M + M^T$ is positive definite, show that $$\det\left(\frac{M + M^T}{2}\right) \le \det M$$

 

[Hill]

Spoiler

A positive definite matrix can be diagonalized. This transformation, when applied to $M$ and $M^T$, keeps them transpose of each other. Since now their sum is a diagonal matrix, they are antisymmetric with diagonal. So, we need to show that $$\det D_n \le \det (A_n+D_n)$$
This can be shown by induction. $\det D_n$ is product of its diagonal elements. From the Leibniz formula, we see that the terms of $\det (A_n+D_n)$ contain the terms of $\det A_n$ plus various products of diagonal elements and $\det A_m$ for m<n. All these are non-negative, and one of the latter is the product of all the diagonal elements. Thus, their sum is greater or equal to the product of all the diagonal elements. $\blacksquare$

 

[fresh_42]

Spoiler

A positive definite matrix can be diagonalized. This transformation, when applied to $M$ and $M^T$, keeps them transpose of each other. Since now their sum is a diagonal matrix, they are antisymmetric with diagonal. So, we need to show that $$\det D_n \le \det (A_n+D_n)$$
This can be shown by induction. $\det D_n$ is product of its diagonal elements. From the Leibniz formula, we see that the terms of $\det (A_n+D_n)$ contain the terms of $\det A_n$ plus various products of diagonal elements and $\det A_m$ for m<n. All these are non-negative, and one of the latter is the product of all the diagonal elements. Thus, their sum is greater or equal to the product of all the diagonal elements. $\blacksquare$

The Cholesky decomposition was my idea, too, but I do not see the induction part. "All these are non-negative" appears to be wrong to me, at least I am not convinced. Applied to the two by two case $\begin{pmatrix}a&b\\c&d\end{pmatrix}$, it comes down to $(c-b)^2>0$ which does not say anything about $b$ and $c$, and higher dimensions get even messier. The induction has to be executed in detail, and not by "All these are non-negative".

 

[Hill]

A detailed induction.

Let $B_n$ be a real $n \times n$ matrix such that $b_{kk} \gt 0$ for all $k$, and $b_{ij}=-b_{ji}$ for all $i \ne j$. Show that $\det (B_n) \ge \prod b_{kk}$.

It is true for $n=2$: $\det (B_2) = b_{11}b_{22}-b_{12}b_{21}=b_{11}b_{22}+b_{12}^2 \ge b_{11}b_{22}$.

Assume that it is true for all $B_{n-1}$ matrices of this kind.

Make matrix $B'_n$ from $B_n$ by making $b'_{11}=0$. $$\det (B_n)=\det (B'_n) + b_{11} \det (B_{n-1})$$ where $B_{n-1}$ is made from $B_n$ by removing the first row and the first column in the $B_n$.

The second term, $b_{11} \det (B_{n-1}) \ge \prod b_{kk}$ by assumption. We need to show that the first term, $\det (B'_n) \ge 0$. Use induction.

$\det (B'_2) = \det \begin{pmatrix} 0 & b \\-b & c\end{pmatrix}=b^2 \ge 0$.

Assume that $\det (B'_{n-1}) \ge 0$.

Make matrix $B''_n$ from $B'_n$ by making $b''_{22}=0$. $$\det (B'_n)=\det (B''_n) + b_{22} \det (B'_{n-1})$$ where $B'_{n-1}$ is made from $B'_n$ by removing the second row and the second column in the $B'_n$.

The second term, $b_{22} \det (B'_{n-1}) \ge 0$ by assumption. We need to show that the first term, $\det (B''_n) \ge 0$. Use induction.

Continue this procedure of replacing diagonal elements with 0's one-by-one until reaching $B^{(n)}_n$. Since it is antisymmetric, $\det B^{(n)}_n \ge 0$. Thus, $\det B^{(n-1)}_n \ge 0$, etc. until $\det (B'_n) \ge 0$ and $$\det (B_n)=\det (B'_n) + b_{11} \det (B_{n-1}) \ge \prod b_{kk}$$.
$\blacksquare$

 

[fresh_42]

That was not what I meant.

Cholesky says $M+M^\tau =LL^\tau$ with a lower triangular matrix $L$ that has positive diagonal elements $b_{kk}.$ Therefore we need to show that $\prod_{k=1}^n b_{kk}^2 \leq 2^n\det M.$

This is the step that I do not understand. The $b_{kk}$ occur in $L$ but not necessarily in $M$. Where is the connection between $M$ and $L$ in terms of the determinant of them?

The problem with the sum is transferred to the problem between $L$ and $M$. That is a mathematical trick, but not a solution to the problem. It is the center of the task. You cannot hide it behind trivialities.

 

[Hill]

I do not use Cholesky decomposition, but eigenvalue decomposition of the matrix $S=\frac {M+M^T} 2$. If I am not mistaken, the real symmetric positive definite matrix can be diagonalized. Let $S=PDP^{-1}$. Then, $$D=P^{-1}SP=\frac {P^{-1}MP+P^{-1}M^TP} 2=\frac {B+B^T} 2$$
This implies that $B$ has the same diagonal elements as $D$, and all other elements in $B$ are antisymmetric.

 

[fresh_42]

I do not use Cholesky decomposition, but eigenvalue decomposition of the matrix $S=\frac {M+M^T} 2$. If I am not mistaken, the real symmetric positive definite matrix can be diagonalized. Let $S=PDP^{-1}$. Then, $$D=P^{-1}SP=\frac {P^{-1}MP+P^{-1}M^TP} 2=\frac {B+B^T} 2$$
This implies that $B$ has the same diagonal elements as $D$, and all other elements in $B$ are antisymmetric.

Sorry, once on the wrong track (Cholesky) required a wagon-by-wagon help to get back on the right one.

 

[julian]

Spoiler

Define

\begin{align*}
M_S = \frac{M+M^T}{2} , \qquad M_A = \frac{M-M^T}{2}
\end{align*}

Since $M_S$ is positive definite there exists $M_S^{\frac{1}{2}}$ such that $M_S= M_S^{\frac{1}{2}} M_S^{\frac{1}{2}}$. Then we can write

\begin{align*}
\det M & = \det (M_S+M_A)
\\
& = \det M_S \det (\mathbb{1} + M_S^{-\frac{1}{2}} M_A M_S^{-\frac{1}{2}})
\end{align*}

We wish to prove $\det (\mathbb{1} + M_S^{-\frac{1}{2}} M_A M_S^{-\frac{1}{2}}) \geq 1$.

Note $M_S^{-\frac{1}{2}} M_A M_S^{-\frac{1}{2}}$ is a real anti-symmetric matrix. As such it is a normal matrix and can be diagonalised. The eigenvalues of a real anti-symmetric matrix are zero, or are purely imaginary and come in conjugate pairs (i.e. $\pm i \mu_k$ where $\mu_k$ is real). Therefore, $\det (\mathbb{1} + M_S^{-\frac{1}{2}} M_A M_S^{-\frac{1}{2}}) = \prod_k (1+\mu_k^2) \geq 1$. You get equality, i.e., $\det M = \det M_S$, when all the eigenvalues are zero.

 

[Hill]

Since MS is positive definite there exists MS12 such that MS=MS12MS12.

Would you please refer me to where I can read about this kind of decomposition? Thanks.

P.S. I can prove this specific one to myself, but maybe there is more to it.

 

[anuttarasammyak]

Would you please refer me to where I can read about this kind of decomposition? Thanks.

P.S. I can prove this specific one to myself, but maybe there is more to it.

After diangonalization of $M_s$ which has all positive eigenvalues $\{\lambda_i\}$, $M^{1/2}_s$ is also a diangonal matrix whose eigenvalues are $\{\sqrt{\lambda}_i\}$.

 

[julian]

Yep. It is possible to diagonalize a real symmetric matrix by a real orthogonal similarity transformation. If $U^T M_S U = D$, then $M_S = UDU^T = (UD^{1/2}U^T) (U D^{1/2}U^T) = M_S^{1/2} M_S^{1/2}$.