1
$\begingroup$

Let $A(t), A_0$ be a $n\times n$ hermitian complex matrices and consider the following matrix flow

\begin{align} \frac{dA}{dt} &= \left [ C\circ A , A \right ] \\ A(0) &= A_0 \ . \end{align}

Here $\circ$ stands for Hadamard (pointwise) multiplication and the (antisymmetric) matrix $C$ has the form

$$ C=\left(\begin{array}{ccccc} 0 & -1 & -1 & \cdots & -1\\ 1 & 0 & -1 & & \vdots\\ 1 & 1 & 0 & \ddots & -1\\ \vdots & & \ddots & \ddots & -1\\ 1 & 1 & \cdots & 1 & 0 \end{array}\right). $$

I am not 100% sure of the nomenclature Toda vs Morse flow, in any case the flow above or slight variation thereof, has also been considered in a few occasions on MO, for example here. It can be shown that the flow is isospectral and that as $t\to\infty$ , $A(t)$ converges to a diagonal matrix with the eigenvalues of $A_0$ ordered from lowest to largest.

My question is the following:

Is anything known about the convergence rate of $\mathrm{diag}(A(t))$ to the eigenvalues of $A_0$? Can we show that the convergence is bounded by some exponential (and in this case can we estimate the rates)?

If the question above is too complicated I would be equally interested in the convergence rate of the flow with the following modified $C$:

$$ C_1=\left(\begin{array}{ccccc} 0 & -1 & -1 & \cdots & -1\\ 1 & 0 & 0 & 0 & \vdots\\ 1 & 0 & 0 & \ddots & 0\\ \vdots & & \ddots & \ddots & 0\\ 1 & 0 & \cdots & 0 & 0 \end{array}\right). $$

In case of the flow with $C_1$, it can be shown that the matrix element $A_{1,1}(t)$ converges to the lowest eigenvalue of $A_0$, $\lambda_1$.

For the $C_1$-flow, can it be shown that $A_{1,1}(t)$ converges exponentially fast to $\lambda_1$?

It is usually said that the Toda flow is a sort of continuous version of Lanczos diagonalization algorithm. This similarity is even more marked in case of the $C_1$ flow. In fact in the latter case one can show that the "diagonalization" amounts to a (continuous) series of rank-2 unitary rotation (reminiscent of Lanczos algorithm). Since the convergence of the Lanczos algorithm is exponential in the number of iteration, I formulate the conjecture that the convergence of the above flows is also exponential. Is this true? Can it be proven? I couldn't find anything in the literature linked to the MO answers.

$\endgroup$
7
  • $\begingroup$ IN general, the strategy is to show that the correct diagonal matrix is the only stable fixed point, and hence the convergence is exponential. Are you looking to prove more than this ? $\endgroup$ Mar 24, 2020 at 17:33
  • $\begingroup$ @PiyushGrover that is exactly what I would like to prove or see a reference for $\endgroup$
    – lcv
    Mar 24, 2020 at 18:45
  • $\begingroup$ It's easy to see that a diagonal $A$ is a fixed point, but how can you show from there that the convergence is exponential? (How do you prove the "hence" in your sentence?) $\endgroup$
    – lcv
    Mar 24, 2020 at 18:47
  • $\begingroup$ There are several versions of Toda flow, for some there are results by Tomei et.al. that it gives continous version of QR algorithm. Hence the convergene is the same as for QR algorithm which is quite well-known. $\endgroup$ Mar 24, 2020 at 19:45
  • 1
    $\begingroup$ google.com/… $\endgroup$ Mar 24, 2020 at 20:29

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.