2 P. DEIFT, L. C. LI, AND C. TOMEI

M = QR- M' = RQ , (1.5)

which is isospectral, as M' = Q~l MQ. In the case of (1.4), M is now a particular quadratic

matrix polynomial

M = M(X) = EQ + XE1 + X2E2 , (1.6)

where the coefficients E{, i = 0,1,2, depend on X and Y in an explicit way (see below).

and the role of the QR factorization is played by a particular, unique factorization of M

into first order matrix polynomials

M(X) = (B0 + JBiA)(C0 + CiA) . (1.7)

Exchanging the factors,

M'(X) = (Co + d X)(B0 + BXX) (1.8)

implements the mapping ^ associated with (1.4). There are, in addition, further conse-

quences:

(i) The isospectral nature of the map M(X) -• M'(X) implies the 'integrability' of ^ , and

(ii) ^ linearizes on the Jacobi variety of the associated curve {(A, 77) £ W2 : det(M(A) —

7?)

=

0} .

Over the last decade, following the seminal work of Symes ([Syl], [Sy2]), the QR

algorithm, and related algorithms such as the LU algorithm and the Cholesky algorithm,

have come to be understood (see, for example, [Chu], [Wa], [DLNT], [DLT]) as time-one

maps of completely integrable Hamiltonian systems closely related with the Toda flow and

its generalizations. The underlying symplectic structures are Lie-Poisson structures on the

coadjoint orbits of particular Lie-algebras, which in turn are double Lie-algebras carrying

classical R-matices satisfying the (modified) Yang-Baxter equation. Recall that j?-matrix

theory (see, for example, [STS], [FT]; see also [DL] for a more pedestrian account) gives

a natural explanation of the existence of many commuting integrals, and also leads in