Circulant decomposition of a matrix and the eigenvalues of Toeplitz type matrices

We begin by showing that a n*n matrix can be decomposed into a sum of 'n' circulant matrices with appropriate relaxations. We use Fast-Fourier-Transform (FFT) operations to perform a sparse similarity transformation representing only the dominant circulant components, to evaluate all eigenvalues of dense Toeplitz, block-Toeplitz and other periodic or quasi-periodic matrices, to a reasonable approximation in O(n^2) arithmetic operations. This sparse similarity transformation can be exploited for other evaluations as well.