Problem: My code-based implementation of the implicit QR algorithm fails to converge for certain special cases, and it's because those cases have bad shift values.
What are those special cases: While I don't know every single special case where my implementation fails to converge, I do know for a fact that every companion matrix to a polynomial of the form x$^n$+1 (for any integer n>2) fails to converge when asked to find its eigenvalues using the implicit QR algorithm. More specifically, any nxn matrix (n>2) of the form:
$$ \begin{bmatrix}0&0&0&0&...&0&1\\1&0&0&0&...&0&0\\0&1&0&0&...&0&0\\0&0&1&0&...&0&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&0&0&...&0&0\\0&0&0&0&...&1&0\end{bmatrix} $$
This is also the same as taking an nxn identity matrix, and moving the bottom row to the top. I am aware that the correct answer to this is just the set of nth roots of -1, but I worry that there are other special cases that I'm not aware of for which the same problem happens.
Why does this problem occur: As was said before, it's because it uses a bad shift. Each iteration, the program computes the shift by taking the bottom 2x2 submatrix and finding its eigenvalues. Its shift is then one of those 2 eigenvalues. In this case, the bottom right 2x2 submatrix will always be of the form:
$$ \begin{bmatrix}0&0\\1&0\end{bmatrix} $$
which has the double-root eigenvalues of 0 and 0. So nothing gets shifted. The matrix is then QR decomposed, resulting in a Q = original matrix and R = identity matrix (but also, some of the 1s in both matrices have changed to -1). After that, we compute RQ, which is basically just the original matrix, but with some of the 1s changed to -1s. The shift is again computed, which is again 0, and then the matrix is decomposed into Q and R (which are once again permutations of the original matrix and the identity), then re-composed into RQ (which is once again a permutation of the original matrix). This process repeats ad infinitum, never getting any closer to having its subdiagonal bulges removed.
However, whenever I perform this same process, but with the initial shift (only the initial shift) changed to literally anything other than 0 (even to a very small number), it converges. Hence, it's not a bad matrix (if such a thing even exists), but just has a bad shift.
What I'd like help with If there's some other, better shift that can be used which doesn't result in situations like this, then that'd be amazing. I'm aware of the Wilkinson shift, but am given to understand that only works for symmetric matrices (also, when I try it here, I get a shift of $\frac{1}0$). Alternatively, if there's some way of detecting rare situations like these, as well as a way of generating a better shift when said situations arise, that would also be good.
Really, though, just any insight into the nature of this predicament would be helpful. I only discovered this error yesterday, and I have no idea how to rectify it.
Any help would be greatly appreciated. Thank you!