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

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 1992 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.