How to prove this determinant is positive?

Question

Given matrices

$$A_i= \biggl(\begin{matrix} 0 & B_i \\ B_i^T & 0 \end{matrix} \biggr)$$

where $B_i$ are real matrices and $i=1,2,\ldots,N$, how to prove the following?

$$\det \big( I + e^{A_1}e^{A_2}\ldots e^{A_N} \big) \ge 0$$

This seems to be true numerically.

---

Update1: As was shown in below, the above inequality is related to another conjecture $\det(1+e^M)\ge 0$, given a $2n\times 2n$ real matrix $M$ that fulfills $\eta M \eta =-M^T$ and $\eta=diag(1_n, -1_n)$. The answers of Christian and Will, although inspiring, did not really disprove this conjecture as I understood.

Update2: Thank you all for the fruitful discussion. I attached my Python script down here. If you run it for several times you will observe

1. $\det(1+e^{A_1}\ldots e^{A_N})$ seems to be always larger than zero (the conjecture),

2. $M = \log(e^{A_1}\ldots e^{A_N})$ are sometimes indeed pure real and it fulfills the condition mentioned in update1. In this case the eigenvalues of $M$ are either pure real or in complex conjugate pairs. Thus it is easy to show $\det(1+e^M)=\prod_l(1+e^ {\lambda_l})\ge 0$,

3. However, sometimes the matrix $M = \log(e^{A_1}\ldots e^{A_2})$ can be complex and they are indeed in the form written down by Suvrit. In this case, it seems that the eigenvalues of $M$ will contain two sets of complex values: $\pm a+i\pi$ and $\pm b + i\pi$. Therefore, $\det(1+e^{M})\ge 0$ still holds because $(1-e^a)(1-e^{-a})(1-e^{b})(1-e^{-b})\ge 0$.

Update3: Thank you GH from MO, Terry and all others. I am glad this was finally solved. One more question: how should I cite this result in a future academic publication ?

Update4: Please see the publication out of this question at arXiv:1506.05349.

Answer 1

Here are some ideas how to decide the conjecture. (EDIT: In fact these ideas lead to a proof of the conjecture as Terry Tao explained in two comments below.)

As Christian Remling and Will Sawin showed, the conjecture is equivalent to $\det(I+T)\geq 0$ for any $T\in\mathrm{SO}^0(n,n)$.

We can assume that $-1$ is not an eigenvalue of $T$. Up to conjugacy, $T$ is a sum of indecomposable blocks as in Theorem 1 of Nishikawa's 1983 paper, and then $\det(I+T)$ is the product of the determinants of the corresponding blocks of $I+T$. Hence, by the idea of jjcale, we can forget about the blocks that are of exponential type. By page 83 in Djoković's 1980 paper, the remaining blocks are of type $\Gamma_m(\lambda,\lambda^{-1})$ with $\lambda<0$ and $\lambda\neq -1$, which in turn are described on page 77 of the same paper. Such a block contributes $(1+\lambda)^{2m+2}/\lambda^{m+1}$ to $\det(I+T)$, hence we can forget about the blocks where $m$ is odd.

To summarize, we can assume that $T$ is composed of $(2m+2)\times(2m+2)$ blocks of type $\Gamma_m(\lambda,\lambda^{-1})$ with $\lambda<0$ and $\lambda\neq -1$ and $m$ even. The conjecture is true if and only if the number of such blocks is always even. For this, the explicit description of $\mathrm{SO}^0(n,n)$ on page 64 of Nishikawa's 1983 paper might be useful (see also page 68 how to use this criterion for $m=1$). Based on this, I verified by hand that one cannot have a single block for $m=2$, which also shows that the smallest possible counterexample to the conjecture is of size $10\times 10$ (i.e. $n\geq 5$).

Added 1. Terry Tao realized and kindly added that in the remaining case we are done. Read his comments below. To summarize and streamline his ideas, we have in this case \begin{align*}\det(I_{2n}+T) &=\det(I_n+A)\det(I_n+A^{*-1})\\ &=\det(A)\det(I_n+A^{-1})\det(I_n+A^{*-1})\\ &=\det(A+A^{*-1})\frac{\det(I_n+A^{-1})^2}{\det(I_n+A^{-1}A^{*-1})}, \end{align*} where $(A+A^{*-1})/2$ can be described as the restriction of $T$ to a totally positive subspace followed by the orthogonal projection to this subspace. Now we have $\det(A+A^{*-1})>0$ by $T\in\mathrm{SO}^0(n,n)$, while the fraction on the right is clearly positive, hence we conclude $\det(I_{2n}+T)>0$.

Added 2. Terry Tao wrote a great blog entry on this topic.

Added 3. Let me add a variation on Terry's original argument. Djoković defines $\mathrm{SO}(n,n)$ via $J:=\begin{pmatrix} 0 & I_n \\ I_n & 0 \end{pmatrix}$, while Nishikawa defines it via $K:=\begin{pmatrix} I_n & 0 \\ 0 & -I_n\end{pmatrix}$. These two matrices are connected via $J=M^*KM$, where $M:=\frac{1}{\sqrt{2}}\begin{pmatrix} I_n & I_n\\ -I_n & I_n\end{pmatrix}$, hence any matrix $T$ in Djoković's $\mathrm{SO}(n,n)$ corresponds to $MTM^*$ in Nishikawa's $\mathrm{SO}(n,n)$. We need to examine the case of $T = \begin{pmatrix} A & 0 \\ 0 & A^{*-1} \end{pmatrix}$, which corresponds to $MTM^*=\frac{1}{2}\begin{pmatrix} A+A^{*-1} & -A+A^{*-1} \\ -A+A^{*-1} & A+A^{*-1} \end{pmatrix}$. This lies in Nishikawa's $\mathrm{SO}^0(n,n)$, whence $\det(A+A^{*-1})>0$.

Answer 2

Update 1: Thanks to jjcale for pointing out a fatal flaw. Indeed $SO(n,n)$ has two components, see here, and it looks suspiciously like my $T$ below is in the wrong component. I don't really know what Wikipedia means by "preserving/reversing orientation," but certainly $T=\textrm{diag}(-1,1,-1,1)$ is in the wrong component, and my $T$ below feels like it probably is in the same component.

It's hard to be sure about anything after so many mistakes, but there seems to be some circumstantial evidence that indeed $\det (1+T)$ could be $\ge 0$ on $SO^+(n,n)$. For example, $T_0=-1$ looks like a reasonable starting point that, evolved a little along a suitable flow, should produce a counterexample if there is one, but this isn't working.

Update 2: Thanks also to GH from MO for moral support. So I'll leave it up for now, as a monument to my ignorance (plus who wouldn't like to keep the reputation). I really shouldn't dabble in areas I don't understand. (But amazing what one can learn from an innocuous looking question.)

---

I believe the OP's conjecture is false. This is going to be a bit light on details. Essentially, I'll elaborate on Terry's and the OP's comments above.

The Lie (matrix) algebra generated by the matrices $A=\left( \begin{smallmatrix} 0 & B\\ B^t & 0\end{smallmatrix}\right)$ is (certainly contained in, but I believe equal to) $$ g=\left\{ M=\begin{pmatrix} A & B \\ B^t & D \end{pmatrix}: A=-A^t, D=-D^t \right\} . $$ As observed by the OP, this can equivalently be described as all $M$ with $MI=-IM^t$, where $I=\textrm{diag}(1,-1)$. Since this is the Lie algebra of $O(n,n)$, defined as all matrices $T$ with $$ TIT^t=I , \quad\quad\quad\quad (1) $$ I believe that this means we can make the product of matrix exponentials approach any matrix in $O(n,n)$ that is in the connected component of the identity (but I haven't thought through this step very carefully).

Now it's easy to find counterexamples $T\in O(n,n)$ to the claim that $\det (1+T)>0$. For example, for $n=1$, we could take $T=\left( \begin{smallmatrix} -2 & \sqrt{3} \\ \sqrt{3} & -2 \end{smallmatrix}\right)$. It is easily checked that $T\in O(1,1)$ and $\det (1+T)=-2$. Obviously, this is not a counterexample to the OP's conjecture, which is trivially true for $n=1$ (since any two $A_j$'s commute). We cannot reach this $T$ because when written out, (1) for $n=1$ in particular demands that $T_{11}^2=1+T_{12}^2\ge 1$, so we cannot get to negative values.

However, as usual, these obstructions disappear in higher dimensions. Note that we have the full Lie algebra $so(n)$ available for the diagonal blocks. A counterexample for $n=2$ is given by the matrix $$ T = \begin{pmatrix} -\sqrt{2} & 0 & 1 & 0 \\ 0 & 1 & 0 & 0\\ 1 & 0 & -\sqrt{2} & 0\\ 0 & 0& 0& 1\end{pmatrix} . $$ For this $T$, we have that $T\in O(2,2)$, $\det (1+T)=8(1-\sqrt{2})<0$.

Finally, let me point out that this only shows that the determinant can not be always positive for arbitrarily large $N$; it is still conceivable that this is true for certain small values of $N$.

Answer 3

The set of matrices of the form $e^{A_1} \dots e^{A_n}$ with $A_1, \dots , A_n$ of this form are a group. This is because it is clearly closed under multiplication and if $A$ is of this form then $-A$ is of this form, so they are closed under inverses. The closure of this set remains a group, hence is a Lie subgroup of $GL_n(\mathbb R)$.

So if we compute its Lie algebra, and find the associated connected Lie subgroup, then all elements in the Lie group will be limits of these products.

The Lie algebra certainly contains matrices of the form $A_i$ by multiplication. Observe that the commutator is:

$$\left[ \biggl(\begin{matrix} 0 & B_1 \\ B_1^T & 0 \end{matrix} \biggr), \biggl(\begin{matrix} 0 & B_2 \\ B_2^T & 0 \end{matrix} \biggr) \right] = \biggl(\begin{matrix} 0 & B_1 \\ B_1^T & 0 \end{matrix} \biggr)\biggl(\begin{matrix} 0 & B_2 \\ B_2^T & 0 \end{matrix} \biggr) - \biggl(\begin{matrix} 0 & B_2 \\ B_2^T & 0 \end{matrix} \biggr) \biggl(\begin{matrix} 0 & B_1 \\ B_1^T & 0 \end{matrix} \biggr) $$

$$= \biggl(\begin{matrix} B_1 B_2^T & 0\\ 0 & B_1^T B_2 \end{matrix} \biggr) - \biggl(\begin{matrix} B_2 B_1^T & 0\\ 0 & B_2^T B_1 \end{matrix} \biggr) = \biggl(\begin{matrix} B_1 B_2^T - B_2 B_1^T & 0\\ 0 & B_1^T B_2 - B_2^T B_1 \end{matrix} \biggr) $$

Observe that $B_1 B_2^T - B_2 B_1^T = M - M^T$ where $M= B_1 B_2^T$ is arbitrary so we can get any skew-symmetric matrix. Moreover, we can get any rank $1$ trace $0$ matrix as $B_1 B_2^T$ when $B_2^T B_1$ is $0$, so that the other square is $0$. So by summing we get arbitrary skew-symmetric matrices in the top left, and independently in the bottom right, so we get every element of $so(n,n)$. (There may be easy ways to show this.)

This shows that every matrix in $SO(n,n)^{+}$ can be reached.

Answer 4

Here is a counterexample with $N=3$. Consider the matrices $$ B_1 = \log(t) \pmatrix{0 & 4\cr -1 & 0\cr}, B_2 = \log(t) \pmatrix{-2 & 2\cr 1 & 2\cr}, B_3 = \log(t) \pmatrix{4 & -2\cr -2 & 1\cr}$$ where a positive value of $t$ will be chosen later. The $B_i$ were chosen so that the eigenvalues of the corresponding $A_i/\log(t)$ would be integers, and then the entries of $\exp(A_i)$ would be rational functions in $t$ with rational coefficients. Then it turns out that $$\det(I+e^{A_1} e^{A_2} e^{A_3}) = \left( t+1 \right) ^{2} \left( 2\;{t}^{12}-27\;{t}^{11}+27\;{t}^{10}- 30\;{t}^{9}+30\;{t}^{8}-79\;{t}^{7}+54\;{t}^{6}-79\;{t}^{5}+30\;{t}^{4 }-30\;{t}^{3}+27\;{t}^{2}-27\;t+2 \right) ^{2} /(2500 t^{13}) $$ and the polynomial $2\;{t}^{12}-27\;{t}^{11}+27\;{t}^{10}- 30\;{t}^{9}+30\;{t}^{8}-79\;{t}^{7}+54\;{t}^{6}-79\;{t}^{5}+30\;{t}^{4 }-30\;{t}^{3}+27\;{t}^{2}-27\;t+2$ has two positive roots (note e.g. that its value at $0$ is $+2$ and its value at $1$ is $-100$).

There are no counterexamples with $N=2$, because $e^{A_1} e^{A_2}$ has the same eigenvalues as $e^{A_1/2} e^{A_2} e^{A_1/2}$ which is positive definite.

Answer 5

The conjecture ist true :

It follows from $$det(I + e^{M}) = det(I + i e^{M/2}) * det(I - i e^{M/2}) = {\left\lvert{det(I + i e^{M/2})}\right\lvert}^2 \ge 0$$ .

I.e. it follows from the fact that every Matrix in SO(n,n) which belongs to the same connected component of SO(n,n) as the identity has a real square root. Update : Not true, see comment of GH from MO and given reference.

Answer 6

It seems that the claim could hold. In particular, we have a sufficient condition under which the claimed inequality holds. Let each $B_i$ be a real $d\times d$ matrix.

[EDIT:] If there exists a matrix $M$ in $\mathbb{C}^{2d\times 2d}$ such that $e^{A_1}e^{A_2}\cdots e^{A_n}=e^M$, and $M$ has the structure \begin{equation*} M = \begin{pmatrix} A & C\\ C^* & B \end{pmatrix}, \end{equation*} where $A$ and $B$ are skew-Hermitian, then $\det(I+e^M) > 0$.

To prove this claim consider the eigenvalues of the ``Skew-Hamiltonian like matrix'' $M$---this matrix satisfies $(MJ)^*=-MJ$ where $J=\text{diag}(I,-I)$.

Lemma. Let $M$ be as defined above. Then, the eigenvalues of $M$ arise in complex conjugate pairs with the real part having both signs. That is, \begin{equation*} \lambda(M) = \pm a_k \pm i b_k,\quad 1 \le k \le d. \end{equation*}

Observe that with these eigenvalues we do have $\det(e^M)=1$.

By grouping terms appropriately, it follows that the eigenvalues of $e^M$ are $r_k\pm i s_k$ for $1\le k \le d$. Hence, $$\det(I+e^M)=\prod_{j=1}^{2d} (1+e^{\lambda_j(M)}) = \prod_{k=1}^d ((1+r_k)\pm i s_k) > 0.$$

Note: the only time $e^M$ can have an eigenvalue with a negative real part is when $M$ has a complex eigenvalue. But these eigenvalues arise in conjugate pairs, so they match up.

Answer 7

Consider a $2n\times 2n$ real matrix $M$ that satisfies the pseudo-unitarity condition

$$M^{\rm T}\Lambda M=\Lambda,\;\;\Lambda=\begin{pmatrix}1_n & 0\\ 0 & -1_n\end{pmatrix}.\qquad [1]$$

(The matrix $1_n$ is the $n\times n$ unit matrix.) If $z$ is an eigenvalue of $M$, then also the complex conjugate $\bar{z}$ and the inverse $1/z$ are eigenvalues.

If $M$ is also symmetric, $M^{\rm T}=M$, it has the block-decomposition

$$M=\begin{pmatrix}U&0\\ 0&V\end{pmatrix} \begin{pmatrix}\cosh X&\sinh X\\ \sinh X&\cosh X\end{pmatrix}\begin{pmatrix}U^{\rm T}&0\\ 0&V^{\rm T}\end{pmatrix},\qquad [2]$$

where $U$ and $V$ are $n\times n$ orthogonal matrices ($UU^{\rm T}=VV^{\rm T}=1_{n}$) and $X$ is a diagonal $n\times n$ matrix with real numbers $x_1,x_2\ldots x_n$ on the diagonal. This matrix satisfies

$${\rm det}\,(1_{2n}+M)=\prod_{k=1}^n [(1+\cosh x_k)^2-\sinh^2 x_k]=\prod_{k=1}^n[2(1+\cosh x_k)]>0.\qquad [3]$$

The matrix product $Z=e^{A_1} e^{A_2}\ldots e^{A_N}$ satisfies the pseudo-unitarity condition [1], $Z^{\rm T}\Lambda Z=\Lambda$, but it is not symmetric in general for $N>1$. The matrix can be symmetrized for $N=2$ or for any $N$ if $A_k=A_{N-k}$ ($k=1,2,\ldots N-1$), but more generally there is no symmetrization possible and this line of argument fails. (In my first posting I overlooked this, thanks to Christian Remling for correcting me.)

---

Addendum: I discussed the awesome proof provided by GH from MO and Terry Tao with some of my students, and one of them (Brian Tarasinski) made this diagram which I find quite instructive and want to share with you.

The diagram shows some of the eigenvalues of the matrix $M$ in the complex plane. Colors are used to identify eigenvalues that are paired by the requirement that $z,\bar{z},1/z,1/\bar{z}$ must all be an eigenvalue of $M$. The arrows indicate how the eigenvalues evolve [*] with increasing $N$. We start out (for $N=1$) with all eigenvalues on the positive real axis, so ${\rm det}(1+M)>0$. With increasing $N$ some of the eigenvalues move out into the complex plane, crossing the line ${\rm Re}\,z=-1$, but because they come in complex conjugate pairs (black dots), they still make a positive contribution to ${\rm det}(1+M)$. If an eigenvalue on the real axis passes through $z=-1$, its inverse partner passes through from the opposite direction (purple dots), again without a change in ${\rm det}(1+M)$. The only way ${\rm det}(1+M)$ can change is when a pair of eigenvalues on the unit circle meets at the point $z=-1$ and then takes off along the real axis in opposite directions (blue dots). That this exceptional process is forbidden cannot be deduced from these elementary considerations. (Brian has a derivation, but this is no substitute for the rigorous proof in the accepted answer.)

[*] This idea of a continuous evolution of the eigenvalues as a function of some parameter $t$ is in line with the physics origin of this problem where $M(t)$ is the time-ordered exponential $\exp[\int_0^t A(t')dt']$.