# Eigenvalues of unitary matrices

I have a sparse unitary matrix with complex entries and want to compute all its eigenvalues. Unfortunately, matlab doesn't like this. If I try do enter eigs(A, N) (A the matrix, N its size), it tells me that I should use eig(full(A)) instead. This is awfully slow ... comparred to the computation for self-adjoint sparse matrices.

Is there any way to do this quicker?

-
You said "sparse", but is there any particular pattern in the sparsity? – J. M. Sep 10 '11 at 23:41
It's a CMV matrix. See Section 4.2. of Barry's OPUC book available at math.caltech.edu/opuc/sampleopuc.html ... (set |alpha_N| = 1 to get an N times N matrix). – Helge Sep 11 '11 at 10:48

An unitary matrix $A$ is normal, i.e. $A^HA=AA^H$. Let's define $\operatorname{Re}(A):=(A+A^H)/2$ and $\operatorname{Im}(A):=(A-A^H)/(2i)$. Note that $\operatorname{Re}(A)$ and $\operatorname{Im}(A)$ are self adjoint (sparse) matrices, and satisfy $\operatorname{Re}(A)\operatorname{Im}(A)=\operatorname{Im}(A)\operatorname{Re}(A)$, i.e. they commute.
'you have to look at the mutual eigenspaces' Perhaps it's more simple (and efficient) to compute just the real part and, knowing that $|\lambda|=1$, try out the two possible imaginary parts. – leonbloy Sep 11 '11 at 0:09
@leonbloy Maybe it can be done simpler for unitary matrices, like you describe. I'm not really how to "try out" the imaginary parts, especially when $\operatorname{Re}(A)$ has duplicate eigenvalues. I also tried to explain why matlab and most libraries for computing eigenvalues don't provide special routines for normal matrices. – Thomas Klimpel Sep 11 '11 at 9:15
If $A$ has $m$-nonzero entries, $A+A^H$ will have at most $2m$-nonzero entries. So if the computation is fast for upper Hessenberg matrices, I guess it's because these matrices are quite sparse Hessenberg matrices, and this sparsity will be preserved as far as possible. I don't fully understand your comment with the 20 lines. Just write a subroutine to compute the eigendecomposition of normal/unitary $A$. Writing eigs((A+A')/2,N) is probably not the difficult part, so I guess your complaint is about the matching part, which I haven't described in detail. Is this missing detail the real issue? – Thomas Klimpel Sep 11 '11 at 16:13