The Toda lattice with random initial data

For an integer $n\ge 2$, let $J(0)$ be an $n\times n$ tridiagonal TE1 matrix with diagonal entries $a_1(0),\ldots,a_n(0)$ and positive off-diagonal entries $b_1(0),\ldots,b_{n-1}(0)$. In the stated TE1 convention, the diagonal entries are independent identically distributed Gaussians, the off-diagonal entries have respective $\chi_{n-j}$ distributions, and all these entries are independent. Evolve $J(t)$ by the finite, nonperiodic Toda flow. In particle coordinates its convention is

$$\ddot{x}_k=e^{x_{k-1}-x_k}-e^{x_k-x_{k+1}},\qquad 1\le k\le n,$$

with $x_0=-\infty$ and $x_{n+1}=+\infty$, and the Jacobi entries are

$$a_k(t)=-\frac{\dot{x}_k(t)}{2},\qquad b_j(t)=\frac12 e^{(x_j(t)-x_{j+1}(t))/2}.$$

Deift (2007)

For tolerance $\varepsilon>0$, define the first time at which every off-diagonal entry is below tolerance by

$$\tau_{n,\varepsilon}:=\inf\left\{t\ge 0:\max_{1\le j\le n-1}b_j(t)<\varepsilon\right\}.$$

The question is to determine the expected time $\mathbb{E}_{\mathrm{TE1}}[\tau_{n,\varepsilon}]$ as a function of $n$ and $\varepsilon$—equivalently, the average time for these random-initial-data Toda particles to become free to this tolerance. Deift (2007)

Background

The finite Toda lattice is an integrable system of particles interacting through exponential forces. Flaschka and Manakov established its integrable structure in the 1970s: the particle motion has a tridiagonal Lax matrix and preserves its spectrum. In the Toda convention above, the long-time particle velocities satisfy $\dot{x}_n(\infty)>\cdots>\dot{x}_1(\infty)$, and the limiting diagonal entries are paired with them by $a_k(\infty)=-\dot{x}_k(\infty)/2$. Thus the diagonal entries occur in the reverse order from the asymptotic velocities; they are the eigenvalues of the initial Jacobi matrix. Deift (2007)

The random initial condition links this asymptotic diagonalization to random matrix theory: Householder tridiagonalization of a GOE matrix yields the independent Gaussian and chi-distributed entries of the TE1 Jacobi matrix. Deift, Li, Nanda, and Tomei proposed Toda evolution as an eigenvalue algorithm. Earlier work of Symes connected QR iteration to a discrete-time integrable Hamiltonian evolution that Poisson commutes with the Toda Hamiltonian. The 2007 discussion posed the average time for TE1 data to become free as a central question; its suggestion to focus on one off-diagonal entry concerns deflation and is not the full stopping criterion formulated here. Deift (2007)

Known results

For $n=2$, the full stopping condition is just $b_1(t)<\varepsilon$. An analysis of the Toda flow on $\mathrm{Symm}(2)$ reports the GOE estimate $\mu_{2,\varepsilon,\mathrm{GOE}}\sim C|\log\varepsilon|$ as $\varepsilon\to0$. The authors characterize their estimates as formal and say that further work would be needed to make them rigorous. This therefore gives a proposed small-tolerance scale in the two-dimensional case, not a rigorous theorem for the stated general-$n$ expectation. How long does it take to compute the eigenvalues of a random symmetric matrix? (2012)

A rigorous universality result concerns a different, localized halting time: $T^{(1)}$, the time when the norm of the off-diagonal entries in the first row becomes at most $\varepsilon$. For fixed $0<\sigma<1$, in the scaling region $\log(\varepsilon^{-1})/\log N\ge 5/3+\sigma/2$, and for real or complex invariant ensembles or Wigner ensembles, the normalized $T^{(1)}$ converges in distribution as $N\to\infty$ to the law of the reciprocal limiting gap between the two largest eigenvalues. This result addresses one specified deflation event, not the time until all Jacobi off-diagonal entries are below tolerance, so it does not determine the expectation asked for here. Universality for the Toda algorithm to compute the largest eigenvalue of a random matrix (2016)