Non-Unit Bidiagonal Decompositions of Totally Nonnegative Matrices

Abstract

Abstract. A procedure requiring only n³/3 flops for factorizing a given totally nonnegative (TN) n x n matrix A=[a_ij] is proposed as against existing procedures requiring n³/2 flops. In this procedure, at the i^th step, the i^th non-unit bidiagonal factor of A^-1 is generated. Product of such previous i-factors of A^-1 are multiplied with the (i+1)^th column of A. This strategy replaces the usual expensive row operations with more economical triangular matrix – vector multiplications. Another attraction with the procedure is its simple non-unit bidiagonal factors which can be constructed without any computations at all. These features contribute to reduce number of flops as claimed. The procedure exposes that it is the non-negativity of 2 X 2 minors of factors with non-negative entries that makes A, a totally positive (TP) matrix. It is proved that entries of A are constituted by partial sums of the entries of the factors. This in turn contributes to the extension of positivity of 2 X 2 minors from factors to their products as a chained process which culminates in the total positivity of A. This way the total positivity of A is explained independent of earlier results.