Math 665: Combinatorial Matrix Theory

Fall 2003

Course meets: TuTh 2:40-4, 3088 East Hall.

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

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

Level: introductory graduate.

Student work expected: several problem sets.

Synopsis: This is an introductory graduate course in matrix theory, emphasizing its algebraic and combinatorial aspects (as opposed to analytic and numerical).

Reference texts (none required):

• A.Björner, M.Las Vergnas, B.Sturmfels, N.White, G.Ziegler, Oriented matroids, Cambridge University Press, 1999.
• R.A.Brualdi and H.J.Ryser, Combinatorial matrix theory, Cambridge University Press, Cambridge, 1991.
• S.Fomin and A.Zelevinsky, Total positivity: tests and parametrizations, Math. Intelligencer 22 (2000), 23-33.
• 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:

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.