Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
"Toda" means "thanks" in Hebrew. This makes the title amusing. –  Asaf Karagila Jul 31 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 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 at 16:35
1  
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 at 22:57

3 Answers 3

up vote 13 down vote accepted

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

share|improve this answer
    
Elegant presentation! One minor comment: I think you're not really using the Schur-Horn Theorem (or rather, you're using the trivial direction): $X_{ii}=\langle e_i, X e_i\rangle \le \lambda_1$ is obvious, without any tools. –  Christian Remling Aug 1 at 2:03
1  
It has more names, too: I would call this the min-max principle. –  Christian Remling Aug 1 at 2:28
1  
Note the similarity to this answer mathoverflow.net/a/118640 –  Steven Gubkin Aug 1 at 4:00
1  
@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 Speyer Aug 1 at 12:05
1  
I put up another answer to that question which I think is closer to Toda flow mathoverflow.net/a/177584/297 . –  David Speyer Aug 1 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).

share|improve this answer
    
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 at 8:28
3  
@smyrlis: Deift-Li-Tomei prove it, too; see Proposition 5. I mentioned Moser only as an attempt at historical accuracy. –  Christian Remling Jul 31 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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