MONOTONICITY PROPERTIES OF THE TODA FLOW, THE QR-FLOW, AND SUBSPACE ITERATION

Let X(t) denote the Toda flow on the space of n x n matrices, with X(0) a symmetric matrix, and let X(r)(t) denote the r x r upper left corner principal submatrix of X(t), i.e., X(r)(t) = E(r)(T)X(t)E(r) where E(r) = [0r(I)]. Then the r ordered eigenvalues lambda-1(X(r)(t)) greater-than-or-equal-to lambda-2(X(r)(t)) greater-than-or-equal-to ... greater-than-or-equal-to lambda-r(X(r)(t)) of X(r)(t) are each a nondecreasing function of t, for 1 less-than-or-equal-to r less-than-or-equal-to n. A similar result is proved for the QR-flow Y(t) = exp (X(t)), for the eigenvalues of Y(r)(t) = E(r)(T)Y(t)E(r). For any generalized Toda flow f(X(t)) with f(.) a nondecreasing function, it is shown that Tr(E(r)(T)f(X(t))E(r)) is a nondecreasing function of t. The QR-flow inequalities are used to show that the Ritz values of a symmetric matrix X on a subspace are nondecreasing under subspace iteration.