The power of bidiagonal matrices

Abstract

Bidiagonal matrices are widespread in numerical linear algebra, not least because of their use in the standard algorithm for computing the singular value decomposition and their appearance as LU factors of tridiagonal matrices. We show that bidiagonal matrices have a number of interesting properties that make them powerful tools in a variety of problems, especially when they are multiplied together. We show that the inverse of a product of bidiagonal matrices is insensitive to small componentwise relative perturbations in the factors if the factors or their inverses are nonnegative. We derive componentwise rounding error bounds for the solution of a linear system  $Ax = b$, where $A$ or $A^{-1}$ is a product $B_1 B_2\dots B_k$ of bidiagonal matrices, showing that strong results are obtained when the $B_i$ are nonnegative or have a checkerboard sign pattern. We show that given the factorization of an $n\times n$ totally nonnegative matrix $A$ into the product of bidiagonal matrices, $\| A^{-1} \|_{\infty}$ can be computed in $O(n^2)$ flops and that in floating-point arithmetic the computed result has small relative error, no matter how large $\| A^{-1} \|_{\infty}$ is. We also show how factorizations involving bidiagonal matrices of some special matrices, such as the Frank matrix and the Kac-Murdock-Szegö matrix, yield simple proofs of the total nonnegativity and other properties of these matrices.