Singular Matrix Pencils and the QZ Algorithm - Cleve Moler on Mathematics and Computing

[poster]

This year, 2023, is the 50-th anniversary of the QZ algorithm for generalized matrix eignenvalue problems,

Ax = λBxThe algorithm computes these eigevalues without inverting either A or B. And, the QZ-algorithm can help detect and analyze exceptional situaions known as singular pencils.

Contents

• Matrix pencils
• Example
• Wilkinson example
• References

Matrix pencils

If A and B are two square matrices, the linear matrix pencil is the matrix-valued function

A - λBA pencil is regular if there is at least one value of λ for which A - λB if not singular. The pencil is singular if both A and B are singular and, moreover, A - λB is singular for all λ. In other words,

det(A - λB) = 0 for all λ.Singular pencils are more insiduous than migt appear at first glance.

Example

A = [9 8 7; 6 5 4; 3 2 1] B = [7 9 8; 4 6 5; 1 3 2]A = 9 8 7 6 5 4 3 2 1B = 7 9 8 4 6 5 1 3 2 syms s AB = A - s*B d = det(AB) AB = [9 - 7*s, 8 - 9*s, 7 - 8*s][6 - 4*s, 5 - 6*s, 4 - 5*s][ 3 - s, 2 - 3*s, 1 - 2*s] d = 0 eig1 = eig(A,B) eig2 = 1./eig(B,A) [QAZ,QBZ,Q,Z,V,W] = qz(A,B); QAZ, QBZeig1 = -0.4071 1.0000 0.2439eig2 = -2.0000 1.0000 0.3536QAZ = -1.0298 -13.0363 7.7455 0 5.6991 -4.6389 0 0 0.0000QBZ = 2.4396 -11.4948 9.6394 0 5.6991 -4.6389 0 0 0.0000 eig3 = eig(A',B') eig4 = 1./eig(B',A') [QATZ,QBTZ,Q,Z,V,W] = qz(A',B'); QATZ, QBTZeig3 = -0.2169 Inf 1.0000eig4 = -0.0738 0 1.0000QATZ = -0.0000 -15.0218 6.8390 0 2.6729 -2.2533 0 0 0.5922QBTZ = 0.0000 -15.2578 7.1280 0 0 1.0203 0 0 0.5922Wilkinson example

clear A = [4 3 2 5; 6 4 2 7; -1 -1 -2 -2; 5 3 2 6] B = [2 1 3 4; 3 3 3 5; 0 0 -3 -2; 3 1 3 5]A = 4 3 2 5 6 4 2 7 -1 -1 -2 -2 5 3 2 6B = 2 1 3 4 3 3 3 5 0 0 -3 -2 3 1 3 5 syms s AB = A - s*B d = det(AB) AB = [4 - 2*s, 3 - s, 2 - 3*s, 5 - 4*s][6 - 3*s, 4 - 3*s, 2 - 3*s, 7 - 5*s][ -1, -1, 3*s - 2, 2*s - 2][5 - 3*s, 3 - s, 2 - 3*s, 6 - 5*s] d = 0 eig1 = eig(A,B) eig2 = 1./eig(B,A) [QAZ,QBZ,Q,Z,V,W] = qz(A,B); QAZ, QBZeig1 = 1.2056 0.7055 -1.0000 -Infeig2 = 1.5097 0.6408 0 -1.0000QAZ = 0.7437 4.1769 -12.7279 -5.5000 0 0.0000 5.2328 2.1602 0 0 0.7857 0.0123 0 0 0 -0.2887QBZ = 0.5005 6.6143 -8.4853 -2.5000 0 0.0000 3.2668 2.0105 0 0 1.1525 -0.7904 0 0 0 0.2887 eig3 = eig(A',B') eig4 = 1./eig(B',A') [QATZ,QBTZ,Q,Z,V,W] = qz(A',B'); QATZ, QBTZeig3 = -0.2141 + 0.2033i -0.2141 - 0.2033i 0.7013 + 0.0000i 1.4508 + 0.0000ieig4 = 0.3168 0.9823 1.2325 0QATZ = 0.1281 - 0.2434i 0.2665 + 0.0169i 0.2663 + 1.4905i 0.3721 + 3.5350i 0.0000 + 0.0000i 0.0587 + 0.1116i 5.2603 - 1.6197i 12.7878 - 4.0110i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 4.1745 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.7572 + 0.0000iQBTZ = 0.9052 + 0.0000i 0.6130 - 0.6141i -0.2443 + 0.8738i 1.2233 + 2.5485i 0.0000 + 0.0000i 0.4150 + 0.0000i 3.5658 - 1.2114i 8.0696 - 2.2671i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 6.6127 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.0000 + 0.0000i 0.5220 + 0.0000iReferences

C. B. Moler and G. W. Stewart, "An Algorithm for Generalized Matrix Eigenvalue Problems", SIAM J.NUMER.ANAL. Vol.10, No.2, April 1973. Also available at cbm_gws.pdf

J. H. Wilkinson, Kronecker's Canonical Form and the QZ Algorithm", LINEAR ALGEBRA AND ITS APPPLICATIONS, Vol. 28, 1979. Also available at Also available at wilkinson.pdf

Get the MATLAB code (requires JavaScript)

Published with MATLAB® R2023a