Skip to main content
SpringerLink
Log in

Tests for the recognition of total positivity

  • Published:
SeMA Journal Aims and scope Submit manuscript

Abstract

Totally positive matrices are matrices with all their minors nonnegative and have important applications in many fields. We review tests to recognize if a given matrix belongs to this class of matrices or to some related classes. Several applications are presented, including the relationship of these tests with the construction of algorithms for the computation with totally positive matrices to high relative accuracy.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Alonso, P., Gasca, M., Peña, J.M.: Backward error analysis of Neville elimination. Appl. Numer. Math. 23, 193–204 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  • Alonso, P., Delgado, J., Gallego, R., Peña, J.M.: A collection of examples where Neville elimination outperforms Gaussian elimination. Appl. Math. Comput. 216, 2525–2533 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  • Alonso, P., Delgado, J., Gallego, R., Peña, J.M.: Conditioning and accurate computations with Pascal matrices. J. Comput. Appl. Math. 252, 21–26 (2013)

    Google Scholar 

  • Ando, T.: Totally positive matrices. Linear Algebra Appl. 90, 165–219 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  • Barreras, A., Peña, J.M.: Accurate computations of matrices with bidiagonal decomposition using methods for totally positive matrices. Numer. Linear Algebra Appl. 20, 413–424 (2013)

    Google Scholar 

  • Barreras, A., Peña, J.M.: Matrices with bidiagonal decomposition, accurate computations and corner cutting algorithms. In: Cepedello, M., Hedenmalm, H., Kaashoek, M.A., Montes-Rodríguez, A., Treil, S.R. (eds.) Proceedings of IWOTA 2011 Operator Theory. Advances and Applications. Springer, Berlin (2013, to appear)

  • de Boor, C., Pinkus, A.: Backward error analysis for totally positive linear systems. Numer. Math. 27, 485–490 (1977)

    Article  MATH  Google Scholar 

  • Brenti, F.: Combinatorics and Total positivity. J. Combin. Theory Ser. A 71, 175–218 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  • Brown, L.D., Johnstone, I.M., MacGibbon, K.B.: Variation diminishing transformations: a direct approach to total positivity and its statistical applications. J. Am. Statistical Assoc. 76, 824–832 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  • Carnicer, J.M., Peña, J.M.: Shape preserving representations and optimality of the Bernstein basis. Adv. Comput. Math. 1, 173–196 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  • Carnicer, J.M., Peña, J.M.: Totally positive bases for shape preserving curve design and optimality of B-splines. Comput. Aided Geom. Design 11, 633–654 (1994)

    Article  MathSciNet  Google Scholar 

  • Carnicer, J.M., Peña, J.M.: Least supported bases and local linear independence. Numer. Math. 67, 289–301 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  • Carnicer, J.M., Peña, J.M., Zalik, R.: On strictly totally positive systems. J. Approx. Theory 98, 411–441 (1998)

    Article  Google Scholar 

  • Cortés, V., Peña, J.M.: A stable test for strict sign regularity. Math. Comp. 77, 2155–2171 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  • Craven, T., Csordas, G.: A sufficient condition for strict total positivity of a matrix. Linear Multilinear Algebra 45, 19–34 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  • Cryer, C.W.: The LU-factorization of totally positive matrices. Linear Algebra Appl. 7, 83–92 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  • Cryer, C.W.: Some properties of totally positive matrices. Linear Algebra Appl. 15, 1–25 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  • Cvetkovič, L., Kostic, V., Peña, J.M.: Eigenvalue localization refinements for matrices related to positivity. SIAM J. Matrix Anal. Appl. 32, 771–784 (2012)

    Article  Google Scholar 

  • Delgado, J., Peña, J.M.: Corner cutting systems. Comput. Aided Geom. Design 22, 81–97 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  • Delgado, J., Peña, J.M.: Progressive iterative approximation and bases with the fastest convergence rates. Comput. Aided Geom. Design 24, 10–18 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Delgado, J., Peña, J.M.: A corner cutting algorithm for evaluating rational Bézier surfaces and the optimal stability of the basis. SIAM J. Sci. Comput. 29, 1668–1682 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Delgado, J., Peña, J.M.: Optimal conditioning of Bernstein collocation matrices. SIAM J. Matrix Anal. Appl. 31, 990–996 (2009)

    Article  MathSciNet  Google Scholar 

  • Delgado, J., Peña, J.M.: Running relative error for the evaluation of polynomials. SIAM J. Sci. Comput. 31, 3905–3921 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  • Delgado, J., Peña, J.M.: Accurate computations with collocation matrices of rational bases. Appl. Math. Comput. (2013, to appear)

  • Demmel, J., Gu, M., Eisenstat, S., Slapnicar, I., Veselic, K., Drmac, Z.: Computing the singular value decomposition with high relative accuracy. Linear Algebra Appl. 299, 21–80 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  • Demmel, J., Koev, P.: The accurate and efficient solution of a totally positive generalized Vandermonde linear system. SIAM J. Matrix Anal. Appl. 27, 142–152 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  • Dimitrov, D., Peña, J.M.: Almost strict total positivity and a class of Hurwitz polynomials. J. Approx. Theory 132, 212–223 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  • Dopico, F.M., Koev, P.: Bidiagonal decompositions of oscillating systems of vectors. Linear Algebra Appl. 428, 2536–2548 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  • Fallat, S.: Bidiagonal factorizations of totally nonnegative matrices. Am. Math. Monthly 108, 697–712 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  • Fallat, S., Johnson, C.R.: Totally nonnegative matrices. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2011)

    Google Scholar 

  • Fekete, M., Polya, G.: Uber ein Problem von Laguerre. Rend. C.M. Palermo 34, 89–120 (1912)

    Google Scholar 

  • Fiedler, M., Markham, T.: Consecutive-column and -row properties of matrices and the Loewner–Neville factorization. Linear Algebra Appl. 266, 243–259 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  • Fomin, S., Zelevinsky, A.: Double Bruhat cells and total positivity. JAMS 12, 335–380 (1999)

    MathSciNet  MATH  Google Scholar 

  • Fomin, S., Zelevinsky, A.: Total positivity: tests and parameterizations. Math. Intell. 22, 23–33 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  • Frydman, H., Singer, B.: Total positivity and the embedding problem for Markov chains. Math. Proc. Cambridge Philos. Soc. 85, 339–344 (1979)

    Article  MathSciNet  Google Scholar 

  • Gantmacher, F.R., Krein, M.G.: Oszillationsmatrizen. Oszillationskerne und kleine Schwingungen mechanischer Systeme. Akademie-Verlag, Berlin (1960). (Revised English version: Oscillation matrices, AMS, 2002)

    MATH  Google Scholar 

  • Garloff, J.: Intervals of almost totally positive matrices. Linear Algebra Appl. 363, 103–108 (2006)

    Article  MathSciNet  Google Scholar 

  • Gasca, M., Micchell, C.A. (eds.): Total Positivity and its Applications. Kluwer, Dordrecht (1996)

    MATH  Google Scholar 

  • Gasca, M., Micchelli, C.A., Peña, J.M.: Almost strictly totally positive matrices. Numer. Algorithms 2, 225–236 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  • Gasca, M., Peña, J.M.: Total positivity and Neville elimination. Linear Algebra Appl. 165, 25–44 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  • Gasca, M., Peña, J.M.: Total positivity, QR factorization and Neville elimination. SIAM J. Matrix Anal. Appl 14, 1132–1140 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  • Gasca, M., Peña, J.M.: Scaled pivoting in Gauss and Neville elimination for totally positive systems. Appl. Numer. Math. 13, 345–356 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  • Gasca, M., Peña, J.M.: A matricial description of Neville elimination with applications to total positivity. Linear Algebra Appl. 202, 33–53 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  • Gasca, M., Peña, J.M.: A test for strict sign-regularity. Linear Algebra Appl. 197–198, 133–142 (1994)

    Article  Google Scholar 

  • Gasca, M., Peña, J.M.: On the characterization of almost strictly totally positive matrices. Adv. Comput. Math. 3, 239–250 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  • Gasca, M., Peña, J.M.: On factorizations of totally positive matrices. In: Gasca, M., Micchelli, C.A. (eds.) Total Positivity and Its Applications, pp. 109–130. Kluwer, Dordrecht (1996)

    Chapter  Google Scholar 

  • Gasca, M., Peña, J.M.: Characterizations and decompositions of almost strictly positive matrices. SIAM J. Matrix Anal. Appl. 28, 1–8 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  • Gladwell, G.M.L.: Inner total positivity. Linear Alg. Appl. 393, 179–195 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  • Goodman, T.N.T., Micchelli, C.A.: Corner cutting algorithms for the Bezier representation of free form curves. Linear Alg. Appl. 99, 225–252 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  • Gassó, M., Torregrosa, J.R.: A totally positive factorization of rectangular matrices by the Neville elimination. SIAM J. Matrix Anal. Appl. 25, 986–994 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  • Gassó, M., Torregrosa, J.R.: Bidiagonal factorizations and quasi-oscillatory rectangular matrices. Linear Algebra Appl. 429, 1886–1893 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  • Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM, Philadelphia (2002)

    Book  MATH  Google Scholar 

  • Karlin, S.: Total Positivity, vol. I. Stanford University Press, California (1968)

    MATH  Google Scholar 

  • Karlin, S., McGregor, J.L.: Coincidence probabilities of birth and death processes. Pacific J. Math. 9, 1109–1140 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  • Katkova, O.M., Vishnyakova, A.M.: On sufficient conditions for the total positivity and for the multiple positivity of matrices. Linear Algebra Appl. 416, 108–1097 (2006)

    Article  MathSciNet  Google Scholar 

  • Koev, P.: Accurate eigenvalues and SVDs of totally nonnegative matrices. SIAM J. Matrix Anal. Appl. 27, 1–23 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  • Koev, P.: Accurate Computations with totally nonnegative matrices. SIAM J. Matrix Anal. Appl. 29, 731–751 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Loewner, C.: On totally positive matrices. Math. Z. 63, 338–340 (1955)

    Article  MathSciNet  MATH  Google Scholar 

  • Lusztig, G.: A survey of total positivity. Milan J. Math. 76, 125–134 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  • Lyche, T., Peña, J.M.: Optimally stable multivariate bases. Adv. Comput. Math. 20, 49–159 (2004)

    Article  Google Scholar 

  • Mainar, E., Peña, J.M.: Corner cutting algorithms associated with optimal shape preserving representations. Comput. Aided Geom. Design 16, 883–906 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  • Marco, A., Martínez, J.-J.: A fast and accurate algorithm for solving Bernstein-Vandermonde linear systems. Linear Algebra Appl. 422, 616–628 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Marco, A., Martínez, J.-J.: Accurate computations with Said-Ball-Vandermonde matrices. Linear Algebra Appl. 432, 2894–2908 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  • Martínez, J.-J., Peña, J.M.: Factorizations of Cauchy-Vandermonde matrices. Linear Algebra Appl. 284, 229–237 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  • Mühlbach, G., Gasca, M.: A test for strict total positivity via Neville elimination. In: Uhlig, F., Groue, R. (eds.) Current Trends in Matrix Theory, pp. 225–232. Elsevier, Amsterdam (1987)

    Google Scholar 

  • Peña, J.M.: Shape preserving representations for trigonometric polynomial curves. Comput. Aided Geom. Design 14, 5–11 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  • Peña, J.M. (ed.): Shape Preserving Representations in Computer-Aided Geometric Design. Nova Science Publishers, Commack (1999)

    MATH  Google Scholar 

  • Peña, J.M.: A class of P-matrices with applications to the localization of the eigenvalues of a real matrix. SIAM J. Matrix Anal. Appl. 22, 1027–1037 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  • Peña, J.M.: Determinantal criteria for total positivity. Linear Algebra Appl. 332–334, 131–137 (2001)

    Article  Google Scholar 

  • Peña, J.M.: On the optimal stability of bases of univariate functions. Numer. Math. 91, 305–318 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  • Peña, J.M.: Scaled pivots and scaled partial pivoting strategies. SIAM J. Numer. Anal. 41, 1022–1031 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  • Peña, J.M.: On an alternative to Gerschgorin circles and ovals of Cassini. Numer. Math. 95, 337–345 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  • Peña, J.M.: Characterizations and stable tests for the Routh-Hurwitz conditions and total positivity. Linear Alg. Appl. 393, 319–332 (2004)

    Article  MATH  Google Scholar 

  • Peña, J.M.: Exclusion and inclusion intervals for the real eigenvalues of positive matrices. SIAM J. Matrix Anal. Appl. 26, 908–917 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  • Peña, J.M.: A note on the optimal stability of bases of univariate functions. Numer. Math. 103, 151–154 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  • Peña, J.M.: Eigenvalue localization for totally positive matrices. In: Bru, R., Romero-Vivó, S. (eds.) Positive Systems. Lecture Notes in Control and Information Sciences, vol. 389, pp. 123–130 (2009)

  • Peña, J.M., Sauer, T.: On the multivariate Horner scheme. SIAM J. Numer. Anal. 37, 1186–1197 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  • Pinkus, A.: Totally positive matrices. In: Cambridge Tracts in Mathematics, vol. 181. Cambridge University Press, Cambridge (2010)

  • Schoenberg, I.: Über variationsvermindernde lineare Transformationen. Math. Z. 32, 321–328 (1930)

    Article  MathSciNet  MATH  Google Scholar 

  • Schumaker, L.L.: Spline functions: basic theory, 3rd edn. Cambridge Mathematical Library. Cambridge University Press, Cambridge (2007)

    Book  MATH  Google Scholar 

  • Varga, R.S.: Geršgorin and His Circles. Springer, Berlin (2004)

    Book  MATH  Google Scholar 

  • Whitney, A.M.: A reduction theorem for totally positive matrices. J. d’Analyse Math. 2, 88–92 (1952)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Matemática Aplicada, Universidad de Zaragoza, 50009 , Zaragoza, Spain

    J. M. Peña

Authors
  1. J. M. Peña
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. M. Peña.

Additional information

Research partially supported the Spanish Research Grant MTM2012-31544 and by Gobierno de Aragón and Fondo Social Europeo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Peña, J.M. Tests for the recognition of total positivity. SeMA 62, 61–73 (2013). https://doi.org/10.1007/s40324-013-0008-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40324-013-0008-z

Keywords

Mathematics Subject Classification (2000)

Search

Navigation