!=yTAx6=0,thenthematrixB=A!1AxyTAhasrankexactlyonelessthantherankofA. Abstract.LetA2Rmndeno.pdf

A RANK-ONE REDUCTION FORMULAAND ITS APPLICATIONS TO MATRIX FACTORIZATIONSMOODY T. CHU , ROBERT. E. FUNDERLICy AND GENE H. GOLUBzDedicated to the Memory of Alston S. Householder.Abstract. Let A 2 Rmn denote an arbitrary matrix. If x 2 Rn and y 2 Rm are vectors such that! = yTAx 6= 0, then the matrix B := A !1AxyTA 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 perhapsall matrix factorizations can be derived from it. The formula also appears in places like the positivedenite secant updates BFGS and DFP as well as the ABS methods. By repeatedly applying theformula to reduce ranks, a biconjugation process analogous to the Gram-Schmidt process with obliqueprojections can be developed. This process provides a mechanism for constructing factorizations such asLDMT , QR and SVD under a common framework of a general biconjugate decomposition V TAU = that is diagonal and nonsingular. Two characterizations of biconjugation provide new insight into theLanczos method including its breakdown. One characterization shows that the Lanczos algorithm (andthe conjugate gradient method) is a special case of the rank-one process and in fact these processes canbe identied with the class of biconjugate direction methods so that history is pushed back by abouttwenty years.Key words. Rank Reduction, Matrix Factorization, Matrix Decomposition, QR Factorization, LUFactorization, Outer Product Expansion, Conjugate Directions, Conjugate Gradient Method, LanczosMethod, Singular Value Decomposition, SVD, De ation.AMS(MOS) subject classications. 65F15, 65H15.1. Introduction. Matrix factorizations or decompositions reign supreme in pro-viding practical numerical algorithms and theoretical linear algebra insights. Matrixfactorizations are examples of perhaps the most important strategy of numerical analy-sis: replace a relatively dicult problem with a much easier one, e.g. triangular systemsare easier