6
$\begingroup$

Let $A$ be a Metzler matrix, i.e. a real matrix (not necessarily symmetric) whose off-diagonal elements are all non-negative. Then, for $t\ge 0$, the matrix exponential $\exp(At)$ will have all non-negative elements.

Numerically, it seems that given a single off-diagonal element of $\exp(At)$, it is always a log-concave (i.e. log-convex downward) function of $t$, for $t\ge 0$, and that the diagonal elements are always log-convex upward functions.

That is, it looks like the function $$ f(t) = \log\Big(\big(\exp(At)\big)_{ij}\Big) $$ is a concave function of $t$ for $t\ge 0$ if $i\ne j$, and a convex function of $t$ if $i=j$. My question is whether this indeed is the case. Note that in this expression $\exp$ is a matrix exponential, but $\log$ is just an ordinary logarithm of a positive number.

Here is a typical result. The plot shows each element of $\exp(At)$ as a function of $t$, where $A$ is a matrix whose off-diagonal elements are independently uniformly sampled from $[0,1]$ and whose diagonal elements are independently uniformly sampled from $[-1,0]$. The diagonal elements of $\exp(At)$ are shown in red.

enter image description here

Showing this should be a simple case of finding the second derivative and showing that it can't be positive, but I haven't seen a way to do that. I haven't been able to find a counterexample either.

$\endgroup$
  • $\begingroup$ Note: I asked a closely related question on Math.SE recently (based on a slightly weaker version of the hypothesis), but it hasn't been answered yet. $\endgroup$ – Nathaniel Feb 28 '17 at 2:25
  • $\begingroup$ How many numerical experiments have you tried? Computer cycles are cheap, you should be fairly sure that it's true before looking for a proof. $\endgroup$ – Federico Poloni Feb 28 '17 at 7:32
  • $\begingroup$ @FedericoPoloni I'd done quite a few, but for some reason I hadn't looked at the diagonal entries. Having done that I will now make a substantial change to the question. $\endgroup$ – Nathaniel Feb 28 '17 at 7:49
8
$\begingroup$

The following Matlab code (unless I coded something wrong, which is well possible) finds a few random counterexamples each time I run it, even when restricted to off-diagonal entries:

n = 3;
for trie = 1:100
   A = rand(n);
   B1 = log(expm(A));
   B2 = log(expm(2*A));
   B3 = log(expm(3*A));

   C = B2 - (B3+B1)/2; %its off-diagonal should be >= 0 if the claim holds
   C = C - diag(diag(C));
   if not(all(all(C >= 0)))
       A
   end
end

For instance:

A =
   0.804449583613070   0.535664190667238   0.989144909700340
   0.986104241895970   0.087077219900892   0.066946258397750
   0.029991950269390   0.802091440555804   0.939398361884535
A =
   0.018177533636696   0.534137567882728   0.625937626080496
   0.683838613746355   0.885359450931142   0.137868992412558
   0.783736480083219   0.899004898906140   0.217801593712125
A =
   0.133503859661312   0.300819018069489   0.286620388894259
   0.021555887203497   0.939409713873458   0.800820286951535
   0.559840705872510   0.980903636046859   0.896111351432604
A =
   0.108016694136759   0.559370572403004   0.848709226458282
   0.516996758096945   0.004579623947323   0.916821270253738
   0.143156022083576   0.766681998621487   0.986968274783658
A =
   0.068357220470829   0.026107108154905   0.961558573103663
   0.436327077480103   0.954678274080449   0.762414484002993
   0.173853037365001   0.430596519859417   0.007348661102847

Quick remarks with some tips for numerical experimentation:

  1. For continuous functions, midpoint convexity is equivalent to convexity, so I only tested for that. The $t=1,2,3$ interval is chosen because it looked like the simplest thing to try.
  2. Out of habit, I first coded this with 1000 tries with $5\times 5$ matrices. $100$ and $3\times 3$ are here just for quicker display. It's so fast that it doesn't matter anyway, so it's better to err on the side of more and larger examples.
  3. One should be careful with instructions such as C - diag(diag(C)) (which subtracts its diagonal from a matrix), which could hide numerical mistakes (what if a -1e-16 pops up on the diagonal?). In this case though the subtractions are of the form a - a, which is guaranteed to return 0 even in double-precision arithmetic. Matlab does not have a simpler way to set the diagonal of a matrix to zero or ignore it, unfortunately. (I actually first wrote C(1:n+1:n^2) = 0, but then I replaced it because it is hackish and difficult to read).
  4. There are lots of factoids about matrices (and especially about monotonicity of eigenvalues of nonsymmetric matrices and the matrix exponential) that look true at first sight but have counterexamples. I suggest you to always try some random experiments like these ones. Once one gets in the habit, it's faster to write the code than to think about it. :)
$\endgroup$
  • $\begingroup$ Well, that settles it - I re-wrote the same code in Python, plotted the results, and confirmed the convex (convex upward) sections by holding a ruler up to the screen. Thank you! $\endgroup$ – Nathaniel Feb 28 '17 at 8:48
6
$\begingroup$

For $2\times2$ matrices, the log-concavity is true. One has $e^{tA}=f(t)I_2+g(t)A$ by Cayley-Hamilton. Writing that the eigenvalues of $e^{tA}$ are the exponentials of those of $tA$, we find $$g(t)=\frac{e^{t\mu}-e^{t\lambda}}{\mu-\lambda}\,,$$ where $\mu,\lambda$ are the eigenvalues of $A$. Thus we only have to prove that $g$ is log-concave, that is $$gg''-g'^2=-e^{t(\mu+\lambda)}\le0.$$ Notice that the assumption is implicitely used in that it implies $g>0$.

Edit. The formula above seems to be a particular case of a more general one. Suppose $A$ is $n\times n$. With Cayley-Hamilton, we have $$e^{tA}=f(t)I_n+g(t)A+\cdots+h(t)A^{n-1}.$$ Let us form the Hankel matrix $M_h(t)=\left(h^{(i+j-2)}(t)\right)_{1\le i,j\le n}$. Then $\det M_h(t)=(-1)^{n+1}e^{t{\rm Tr}\,A}$.

Remark that a smooth function $h$ satisfies a linear ODE of order $n-1$ with some constant coefficients if, and only if, $\det M_h\equiv0$.

$\endgroup$
1
$\begingroup$

Try e.g. $$ A = \pmatrix{0 & 0\cr 1 & 0\cr},\ \exp(At) = \pmatrix{1 & 0\cr t & 1\cr} $$ where $\log(t)$ is not convex.

Or did you mean log-concave?

$\endgroup$
  • 1
    $\begingroup$ Sorry, I understand "convex" to mean convex downward. If $\log t$ is considered concave, then I meant concave. I'll edit the post accordingly. $\endgroup$ – Nathaniel Feb 28 '17 at 7:18
  • 3
    $\begingroup$ @DenisSerre I'm pretty confused by the comments I'm getting about the word convex. I first learned about it in the context of the entropy in physics, which is typically referred to as a convex function, and is convex in the sense I originally used the word in my question. Once I got a couple of comments about the convex/concave terminology I changed it in the question. One has to choose one convention or the other, and I'm doing my best to use the same one as everyone else. Not really sure how any kind of "attitude" could be inferred from that, let alone an unscientific one. $\endgroup$ – Nathaniel Feb 28 '17 at 8:17
  • 3
    $\begingroup$ @DenisSerre I repeat: after I got a couple of comments about it I changed it. One has to choose one convention or the other and I'm doing my best to use the same one as everyone else. What's the problem? $\endgroup$ – Nathaniel Feb 28 '17 at 8:21
  • 1
    $\begingroup$ @FrancoisZiegler yep - some people use one convention and some use the other. But that point that was made already. I emphasise once again that I changed it when people complained in order to use the more widely accepted convention, and I don't see value in a continuing discussion on the topic. $\endgroup$ – Nathaniel Feb 28 '17 at 10:18
  • 2
    $\begingroup$ A reverse convention (entropy convex, or $x\mapsto x^2$ concave) doesn't seem used at all — let alone "typically". $\endgroup$ – Francois Ziegler Feb 28 '17 at 12:00

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.