24.8 Lax Pairs and the Toda Flow

The QR algorithm of Section 5 is a sequence $\mathbf{A}^{(1)}, \mathbf{A}^{(2)}, \mathbf{A}^{(3)}, \dots$ of matrices, each similar to the last, drifting towards triangular form. Nothing in it looks like a differential equation. This section shows that it is one: there is a curve $\mathbf{L}(t)$ of matrices, all with the same eigenvalues, that passes through the QR iterates at the integer times. The bridge is a class of matrix differential equations whose solutions cannot change their spectrum, and the proof that they cannot is a page of pure algebra. It is the one place in the chapter where nothing is computed and nothing is rounded.

Throughout, $I \subseteq \mathbb{R}$ is an open interval and matrix-valued functions of $t \in I$ are differentiated entrywise, as in Definition 16.6.1. In this section the letter $\mathbf{L}$ names the matrix being flowed, following the universal notation for it; the graph Laplacian of Section 11 carries the same symbol and never appears here.

24.8.1. Which matrix differential equations preserve the spectrum?

Start from the answer we want and read the equation off it. Suppose $\mathbf{L}(t)$ is a curve of matrices, all similar to $\mathbf{L}(0)$ by a similarity that also moves with $t$ : $\mathbf{L}(t) = \mathbf{S}(t)\,\mathbf{L}(0)\,\mathbf{S}(t)^{-1},$ with $\mathbf{S} \colon I \to M_n(\mathbb{C})$ differentiable and everywhere invertible. Differentiate. By the product rule (Lemma 16.6.4) and the derivative of the inverse (Theorem 16.6.5), $\begin{aligned} \mathbf{L}' &= \mathbf{S}'\mathbf{L}(0)\mathbf{S}^{-1} - \mathbf{S}\mathbf{L}(0)\mathbf{S}^{-1}\mathbf{S}'\mathbf{S}^{-1}\\ &= (\mathbf{S}'\mathbf{S}^{-1})\mathbf{L} - \mathbf{L}(\mathbf{S}'\mathbf{S}^{-1}) , \end{aligned}$ where the second line inserts $\mathbf{S}^{-1}\mathbf{S} = \mathbf{I}$ in the first term and recognizes $\mathbf{S}\mathbf{L}(0)\mathbf{S}^{-1} = \mathbf{L}$ in both. So with $\mathbf{B} = \mathbf{S}'\mathbf{S}^{-1}$ the curve satisfies $\mathbf{L}' = \mathbf{B}\mathbf{L} - \mathbf{L}\mathbf{B}$ . The commutator is not a clever choice: it is what a moving similarity is forced to satisfy.

A Lax pair is a matrix that moves, together with the infinitesimal similarity that moves it.

Definition 24.8.1 (Lax Pair)

Let $I \subseteq \mathbb{R}$ be an open interval. A Lax pair on $I$ is a pair of functions $\mathbf{L}, \mathbf{B} \colon I \to M_n(\mathbb{C})$ , with $\mathbf{L}$ differentiable, such that $\mathbf{L}'(t) = [\mathbf{B}(t), \mathbf{L}(t)] \mathrel{:=} \mathbf{B}(t)\mathbf{L}(t) - \mathbf{L}(t)\mathbf{B}(t) \qquad \text{for every } t \in I .$ The equation itself is called a Lax equation, and $\mathbf{L}$ is said to flow under it.

Clause by clause. The two matrices are square of the same size $n$ , or the bracket is not defined. Only $\mathbf{L}$ is required to be differentiable; $\mathbf{B}$ may be any function of $t$ whatsoever, and in the interesting cases it is built out of $\mathbf{L}(t)$ itself, which makes the equation nonlinear. The bracket $[\mathbf{B}, \mathbf{L}]$ is the commutator of the notation list, and the order matters: $[\mathbf{L}, \mathbf{B}] = -[\mathbf{B}, \mathbf{L}]$ , so swapping the two letters runs the flow backwards.

Examples.

$\mathbf{B} = \mathbf{O}$ . Then $\mathbf{L}' = \mathbf{O}$ , so $\mathbf{L}$ is constant. The degenerate case, and it matters: it is the sanity check that the definition does not force motion.
Constant $\mathbf{B}$ . Put $\mathbf{L}(t) = e^{t\mathbf{B}}\mathbf{L}_0e^{-t\mathbf{B}}$ for a fixed $\mathbf{L}_0$ . By Theorem 10.9.4 (b) and Lemma 16.6.4, $\mathbf{L}'(t) = \mathbf{B} e^{t\mathbf{B}}\mathbf{L}_0e^{-t\mathbf{B}} + e^{t\mathbf{B}}\mathbf{L}_0(-\mathbf{B} e^{-t\mathbf{B}}) = \mathbf{B}\mathbf{L} - \mathbf{L}\mathbf{B} ,$ the last step because $\mathbf{B}$ commutes with $e^{\pm t\mathbf{B}}$ , again by Theorem 10.9.4 (b). So $(\mathbf{L}, \mathbf{B})$ is a Lax pair on all of $\mathbb{R}$ . Corollary 24.8.2 below says these are the only solutions when $\mathbf{B}$ is constant.

A third example is worth a block of its own, because it is the one to hold in mind.

Example (A curve of matrices with a frozen spectrum)

Take $\mathbf{B} = \begin{psmallmatrix} 0 & 1 \\ 0 & 0\end{psmallmatrix}$ and $\mathbf{L}_0 = \begin{psmallmatrix} 0 & 0 \\ 1 & 0\end{psmallmatrix}$ . Since $\mathbf{B}^2 = \mathbf{O}$ , Definition 10.9.2 gives $e^{t\mathbf{B}} = \mathbf{I} + t\mathbf{B}$ , and the recipe of the previous example produces $\mathbf{L}(t) = \begin{pmatrix} 1 & t \\ 0 & 1\end{pmatrix}\begin{pmatrix} 0 & 0 \\ 1 & 0\end{pmatrix}\begin{pmatrix} 1 & -t \\ 0 & 1\end{pmatrix} = \begin{pmatrix} t & -t^2 \\ 1 & -t\end{pmatrix} .$ Three of the four entries move — only the corner $\ell_{21} = 1$ stands still — and yet $\operatorname{tr}\mathbf{L}(t) = 0$ and $\det\mathbf{L}(t) = -t^2 + t^2 = 0$ , so $p_{\mathbf{L}(t)}(x) = x^2$ for every $t$ . The curve stays inside one similarity class the whole time.

A nonexample, by dropping the second term. Replace the Lax equation by $\mathbf{L}' = \mathbf{B}\mathbf{L}$ with $\mathbf{B} = \mathbf{I}$ . The unique solution with $\mathbf{L}(0) = \mathbf{L}_0$ is $\mathbf{L}(t) = e^{t}\mathbf{L}_0$ (Theorem 10.9.6, applied to each column). Its eigenvalues are $e^{t}\lambda_i$ , which move. What was lost is precisely the second term: $\mathbf{B}\mathbf{L}$ alone is not a commutator, and a commutator is what the differentiation of a similarity produced.

Warning. Isospectral does not mean constant. In Example (A curve of matrices with a frozen spectrum) the matrix $\mathbf{L}(t)$ changes at every instant; what stays put is its list of eigenvalues. The eigenvectors move, and they must, since they are the columns of $\mathbf{S}(t)$ up to scale. A flow that fixed the eigenvectors as well would fix $\mathbf{L}$ . The whole use of a Lax pair — in Section 5’s language, in this section’s, and in the theory of integrable systems generally — is that something moves while something else does not.

24.8.2. The isospectral theorem

The derivation above suggests the proof: manufacture $\mathbf{S}(t)$ and conclude by similarity. That route runs into an obstacle the book cannot clear. The natural $\mathbf{S}$ is the solution of $\mathbf{S}' = \mathbf{B}\mathbf{S}$ , $\mathbf{S}(t_0) = \mathbf{I}$ , and for a constant $\mathbf{B}$ that is $e^{(t-t_0)\mathbf{B}}$ by Chapter 10 §09. For a $\mathbf{B}$ that depends on $t$ — the only case of interest here — the existence of such an $\mathbf{S}$ is a theorem about linear differential equations with variable coefficients, and this book does not prove it. So we take a different route, which needs no flow at all.

Theorem 24.8.1 (Lax Pairs Are Isospectral)

Let $(\mathbf{L}, \mathbf{B})$ be a Lax pair on an open interval $I$ . Then the characteristic polynomial of $\mathbf{L}(t)$ does not depend on $t$ : $p_{\mathbf{L}(t)} = p_{\mathbf{L}(s)} \qquad \text{for all } s, t \in I .$ In particular $\mathbf{L}(t)$ has the same eigenvalues as $\mathbf{L}(s)$ , with the same algebraic multiplicities, and $\operatorname{tr}\mathbf{L}(t)$ and $\det\mathbf{L}(t)$ are constant.

Idea. Freeze $x \in \mathbb{C}$ and watch the single number $f(t) = \det(x\mathbf{I} - \mathbf{L}(t))$ . Jacobi’s formula turns its derivative into a trace against the adjugate, and the adjugate is the one matrix that turns $\mathbf{M}$ into the scalar $\det\mathbf{M}$ from either side. Writing the bracket in terms of $\mathbf{M} = x\mathbf{I} - \mathbf{L}$ rather than $\mathbf{L}$ — which is legitimate, because $x\mathbf{I}$ commutes with everything — makes the two halves of the trace cancel, because a trace is unchanged by a cyclic shift. So $f' \equiv 0$ , and a polynomial identity valid for every $x$ is an identity of polynomials.

Proof. Fix $x \in \mathbb{C}$ and put $\mathbf{M}(t) = x\mathbf{I} - \mathbf{L}(t)$ , which is differentiable with $\mathbf{M}'(t) = -\mathbf{L}'(t)$ (Definition 16.6.1). Let $f(t) = \det\mathbf{M}(t) = p_{\mathbf{L}(t)}(x) .$ By Jacobi’s formula (Theorem 16.6.6), $f$ is differentiable on $I$ with $f'(t) = \operatorname{tr}\bigl(\operatorname{adj}\mathbf{M}(t)\,\mathbf{M}'(t)\bigr).$

Rewrite the bracket in terms of $\mathbf{M}$ . Since $\mathbf{L} = x\mathbf{I} - \mathbf{M}$ and $x\mathbf{I}$ commutes with $\mathbf{B}$ , $[\mathbf{B}, \mathbf{L}] = \mathbf{B}(x\mathbf{I} - \mathbf{M}) - (x\mathbf{I} - \mathbf{M})\mathbf{B} = \mathbf{M}\mathbf{B} - \mathbf{B}\mathbf{M} ,$ so $\mathbf{M}' = -\mathbf{L}' = -[\mathbf{B}, \mathbf{L}] = \mathbf{B}\mathbf{M} - \mathbf{M}\mathbf{B}$ . Writing $\mathbf{M} = \mathbf{M}(t)$ and using the linearity of the trace (Theorem 0.9.6 (1)), $f'(t) = \operatorname{tr}\bigl(\operatorname{adj}\mathbf{M}\,\mathbf{B}\mathbf{M}\bigr) - \operatorname{tr}\bigl(\operatorname{adj}\mathbf{M}\,\mathbf{M}\mathbf{B}\bigr).$ A cyclic shift (Theorem 0.9.6 (3)) moves $\mathbf{M}$ to the front of the first trace, so $f'(t) = \operatorname{tr}\bigl(\mathbf{M}\,\operatorname{adj}\mathbf{M}\,\mathbf{B}\bigr) - \operatorname{tr}\bigl(\operatorname{adj}\mathbf{M}\,\mathbf{M}\,\mathbf{B}\bigr).$ By Theorem 7.6.2, $\mathbf{M}\operatorname{adj}\mathbf{M} = \operatorname{adj}\mathbf{M}\,\mathbf{M} = (\det\mathbf{M})\mathbf{I}$ , so the two traces are the same number and $f'(t) = 0$ for every $t \in I$ .

A differentiable function on an interval with vanishing derivative is constant — the mean value theorem, fact (A6) of Chapter 16’s introduction, applied to the real and imaginary parts of $f$ . (Chapter 10 §09’s fact (A4) says this for functions defined on all of $\mathbb{R}$ , which is not the hypothesis here.) So $p_{\mathbf{L}(t)}(x) = p_{\mathbf{L}(s)}(x)$ for all $s, t \in I$ .

Finally, $x \in \mathbb{C}$ was arbitrary, so the two polynomials $p_{\mathbf{L}(t)}$ and $p_{\mathbf{L}(s)}$ define the same function $\mathbb{C} \to \mathbb{C}$ ; since $\mathbb{C}$ is infinite, Theorem 6.1.5 (b) gives $p_{\mathbf{L}(t)} = p_{\mathbf{L}(s)}$ as polynomials. The eigenvalues are their roots and the multiplicities the multiplicities of those roots, and $\operatorname{tr}$ and $\det$ are two of the coefficients up to sign (Theorem 7.10.2). This proves the theorem.

Remark. What the proof did not need. It never produced the similarity $\mathbf{S}(t)$ , never solved a differential equation, and never used any property of $\mathbf{B}$ — not continuity, and not differentiability. The only analytic ingredients are two: (D1), the differentiation package Chapter 16 §06 quoted, which is what Jacobi’s formula rests on, and the mean value theorem (A6) of Chapter 16’s introduction, in the form “zero derivative on an interval implies constant”. Everything else is the adjugate identity and the invariance of the trace under a cyclic shift.

When $\mathbf{B}$ is constant, the similarity is available and the theorem can be sharpened: the flow is completely determined.

Corollary 24.8.2 (Constant

\mathbf{B}

: the flow is conjugation by the exponential)

Let $\mathbf{B} \in M_n(\mathbb{C})$ be a fixed matrix and let $\mathbf{L} \colon \mathbb{R} \to M_n(\mathbb{C})$ be differentiable with $\mathbf{L}' = [\mathbf{B}, \mathbf{L}]$ . Then $\mathbf{L}(t) = e^{t\mathbf{B}}\,\mathbf{L}(0)\,e^{-t\mathbf{B}} \qquad (t \in \mathbb{R}),$ so $\mathbf{L}(t)$ is similar to $\mathbf{L}(0)$ for every $t$ .

Proof. Put $\mathbf{M}(t) = e^{-t\mathbf{B}}\mathbf{L}(t)e^{t\mathbf{B}}$ , a product of three differentiable matrix functions. By Lemma 16.6.4 and Theorem 10.9.4 (b), which also gives $\mathbf{B} e^{\pm t\mathbf{B}} = e^{\pm t\mathbf{B}}\mathbf{B}$ , $\begin{aligned} \mathbf{M}'(t) &= -\mathbf{B} e^{-t\mathbf{B}}\mathbf{L} e^{t\mathbf{B}} + e^{-t\mathbf{B}}\mathbf{L}' e^{t\mathbf{B}} + e^{-t\mathbf{B}}\mathbf{L}\mathbf{B} e^{t\mathbf{B}}\\ &= e^{-t\mathbf{B}}\bigl(-\mathbf{B}\mathbf{L} + (\mathbf{B}\mathbf{L} - \mathbf{L}\mathbf{B}) + \mathbf{L}\mathbf{B}\bigr)e^{t\mathbf{B}} = \mathbf{O} . \end{aligned}$ By fact (A4) of Chapter 10 §09, every entry of $\mathbf{M}$ is constant, so $\mathbf{M}(t) = \mathbf{M}(0) = \mathbf{L}(0)$ . Multiplying on the left by $e^{t\mathbf{B}}$ and on the right by $e^{-t\mathbf{B}}$ , and using $(e^{t\mathbf{B}})^{-1} = e^{-t\mathbf{B}}$ from Theorem 10.9.4 (c), gives the formula. This proves the corollary.

Quick check. Prove directly from the Lax equation, without Theorem 24.8.1, that $\operatorname{tr}\mathbf{L}(t)$ is constant.

Solution. The trace of a matrix is a linear function of its entries, so $(\operatorname{tr}\mathbf{L})'(t) = \operatorname{tr}(\mathbf{L}'(t))$ by (D1) and Theorem 0.9.6 (1). Then $\operatorname{tr}\mathbf{L}'(t) = \operatorname{tr}(\mathbf{B}\mathbf{L}) - \operatorname{tr}(\mathbf{L}\mathbf{B}) = 0$ by Theorem 0.9.6 (3). So $\operatorname{tr}\mathbf{L}$ has zero derivative on $I$ and is constant by fact (A6) of Chapter 16’s introduction. The same argument applied to $\mathbf{L}^m$ gives $\operatorname{tr}(\mathbf{L}^m)' = 0$ for every $m \ge 1$ (Exercise (C1: The power sums are constants of the motion)).

24.8.3. The Toda flow

Now for the flow that matters. Take $\mathbf{L}$ real symmetric and tridiagonal, and take $\mathbf{B}$ to be the skew-symmetric matrix built from the off-diagonal entries of $\mathbf{L}$ . There are two sign conventions, differing by $\mathbf{B} \mapsto -\mathbf{B}$ and so running the flow in opposite directions; we fix the one that drives the largest eigenvalue towards the top-left corner, as Example (The $2 \times 2$ flow, twice) will confirm.

Definition 24.8.2 (The Toda Flow)

For $\mathbf{M} \in M_n(\mathbb{R})$ write $\mathbf{M}_{+}$ for its strictly upper triangular part and $\mathbf{M}_{-}$ for its strictly lower triangular part, so that $\mathbf{M}$ is the sum of $\mathbf{M}_{-}$ , its diagonal part, and $\mathbf{M}_{+}$ , and set $\mathbf{B}(\mathbf{M}) \mathrel{:=} \mathbf{M}_{+} - \mathbf{M}_{-} .$ The Toda flow is the Lax equation $\mathbf{L}'(t) = \bigl[\mathbf{B}(\mathbf{L}(t)),\ \mathbf{L}(t)\bigr]$ for a differentiable $\mathbf{L} \colon I \to M_n(\mathbb{R})$ taking symmetric tridiagonal values.

Two clauses need checking. First, $\mathbf{B}(\mathbf{M})$ is skew-symmetric when $\mathbf{M}$ is symmetric: transposing turns the strictly upper part into the strictly lower part of $\mathbf{M}^{\top} = \mathbf{M}$ , so $\mathbf{B}(\mathbf{M})^{\top} = \mathbf{M}_{-} - \mathbf{M}_{+} = -\mathbf{B}(\mathbf{M})$ . Second, the equation is nonlinear: $\mathbf{B}$ depends on $\mathbf{L}$ , and the right-hand side is quadratic in the entries of $\mathbf{L}$ . That is what makes it a genuine dynamical system rather than a rewriting of Corollary 24.8.2.

Writing the equation out shows what it does.

Proposition 24.8.3 (The Toda Flow in Coordinates)

Let $\mathbf{L} \in M_n(\mathbb{R})$ be symmetric and tridiagonal, with diagonal entries $d_1, \dots, d_n$ and off-diagonal entries $e_1, \dots, e_{n-1}$ , so $\ell_{i,i+1} = \ell_{i+1,i} = e_i$ . Put $e_0 = e_n = 0$ . Then $[\mathbf{B}(\mathbf{L}), \mathbf{L}]$ is again symmetric and tridiagonal, with $\bigl[\mathbf{B}(\mathbf{L}), \mathbf{L}\bigr]_{ii} = 2\bigl(e_i^2 - e_{i-1}^2\bigr), \qquad \bigl[\mathbf{B}(\mathbf{L}), \mathbf{L}\bigr]_{i,i+1} = e_i\,(d_{i+1} - d_i) .$ Consequently the Toda flow is the system

d_i' = 2\bigl(e_i^2 - e_{i-1}^2\bigr) \ \ (1 \le i \le n), \qquad e_i' = e_i\,(d_{i+1} - d_i) \ \ (1 \le i \le n-1) .

(24.8.1)

Proof. Write $\mathbf{B} = \mathbf{B}(\mathbf{L})$ , so that $b_{i,i+1} = e_i$ , $b_{i+1,i} = -e_i$ , and every other entry of $\mathbf{B}$ is $0$ . Then for all $i, j$ , $(\mathbf{B}\mathbf{L})_{ij} = e_i\,\ell_{i+1,j} - e_{i-1}\,\ell_{i-1,j}, \qquad (\mathbf{L}\mathbf{B})_{ij} = e_{j-1}\,\ell_{i,j-1} - e_{j}\,\ell_{i,j+1},$ with the convention that a term with an index outside $1, \dots, n$ is $0$ ; this is just the two nonzero entries in row $i$ of $\mathbf{B}$ , respectively in column $j$ of $\mathbf{B}$ . Write $\mathbf{C} = \mathbf{B}\mathbf{L} - \mathbf{L}\mathbf{B}$ , so $c_{ij} = e_i\ell_{i+1,j} - e_{i-1}\ell_{i-1,j} - e_{j-1}\ell_{i,j-1} + e_{j}\ell_{i,j+1} . \tag{$\ast$}$

$\mathbf{C}$ is symmetric: since $\mathbf{B}^{\top} = -\mathbf{B}$ and $\mathbf{L}^{\top} = \mathbf{L}$ , $\mathbf{C}^{\top} = \mathbf{L}^{\top}\mathbf{B}^{\top} - \mathbf{B}^{\top}\mathbf{L}^{\top} = -\mathbf{L}\mathbf{B} + \mathbf{B}\mathbf{L} = \mathbf{C} ,$ so it is enough to compute $c_{ij}$ for $j \ge i$ .

Case $j = i$ . Every $\ell$ appearing in $(\ast)$ is then an off-diagonal neighbor: $\ell_{i+1,i} = e_i$ , $\ell_{i-1,i} = e_{i-1}$ , $\ell_{i,i-1} = e_{i-1}$ , $\ell_{i,i+1} = e_i$ . So $c_{ii} = e_i^2 - e_{i-1}^2 - e_{i-1}^2 + e_i^2 = 2(e_i^2 - e_{i-1}^2).$

Case $j = i+1$ . Now $\ell_{i+1,i+1} = d_{i+1}$ and $\ell_{i,i} = d_i$ , while $\ell_{i-1,i+1} = 0$ and $\ell_{i,i+2} = 0$ because $\mathbf{L}$ is tridiagonal. So $c_{i,i+1} = e_i d_{i+1} - e_i d_i$ .

Case $j = i+2$ . Here $\ell_{i+1,i+2} = e_{i+1}$ and $\ell_{i,i+1} = e_i$ , while $\ell_{i-1,i+2} = \ell_{i,i+3} = 0$ . So $c_{i,i+2} = e_ie_{i+1} - 0 - e_{i+1}e_i + 0 = 0 .$

Case $j \ge i+3$ . Each of the four entries $\ell_{i+1,j}$ , $\ell_{i-1,j}$ , $\ell_{i,j-1}$ , $\ell_{i,j+1}$ has its two indices differing by at least $2$ , so all four are $0$ and $c_{ij} = 0$ .

Hence $\mathbf{C}$ is symmetric tridiagonal with the stated entries, and equating $\mathbf{L}'$ with $\mathbf{C}$ entry by entry gives Eq. 24.8.1. This proves the proposition.

Read Eq. 24.8.1 for what it is. The off-diagonal entries feed the diagonal — mass $e_i^2$ flows from $d_{i+1}$ up to $d_i$ — and the diagonal drives the off-diagonal, each $e_i$ growing or shrinking according to the sign of $d_{i+1} - d_i$ . Summing the first family gives $\sum_i d_i' = 0$ , the constancy of the trace, with the terms canceling in pairs. And an $e_i$ that vanishes at some time has $e_i' = 0$ at that same time. It is tempting to read off that such an $e_i$ stays $0$ for ever — that the flow never re-couples two blocks which have already separated, the continuous shadow of deflation in Section 5 — but that is a statement about the solutions of the system, and getting it from the instantaneous one needs a uniqueness theorem for differential equations of the sort this section declined to assume above. Only the instantaneous statement is claimed here.

Example (The

2 \times 2

flow, twice)

Let $n = 2$ , so $\mathbf{L} = \begin{psmallmatrix} d_1 & e_1 \\ e_1 & d_2\end{psmallmatrix}$ and Eq. 24.8.1 reads $d_1' = 2e_1^2, \qquad d_2' = -2e_1^2, \qquad e_1' = e_1(d_2 - d_1) .$

(a) Verify by hand that $\operatorname{tr}\mathbf{L}$ and $\det\mathbf{L}$ are constant along the flow.
(b) Solve the flow explicitly for $\mathbf{L}(0) = \begin{psmallmatrix} 0 & 1 \\ 1 & 0\end{psmallmatrix}$ .

Solution.

(a) $(\operatorname{tr}\mathbf{L})' = d_1' + d_2' = 2e_1^2 - 2e_1^2 = 0$ . For the determinant, $(\det\mathbf{L})' = (d_1d_2 - e_1^2)' = d_1'd_2 + d_1d_2' - 2e_1e_1' ,$ by (D1) of Chapter 16 §06. Substituting, $2e_1^2d_2 - 2d_1e_1^2 - 2e_1^2(d_2 - d_1) = 0 .$ So both coefficients of $p_{\mathbf{L}(t)}(x) = x^2 - (\operatorname{tr}\mathbf{L})x + \det\mathbf{L}$ are constant, which is Theorem 24.8.1 for $n = 2$ , got by hand.
(b) Put $u = e^{4t}$ and $d_1(t) = \frac{u - 1}{u + 1}, \qquad d_2(t) = -d_1(t), \qquad e_1(t) = \frac{2e^{2t}}{u + 1} .$ At $t = 0$ , $u = 1$ gives $d_1 = 0$ and $e_1 = 1$ , which is $\mathbf{L}(0)$ . Differentiating, with $u' = 4u$ , $d_1' = \frac{4u(u+1) - (u-1)4u}{(u+1)^2} = \frac{8u}{(u+1)^2}, \qquad 2e_1^2 = \frac{8e^{4t}}{(u+1)^2} = \frac{8u}{(u+1)^2},$ so the first equation holds; the second then holds because $d_2 = -d_1$ . For the third, $e_1' = \frac{4e^{2t}(u+1) - 2e^{2t}\cdot 4u}{(u+1)^2} = \frac{4e^{2t}(1 - u)}{(u+1)^2},$ while $e_1(d_2 - d_1) = -2d_1e_1 = -2\cdot\frac{u-1}{u+1}\cdot\frac{2e^{2t}}{u+1}$ , which is the same. Two checks: $d_1^2 + e_1^2 = \bigl((u-1)^2 + 4u\bigr)/(u+1)^2 = 1$ , so $\det\mathbf{L}(t) = -1$ for every $t$ , matching $\det\mathbf{L}(0) = -1$ ; and as $t \to \infty$ , $d_1 \to 1$ and $e_1 \to 0$ , so $\mathbf{L}(t) \to \operatorname{diag}(1, -1)$ . The flow sorts the eigenvalues $\pm 1$ onto the diagonal, largest first.

The last sentence of that example is the whole point of the section. Sorting the eigenvalues onto the diagonal in decreasing order, with the off-diagonal entries dying away, is exactly what the QR algorithm does. The next theorem says the resemblance is an identity.

24.8.4. The QR algorithm is the Toda flow at integer times

One piece of algebra first. The skew-symmetric matrices and the upper triangular matrices fill $M_n(\mathbb{R})$ between them, without overlap.

Lemma 24.8.4 (Skew plus upper triangular, uniquely)

Every $\mathbf{M} \in M_n(\mathbb{R})$ is $\mathbf{M} = \mathbf{K} + \mathbf{U}$ for exactly one skew-symmetric $\mathbf{K}$ and one upper triangular $\mathbf{U}$ . If $\mathbf{M}$ is symmetric then $\mathbf{K} = \mathbf{M}_{-} - \mathbf{M}_{+} = -\mathbf{B}(\mathbf{M})$ .

Proof. Uniqueness. It suffices to show that a matrix $\mathbf{X}$ that is both skew-symmetric and upper triangular is $\mathbf{O}$ . Its transpose $\mathbf{X}^{\top} = -\mathbf{X}$ is lower triangular and upper triangular at once, hence diagonal; so $\mathbf{X}$ is diagonal with $x_{ii} = -x_{ii}$ , giving $\mathbf{X} = \mathbf{O}$ . If $\mathbf{K}_1 + \mathbf{U}_1 = \mathbf{K}_2 + \mathbf{U}_2$ then $\mathbf{K}_1 - \mathbf{K}_2 = \mathbf{U}_2 - \mathbf{U}_1$ is such an $\mathbf{X}$ .

Existence for symmetric $\mathbf{M}$ , which is the only case we use. Put $\mathbf{K} = \mathbf{M}_{-} - \mathbf{M}_{+}$ , skew-symmetric by the computation after Definition 24.8.2, and $\mathbf{U} = \mathbf{M} - \mathbf{K}$ , whose strictly lower part is $\mathbf{M}_{-} - \mathbf{M}_{-} = \mathbf{O}$ , so it is upper triangular. For a general $\mathbf{M}$ , take $\mathbf{K} = \mathbf{M}_{-} - (\mathbf{M}_{-})^{\top}$ and $\mathbf{U} = \mathbf{M} - \mathbf{K}$ ; the entries of $\mathbf{U}$ below the diagonal are $m_{ij} - m_{ij} = 0$ for $i > j$ . This proves the lemma.

Theorem 24.8.5 (One QR Step Is One Unit of Toda Time)

Let $\mathbf{L}_0 \in M_n(\mathbb{R})$ be symmetric and let $\mathbf{A}^{(1)}, \mathbf{A}^{(2)}, \mathbf{A}^{(3)}, \dots$ be the unshifted QR iterates of Definition 24.5.1 started at $\mathbf{A}^{(1)} = e^{\mathbf{L}_0}$ , with the factorizations $\mathbf{A}^{(k)} = \mathbf{Q}^{(k)}\mathbf{R}^{(k)}, \qquad \mathbf{A}^{(k+1)} = \mathbf{R}^{(k)}\mathbf{Q}^{(k)} \qquad (k \ge 1)$ normalized so that each $\mathbf{R}^{(k)}$ has positive diagonal entries, and write $\mathbf{W}_k = \mathbf{Q}^{(1)}\mathbf{Q}^{(2)}\cdots\mathbf{Q}^{(k)}$ , with $\mathbf{W}_0 = \mathbf{I}$ . Then for every $k \ge 0$ :

(a) the factorizations exist and are unique, and $\mathbf{A}^{(k+1)} = \mathbf{W}_k^{\top}\,\mathbf{A}^{(1)}\,\mathbf{W}_k$ ;
(b) $\mathbf{W}_k$ is the orthogonal factor in the QR factorization of $e^{k\mathbf{L}_0}$ ;
(c) $\mathbf{A}^{(k+1)} = e^{\mathbf{L}_k}$ , where $\mathbf{L}_k = \mathbf{W}_k^{\top}\,\mathbf{L}_0\,\mathbf{W}_k$ is symmetric and has the same eigenvalues as $\mathbf{L}_0$ .

Idea. Each QR step is a similarity by the orthogonal factor, so after $k$ steps the matrix has been conjugated by the accumulated product $\mathbf{W}_k$ . Conjugating an exponential is exponentiating the conjugate, which turns the statement about $\mathbf{A}$ into a statement about $\mathbf{L}$ . The only thing left to identify is $\mathbf{W}_k$ , and Section 5 has already done the work: Theorem 24.5.2 supplies the telescoping identity $(\mathbf{A}^{(1)})^k = \mathbf{W}_k\mathbf{R}^{(k)}\cdots\mathbf{R}^{(1)}$ . A product of orthogonal matrices is orthogonal, a product of upper triangular matrices with positive diagonal is again one, so uniqueness of the QR factorization names $\mathbf{W}_k$ for us.

Proof. Step 1: the factorizations exist and are unique. By Theorem 10.9.4 (c), $\mathbf{A}^{(1)} = e^{\mathbf{L}_0}$ is invertible, so its columns are independent and Theorem 11.8.1 applies, giving a unique $\mathbf{Q}^{(1)}$ with orthonormal columns — here square, hence orthogonal — and a unique upper triangular $\mathbf{R}^{(1)}$ with positive diagonal. Every $\mathbf{A}^{(k)}$ is similar to $\mathbf{A}^{(1)}$ by Proposition 24.5.1, hence invertible, so the same argument runs at every step. This positive-diagonal normalization is the choice Definition 24.5.1 deliberately left open, and it is the only ingredient here that Section 5 does not already supply.

Step 2: (a), and the telescoping identity. Every matrix here is real and each $\mathbf{Q}^{(k)}$ is orthogonal, so the conjugate transpose in Theorem 24.5.2 is a transpose. With $\mathbf{S}_k \mathrel{:=} \mathbf{R}^{(k)}\mathbf{R}^{(k-1)}\cdots\mathbf{R}^{(1)}$ and $\mathbf{S}_0 = \mathbf{I}$ , that theorem — whose $\mathbf{U}_k$ and $\mathbf{T}_k$ are our $\mathbf{W}_k$ and $\mathbf{S}_k$ — gives, for every $k \ge 1$ , $\mathbf{A}^{(k+1)} = \mathbf{W}_k^{\top}\,\mathbf{A}^{(1)}\,\mathbf{W}_k \qquad\text{and}\qquad (\mathbf{A}^{(1)})^{k} = \mathbf{W}_k\mathbf{S}_k ,$ and for $k = 0$ the two read $\mathbf{A}^{(1)} = \mathbf{A}^{(1)}$ and $\mathbf{I} = \mathbf{I}$ , since $\mathbf{W}_0 = \mathbf{S}_0 = \mathbf{I}$ . The first is (a).

Step 3: (b). Since $\mathbf{L}_0$ commutes with itself, Theorem 10.9.4 (d) gives $(e^{\mathbf{L}_0})^{k} = e^{k\mathbf{L}_0}$ , so $e^{k\mathbf{L}_0} = \mathbf{W}_k\mathbf{S}_k$ . Each $\mathbf{Q}^{(j)}$ is orthogonal, so $\mathbf{W}_k$ is orthogonal. Each $\mathbf{R}^{(j)}$ is upper triangular with positive diagonal, and a product of such matrices is upper triangular with diagonal entries the products of the diagonal entries, hence positive; so $\mathbf{S}_k$ is upper triangular with positive diagonal. By the uniqueness in Theorem 11.8.1, $\mathbf{W}_k\mathbf{S}_k$ is the QR factorization of $e^{k\mathbf{L}_0}$ .

Step 4: (c). $\mathbf{W}_k$ is orthogonal, so $\mathbf{W}_k^{\top} = \mathbf{W}_k^{-1}$ , and Theorem 10.9.4 (a) gives $\mathbf{A}^{(k+1)} = \mathbf{W}_k^{-1}e^{\mathbf{L}_0}\mathbf{W}_k = e^{\mathbf{W}_k^{-1}\mathbf{L}_0\mathbf{W}_k} = e^{\mathbf{L}_k} .$ Finally $\mathbf{L}_k^{\top} = \mathbf{W}_k^{\top}\mathbf{L}_0^{\top}\mathbf{W}_k = \mathbf{L}_k$ , and $\mathbf{L}_k$ is similar to $\mathbf{L}_0$ , so the two have the same characteristic polynomial (Theorem 7.10.3) and hence the same eigenvalues. This proves the theorem.

So the QR algorithm, applied to the exponential of a symmetric matrix, is a sequence of orthogonal conjugations of $\mathbf{L}_0$ whose $k$ -th term is read off the QR factorization of $e^{k\mathbf{L}_0}$ . That last description makes sense for every real $t$ , not only for integers, and it is the missing curve.

Remark. The continuous statement, and the one thing in it we do not prove. For $t \in \mathbb{R}$ let $e^{t\mathbf{L}_0} = \mathbf{Q}(t)\mathbf{R}(t)$ be the QR factorization with $\mathbf{R}(t)$ of positive diagonal, and put $\mathbf{L}(t) = \mathbf{Q}(t)^{\top}\mathbf{L}_0\mathbf{Q}(t)$ . By Theorem 24.8.5 (b) and (c), $\mathbf{Q}(k) = \mathbf{W}_k$ and $\mathbf{L}(k) = \mathbf{L}_k$ , so this curve passes through the QR iterates at the integer times. Granting that $t \mapsto \mathbf{Q}(t)$ is differentiable — it is, because the Gram–Schmidt formulas express its entries through arithmetic and square roots of positive quantities, but that is a fact of analysis this book has not set up — the curve satisfies the Lax equation $\mathbf{L}' = [\mathbf{B}(\mathbf{L}), \mathbf{L}]$ . Here is the derivation. Differentiating $e^{t\mathbf{L}_0} = \mathbf{Q}\mathbf{R}$ with Theorem 10.9.4 (b) and Lemma 16.6.4 gives $\mathbf{L}_0\mathbf{Q}\mathbf{R} = \mathbf{Q}'\mathbf{R} + \mathbf{Q}\mathbf{R}'$ ; multiplying by $\mathbf{R}^{-1}$ on the right and $\mathbf{Q}^{\top}$ on the left, $\mathbf{L}(t) = \mathbf{Q}^{\top}\mathbf{L}_0\mathbf{Q} = \mathbf{Q}^{\top}\mathbf{Q}' + \mathbf{R}'\mathbf{R}^{-1} .$ Now $\mathbf{Q}^{\top}\mathbf{Q} = \mathbf{I}$ differentiates to $(\mathbf{Q}')^{\top}\mathbf{Q} + \mathbf{Q}^{\top}\mathbf{Q}' = \mathbf{O}$ , so $\mathbf{Q}^{\top}\mathbf{Q}'$ is skew-symmetric, while $\mathbf{R}'\mathbf{R}^{-1}$ is upper triangular. By Lemma 24.8.4 the splitting is unique, so $\mathbf{Q}^{\top}\mathbf{Q}' = -\mathbf{B}(\mathbf{L}(t))$ . Differentiating $\mathbf{L} = \mathbf{Q}^{\top}\mathbf{L}_0\mathbf{Q}$ , inserting $\mathbf{Q}\mathbf{Q}^{\top} = \mathbf{I}$ in each term, and using $(\mathbf{Q}')^{\top}\mathbf{Q} = -\mathbf{Q}^{\top}\mathbf{Q}'$ , $\mathbf{L}' = (\mathbf{Q}')^{\top}\mathbf{L}_0\mathbf{Q} + \mathbf{Q}^{\top}\mathbf{L}_0\mathbf{Q}' = -(\mathbf{Q}^{\top}\mathbf{Q}')\mathbf{L} + \mathbf{L}(\mathbf{Q}^{\top}\mathbf{Q}') = [\mathbf{B}(\mathbf{L}), \mathbf{L}] .$ That is a Lax equation, and $\mathbf{L}_0$ was only assumed symmetric. It is the Toda flow of Definition 24.8.2 when $\mathbf{L}(t)$ is in addition symmetric tridiagonal, which the definition demands, and it is so whenever $\mathbf{L}_0$ is. Here is why. Since $\mathbf{R}(t)$ is upper triangular and invertible, the span of the first $j$ columns of $\mathbf{Q}(t)$ is the span of the first $j$ columns of $e^{t\mathbf{L}_0}$ , namely $e^{t\mathbf{L}_0}\operatorname{span}(\mathbf{e}_1, \dots, \mathbf{e}_j)$ . A tridiagonal $\mathbf{L}_0$ carries $\operatorname{span}(\mathbf{e}_1, \dots, \mathbf{e}_j)$ into $\operatorname{span}(\mathbf{e}_1, \dots, \mathbf{e}_{j+1})$ , and it commutes with $e^{t\mathbf{L}_0}$ (Theorem 10.9.4 (b)), so it carries the span of the first $j$ columns of $\mathbf{Q}(t)$ into the span of the first $j+1$ . The $i$ -th column of $\mathbf{Q}(t)$ is orthogonal to that span for $i > j+1$ , so the $(i,j)$ entry of $\mathbf{L}(t) = \mathbf{Q}^{\top}\mathbf{L}_0\mathbf{Q}$ vanishes there: nothing below the subdiagonal, and symmetric, hence tridiagonal. For such an $\mathbf{L}_0$ the curve is the Toda flow, Proposition 24.8.3 puts it in the coordinates Eq. 24.8.1, and, modulo that one differentiability, the QR algorithm is the time-one map of the Toda flow. The discrete half of the statement, Theorem 24.8.5, rests on nothing unproved; the continuous half is flagged here and nothing later depends on it.

Warning. The interpolation is of $\mathbf{L}$ , not of $\mathbf{A}$ , and it needs the starting matrix to be an exponential. Theorem 24.8.5 starts from $\mathbf{A}^{(1)} = e^{\mathbf{L}_0}$ , so it says nothing directly about the QR algorithm run on an arbitrary matrix. The matrices it does cover are exactly the symmetric positive definite ones. On the one hand $e^{\mathbf{L}_0} = \mathbf{Q} e^{\mathbf{D}}\mathbf{Q}^{\top}$ is symmetric with positive eigenvalues $e^{\lambda_i}$ , writing $\mathbf{L}_0 = \mathbf{Q}\mathbf{D}\mathbf{Q}^{\top}$ by Corollary 12.5.2 and using Theorem 10.9.4 (a) together with Corollary 10.9.5; on the other, a symmetric $\mathbf{A} \succ \mathbf{O}$ with eigenvalues $\mu_i > 0$ is $e^{\mathbf{L}_0}$ for the symmetric $\mathbf{L}_0 = \mathbf{Q}\operatorname{diag}(\log\mu_1, \dots, \log\mu_n)\mathbf{Q}^{\top}$ , the logarithm being the one built in Chapter 18 §11 (Lemma 18.11.1). A symmetric matrix with a negative eigenvalue is therefore out of reach. The right reading is not “QR is Toda” but “QR on $e^{\mathbf{L}_0}$ is Toda on $\mathbf{L}_0$ ”.

24.8.5. What this buys

Nothing in this section makes a computation faster. What it does is change what the QR algorithm is. As an algorithm it is a rule: factor, multiply back, repeat, and hope the subdiagonal shrinks. As a flow it is a curve in a bounded set — every entry of a symmetric matrix is at most its largest eigenvalue in absolute value, and the spectrum is frozen — and the questions one asks about it change accordingly. Why does the largest eigenvalue surface at the top left? Because $d_1' = 2e_1^2 \ge 0$ at all times. Why do the off-diagonal entries die away geometrically once the diagonal has almost settled? Because $e_i' = e_i(d_{i+1} - d_i)$ , which near a diagonal limit is decay at the rate of the gap $d_i - d_{i+1}$ — the same eigenvalue gap that governs the QR algorithm’s rate in Section 5. Neither reading is a proof, and neither is visible at all in the discrete language.

That is the general lesson, and it is worth naming as one of this chapter’s moves: an algorithm and a differential equation can be the same object at two resolutions, and which resolution to use is a choice. Similar correspondences are known for other iterations, including the shifted QR algorithm; none of them is proved here. The subject they belong to is the theory of integrable systems, and it is the one place where this computational chapter touches pure mathematics.

24.8.6. Exercises

A. Check your understanding

Exercise (A1)

(a) Define a Lax pair, and say which of the two functions is required to be differentiable.
(b) State Theorem 24.8.1, and name the two results from earlier chapters its proof uses.
(c) Determine whether the following statement is correct, and justify your answer: if $\mathbf{L}' = [\mathbf{B}, \mathbf{L}]$ then $\mathbf{L}(t) = \mathbf{L}(0)$ for all $t$ .
(d) Explain in one sentence why the proof of Theorem 24.8.1 does not construct the conjugating matrix $\mathbf{S}(t)$ .
(e) Write down the Toda equations Eq. 24.8.1 for $n = 3$ , and check that the sum of the three diagonal equations is $0$ .

Solution.

(a) A pair $\mathbf{L}, \mathbf{B} \colon I \to M_n(\mathbb{C})$ with $\mathbf{L}$ differentiable and $\mathbf{L}'(t) = \mathbf{B}(t)\mathbf{L}(t) - \mathbf{L}(t)\mathbf{B}(t)$ for all $t \in I$ . Only $\mathbf{L}$ must be differentiable.
(b) The characteristic polynomial of $\mathbf{L}(t)$ is independent of $t$ . The proof uses Jacobi’s formula (Theorem 16.6.6) and the adjugate identity (Theorem 7.6.2), together with $\operatorname{tr}(\mathbf{X}\mathbf{Y}) = \operatorname{tr}(\mathbf{Y}\mathbf{X})$ (Theorem 0.9.6 (3)).
(c) Incorrect. Example (A curve of matrices with a frozen spectrum) has $\mathbf{L}(t) = \begin{psmallmatrix} t & -t^2 \\ 1 & -t\end{psmallmatrix}$ , which is nonconstant while its characteristic polynomial $x^2$ is constant. Isospectral is much weaker than constant.
(d) Because for a $\mathbf{B}$ depending on $t$ that matrix is the solution of a linear differential equation with variable coefficients, whose existence this book does not prove; differentiating the determinant avoids needing it at all.
(e) With $e_0 = e_3 = 0$ : $d_1' = 2e_1^2, \quad d_2' = 2(e_2^2 - e_1^2), \quad d_3' = -2e_2^2,$ $e_1' = e_1(d_2 - d_1), \quad e_2' = e_2(d_3 - d_2).$ The three diagonal right-hand sides sum to $2e_1^2 + 2e_2^2 - 2e_1^2 - 2e_2^2 = 0$ , which is the constancy of the trace.

B. Practice

Exercise (B1: A Lax pair verified)

Let $\mathbf{B} = \begin{pmatrix} 0 & 1 \\ 0 & 0\end{pmatrix}$ and $\mathbf{L}(t) = \begin{pmatrix} t & -t^2 \\ 1 & -t \end{pmatrix}$ .

(a) Verify directly that $\mathbf{L}'(t) = [\mathbf{B}, \mathbf{L}(t)]$ .
(b) Compute $p_{\mathbf{L}(t)}$ and confirm Theorem 24.8.1 in this case.
(c) Determine whether $\mathbf{L}(t)$ and $\mathbf{L}(0)$ are similar for every $t$ , and exhibit the similarity.

Solution.

(a) $\mathbf{L}'(t) = \begin{psmallmatrix} 1 & -2t \\ 0 & -1\end{psmallmatrix}$ . On the other side, $\mathbf{B}\mathbf{L} = \begin{pmatrix} 1 & -t \\ 0 & 0\end{pmatrix}, \qquad \mathbf{L}\mathbf{B} = \begin{pmatrix} 0 & t \\ 0 & 1\end{pmatrix},$ so $[\mathbf{B}, \mathbf{L}] = \begin{psmallmatrix} 1 & -2t \\ 0 & -1\end{psmallmatrix} = \mathbf{L}'(t)$ .
(b) $\operatorname{tr}\mathbf{L}(t) = t - t = 0$ and $\det\mathbf{L}(t) = -t^2 - (-t^2) = 0$ , so $p_{\mathbf{L}(t)}(x) = x^2$ for every $t$ . The spectrum is $\{0\}$ at all times.
(c) Yes. Since $\mathbf{B}$ is constant, Corollary 24.8.2 applies, and $e^{t\mathbf{B}} = \mathbf{I} + t\mathbf{B}$ because $\mathbf{B}^2 = \mathbf{O}$ . So $\mathbf{L}(t) = \begin{pmatrix} 1 & t \\ 0 & 1\end{pmatrix}\mathbf{L}(0)\begin{pmatrix} 1 & -t \\ 0 & 1\end{pmatrix}, \qquad \mathbf{L}(0) = \begin{pmatrix} 0 & 0 \\ 1 & 0\end{pmatrix},$ which one checks by multiplying out. (Similarity is also forced by (b) alone here: both matrices are nonzero and nilpotent of size $2$ , hence both similar to $\mathbf{J}_2(0)$ .)

Exercise (B2: The bracket by hand)

Let $\mathbf{L} = \begin{pmatrix} 1 & 2 & 0 \\ 2 & 3 & 1 \\ 0 & 1 & -1\end{pmatrix}.$ Compute $\mathbf{B}(\mathbf{L})$ and $[\mathbf{B}(\mathbf{L}), \mathbf{L}]$ directly, and check the answer against Proposition 24.8.3.

Solution. Here $d = (1, 3, -1)$ and $e = (2, 1)$ . The strictly upper and lower parts give $\mathbf{B}(\mathbf{L}) = \begin{pmatrix} 0 & 2 & 0 \\ -2 & 0 & 1 \\ 0 & -1 & 0\end{pmatrix}.$ Multiplying, $\mathbf{B}(\mathbf{L})\mathbf{L} = \begin{pmatrix} 4 & 6 & 2 \\ -2 & -3 & -1 \\ -2 & -3 & -1\end{pmatrix}, \qquad \mathbf{L}\mathbf{B}(\mathbf{L}) = \begin{pmatrix} -4 & 2 & 2 \\ -6 & 3 & 3 \\ -2 & 1 & 1\end{pmatrix},$ so $[\mathbf{B}(\mathbf{L}), \mathbf{L}] = \begin{pmatrix} 8 & 4 & 0 \\ 4 & -6 & -4 \\ 0 & -4 & -2\end{pmatrix}.$ Against Proposition 24.8.3: $2(e_1^2 - e_0^2) = 2\cdot4 = 8$ ; $2(e_2^2 - e_1^2) = 2(1 - 4) = -6$ ; $2(e_3^2 - e_2^2) = -2$ ; $e_1(d_2 - d_1) = 2(3-1) = 4$ ; $e_2(d_3 - d_2) = 1(-1-3) = -4$ . All five agree, the matrix is symmetric tridiagonal, and its trace is $8 - 6 - 2 = 0$ , as it must be.

Exercise (B3: One QR step on an exponential)

Let $\mathbf{L}_0 = \begin{psmallmatrix} 0 & 1 \\ 1 & 0\end{psmallmatrix}$ and $\mathbf{A}^{(1)} = e^{\mathbf{L}_0}$ .

(a) Show that $e^{t\mathbf{L}_0} = \begin{psmallmatrix} c(t) & s(t) \\ s(t) & c(t)\end{psmallmatrix}$ with $c(t) = \tfrac12(e^{t} + e^{-t})$ and $s(t) = \tfrac12(e^{t} - e^{-t})$ .
(b) Find the QR factorization of $e^{t\mathbf{L}_0}$ with positive diagonal, and hence $\mathbf{L}(t) = \mathbf{Q}(t)^{\top}\mathbf{L}_0\mathbf{Q}(t)$ .
(c) Compare your $\mathbf{L}(1)$ with Example (The $2 \times 2$ flow, twice) (b).

Solution.

(a) $\mathbf{L}_0^2 = \mathbf{I}$ , so $\mathbf{L}_0^{2m} = \mathbf{I}$ and $\mathbf{L}_0^{2m+1} = \mathbf{L}_0$ . Splitting Definition 10.9.2 into even and odd terms, $e^{t\mathbf{L}_0} = \Bigl(\sum_{m \ge 0}\frac{t^{2m}}{(2m)!}\Bigr)\mathbf{I} + \Bigl(\sum_{m\ge0}\frac{t^{2m+1}}{(2m+1)!}\Bigr)\mathbf{L}_0 ,$ and the two scalar series are the even and odd halves of $e^{t} = \sum_j t^j/j!$ , namely $c(t)$ and $s(t)$ by fact (A1) of Chapter 10 §09.
(b) Write $\rho = (c^2 + s^2)^{1/2} > 0$ . Gram–Schmidt on the columns, as in Theorem 11.8.1: the first column $(c, s)$ normalizes to $\mathbf{q}_1 = \rho^{-1}(c,s)$ ; the second column $(s,c)$ has $\langle (s,c), \mathbf{q}_1 \rangle = 2cs/\rho$ , and $(s,c) - \frac{2cs}{\rho^2}(c,s) = \frac{c^2 - s^2}{\rho^2}(-s, c) = \frac{1}{\rho^2}(-s,c),$ because $c^2 - s^2 = 1$ . That vector has length $1/\rho$ , so $\mathbf{q}_2 = \rho^{-1}(-s, c)$ . Hence $\mathbf{Q}(t) = \rho^{-1}\begin{psmallmatrix} c & -s \\ s & c\end{psmallmatrix}$ , whose determinant is $1$ , and $\mathbf{R}(t) = \mathbf{Q}(t)^{\top} e^{t\mathbf{L}_0}$ has positive diagonal. Then $\mathbf{L}(t) = \mathbf{Q}^{\top}\mathbf{L}_0\mathbf{Q} = \frac{1}{\rho^2}\begin{pmatrix} 2cs & 1 \\ 1 & -2cs\end{pmatrix}.$ Since $\rho^2 = c^2 + s^2 = \tfrac12(e^{2t} + e^{-2t})$ and $2cs = \tfrac12(e^{2t} - e^{-2t})$ , multiplying numerator and denominator by $2e^{2t}$ gives $\mathbf{L}(t) = \begin{pmatrix} \dfrac{e^{4t} - 1}{e^{4t}+1} & \dfrac{2e^{2t}}{e^{4t}+1} \\[6pt] \dfrac{2e^{2t}}{e^{4t}+1} & -\dfrac{e^{4t}-1}{e^{4t}+1}\end{pmatrix}.$
(c) This is exactly the solution written down in Example (The $2 \times 2$ flow, twice) (b). At $t = 1$ it is $d_1 = (e^4-1)/(e^4+1) \approx 0.9640$ and $e_1 = 2e^2/(e^4+1) \approx 0.2658$ . One QR step on $e^{\mathbf{L}_0}$ has moved $\mathbf{L}$ one unit of Toda time, and the off-diagonal entry has already fallen from $1$ to about $0.27$ .

C. Going deeper

Exercise (C1: The power sums are constants of the motion)

Let $(\mathbf{L}, \mathbf{B})$ be a Lax pair on $I$ .

(a) Prove that $t \mapsto \operatorname{tr}\bigl(\mathbf{L}(t)^{m}\bigr)$ is constant for every integer $m \ge 1$ . Hint: the product rule, then Theorem 0.9.6 (3).
(b) Deduce, for $n = 2$ , that the characteristic polynomial of $\mathbf{L}(t)$ is constant, without using Theorem 24.8.1.

Solution.

(a) By Lemma 16.6.4 and induction, $t \mapsto \mathbf{L}(t)^m$ is differentiable with $(\mathbf{L}^m)' = \sum_{j=0}^{m-1}\mathbf{L}^{j}\,\mathbf{L}'\,\mathbf{L}^{m-1-j} .$ The trace is linear (Theorem 0.9.6 (1)) and unchanged by a cyclic shift (Theorem 0.9.6 (3)), so each summand contributes $\operatorname{tr}(\mathbf{L}^{m-1}\mathbf{L}')$ , and $\bigl(\operatorname{tr}\mathbf{L}^m\bigr)' = m\,\operatorname{tr}\bigl(\mathbf{L}^{m-1}\mathbf{L}'\bigr) = m\,\operatorname{tr}\bigl(\mathbf{L}^{m-1}(\mathbf{B}\mathbf{L} - \mathbf{L}\mathbf{B})\bigr).$ Now $\operatorname{tr}(\mathbf{L}^{m-1}\mathbf{B}\mathbf{L}) = \operatorname{tr}(\mathbf{L}\mathbf{L}^{m-1}\mathbf{B}) = \operatorname{tr}(\mathbf{L}^{m}\mathbf{B})$ by a cyclic shift, and $\operatorname{tr}(\mathbf{L}^{m-1}\mathbf{L}\mathbf{B}) = \operatorname{tr}(\mathbf{L}^m\mathbf{B})$ as well, so the bracket contributes $0$ . By fact (A6) of Chapter 16’s introduction the function is constant on $I$ .
(b) For $n = 2$ , $p_{\mathbf{L}(t)}(x) = x^2 - \tau x + \delta$ with $\tau = \operatorname{tr}\mathbf{L}(t)$ and $\delta = \det\mathbf{L}(t)$ . By Cayley–Hamilton (Theorem 9.6.1), $\mathbf{L}^2 - \tau\mathbf{L} + \delta\mathbf{I} = \mathbf{O}$ ; taking traces gives $\operatorname{tr}(\mathbf{L}^2) - \tau^2 + 2\delta = 0$ , that is $\delta = \tfrac12\bigl(\tau^2 - \operatorname{tr}(\mathbf{L}^2)\bigr).$ Part (a) with $m = 1$ makes $\tau$ constant and with $m = 2$ makes $\operatorname{tr}(\mathbf{L}^2)$ constant, so $\delta$ is constant too. Hence $p_{\mathbf{L}(t)}$ is constant.

Exercise (C2: How far

\mathbf{B}

is from being determined)

Let $(\mathbf{L}, \mathbf{B})$ be a Lax pair on $I$ and let $\mathbf{C} \colon I \to M_n(\mathbb{C})$ satisfy $[\mathbf{C}(t), \mathbf{L}(t)] = \mathbf{O}$ for every $t$ .

(a) Prove that $(\mathbf{L}, \mathbf{B} + \mathbf{C})$ is also a Lax pair.
(b) Give an example with $\mathbf{C} \ne \mathbf{O}$ , and conclude that a Lax equation does not determine $\mathbf{B}$ .
(c) Prove, using Lemma 24.8.4, that there is nevertheless exactly one skew-symmetric $\mathbf{B}$ for which $\mathbf{B} +$ (upper triangular) equals a given symmetric $\mathbf{L}$ — that is, the $\mathbf{B}(\mathbf{L})$ of Definition 24.8.2 is the only natural candidate once “skew-symmetric” and “upper triangular” are the two slots.

Solution.

(a) $[\mathbf{B} + \mathbf{C}, \mathbf{L}] = [\mathbf{B}, \mathbf{L}] + [\mathbf{C}, \mathbf{L}] = [\mathbf{B}, \mathbf{L}] + \mathbf{O} = \mathbf{L}'$ .
(b) Take $\mathbf{C}(t) = c\,\mathbf{I}$ for any scalar $c \ne 0$ , or $\mathbf{C}(t) = q(\mathbf{L}(t))$ for any polynomial $q$ , since a polynomial in $\mathbf{L}$ commutes with $\mathbf{L}$ . So $\mathbf{B}$ can always be altered by a multiple of $\mathbf{I}$ without changing the flow, and the Lax equation determines $\mathbf{B}$ at most up to the commutant of $\mathbf{L}$ .
(c) Lemma 24.8.4 says $\mathbf{L} = \mathbf{K} + \mathbf{U}$ for exactly one skew-symmetric $\mathbf{K}$ and one upper triangular $\mathbf{U}$ , and computes $\mathbf{K} = \mathbf{L}_{-} - \mathbf{L}_{+} = -\mathbf{B}(\mathbf{L})$ for symmetric $\mathbf{L}$ . So the pair of slots (skew, upper triangular) picks out $\mathbf{B}(\mathbf{L})$ uniquely, up to the sign convention, and the remaining freedom found in (a) and (b) is freedom in a different decomposition, not in this one.

Exercise (C3: Symmetry constrains

\mathbf{B}

)

Let $(\mathbf{L}, \mathbf{B})$ be a Lax pair of real matrices on $I$ with $\mathbf{L}(t)$ symmetric for every $t$ .

(a) Prove that $[\mathbf{B}(t) + \mathbf{B}(t)^{\top},\ \mathbf{L}(t)] = \mathbf{O}$ for every $t$ .
(b) Deduce that $\bigl(\mathbf{L}, \tfrac12(\mathbf{B} - \mathbf{B}^{\top})\bigr)$ is also a Lax pair, so that $\mathbf{B}$ may always be taken skew-symmetric.
(c) Determine whether the Toda $\mathbf{B}(\mathbf{L})$ of Definition 24.8.2 satisfies the hypothesis of (a). Justify your answer.

Solution.

(a) Transposing $\mathbf{L}' = \mathbf{B}\mathbf{L} - \mathbf{L}\mathbf{B}$ and using $\mathbf{L}^{\top} = \mathbf{L}$ — so that $(\mathbf{L}')^{\top} = (\mathbf{L}^{\top})' = \mathbf{L}'$ , differentiation being entrywise — gives $\mathbf{L}' = (\mathbf{L}')^{\top} = \mathbf{L}^{\top}\mathbf{B}^{\top} - \mathbf{B}^{\top}\mathbf{L}^{\top} = \mathbf{L}\mathbf{B}^{\top} - \mathbf{B}^{\top}\mathbf{L} = -[\mathbf{B}^{\top}, \mathbf{L}].$ Adding this to $\mathbf{L}' = [\mathbf{B}, \mathbf{L}]$ gives $2\mathbf{L}' = [\mathbf{B}, \mathbf{L}] - [\mathbf{B}^{\top}, \mathbf{L}]$ , while subtracting gives $\mathbf{O} = [\mathbf{B}, \mathbf{L}] + [\mathbf{B}^{\top}, \mathbf{L}] = [\mathbf{B} + \mathbf{B}^{\top}, \mathbf{L}]$ .
(b) Put $\mathbf{C} = -\tfrac12(\mathbf{B} + \mathbf{B}^{\top})$ . By (a), $[\mathbf{B} + \mathbf{B}^{\top}, \mathbf{L}] = \mathbf{O}$ , so $[\mathbf{C}, \mathbf{L}] = \mathbf{O}$ , and Exercise (C2: How far $\mathbf{B}$ is from being determined) (a) says $(\mathbf{L}, \mathbf{B} + \mathbf{C})$ is a Lax pair. But $\mathbf{B} + \mathbf{C} = \mathbf{B} - \tfrac12(\mathbf{B} + \mathbf{B}^{\top}) = \tfrac12(\mathbf{B} - \mathbf{B}^{\top})$ , which is skew-symmetric. So the skew part of $\mathbf{B}$ already drives the flow, and the symmetric part is inert.
(c) Yes, and trivially: $\mathbf{B}(\mathbf{L})$ is skew-symmetric for symmetric $\mathbf{L}$ , so $\mathbf{B}(\mathbf{L}) + \mathbf{B}(\mathbf{L})^{\top} = \mathbf{O}$ , which commutes with everything. Part (b) says that this is not a lucky feature of the Toda choice but the normal form of any Lax pair with symmetric $\mathbf{L}$ .