User Tools

Site Tools


Gerard Cornuejols

Lehman Matrices

Abstract for the Colloquium and Combinatorics Seminar 2009 July 27

Two square 0,1-matrices, A and B, such that AB = E + kI (where E is the n×n matrix of all 1's and k is a positive integer) are called “Lehman matrices”. These matrices figure prominently in Lehman's seminal theorem on minimally nonideal matrices.

There are two choices of k for which this matrix equation is known to have infinite families of solutions. When n = k2 + k + 1 and A = BT, we get the point-line incidence matrices of finite projective planes, which have been widely studied in the literature. The other case occurs when k = 1 and n is arbitrary, but very little is known in this case. I will discuss this class of Lehman matrices.

The work is joint with Bertrand Guenin and Levent Tuncel.

seminars/comb/abstract.200907cor.txt · Last modified: 2020/01/29 14:03 (external edit)