Non-Unit Bidiagonal Decompositions of Totally Nonnegative Matrices - R, Purushothaman Nair (Journal of Global Research in Mathematical Archives(JGRMA), 2015)
Abstract. A procedure requiring only n3/3 flops for factorizing a given totally nonnegative (TN) n x n matrix A=[aij] is proposed as against existing procedures requiring n3/2 flops. In this procedure, at the ith step, the ith 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.Â 