7
$\begingroup$

inAccording to some almost indecipherable notes of a graduate Linear Algebra class, a symmetric matrix $A\in\mathbb R^{n\times n}$ can be diagonalized via the Toda flow. More specifically, if $X=X(t)\in\mathbb R^{n\times n}$ is the solution of the initial value problem ($n^2\times n^2$) \begin{equation} \frac{dX}{dt} \,=\, B(X)X-XB(X), \quad X(0)\,=\, A, \end{equation} where $B(X)=X_+-(X_+)^T=-B(X)^T$, and $X_+$ is the strict upper part of $X$: $$ X_+ \,=\, \left(\! \begin{array}{cccccccc} 0 & x_{12} & x_{13} & x_{14} &\cdots & x_{1n}\\ & 0 & x_{23} & x_{24} &\cdots & x_{2n}\\ & & 0 & x_{34} & \cdots & x_{3n} \\ &&&\ddots&& \vdots \\ & & & &0&x_{n-1,n} \\ & & &&& 0 \end{array} \!\right), $$ then $$ \lim_{t\to\infty} X(t)=\varLambda, $$ where $\varLambda$ is a diagonal matrix containing the spectrum of $A$.

Is there any reference for this fact?

Update. This is due to Moser:

J. MOSER, Finitely many mass points on the line under the influence of an exponential potential-an integrable system, in “Dynamic Systems Theory and Applications” (J. Moser, Ed.), pp. 467-497, Springer-Verlag, New York/Berlin, 1975.

I was wondering if its proof is accessible anywhere.

$\endgroup$
  • $\begingroup$ "Toda" means "thanks" in Hebrew. This makes the title amusing. $\endgroup$ – Asaf Karagila Jul 31 '14 at 19:27
  • $\begingroup$ By the way, Toda flows on (Jacobi) operators on $\ell^2(\mathbb Z)$ behave very differently asymptotically, so the result almost becomes more surprising with some background knowledge (or "a little learning..."). $\endgroup$ – Christian Remling Aug 1 '14 at 2:12
  • $\begingroup$ The notes, while perhaps indecipherable, seem like they must be pretty cool if they mention stuff like this. Are they available somewhere? $\endgroup$ – Steven Gubkin Aug 1 '14 at 16:35
  • 1
    $\begingroup$ No, the are not available. I am trying to LaTeXify them. It was from a course taught at Courant by Percy Deift. $\endgroup$ – smyrlis Aug 1 '14 at 22:57
15
$\begingroup$

$\def\Tr{\mathrm{Tr}}$This proof is short enough that I thought I'd just write it out. On a skim, this looks like the same proof that Christian Remling pointed you to, and which Deift-Li-Tomei say is the same as the proof of Moser.

Disclaimer: all signs in this argument have at best a 55% chance of being right.

First of all, let $C$ be any continuous function at all from $n \times n$ matrices to $n \times n$ matrices and define $Y(t)$ by the ODE $$\frac{dY}{dt} = C(Y) Y - Y C(Y).$$ Then $$\frac{d \Tr(Y^m)}{dt} = \Tr \left( \frac{dY}{dt} Y^{m-1} + Y \frac{dY}{dt} Y^{m-2} + \cdots + Y^{m-1} \frac{dY}{dt} \right)$$ $$=\Tr \left( C(Y) Y^m - Y C(Y) Y^{m-1} + Y C(Y) Y^{m-1} - Y^2 C(Y) Y^{m-2} + \cdots + Y^{m-1} C(Y) Y - Y^m C(Y) \right) = \Tr\left( C(Y) Y^m - Y^m C(Y) \right)=0.$$ So $\Tr(Y^m)$ is constant and all the $Y(t)$'s have the same spectrum.

Also, if $Y$ is symmetric and $C(Y)$ is skew-symmetric, then $C(Y) Y - Y C(Y)$ is symmetric, so symmetric matrices stay symmetric.

Now, we specialize to the case of Toda flow. Let $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$ be the spectrum of $X$. A quick computation shows that $$\frac{d X_{kk}}{dt} = - \sum_{i< k} X_{ik}^2 + \sum_{i>k} X_{ik}^2.$$ So $$\frac{d (X_{11}+X_{22} + \cdots + X_{kk})}{dt} = \sum_{i \leq k,\ j > k} X_{ij}^2.$$ So all the quantities $X_{11}+X_{22} + \cdots + X_{kk}$ are increasing.

Since $X$ is symmetric we have $X_{ii} \leq \lambda_1$ (an inequality of Schur), so $X_{11} + \cdots + X_{kk}$ is bounded above and we conclude that $\lim_{t \to \infty} X_{11} + \cdots + X_{kk}$ exists. As a result, $\lim_{t \to \infty} X_{kk}$ exists, call it $\mu_k$.

Also, we see that $\lim_{t \to \infty} \sum_{i \leq k,\ j > k} X_{ij}^2 =0$ and we thus deduce that $\lim_{t \to \infty} X_{ij} =0$ for each $i \neq j$. So $\lim_{t \to \infty} X$ is a diagonal matrix, with diagonal entries $\mu_i$, and the same spectrum as $X$. So the $\mu$'s are a permutation of the $\lambda$'s.

Finally, we want to know in what order the $\lambda$'s occur. We can't answer this in general: all the diagonal matrices are fixed points of the flow. However, I claim that $\mu_1 \geq \mu_2 \geq \cdots \geq \mu_n$ is the only stable fixed point. Proof: If $\mu_i < \mu_{i+1}$, then a tiny perturbation in direction $e_{i,i+1} + e_{i+1, i}$ is magnified, where $e_{i,j}$ is the matrix whose unique nonzero entry is a $1$ in position $(i,j)$. So almost all matrices flow to $\mu_1 \geq \mu_2 \geq \cdots \geq \mu_n$.


On Toda flow and Morse flow The exact same proof works if $$B(X)_{ij} = c_{ij} X_{ij}$$ for any skew symmetric matrix $c$ with positive entries above the diagonal. In another answer, I work out that the Morse flow for the function $\psi(X) = \sum a_i X_{ii}$ is given by this equation with $c_{ij} = a_i - a_j$. (The metric on the set of matrices with fixed spectrum is induced by the $SO(n)$ action, and the inner product on $\mathfrak{so}(n)$ is the standard one.) So Toda flow would be Morse flow if we could arrange that $a_i -a_j = 1$ for all $i<j$. This is possible for tridiagonal matrices (a very cool lemma is that Toda flow preserves the property of having $X_{ij} = 0$ for $|i-j|>k$), but not in general. Still, I can imagine a fake history where Toda flow was discovered by writing down Morse flow for $\psi$ and then noticing that it still worked for any $c_{ij}$.

$\endgroup$
  • 1
    $\begingroup$ Indeed, this is the trivial direction. In my experience, the easy direction of that theorem is also the more useful one :). $\endgroup$ – David E Speyer Aug 1 '14 at 2:11
  • 1
    $\begingroup$ It has more names, too: I would call this the min-max principle. $\endgroup$ – Christian Remling Aug 1 '14 at 2:28
  • 1
    $\begingroup$ Note the similarity to this answer mathoverflow.net/a/118640 $\endgroup$ – Steven Gubkin Aug 1 '14 at 4:00
  • 1
    $\begingroup$ @StevenGubkin Neat! Maybe not quite so similar, though: All $n!$ diagonal matrices have the same value of for $\phi:=\sum_{i<j} X_{ij}^2$, and there are other critical points $\phi$, so Toda flow is not Morse flow, or any variant thereof, for $\phi$. I suspect it is closer to being Morse flow for $\sum (n-i) X_{ii}$; I was trying to work this out last night. $\endgroup$ – David E Speyer Aug 1 '14 at 12:05
  • 1
    $\begingroup$ I put up another answer to that question which I think is closer to Toda flow mathoverflow.net/a/177584/297 . $\endgroup$ – David E Speyer Aug 1 '14 at 12:19
6
$\begingroup$

A rather readable reference for this is Deift, Li, Tomei, Toda flows with infinitely many variables, JFA 64 (1985), 358-402 (who attribute the result to Moser).

$\endgroup$
  • $\begingroup$ Thanks. Unfortunately, I have no access to the work of Moser. I am trying to find a proof of this fact, aw well. $\endgroup$ – smyrlis Jul 31 '14 at 8:28
  • 3
    $\begingroup$ @smyrlis: Deift-Li-Tomei prove it, too; see Proposition 5. I mentioned Moser only as an attempt at historical accuracy. $\endgroup$ – Christian Remling Jul 31 '14 at 8:31
1
$\begingroup$

There's a nice reference here: Ordinary Differential equations and the Symmetric Eigenvalue Problem by Deift, Nanda and Tomei which generalizes the above result by interpreting the Toda flow on a permutahedron whose vertices are indexed by permutations of the eigenvalues of the flow (they correspond to diagonal matrices where the eigenvalues ordered on the diagonal). Specifically, all non-degenerate (non-diagonal) initial conditions flow to the diagonal matrix of its eigenvalues, where the ordering of eigenvalues is determined initially by the size of the first component of the normalized eigenvectors.

A really cute way of thinking about this is to think of the Toda flow as a continous-time version of eigenvalue iteration algorithms such as QR, Lanczos, or Householder iteration.

$\endgroup$

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.