Department of Mathematics

Combinatorics and Graph Theory

  •  Richard A. Brualdi, University of Wisconsin - Madison
  •  About Permutation Matrices
  •  10/06/2021
  •  3:00 PM - 3:50 PM
  •  Online (virtual meeting) (Virtual Meeting Link)
  •  Bruce E Sagan (bsagan@msu.edu)

The study of permutations is both ancient and modern. They can be viewed as the integers $1,2,\ldots,n$ in some order or as $n\times n$ permutation matrices. They can be regarded as data which is to be sorted. The explicit definition of the determinant uses permutations. An inversion of a permutation occurs when a larger integer precedes a smaller integer. Inversions can be used to define two partial orders on permutations, one weaker than the other. Partial orders have a unique minimal completion to a lattice, the Dedekind-MacNeille completion. Generalizations of permutation matrices determine related matrix classes, for instance, alternating sign matrices (ASMs) which arose independently in the mathematics and physics literature. Permutations may contain certain patterns, e.g. three integers in increasing order; avoiding such patterns determines certain permutation classes. Similar restrictions can be placed more generally on $(0,1)$-matrices. The convex hull of $n\times n$ permutation matrices is the polytope of $n\times n$ doubly stochastic matrices. In a similar way we get ASM polytopes. We shall explore these and other ideas and their connections.

 

Contact

Department of Mathematics
Michigan State University
619 Red Cedar Road
C212 Wells Hall
East Lansing, MI 48824

Phone: (517) 353-0844
Fax: (517) 432-1562

College of Natural Science