# Accession Number:

## AD0702869

# Title:

## INTEGRAL EXTREME POINTS

# Descriptive Note:

## Technical rept.

# Corporate Author:

## STANFORD UNIV CA OPERATIONS RESEARCH HOUSE

# Personal Author(s):

# Report Date:

## 1967-11-01

# Pagination or Media Count:

## 8.0

# 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.

# Descriptors:

# Subject Categories:

- Operations Research