On theLU factorization ofM-matrices

Summary In this paper, we give in Theorem 1 a characterization, based on graph theory, of when anM-matrixA admits anLU factorization intoM-matrices, whereL is a nonsingular lower triangularM-matrix andU is an upper triangularM-matrix. This result generalizes earlier factorization results of Fiedler and Pták (1962) and Kuo (1977). As a consequence of Theorem 1, we show in Theorem 3 that the conditionx ^T A0 ^T for somex>0, for anM-matrixA, is both necessary and sufficient forPAP ^T to admit such anLU factorization for everyn×n permutation matrixP. This latter result extends recent work of Funderlic and Plemmons (1981). Finally, Theorem 1 is extended in Theorem 5 to give a characterization, similarly based on graph theory, of when anM-matrixA admits anLU factorization intoM-matrices.Dedicated to Professor Ky Fan on his sixty-seventh birthday, September 19, 1981.Research supported in part by the Air Force Office of Scientific Research, and by the Department of Energy