# A new algorithm for computing the inverse and the determinant of a Hessenberg matrix

## A new algorithm for computing the inverse and the determinant of a Hessenberg matrix

Applied Mathematics and Computation 218 (2011) 4433–4436 Contents lists available at SciVerse ScienceDirect Applied Mathematics and Computation jour...

Applied Mathematics and Computation 218 (2011) 4433–4436

Contents lists available at SciVerse ScienceDirect

Applied Mathematics and Computation journal homepage: www.elsevier.com/locate/amc

A new algorithm for computing the inverse and the determinant of a Hessenberg matrix q Yue-Hui Chen ⇑, Cheng-Yi Yu Department of Mathematics and Information Science, Zhangzhou Normal University, Zhangzhou, Fujian 363000, China

a r t i c l e

i n f o

a b s t r a c t In this paper, a new recursive symbolic computational Hessenberg matrix algorithm is presented to compute the inverse and the determinant of a Hessenberg matrix. Ó 2011 Elsevier Inc. All rights reserved.

Keywords: Hessenberg matrix Inverse Determinant

1. Introduction Hessenberg matrix is one of the important matrices in numerical analysis [1,2]. For example, the Hessenberg decomposition played an important role in the matrix eigenvalues computation . In this article, we present a new recursive algorithm for computing the inverse and the determinant of an n-by-n lower Hessenberg matrix. It extends the work presented in .

2. Notations and preliminaries We consider the n-by-n lower Hessenberg matrix of the form

0

h11

B B B h21 B B B . H ¼ B .. B B B B hn1;1 @ hn;1

1

h12 h22

h23

.. .

..

hn1;2



hn1;n1

hn;2



hn;n1

.

..

.

C C C C C C C: C C C hn1;n C A hn;n

Assume that H is nonsingular. Without loss of generality, suppose that all elements of the super diagonal are non-zero, i.e., hi,i+1 – 0, i = 1, 2, . . . , n  1. If hi,i+1 = 0, H can be solved by partitioning. Let the (n + 1)-by-(n + 1) lower triangular matrix

q

Foundation item: The Foundation of Fujian Educational Committee (JB07147).

⇑ Corresponding author.

4434

Y.-H. Chen, C.-Y. Yu / Applied Mathematics and Computation 218 (2011) 4433–4436

0

1

B  B B B h11 T B e1 j 0 B C B e ¼B H  A ¼ B h21 @  B B .. H j en B . B B @ hn1;1 0

0





0









1

h12

j j

h22 .. .

h23 .. .

..

hn1;2



hn1;n1

hn1;n

j

hn;2



hn;n1

hn;n

j

hn;1

j j

.

0

1

 C C C 0 C C .. C C . C; C .. C . C C C 0 A 1

where e1 and en are the ﬁrst and the last column of matrix In respectively, and In denotes the identity matrix of order n.   e is nonsingular. Partition H e 1 into a LT , where a, L, h and b are matrices of size n  1, n  n, 1  1, It is clear that H h b n  1 respectively. By

e H e 1 ¼ H



eT1 H

0



en

a

L

h

T



 ¼

b

1

0

0 In



¼ Inþ1 ;

we have

Ha þ hen ¼ 0

ð2:1Þ

HL þ en bT ¼ In :

ð2:2Þ

and

e 1 is singular, which is It is easy to see h – 0. In fact, if h = 0, then it follows that a = 0 since Ha = 0 by (2.1). This implies that H a contradiction. From the (2.1), we know that en = h1Ha. Substitution of this equation into (2.2) that yields the following equation 1

HðL  h abT Þ ¼ In : Thus 1

H1 ¼ L  h abT : It is noticed that 1

In

h a

0

1

!

a

L

h

bT



1

¼

0 L  h abT bT

h

! :

ð2:3Þ

e is its associated lower triangular matrix as Lemma 1. Suppose that H is a nonsingular lower Hessenberg matrix of order n and H above. Then

e detðHÞ ¼ ð1Þn h  detð HÞ: Proof. From (2.3) it is easy to verify that

e 1 Þ ¼ ð1Þnþ1þ1 h  detðL  h abT Þ ¼ ð1Þn h  detðH1 Þ: detð H 1

Thus

e detðHÞ ¼ ð1Þn h  detð HÞ:



3. Main results

e be the Theorem 1. Let H be a nonsingular lower Hessenberg matrix and all elements of the super diagonal be non-zero, and H   e 1 as a LT , where a, L, h and b are as above. Then associated matrix as above. Partition H h b (1) H1 = L  h1abT, and (2) detðHÞ ¼ ð1Þn h  Pn1 i¼1 hi;iþ1 ,

Y.-H. Chen, C.-Y. Yu / Applied Mathematics and Computation 218 (2011) 4433–4436

4435

where hi,i+1 (i = 1,2, . . . , n  1) are the super diagonal elements of H. Proof (1) This is readily obtained above. e ¼ Pn1 hi;iþ1 , we can get it. (2) Using Lemma 1 and detð HÞ i¼1

h

e 1 . To ﬁnd the inverse and the determinant of H, it is necessary to obtain the matrix a, L, h and b, i.e., to compute H e 1 . In the following we show how to determine the H Denote

e 1 ¼ ðc1 ; c2 ; . . . ; cnþ1 Þ; H e 1 . where cj is jth column of H e 1 H e ¼ Inþ1 , where In+1 denotes the identity matrix of order (n + 1), we have From the relation H n X

hij ciþ1 ¼ ej

for j ¼ 1; 2; . . . ; n

i¼j1

and

cnþ1 ¼ enþ1 ; where h01 = 1 and ej is the jth column of the In+1. Consequently, all cj can be calculated recursively as follows

8 c ¼ enþ1 > < nþ1 ! n  P > hj1;j c ¼ e  h c j ij iþ1 : j

j ¼ n; n  1; . . . ; 1

i¼j

e 1 is lower triangular matrix, we obtain the following algorithms: Combining this iteration with Theorem 1 when H e 1 , denoted as C Algorithm 1: Computing H e (1) input n and H; (2) C = zeros (n+1); C(n + 1, n + 1) = 1; (3) for j = n : 1: 2 e jÞ; C(j, j) = a; a ¼ 1= Hðj; for k = j + 1 : n + 1 e : n þ 1; jÞÞ Cðk; jÞ ¼ a  ðCðk; k : n þ 1Þ  Hðk end end; (4) C(1, 1) = 1; for k = 2 : n + 1 e : k; 1ÞÞ Cðk; jÞ ¼ ðCðk; 2 : kÞ  Hð2 end.

Algorithm 2: Computing H1 and det (H), denoted as V and D respectively (1) h = C(n + 1,1); b = 1/h; (2) V = C(1 : n, 2 : n + 1) + b ⁄ C(1:n, 1) ⁄ C(n + 1, 2 : n + 1); (3) D = (1)n ⁄ h for j = 2 : n e jÞ D ¼ D  Hðj; end. Let us now  have a look  at the number of multiplications and divisions executed by Algorithms  1 and 2.  For Algorithm 1, it takes about 16 n3 þ 12 n2 operations in Step3, and about 12 n2 operations in Step4. We need about 16 n3 þ n2 operations to com  e 1 . Algorithm 2 amounts to about n2 operations. Therefore, we need about 1 n3 þ 2n2 operations computing H1. Our pute H 6   algorithm is better than Elouaﬁ’s algorithm that needs about 12 n3 þ n2 operations in computing H1.

4436

Y.-H. Chen, C.-Y. Yu / Applied Mathematics and Computation 218 (2011) 4433–4436

4. An example Consider the Hessenberg matrix as

0

1

1 1

B B1 B H¼B B1 B @1

1

1

1

1

1

1

1

1

C C C C: 1 C C 1 1 A 1 1

1

By Algorithm 1, we have

0 B B B B C¼B B B B @

1

0

0

0

0

0

1

0C C C 2 1 1 0 0 0C C: 4 2 1 1 0 0 C C C 8 4 2 1 1 0 A 16 8 4 2 1 1 1

1

0

0

0

Using Algorithm 2, we obtain

h ¼ 16; 0 H

1

0:5

0:25

0:125 0:0625 0:0625

1

C B B 0:5 0:25 0:125 0:0625 0:0625 C C B ¼V¼B 0:5 0:25 0:125 0:125 C C B 0 C B 0 0:5 0:25 0:25 A @ 0 0 0 0 0:5 0:5

and

detðHÞ ¼ D ¼ 16: Acknowledgment The authors gratefully acknowledge the referees for valuable comments and suggestions. References  M. Elouaﬁ, A.D. Aiat Hadj, A new recursive algorithm for inverting Hessenberg matrices, Appl. Math. Comput. 214 (2009) 497–499.  G.H. Golub, C.F. Van Loan, Matrix Computations, third ed., Johns Hopkins University Press, Baltimore and London, 1996. pp. 341–352.  X.G. Lv, T.Z. Huang, J. Le, A note on computing the inverse and the determinant of a pentadiagonal Toeplitz matrix, Appl. Math. Comput. 206 (2008) 327– 331.