Let $H$ be an $n\times n$ Hermitian matrix. The Jacobi method is an iterative method for finding the spectrum of $H$. It is described in every book on numerical linear algebra.
Principle: At step $k$, the matrix has become $H^k$. You choose a pair $(i,j)$ with $1\le i,j\le n$ and $i\ne j $. Then you conjugate $H^k$ by a rotation in the plane of coordinates $(x_i,x_j)$, in such a way that the new matrix $H^{k+1}$ has a zero entry in position $(i,j)$. Of course, after several other steps, this entry will be again nonzero.
Let us recall that the Frobenius norm is $\|M\|:=\sqrt{\sum_{i,j}|m_{ij}|^2}$. The norm $e_k$ of the off-diagonal part of $H^k$ is called the error. It is non-increasing. This question is about the order at which $e_k\rightarrow0$.
There are at least three strategies for the choice of $(i,j)$ at each step, and I shall concentrate on the optimal one, in which we choose the entry that has the largest modulus among the off-diagonal ones. Every book presents and proves the first-order convergence, thanks to the inequality $$e_{k+1}\le\rho e_k, \qquad \rho:=\sqrt{1-\frac{2}{n(n-1)}}.$$ When the eigenvalues of $H$ are simple, advanced books (see [1,2]) give also a quadratic convergence result. However, it is not really quadratic, because it is based upon an inequality of the form $$e_{k+N}\le c\cdot e_k^2,\qquad N:=\frac{n(n-1)}{2}$$ where it requires $N$ step to square the error. We should better call this a result of convergence of order $2^{1/N}$.
Question. Of course the result mentionned above gives only an upper bound of the order of the method. If $n=3$, I can prove that the exact order is the root $\omega>1$ of the polynomial $X^3-X-1$. What is the exact order for larger sizes ? Even an upper bound of the order, better than $2^{1/N}$, is welcome.
[1] J. H. Wilkinson. The algebraic eigenvalue problem. Oxford University Press, 1965.
[2] D. Serre. Matrices; Theory and applications. GTM 216, Springer-Verlag, 2000.
