Math 665: Combinatorial Matrix Theory
Fall 2003
Course meets: TuTh 2:404, 3088 East Hall.
Instructor:
Sergey Fomin, 2858 East Hall, 7646297,
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), 2333.
 F.R.Gantmacher, The theory of matrices, vol.12,
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:
 Overview. Linearalgebraic proof of Hall's marriage theorem.
Combinatorial proof of the CayleyHamilton theorem.
 Polynomial identities in matrix algebras.
The AmitsurLevitzki theorem.
 Combinatorial evaluation of determinants: Vandermonde, Cauchy,
and Smith.
 Compound matrices. Theorems of BinetCauchy, Kronecker, and
SylvesterFranke.
 Jacobi's formula. Muir's Extension Principle and its
applications.
Grassmannians. Plücker embedding.
 First and second fundamental theorems of invariant theory.
GrassmannPlücker relations and
van der Waerden syzygies.
 The GrassmannCayley algebra and its applications in projective
geometry.
Theorems of
Desargues
and
Pappus.
 Matroids. Realizability.
 Matroid stratification of a Grassmannian.

Oriented matroids. Pseudoline arrangements.
 Greedy algorithm for a minimal cost basis.
Schubert cells in a Grassmannian.
 The Bruhat order on a Grassmannian. Schubert varieties.
 Bruhat decomposition of a general linear group.
 Jordan form. Nilpotent varieties. The GansnerSaks theorem.
 Applications to extremal poset theory: theorems of Dilworth and
Greene.
 Stabilizer of two flags. The RobinsonSchensted correspondence.
 Gaussian decomposition. Jacobi's rule.
 Real roots of polynomials. The SturmHermite criterion.

Realrooted polynomials in combinatorics.
The LeverrierFaddeev method.
 PerronFrobenius theory.
 Total positivity: first steps.
 Spectra of totally positive and oscillatory matrices.
The KarlinMcGregorLindström lemma.
 Rhombus tilings of a hexagon.
Total positivity of Toeplitz matrices.
 Schur functions. GesselViennot proof of the JacobiTrudi
formula.
Parametrization of totally positive matrices.
 Total positivity criterion of Gasca and Peña.
Theorems of Loewner and Whitney.
 Pfaffians (guest lecture by A.Barvinok).
 General total positivity criteria.
Totally nonnegative varieties.
Homework assignments:
#1,
#2.