The eigenvalue decomposition of normal matrices by the decomposition of the skew-symmetric part with applications to orthogonal matrices

We propose a fast method for computing the eigenvalue decomposition of a dense real normal matrix $A$. The method leverages algorithms that are known to be efficiently implemented, such as the bidiagonal singular value decomposition and the symmetric eigenvalue decomposition. For symmetric and skew-symmetric matrices, the method reduces to calling the latter, so that its advantages are for orthogonal matrices mostly and, potentially, any other normal matrix. The method relies on the real Schur decomposition of the skew-symmetric part of $A$. To obtain the eigenvalue decomposition of the normal matrix $A$, additional steps depending on the distribution of the eigenvalues are required. We provide a complexity analysis of the method and compare its numerical performance with existing algorithms. In most cases, the method is as fast as obtaining the Hessenberg factorization of a dense matrix. Finally, we evaluate the method's accuracy and provide experiments for the application of a Karcher mean on the special orthogonal group.