INTEGRAL EXTREME POINTS
Abstract
It is shown that if A is an integral matrix having linearly independent rows, then the extreme points of the set of nonnegative solutions to Ax = b are integral for all integral b if and only if the determinant of every basis matrix is plus or minus 1. This provides a short proof of the Hoffman- Kruskal theorem characterizing unimodular matrices, i.e., matrices in which the determinant of each nonsingular submatrix is plus or minus 1. Their theorem is that if A is integral, then A is unimodular if and only if the extreme points of the set of nonnegative solutions to Ax = or < b are integral for all integral b.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1967
- Accession Number
- AD0702869
Entities
People
- Arthur F. Veinott Jr.
- George Bernard Dantzig
Organizations
- Stanford University