Singular Matrix Pencils and the QZ Algorithm
This year, 2023, is the 50-th anniversary of the QZ algorithm for generalized matrix eignenvalue problems,
Ax = λBx
The 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
If A and B are two square matrices, the linear matrix pencil is the matrix-valued function
A - λB
A 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 1
B =
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, QBZ
eig1 =
-0.4071
1.0000
0.2439
eig2 =
-2.0000
1.0000
0.3536
QAZ =
-1.0298 -13.0363 7.7455
0 5.6991 -4.6389
0 0 0.0000
QBZ =
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, QBTZ
eig3 =
-0.2169
Inf
1.0000
eig4 =
-0.0738
0
1.0000
QATZ =
-0.0000 -15.0218 6.8390
0 2.6729 -2.2533
0 0 0.5922
QBTZ =
0.0000 -15.2578 7.1280
0 0 1.0203
0 0 0.5922
Wilkinson 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 6
B =
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, QBZ
eig1 =
1.2056
0.7055
-1.0000
-Inf
eig2 =
1.5097
0.6408
0
-1.0000
QAZ =
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.2887
QBZ =
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, QBTZ
eig3 =
-0.2141 + 0.2033i
-0.2141 - 0.2033i
0.7013 + 0.0000i
1.4508 + 0.0000i
eig4 =
0.3168
0.9823
1.2325
0
QATZ =
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.0000i
QBTZ =
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.0000i
References
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
Comments
To leave a comment, please click here to sign in to your MathWorks Account or create a new one.