Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-20T05:33:33.880Z Has data issue: false hasContentIssue false
  • English
  • Français

On Gaussian elimination and determinant formulas for matrices with chordal inverses

Published online by Cambridge University Press:  17 April 2009

Mihály Bakonyi
Mihály Bakonyi
Affiliation:
Department of Mathematics, The College of William and Mary, Williamsburg VA 23187-8795, United States of America
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper a formula is obtained for the entries of the diagonal factor in the U D L factorisation of an invertible operator matrix in the case when its inverse has a chordal graph. As a consequence, in the finite dimensional case a determinant formula is obtained in terms of some key principal minors. After a cancellation process this formula leads to a determinant formula from an earlier paper by W.W. Barrett and C.R. Johnson, deriving in this way a different and shorter proof of their result. Finally, an algorithmic method of constructing minimal vertex separators of chordal graphs is presented.

Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 46 , Issue 3 , December 1992 , pp. 435 - 440
Copyright
Copyright © Australian Mathematical Society 1992

References

[1]Bakonyi, M. and Constantinescu, T., ‘Inheritance principles for chordal graphs’, Linear Algebra Appl. 148 (1991), 125–143.CrossRefGoogle Scholar
[2]Barrett, W.W. and Johnson, C.R., ‘Determinantal formulae for matrices with sparse inverses’, Linear Algebra Appl 56 (1984), 73–88.CrossRefGoogle Scholar
[3]Barrett, W.W., Johnson, C.R. and Lundquist, M., ‘Determinantal formulae for matrix completions associated with chordal graphs’, Linear Algebra Appl 121 (1989), 265–289.CrossRefGoogle Scholar
[4]Golumbic, M.C., Algorithmic graph theory and the perfect graph (Academic Press, New York, 1980).Google Scholar
[5]Grone, R., Johnson, C.R., Sa, E. and Wolkowitz, H., ‘Positive definite completions of partial Hermitian matrices’, Linear Algebra Appl 58 (1984), 102–124.CrossRefGoogle Scholar
[6]Johnson, C.R. and Barrett, W.W., ‘Spanning tree extensions of the Hadamard-Fischer inequalities’, Linear Algebra Appl 66 (1985), 177–194.CrossRefGoogle Scholar
[7]Johnson, C.R., Olesky, D.D. and van der Driesche, P., ‘Inherited matrix entries: LU factorization’, SIAM J. Matrix Anal. Appl. 10 (1989), 94–104.CrossRefGoogle Scholar