### Euler Institute for Discrete Mathematics and its Applications Mini-course: Total positivity Sergey Fomin June 2003

A matrix is totally positive (resp., totally nonnegative) if all its minors are positive (resp., nonnegative). These classes of matrices arise and play a prominent role across various fields, including, but not limited to, such areas as discrete mathematics, probability and stochastic processes, and representation theory. This minicourse will provide an introduction to the subject, survey the applications mentioned above, and explore algorithmic, combinatorial, and geometric aspects of total positivity.

The syllabus below is followed by a list of references. All main sources are available electronically as Postscript files: just follow the links.

Introduction and first applications [3]

• Basic notions and examples
• Linear algebra: theorems of Binet-Cauchy, Jacobi, and Sylvester
• Linear algebra: determinantal identities
• Linear algebra: theorems of Perron-Frobenius and Kronecker
• Eigenvalues of TP matrices
• Directed networks and non-intersecting paths
• Toeplitz TP matrices and Polya frequency sequences
• Unimodality and log-concavity of combinatorial sequences
• The Aissen-Schoenberg-Whitney theorem
• Polynomials with real roots. Gantmacher's theorem
• Schur functions and the Gessel-Viennot technique
• Positivity of combinatorial determinants
• Variation-diminishing transformations
Testing for total positivity [2]
• The initial minors criterion
• Theorems of Whitney and Loewner
• Double wiring diagrams and TP tests
• The Laurent phenomenon
• Factorization schemes
• The twist map and matrix factorization
• Bruhat decomposition and double Bruhat cells
• Recognizing Bruhat cells
Topology of totally positive varieties
• Bruhat order. Verma's theorem
• Regular CW-complexes
• TP varieties and related complexes
Total positivity phenomena in discrete potential theory [1]
• Hitting matrices
• Resistor networks and random walks
• Loop-erased walks
• Random spanning trees
• TP phenomena for 2-dimensional Markov processes
Main sources (all of the files are PostScript)
 [1] S.Fomin, Loop-erased walks and total positivity, Tran. Amer. Math. Soc. 353 (2001), 3563-3583. [2] S.Fomin and A.Zelevinsky, Total positivity: tests and parametrizations, Math. Intelligencer 22 (2000), 23-33. [3] M.Skandera, Introductory notes on total positivity, June 2003.

Bibliography
 [4] T.Ando, Totally positive matrices, Linear Algebra Appl. 90 (1987), 165-219. [5] F.Brenti, Combinatorics and total positivity, J. Comb. Theory, Ser. A 71 (1995), 175-218. [6] F.Brenti, The applications of total positivity to combinatorics, and conversely, in [9], pp. 451-473. [7] S.Fomin and M.Shapiro, Stratified spaces formed by totally positive varieties, Michigan Math. J. 48 (2000), 253-270. [8] S.Fomin and A.Zelevinsky, Double Bruhat cells and total positivity, J. Amer. Math. Soc. 12 (1999), 335-380. [9] F.R.Gantmacher and M.G.Krein, Oscillation matrices and kernels and small vibrations of mechanical systems, AMS Chelsea Publ., Providence, RI, 2002. [10] M.Gasca and C.A.Micchelli (Eds.), Total Positivity and its Applications, Kluwer Acad. Publ., Dordrecht, 1996. [11] S.Karlin, Total positivity., Vol. I, Stanford University Press, Stanford, CA, 1968. [12] G.Lusztig, Introduction to total positivity, de Gruyter Exp. Math. 26 (1998), 133--145. [13] A.Pinkus, Spectral properties of totally positive kernels and matrices, in [9], pp. 477-511. [14] R.P.Stanley, Positivity problems and conjectures in algebraic combinatorics, in Mathematics: Frontiers and Perspectives, AMS, Providence, RI, 2000, pp. 295-319.