The Ingleton inequalities are the inequality constraints known to be required of representable matroids. For a matroid ofnelements, there are 16nIngleton inequalities. In this paper, we show that many of these inequalities are redundant. We explicitly determine the unique minimal set of Ingleton inequalities, which number on the order of 6n/4-O(5n). In information theory, these inequalities are required of the entropy functions of certain random variables constructed from linear subspaces. As a result, these inequalities appear as constraints in linear programming outer bounds for the capacity region of multisource network coding where the codes are required to be linear. Ingleton inequalities have also played an instrumental role in demonstrating the insufficiency of linear codes for multisource network coding. The reduction that we obtain for Ingleton inequalities is sufficiently large to meaningfully reduce the complexity of these linear programming bounds.

The Ingleton-LP bound is an outer bound for the multicast capacity region, assuming the use of linear network codes. Computation of the bound is performed on a polyhedral cone obtained by taking the intersection of half-spaces induced by the basic (Shannon-type) inequalities and Ingleton inequalities. This paper simplifies the characterization of this cone, by obtaining the unique minimal set of Ingleton inequalities. As a result, the effort required for computation of the Ingleton-LP bound can be greatly reduced.