63
$\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$
16
  • 6
    $\begingroup$ This is a really nice problem; has already given me plenty of numerical headaches with my mistaken counterexamples! $\endgroup$
    – Suvrit
    May 2, 2015 at 2:37
  • 8
    $\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, 2015 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, 2015 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, 2015 at 17:23
  • 2
    $\begingroup$ I agree with Todd Trimble that the easiest way is to cite this MO entry with a link. If you need to know my name, just tell your email address here and I will contact you. You can also cite Terry Tao's recent blog entry, which looks great: terrytao.wordpress.com/2015/05/03/… I must say this question was one of the best I have seen here, and I learned a lot from it and the discussion that evolved around it. $\endgroup$
    – GH from MO
    May 4, 2015 at 11:23

7 Answers 7

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$
12
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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$
11
  • $\begingroup$ Do we need to have zero trace for $\log T$? $\endgroup$
    – Suvrit
    May 3, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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$
5
  • $\begingroup$ Very nice! I almost feel like I can understand my piece now. $\endgroup$ May 3, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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$
3
  • 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, 2015 at 5:59
  • 1
    $\begingroup$ @user23765: It's a counterexample to the strict inequality. $\endgroup$ May 3, 2015 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, 2015 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$
11
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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$
5
  • $\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$ May 3, 2015 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, 2015 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, 2015 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, 2015 at 20:15
  • $\begingroup$ @Suvrit: Yes, why things still work out remain a mystery to me. $\endgroup$
    – Lei Wang
    May 3, 2015 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$
3
  • 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, 2015 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, 2015 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, 2015 at 21:06

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.