The power of bidiagonal matrices

DOI10.13001/ELA.2024.8297MaRDI QIDQ6628853zbMATH OpenFDO

Publication date 29 October 2024

Published in ELA. The Electronic Journal of Linear Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.13001/ELA.2024.8297

bidiagonal matrix condition number Frank matrix Kac-Murdock-Szegö matrix matrix function Pascal matrix Toeplitz matrix totally nonnegative matrix Vandermonde system

Mathematics Subject Classification ID

Linear equations (linear algebraic aspects) (15A06) Conditioning of matrices (15A12) Factorization of matrices (15A23) Toeplitz, Cauchy, and related matrices (15B05) Direct numerical methods for linear systems and matrix inversion (65F05) Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35)

Review text

The purpose of this paper is to highlight the importance of bidiagonal matrices, i.e., matrices of the form \N\[\N\begin{bmatrix} b_{1,1} & b_{1,2} & 0 & \dots & 0 & 0 \\\N0 & b_{2,2} & b_{2,3} & \dots & 0 & 0 \\\N0 & 0 & b_{3,3} & \dots & 0 & 0 \\\N\vdots & \vdots & \vdots & \dots & \vdots & \vdots \\\N0 & 0 & 0 & \dots & b_{(n-1),(n-1)} & b_{(n-1), n} \\\N0 & 0 & 0 & \dots & 0 & b_{n,n}\end{bmatrix}\] or \[ \begin{bmatrix} b_{1,1} & 0 & 0 & \dots & 0 & 0 \\\Nb_{2,1} & b_{2,2} & 0 & \dots & 0 & 0 \\\N0 & 0 & b_{3,3} & \dots & 0 & 0 \\\N\vdots & \vdots & \vdots & \dots & \vdots & \vdots \\\N0 & 0 & 0 & \dots & b_{(n-1),(n-1)} & 0 \\\N0 & 0 & 0 & \dots & b_{n,(n-1)} & b_{n,n}\end{bmatrix},\N\]\Nand show how factorizations of matrices into bidiagonal factors can be exploited.\N\NSection 1 presents an outline of the paper and briefly summarizes some of the contexts from numerical linear algebra in which bidiagonal matrices come into play.\N\NSection 2 presents some basic properties of bidiagonal matrices. As an example, the explicit form of the inverse of upper bidiagonal nonsingular matrices is presented. Estimates of the effect of a componentwise perturbation of a nonsingular bidiagonal matrix on its inverse are then derived. Various generalizations of this problem are also considered.\N\NIn Section 3, the author looks at the problem of computing, for a given matrix \(X \in \mathbb{C}^{n \times n}\) in factorized form \(X = A_1A_2 \dots A_k\), where \(A_i \in \mathbb{C}^{n \times n}\) for all \(i\), the exact condition number \(\kappa_\infty(X) = \|X\|_\infty \|X^{-1}\|_\infty\) without explicitly forming \(X\). The main result of this section provides an answer to the case where the factors are nonsingular bidiagonal matrices either all nonnegative or all exhibiting a checkerboard sign pattern.\N\NSection 4 considers examples of linear systems of the form \(Ax = b\) in which \(A\) is either a product of bidiagonal matrices or a product of inverses of bidiagonal matrices. Vandermonde systems and Pascal systems are also considered\NHere, the emphasis is on the backward error and forward error when such systems are solved in floating-point arithmetic.\N\NIn Section 5, it is shown that for a totally nonnegative \(n \times n\) matrix \(A\), \(\kappa_\infty(A)\) can be computed in \(O(n^2)\) flops, given a factorization of \(A\) into a product of bidiagonal matrices and that the computed solution is highly accurate. The computations are summarized in an algorithm and numerical experiments in MATLAB are carried out to illustrate the accuracy of the condition number evaluation.\N\NSection 6 explores functions of bidiagonal matrices. In particular, it is shown that the exponential of a totally nonnegative bidiagonal matrix is totally nonnegative.\N\NSection 7 briefly highlights consequences and observations arising from the fact that upper triangular Toeplitz matrices can be expressed as a linear combination of upper bidiagonal matrices with a superdiagonal consisting entirely of 1's.\N\NSection 8 shows how factorisations involving bidiagonal matrices or their inverses can provide useful information about certain special matrices, such as the Frank matrix, the Kac-Murdock-Szegö matrix, the Pascal matrix, and some tridiagonal matrices.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: The power of bidiagonal matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6628853)