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

|
  • print

Comments

To leave a comment, please click here to sign in to your MathWorks Account or create a new one.