Handbook of Linear Algebra, 2nd Edition

Chapter 55

Symmetric Matrix Eigenvalue Techniques

Ivan Slapničar

University of Split

The eigenvalue decomposition (EVD) is an infinite iterative procedure — finding eigenvalues is equivalent to finding zeros of the characteristic polynomial, and, by the results of Abel and Galois, there is no algebraic formula for roots of the polynomial of degree greater than four. However, the number of arithmetic operations required to compute EVD to some prescribed accuracy is also finite — EVD of a general symmetric matrix requires O(n3) operations, while for matrices with special structure this number can be smaller. For example, the EVD of a tridiagonal matrix can be computed in O(n2) operations (see Sections 55.5 and 55.6).

Basic methods for the symmetric ...