- Email: [email protected]
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 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 [2]. 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 [3].
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 hn1;1 @ hn;1
1
h12 h22
h23
.. .
..
hn1;2
hn1;n1
hn;2
hn;n1
.
..
.
C C C C C C C: C C C hn1;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.
E-mail address: [email protected] (Y.-H. Chen). 0096-3003/$ - see front matter Ó 2011 Elsevier Inc. All rights reserved. doi:10.1016/j.amc.2011.10.022
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 @ hn1;1 0
0
0
1
h12
j j
h22 .. .
h23 .. .
..
hn1;2
hn1;n1
hn1;n
j
hn;2
hn;n1
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 first 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 = h1Ha. Substitution of this equation into (2.2) that yields the following equation 1
HðL h abT Þ ¼ In : Thus 1
H1 ¼ 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ðH1 Þ: 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) H1 = L h1abT, and (2) detðHÞ ¼ ð1Þn h Pn1 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 ¼ Pn1 hi;iþ1 , we can get it. (2) Using Lemma 1 and detð HÞ i¼1
h
e 1 . To find 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¼j1
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 > hj1;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 H1 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 H1. Our pute H 6 algorithm is better than Elouafi’s algorithm[1] that needs about 12 n3 þ n2 operations in computing H1.
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 [1] M. Elouafi, A.D. Aiat Hadj, A new recursive algorithm for inverting Hessenberg matrices, Appl. Math. Comput. 214 (2009) 497–499. [2] G.H. Golub, C.F. Van Loan, Matrix Computations, third ed., Johns Hopkins University Press, Baltimore and London, 1996. pp. 341–352. [3] 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.
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 [2]. 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 [3].
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 hn1;1 @ hn;1
1
h12 h22
h23
.. .
..
hn1;2
hn1;n1
hn;2
hn;n1
.
..
.
C C C C C C C: C C C hn1;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.
E-mail address: [email protected] (Y.-H. Chen). 0096-3003/$ - see front matter Ó 2011 Elsevier Inc. All rights reserved. doi:10.1016/j.amc.2011.10.022
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 @ hn1;1 0
0
0
1
h12
j j
h22 .. .
h23 .. .
..
hn1;2
hn1;n1
hn1;n
j
hn;2
hn;n1
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 first 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 = h1Ha. Substitution of this equation into (2.2) that yields the following equation 1
HðL h abT Þ ¼ In : Thus 1
H1 ¼ 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ðH1 Þ: 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) H1 = L h1abT, and (2) detðHÞ ¼ ð1Þn h Pn1 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 ¼ Pn1 hi;iþ1 , we can get it. (2) Using Lemma 1 and detð HÞ i¼1
h
e 1 . To find 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¼j1
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 > hj1;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 H1 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 H1. Our pute H 6 algorithm is better than Elouafi’s algorithm[1] that needs about 12 n3 þ n2 operations in computing H1.
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 [1] M. Elouafi, A.D. Aiat Hadj, A new recursive algorithm for inverting Hessenberg matrices, Appl. Math. Comput. 214 (2009) 497–499. [2] G.H. Golub, C.F. Van Loan, Matrix Computations, third ed., Johns Hopkins University Press, Baltimore and London, 1996. pp. 341–352. [3] 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.