LAPACK non-convergent eigenvalue algorithm for complex but not double matrix

Question

I've encountered an odd issue with solving for the eigenvalues of the following matrix, in Matlab format:

[ 0 1 0 1 0 0 0 0 0 0 0 0 1 1;
  1 0 0 0 0 0 0 0 0 0 0 0 0 0;
  0 1 0 1 0 0 0 0 0 0 0 0 0 0;
  0 0 1 0 0 0 0 0 0 0 0 0 0 0;
  0 0 0 0 0 1 0 0 0 0 0 0 0 0;
  0 0 0 0 1 0 0 0 0 0 0 0 0 0;
  0 0 0 0 0 0 0 1 0 0 0 0 0 0;
  0 0 0 0 0 0 1 0 0 0 0 0 0 0;
  0 0 0 0 0 0 0 0 0 1 0 0 0 0;
  0 0 0 0 0 0 0 0 1 0 0 1 0 0;
  0 0 0 0 0 0 0 0 1 0 0 1 0 0;
  0 0 0 0 0 0 0 0 0 0 1 0 0 0;
  0 1 0 0 0 0 0 0 0 0 0 0 1 1;
  0 1 0 0 0 0 0 0 0 0 0 0 1 1 ]

When stored as a matrix of doubles, calling dgeev on this matrix correctly finds the eigenvalues.

However, when stored as a matrix of complex doubles (with all the imaginary components set to $0$), calling zgeev on it returns an error value of $13$, indicating that the QR algorithm failed to converge.

Strangely, multiplying this matrix by $i$ (so that the real components are $0$ instead) results in the correct eigenvalues being found again.

What is causing the QR algorithm not to converge in the first complex case, and is there a way to get around it?

Answer 1

Your matrix is not diagonalizable, in the Jordan decomposition of it there is a block for the eigenvalue $0$ of the form $$\begin{pmatrix}0&0&0\\0&0&1\\0&0&0\end{pmatrix},$$ meaning a triple zero eigenvalue with only two eigenvectors. If you compute the matrix of eigenvectors numerically it has condition number $\kappa(X)\sim 10^{16}$ (the actual value is $\kappa(X)=\infty$), which immediately tells you something is wrong because $\kappa(X)$ determines the sensitivity of eigenvalues to perturbations in the original matrix.

The Lapack algorithms probably assume the matrix is diagonalizable, in which case it is sensible for them to give an error. Whether it gives an error or not probably depends on effects of roundoff errors and doesn't have much to do with multiplying by $i$, I wouldn't read much into that.