Accurate computation of all eigenvalues of a totally nonnegative matrix by the Cauchon algorithm

Abstract

Totally nonnegative matrices are considered, i.e., matrices having all their minors nonnegative. Any $n\times n$ nonsingular totally nonnegative matrix can be represented as the product of $2n-1$ entry-wise nonnegative bidiagonal matrices. The $n^2$ nontrivial entries of this factorization parameterize the set of the nonsingular totally nonnegative matrices. This bidiagonal factorization has been used by Plamen Koev in SIAM J. Matrix Anal. Appl. 27, pp. 1-23, 2005, to design an algorithm for the computation of all the eigenvalues of nonsingular totally nonnegative matrices with high relative accuracy. In this paper, a different approach is employed: A matrix is used, which could be obtained by running the Cauchon algorithm, but for the sake of high relative accuracy this matrix is computed from the bidiagonal factorization. The effect of elementary operations applied to reduce this matrix to tridiagonal form is determined. It is shown that the computations can be performed without any subtraction of numbers of equal sign. This provides the basis for an algorithm needing $O(n^3)$ arithmetic operations for the computation of all the eigenvalues of a nonsingular totally nonnegative matrix with guaranteed high relative accuracy, independently of the condition number of the given problem.