# Diagonalization via the Toda flow

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.

• "Toda" means "thanks" in Hebrew. This makes the title amusing. – Asaf Karagila Jul 31 '14 at 19:27
• 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..."). – Christian Remling Aug 1 '14 at 2:12
• The notes, while perhaps indecipherable, seem like they must be pretty cool if they mention stuff like this. Are they available somewhere? – Steven Gubkin Aug 1 '14 at 16:35
• No, the are not available. I am trying to LaTeXify them. It was from a course taught at Courant by Percy Deift. – smyrlis Aug 1 '14 at 22:57

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

• Indeed, this is the trivial direction. In my experience, the easy direction of that theorem is also the more useful one :). – David E Speyer Aug 1 '14 at 2:11
• It has more names, too: I would call this the min-max principle. – Christian Remling Aug 1 '14 at 2:28
• Note the similarity to this answer mathoverflow.net/a/118640 – Steven Gubkin Aug 1 '14 at 4:00
• @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. – David E Speyer Aug 1 '14 at 12:05
• I put up another answer to that question which I think is closer to Toda flow mathoverflow.net/a/177584/297 . – David E Speyer Aug 1 '14 at 12:19

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

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

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.