A Rank–One Reduction Formula and Its Applications to Matrix Factorizations

Abstract

Let $A \in R^{m \times n} $ denote an arbitrary matrix. If $x \in R^n $ and $y \in R^m $ are vectors such that $\omega = y^T Ax \ne 0$, then the matrix $B: = A - \omega ^{ - 1} Axy^T A$ A has rank exactly one less than the rank of A. This Wedderburn rank-one reduction formula is easy to prove, yet the idea is so powerful that perhaps all matrix factorizations can be derived from it. The formula also appears in places such as the positive definite secant updates BFGS and DFP as well as the ABS methods. By repeatedly applying the formula to reduce ranks, a biconjugation process analogous to the Gram–Schmidt process with oblique projections can be developed. This process provides a mechanism for constructing factorizations such as ${\text{LDM}}^T $, QR, and SVD under a common framework of a general biconjugate decomposition $V^T AU = \Omega $ that is diagonal and nonsingular. Two characterizations of biconjugation provide new insight into the Lanczos method and its breakdown. One characterization shows that the Lanczos algorithm (and the conjugate gradient method) is a special case of the rank-one process; in fact, these processes can be identified with the class of biconjugate direction methods so that history is pushed back by about twenty years.