The power of bidiagonal matrices (Q6628853)

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.