Math 665: Combinatorial Matrix Theory

Fall 2009

Course meets: TuTh 1:10-2:30, 3866 East Hall.

Instructor: Sergey Fomin, 2858 East Hall, 764-6297, fomin@umich.edu

Course homepage: http://www.math.lsa.umich.edu/~fomin/665f09.html

Level: introductory graduate.

Student work expected: several problem sets.

Synopsis: This is an introductory graduate course in Combinatorial Matrix Theory, emphasizing its algebraic aspects.

Tentative list of topics: Combinatorial techniques in linear algebra. Canonical forms and factorizations. Determinantal identities. Matroids and projective geometry. Grassmannians and Schubert varieties. Polynomials with real roots. Total positivity.

A follow-up course tentatively planned for Winter 2010 (Math 669, Combinatorial Matrix Theory II) will focus on analytic aspects of matrix theory.

Reference texts (none required):

• A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. Ziegler, Oriented matroids, Cambridge University Press, 1999.
• R. A. Brualdi and D. Cvetkovic, A Combinatorial approach to matrix theory and its applications, Chapman & Hall/CRC, 2008.
• R. A. Brualdi and H. J. Ryser, Combinatorial matrix theory, Cambridge University Press, Cambridge, 1991.
• F. R. Gantmacher, The theory of matrices, vol. 1-2, AMS, 1998.
• F. R. Gantmacher and M. G. Krein, Oscillation matrices and kernels and small vibrations of mechanical systems, AMS, 2002.
• V. V. Prasolov, Problems and theorems in linear algebra, AMS, 1994.
• B. Sturmfels, Algorithms in invariant theory, Springer Verlag, 1993.

Lecture topics (from Fall 2003):

1. Overview. Linear-algebraic proof of Hall's marriage theorem.
   Combinatorial proof of the Cayley-Hamilton theorem.
2. Polynomial identities in matrix algebras. The Amitsur-Levitzki theorem.
3. Combinatorial evaluation of determinants: Vandermonde, Cauchy, and Smith.
4. Compound matrices. Theorems of Binet-Cauchy, Kronecker, and Sylvester-Franke.
5. Jacobi's formula. Muir's Extension Principle and its applications.
   Grassmannians. Plücker embedding.
6. First and second fundamental theorems of invariant theory.
   Grassmann-Plücker relations and van der Waerden syzygies.
7. The Grassmann-Cayley algebra and its applications in projective geometry.
   Theorems of Desargues and Pappus.
8. Matroids. Realizability.
9. Matroid stratification of a Grassmannian.
10. Oriented matroids. Pseudoline arrangements.
11. Greedy algorithm for a minimal cost basis.
    Schubert cells in a Grassmannian.
12. The Bruhat order on a Grassmannian. Schubert varieties.
13. Bruhat decomposition of a general linear group.
14. Jordan form. Nilpotent varieties. The Gansner-Saks theorem.
15. Applications to extremal poset theory: theorems of Dilworth and Greene.
16. Stabilizer of two flags. The Robinson-Schensted correspondence.
17. Gaussian decomposition. Jacobi's rule.
18. Real roots of polynomials. The Sturm-Hermite criterion.
19. Real-rooted polynomials in combinatorics.
    The Leverrier-Faddeev method.
20. Perron-Frobenius theory.
21. Total positivity: first steps.
22. Spectra of totally positive and oscillatory matrices.
    The Karlin-McGregor-Lindström lemma.
23. Rhombus tilings of a hexagon.
    Total positivity of Toeplitz matrices.
24. Schur functions. Gessel-Viennot proof of the Jacobi-Trudi formula.
    Parametrization of totally positive matrices.
25. Total positivity criterion of Gasca and Peña.
    Theorems of Loewner and Whitney.
26. Pfaffians (guest lecture by A.Barvinok).
27. General total positivity criteria.
    Totally nonnegative varieties.