Table of Contents
SIAM


HESSENBERG AND TRIDIAGONAL MATRICES
Theory and Examples

Gérard MEURANT

SIAM
2025
ISBN 978-1-61197-844-5
xii + 231 pages



This book is devoted exclusively to Hessenberg and tridiagonal matrices. Hessenberg matrices are involved in Krylov methods for solving linear systems or computing eigenvalues and eigenvectors, the QR algorithm for computing eigenvalues, and in many other areas of scientific computing (for instance, control theory). Matrices that are both upper and lower Hessenberg are tridiagonal. Their entries are zero except for the main diagonal and the subdiagonal and updiagonal next to it.

This book

-presents known and new results;

-describes the theoretical properties of the matrices, their determinants, LU factorizations, inverses, and eigenvalues;

-illustrates the theoretical properties with applications and examples as well as numerical experiments; and

-considers unitary Hessenberg matrices, inverse eigenvalue problems, and Toeplitz tridiagonal matrices.



Table of Contents

0/ Preface [TOC]



1/ Hessenberg matrices  [TOC]


1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
1.2 Reduction to Hessenberg form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Factorizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Relations between the triangular Hessenberg decomposition and the QR factorization . . . 29
1.5 Normality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39
1.6 Unitary Hessenberg matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40
1.7 Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44
1.8 Inverse eigenvalue problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50
1.9 Eigenvalues and eigenvectors . . . . . . . . . . . . . . . . .  . . . . . . . . . . . . .53
1.10 Toeplitz upper Hessenberg matrices . . . . . . . . . . . . . . . . . . . . . . . . . . .56
1.11 Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
1.12 Block Hessenberg matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61



2/ Tridiagonal matrices  [TOC]


2.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .67
2.2 Similarity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .68
2.3 Determinant. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.4 Factorizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
2.5 Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .77
2.6 Eigenvalues and eigenvectors . . . . . . . . . . . . . . . . .  . . . . . . . . . . . . .85
2.7 Inverse eigenvalue problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92
2.8 Toeplitz tridiagonal matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .97
2.9 Cyclic reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
2.10 Block tridiagonal matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .115



3/ Applications and numerical examples with Hessenberg matrices  [TOC]


3.1 Krylov methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .119
3.2 Functions of matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .127
3.3 The QR algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .128
3.4 Roots of polynomials. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .129
3.5 Trigonometric interpolation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
3.6 The Frank matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .131
3.7 The Grcar matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .143



4/ Applications and numerical examples with tridiagonal matrices  [TOC]


4.1 The Lanczos and CG algorithms . . . . . . . . . . . . . . . . . . . .  . . . . . . . . . 171
4.2 Iterative methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .176
4.3 The qd algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4.4 Gauss quadrature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
4.5 Functions of matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .184
4.6 One-dimensional PDEs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
4.7 Two-dimensional PDEs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
4.8 Cubic spline interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
4.9 The Wilkinson matrices  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .191
4.10 The Kac–Murdock–Szego matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .199






There are 330 references.