# QR algorithm for "general" square matrices

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 ?

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.

## 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}

• Any real matrix has full QR decomposition. And any full rank matrix A has QR decompostion. The question is not about QR decomposition, but about QR algorithms, which is a bit different thing. May 15, 2017 at 22:31
• Reference about algortithm - cstl-csm.semo.edu/jwojdylo/MA345/Chapter6/qrmethod/qrmethod.pdf, www-old.math.gatech.edu/academic/courses/core/math2601/… ,p. 12 May 15, 2017 at 22:40
• @bruziuz: 1) Those are nice references for algorithms. 2) My hope was to provide a demonstration that the basic method works in each of the cases. "Yes, it works and here is the proof." Your point is well taken, and highlights a clarity deficit on my part. May 16, 2017 at 0:07