Computing eigenvalues of normal matrices via complex symmetric matrices

We will show, under modest constraints, that normal matrices also admit a memory cheap intermediate matrix of tridiagonal complex symmetric form. Moreover, we will propose a general approach for computing the eigenvalues of a normal matrix, exploiting thereby the normal complex symmetric structure. An analysis of the computational cost and numerical experiments with respect to the accuracy of the approach are enclosed. In the second part of the manuscript we will investigate the case of nonsimple singular values and propose a theoretical framework for retrieving the eigenvalues. We will, however, also highlight some numerical difficulties inherent to this approach.