Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [eigenvalues]

Eigenvalues are a special set of scalars associated with a linear system of equations (i.e., a matrix equation) that are sometimes also known as characteristic roots, characteristic values (Hoffman and Kunze 1971), proper values, or latent roots (Marcus and Minc 1988, p. 144).


Can all eigenvalues of a Hermitian Toeplitz matrix be computed in $\tilde{O}(n)$ time?

I know there are "superfast" $O(n \log^p n)$ algorithms for solving Toeplitz linear systems. Is it possible to compute all eigenvalues of such a matrix with the same complexity?