Why are eigenvalues in descending order when using QR Algorithm

42 Views Asked by At

I have been experimenting with the QR algorithm for eigenvalue computation and have come across a curious phenomenon. The resulting matrix seems to sort the eigenvalues in descending order from the top-left to the bottom-right corner in its diagonal. I'm curious about the underlying mathematical principles that contribute to this outcome.

Below is the Python code snippet used for the QR iterations:

def algo(A, iters, epsilon):
    Ak = A.copy()
    m = A.shape[0]

    for i in range(iters):
        Q, R = qr(Ak)
        Ak = R @ Q
        if np.abs(Ak[m-1, m-2]) < epsilon:
            Ak[m-1, m-2] = 0
            break

    return Ak

And the input matrix being:

\begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}

Hence, why does the QR algorithm output eigenvalues in descending order on the diagonal? I would appreciate any insights.