QR algorithm for "general" square matrices

Question

1. Can QR algorithm find repeat eigenvalues (https://en.wikipedia.org/wiki/QR_algorithm) ? I.e. does it support the case when not all N eigenvalues for real matrix N x N are distinct?

2. How to extend QR algorithm to support finding complex eigenvalues ?

3. Is it possible to extend QR algorithm to work with not full rank matrices ?

Answer 1

In practice, the Francis QR algorithm finds the eigenvalues of "any" matrix fairly efficiently, as you can confirm with MATLAB's eig() command. To achieve such robustness, many tricks are needed. The basic tricks are described in Matrix Computations by Golub and van Loan, in Section 7.5, where the authors write:

This algorithm requires $25n^3$ flops... These flops counts are very approximate and are based on the empirical observation that on average only two Francis iterations are required before the lower 1-by-1 or 2-by-2 decouples.

Briefly speaking, what makes the Francis QR iteration work for nonsymmetric matrices, is to use use "double shifts", i.e. to shift by both eigenvalues of the lower-right 2x2 block. More recently (Kressner's "aggressive early deflation"), one uses multiple shifts from the lower-right 5x5 or 20x20 block.

Golub and van Loan mention "empirical observations" because they were not able to prove theoretically that the Francis iterations must always converge in two steps, and indeed counterexamples are known. On the abstract theory of convergence, Watkins and Elsner write that

Unfortunately no one has ever been able to devise a practical shifting strategy that is guaranteed to converge for all matrices and can be shown to converge rapidly.

When an eigenvalue with multiplicity is present, an additional difficulty is that it is numerically challenging to locate that eigenvalue accurately, because of eigenvalue perturbation theory. In this context, the Francis QR iteration is necessarily limited by the machine accuracy, but it often succeeds at locating the eigenvalue, up to this intrinsic limit on accuracy.

You ask about extending the Francis QR iteration to rank-deficient matrices, but it's not clear to me what you are looking for. For arbitrary matrices, including low-rank matrices, there are approximate schemes such as the Arnoldi iteration, to help locate a small or moderate number of eigenvalues.

Answer 2

Summary

The QR Decomposition resolves all of your matrix types.

---

a) Repeated eigenvalues

The three eigenvalues of $\mathbf{A}$ are $$ \lambda \left( \mathbf{A} \right) = \left\{ 1, 1, 1 \right\} $$ The decomposition is $$ \begin{align} \mathbf{A} &= \mathbf{Q\,R} \\ % A \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{array} \right] &= % Q \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right] % R \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{array} \right] % \end{align} $$

---

b) Complex eigenvalues

The three eigenvalues of $\mathbf{A}$ are $$ \lambda \left( \mathbf{A} \right) = \left\{ 1 + 2 i, 1 - 2 i \right\} $$ The decomposition is $$ \begin{align} \mathbf{A} &= \mathbf{Q\,R} \\ % A \left[ \begin{array}{cr} 3 & -2 \\ 4 & -1 \\ \end{array} \right] &= % Q \frac{1}{5} \left[ \begin{array}{rc} 3 & 4 \\ -4 & 3 \\ \end{array} \right] % R \left[ \begin{array}{cr} 5 & -2 \\ 0 & 1 \\ \end{array} \right] % \end{align} $$

---

c) Matrices with rank defect

The following matrix has rank $\rho = 1$, therefore the matrix has both a row and a column rank defect.

The decomposition is $$ \begin{align} \mathbf{A} &= \mathbf{Q\,R} \\ % A \left[ \begin{array}{rrr} 1 & -1 & 1 \\ -1 & 1 & -1 \\ \end{array} \right] &= % Q \frac{1}{\sqrt{2}} \left[ \begin{array}{r} 1 \\ -1 \\ \end{array} \right] % R \left[ \begin{array}{crc} \sqrt{2} & -\sqrt{2} & \sqrt{2} \\ \end{array} \right] % \end{align} $$