Circulant decomposition of a matrix and the eigenvalues of Toeplitz type matrices
M. Hariprasad, Murugesan Venkatapathi Β· Applied Mathematics and Computation Β· 2023
We begin by showing that any π Γ π matrix can be decomposed into a sum of n circulant matrices with periodic relaxations on the unit circle. This decomposition is orthogonal with respect to a Frobenius inner product, allowing recursive iterations for these circulant components. It is also shown that the dominance of a few circulant components in the matrix allows sparse similarity transformations using Fast-Fourier-transform (FFT) operations. This enables the evaluation of all eigenvalues of dense Toeplitz, block-Toeplitz, and other periodic or quasi-periodic matrices, to a reasonable approximation in πͺ β‘ ( π 2 ) arithmetic operations. The utility of the approximate similarity transformation in preconditioning linear solvers is also demonstrated.