# 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

Published with MATLAB® R2023a

|