61
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ This is a really nice problem; has already given me plenty of numerical headaches with my mistaken counterexamples! $\endgroup$ – Suvrit May 2 '15 at 2:37
  • 7
    $\begingroup$ Seems like $e^{A_i}$, and hence $e^{A_1} \dots e^{A_n}$, lies in the split orthogonal group. Not sure how to prevent such an element from having a negative eigenvalue pair $-\lambda,-1/\lambda$ though. $\endgroup$ – Terry Tao May 2 '15 at 6:13
  • 1
    $\begingroup$ @ChristianRemling: Thanks. In other words the matrix $M$ satisfies $\eta M \eta = -M^T $, where $\eta = diag(1, 1, \ldots, -1 , -1) $. The statement $\det(1+e^M)>0$ seems to be also true numerically. $\endgroup$ – Lei Wang May 2 '15 at 20:43
  • 2
    $\begingroup$ What Christian Remling and Will Sawin really proved is that your (updated) conjecture is equivalent to $\det(1+T)\geq 0$ for any $T\in\mathrm{SO}^0(n,n)$. $\endgroup$ – GH from MO May 3 '15 at 17:23
  • 1
    $\begingroup$ It seems that the conjecture is true. See my response below and Terry Tao's comments to it. $\endgroup$ – GH from MO May 3 '15 at 22:42
31
$\begingroup$

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

$\endgroup$
  • 11
    $\begingroup$ I think this solves the problem (in the affirmative). If $T$ is composed of such blocks, then it takes the form $T = \begin{pmatrix} A & 0 \\ 0 & A^{*-1} \end{pmatrix}$ for some $A \in GL_n({\bf R})$, which has to have positive determinant since $T$ lies in the identity component of $SO(n,n)$. But then the number of negative real eigenvalues of $A$ [counted with algebraic multiplicity] is even (and the complex ones come in conjugate pairs), so $\det(1+T) \geq 0$. $\endgroup$ – Terry Tao May 3 '15 at 22:17
  • 3
    $\begingroup$ One cautionary note: in the Nishikawa paper, the quadratic form defining $SO(n,n)$ is given by $\begin{pmatrix} 0 & I \\ I & 0 \end{pmatrix}$ rather than $\begin{pmatrix} I & 0 \\ 0 & - I\end{pmatrix}$. It is still true though that $A$ necessarily has positive determinant; testing on the positive subspace $\{ (v,v): v \in {\bf R}^n \}$ shows that $A + A^{*-1}$ has positive determinant, which after dividing by the positive definite matrix $1 + A^{-1} A^{*-1}$ shows that $A$ also has positive determinant. $\endgroup$ – Terry Tao May 3 '15 at 22:29
  • 2
    $\begingroup$ For the sake of self-containedness: if $T: {\bf C}^n \to {\bf C}^n$ has no specturm in $(-\infty,0]$, one can define a "standard logarithm" $\operatorname{Log} T$ of $T$ by breaking up into generalised eigenspaces $V_\lambda$, on which $T$ acts like $\lambda(1+N)$ for some nilpotent $N$, and making $\operatorname{Log} T$ equal to $\operatorname{Log} \lambda + \operatorname{Log}(1+N)$ on that subspace, where $\operatorname{Log} \lambda$ is the usual branch and $\operatorname{Log}(1+N)$ is computed using Taylor expansion. One can check that $\exp( \operatorname{Log}(T) ) = T$ ... $\endgroup$ – Terry Tao May 4 '15 at 4:42
  • 2
    $\begingroup$ ... that $\operatorname{Log}(T)$ is real if $T$ is real, that $\operatorname{Log}(T)$ commutes with conjugations, and that $\operatorname{Log}(T^{-1}) = - \operatorname{Log}(T)$. In particular, if $T$ lies in $SO(Q)$ for some quadratic form $Q$, then $\operatorname{Log} T$ lies in $\mathfrak{so}(Q)$. From this we see that if $T \in SO(Q)$ for some $Q$, then the portion of $T$ on the spectrum outside of $(-\infty,0]$ is in the range of the exponential map. As for the portion in $(-\infty,0] \backslash \{-1\}$ ... $\endgroup$ – Terry Tao May 4 '15 at 4:45
  • 9
    $\begingroup$ Terry just wrote a blog entry on this question, but I suppose he did not want to self-advertise. terrytao.wordpress.com/2015/05/03/… $\endgroup$ – Tony Huynh May 4 '15 at 10:21
14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do we need to have zero trace for $\log T$? $\endgroup$ – Suvrit May 3 '15 at 3:19
  • $\begingroup$ @Suvrit: The exponential map $\exp:\mathfrak{so}(n,n)\to \mathrm{SO}^0(n,n)$ is not surjective. Yet, the image generates a dense subgroup. $\endgroup$ – GH from MO May 3 '15 at 4:14
  • 1
    $\begingroup$ Ok, I finally got the argument I think. Since each $e^{A_i}$ lies in $O(n,n)$ and because we can make the product of these exponentials approach any element in $O(n,n)$, we should eventually have a counterexample for large enough $N$. $\endgroup$ – Suvrit May 3 '15 at 4:16
  • 4
    $\begingroup$ I think T is not connected to the identity (the log T I calculated is complex). This means that it is no counterexample. $\endgroup$ – jjcale May 3 '15 at 11:36
  • 4
    $\begingroup$ I think it is very appropriate to investigate a problem in an area that we are not very familiar with. This is how we make progress and build mathematically. Also, it seems, noone has a clear view of this problem at the moment. $\endgroup$ – GH from MO May 3 '15 at 19:59
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nice! I almost feel like I can understand my piece now. $\endgroup$ – Christian Remling May 3 '15 at 2:58
  • $\begingroup$ @darijgrinberg I'm not sure. A counterexample for $n=2$ applies for all large $n$, so we're looking for a constant independent of $n$, or possibly decreasing slightly. $\endgroup$ – Will Sawin May 3 '15 at 4:39
  • $\begingroup$ Hi Will, in the first sentence, did you mean the set $\left\{e^{\begin{pmatrix}0& A\\A^T & 0\end{pmatrix}}: A\in \mathbb{R}^{n\times n}\right\}$ form a group? I do not see the set is closed under multiplication, perhaps I miss something? $\endgroup$ – M. Lin Nov 2 '15 at 11:58
  • $\begingroup$ The element of the set is clearly symmetric. Thus, if the set is closed under multiplication, it would mean $e^{\begin{pmatrix}0& A\\A^T & 0\end{pmatrix}}e^{\begin{pmatrix}0& B\\B^T & 0\end{pmatrix}}=e^{\begin{pmatrix}0& B\\B^T & 0\end{pmatrix}}e^{\begin{pmatrix}0& A\\A^T & 0\end{pmatrix}}$ for any $A, B\in \mathbb{R}^{n\times n}$, which I do not see why. $\endgroup$ – M. Lin Nov 2 '15 at 12:00
  • $\begingroup$ @M.Lin No, I mean the set of products of matrices of that form. For the set of products of something to form a group, the thing only needs to be closed under inverses. $\endgroup$ – Will Sawin Nov 2 '15 at 14:18
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Sorry, how is this is a counterexample ? I see the determinant is a polynomial square and $t>0$. Am I missing anything ? $\endgroup$ – Lei Wang May 3 '15 at 5:59
  • 1
    $\begingroup$ @user23765: It's a counterexample to the strict inequality. $\endgroup$ – Christian Remling May 3 '15 at 6:11
  • $\begingroup$ @ChristianRemling: Oh, a $det=0$ is not a concern of QMC simulation. I will modify the question to account for this. Thanks! $\endgroup$ – Lei Wang May 3 '15 at 6:19
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. Now I am worried about the first part of the proof: can we always write $e^{A_1}e^{A_2}\ldots e^{A_N} = e^M$, where $A_i$s and $M$ are real matrices which fulfill the property mentioned in the original question. Please forgive my ignorance but this is also not obvious to me. $\endgroup$ – Lei Wang May 3 '15 at 14:31
  • $\begingroup$ @user23765: it seems that one can always have complex $M$ that satisfies the skew-Hamiltonian-like structure mentioned in my answer. Since only existence of $M$ is needed but not its actual construction, should it really matter? $\endgroup$ – Suvrit May 3 '15 at 14:56
  • 1
    $\begingroup$ I don't think that it is true that one can always write $e^{A_1}e^{A_2}\ldots e^{A_N} = e^M$ with a real $M\in\mathfrak{so}(n,n)$. If this were true, then by the answers of Christian Remling and Will Sawin, the exponential map $\exp:\mathfrak{so}(n,n)\to\mathrm{SO}^0(n,n)$ would have a dense image, i.e. $\mathrm{SO}^0(n,n)$ would be weakly exponential. However, this is known to be false. What is true is that the square of any matrix in $\mathrm{SO}(n,n)$ is in the image of the exponential map. See, for example, Proposition 1.6 in heldermann-verlag.de/jlt/jlt07/DOKHOFPL.PDF $\endgroup$ – GH from MO May 3 '15 at 16:28
  • 1
    $\begingroup$ @Christian Remling choose $M = \left[\begin{matrix}0 & \pi & 0 & 0\\- \pi & 0 & 0 & 0\\0 & 0 & 0 & \pi\\0 & 0 & - \pi & 0\end{matrix}\right]$ $\endgroup$ – jjcale May 3 '15 at 17:13
  • 2
    $\begingroup$ @GH from MO : ok, my mistake was that the Baker–Campbell–Hausdorff formula is not always convergent. $\endgroup$ – jjcale May 3 '15 at 19:00
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Well, I just reached the opposite conclusion from the same starting point. But of course it wouldn't surprise anyone if I'm wrong again. $\endgroup$ – Christian Remling May 3 '15 at 1:28
  • $\begingroup$ Is it possible for $e^M$ to have real eigenvalues smaller than -1 that are not paired with others ? $\endgroup$ – Lei Wang May 3 '15 at 15:14
  • $\begingroup$ @Suvrit: The complex eigenvalues are indeed in conjugate pairs, but the real ones are not necessarily doubly degenerate. $\endgroup$ – Lei Wang May 3 '15 at 16:31
  • $\begingroup$ @user23765: I see the difference now. In my answer, I assume a "sufficient" condition, and frequently it is satisfied. In the cases where it is not (the $\pm a + \log(-1)$ case in your bullet point 3), things still work out. So it remains to guarantee that these are the only possible cases. $\endgroup$ – Suvrit May 3 '15 at 20:15
  • $\begingroup$ @Suvrit: Yes, why things still work out remain a mystery to me. $\endgroup$ – Lei Wang May 3 '15 at 20:19
3
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ The case $N=1$ is trivial because $e^{A_1}$ is positive definite, while the case $N=2$ is also trivial because $\lambda(e^{A_1}e^{A_2}) > 0$. $\endgroup$ – Suvrit May 2 '15 at 20:48
  • 4
    $\begingroup$ Since a physics professor jumped in, let me explain the physics background of this conjecture. It is related to the determinant quantum Monte Carlo simulation. The conjecture states there is no so called "fermion sign problem" for certain kind of fermionic lattice models. $\endgroup$ – Lei Wang May 2 '15 at 20:57
  • 1
    $\begingroup$ Thanks for sharing this. Some of the considerations in your Addendum are similar to Wu and Zhang (Fig. 1) and a recent work by Iazzi and Troyer (Fig. 3). Anyway the rigorous proof of the "forbidden exceptional process" is really the key to the solution of the sign problem. $\endgroup$ – Lei Wang May 4 '15 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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