Carnegie Mellon University
Lehman Matrices.pdf.pdf' (244.34 kB)

Lehman Matrices

Download (244.34 kB)
journal contribution
posted on 1968-02-01, 00:00 authored by Gerard CornuejolsGerard Cornuejols, Betrand Guenin, Levent Tunçel
A pair of square 0, 1 matrices A,B such that ABT = E + kI (where E is the n × n matrix of all 1s 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 = B, we get 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. This paper studies this class of Lehman matrices and classifies them according to their similarity to circulant matrices.