ON O(n sup 2) Eigenvalue Update of Symmetric Toeplitz Matrices.

In this paper, a technique for computing the eigenvalues of an (n+1) -by-(n+1) symmetric positive definite Toeplitz matrix from the eigenvalues and the eigenvectors of its n-by-n principal Toeplitz minor in O(n sup 2) computations, is presented. Complexity issues are studied, and two practical O(n sup 2) algorithms are developed. Explicit upper bound formulae for these two algorithms are given. It is not known yet by the authors whether it is possible to also update all the eigenvectors in O(n sup 2) computations.