In mathematics, Ingleton's inequality is an
inequality
Inequality may refer to:
Economics
* Attention inequality, unequal distribution of attention across users, groups of people, issues in etc. in attention economy
* Economic inequality, difference in economic well-being between population groups
* ...
that is satisfied by the
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* H ...
function of any
representable matroid. In this sense it is a necessary condition for representability of a
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
over a finite field. Let ''M'' be a matroid and let ''ρ'' be its rank function, Ingleton's inequality states that for any subsets ''X''
1, ''X''
2, ''X''
3 and ''X''
4 in the
support
Support may refer to:
Arts, entertainment, and media
* Supporting character
Business and finance
* Support (technical analysis)
* Child support
* Customer support
* Income Support
Construction
* Support (structure), or lateral support, a ...
of ''M'', the inequality
:''ρ''(''X''
1)+''ρ''(''X''
2)+''ρ''(''X''
1∪''X''
2∪''X''
3)+''ρ''(''X''
1∪''X''
2∪''X''
4)+''ρ''(''X''
3∪''X''
4) ≤ ''ρ''(''X''
1∪''X''
2)+''ρ''(''X''
1∪''X''
3)+''ρ''(''X''
1∪''X''
4)+''ρ''(''X''
2∪''X''
3)+''ρ''(''X''
2∪''X''
4) is satisfied.
Aubrey William Ingleton, an English mathematician, wrote an important paper in 1969
in which he surveyed the representability problem in matroids. Although the article is mainly expository, in this paper Ingleton stated and proved Ingleton's inequality, which has found interesting applications in
information theory
Information theory is the scientific study of the quantification (science), quantification, computer data storage, storage, and telecommunication, communication of information. The field was originally established by the works of Harry Nyquist a ...
,
matroid theory
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in ...
, and
network coding In computer networking, linear network coding is a program in which intermediate nodes transmit data from source nodes to sink nodes by means of linear combinations.
Linear network coding may be used to improve a network's throughput, efficiency, ...
.
Importance of inequality
There are interesting connections between
matroids
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in ...
, the
entropy region and
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
. Some of those connections are revealed by Ingleton's Inequality.
Perhaps, the more interesting application of Ingleton's inequality concerns the computation of
network coding In computer networking, linear network coding is a program in which intermediate nodes transmit data from source nodes to sink nodes by means of linear combinations.
Linear network coding may be used to improve a network's throughput, efficiency, ...
capacities.
Linear coding solutions are constrained by the inequality and it has an important consequence:
:The region of achievable rates using
linear network coding In computer networking, linear network coding is a program in which intermediate nodes transmit data from source nodes to sink nodes by means of linear combinations.
Linear network coding may be used to improve a network's throughput, efficiency, ...
could be, in some cases, strictly smaller than the region of achievable rates using general network coding.
For definitions see, e.g.
Proof
Theorem (Ingleton's inequality):
[Oxley, James (1992), Matroid Theory, Oxford: Oxford University Press, , MRbr>1207587]
Zblbr>0784.05002
Let ''M'' be a
representable matroid with rank function ''ρ'' and let ''X''
1, ''X''
2, ''X''
3 and ''X''
4 be subsets of the support set of ''M'', denoted by the symbol ''E''(''M''). Then:
:''ρ''(''X''
1)+''ρ''(''X''
2)+''ρ''(''X''
1∪''X''
2∪''X''
3)+''ρ''(''X''
1∪''X''
2∪''X''
4)+''ρ''(''X''
3∪''X''
4) ≤ ''ρ''(''X''
1∪''X''
2)+''ρ''(''X''
1∪''X''
3)+''ρ''(''X''
1∪''X''
4)+''ρ''(''X''
2∪''X''
3)+''ρ''(''X''
2∪''X''
4).
To prove the inequality we have to show the following result:
Proposition: Let ''V''
1,''V''
2, ''V''
3 and ''V''
4 be subspaces of a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
''V'', then
# dim(''V''
1∩''V''
2∩''V''
3) ≥ dim(''V''
1∩''V''
2) + dim(''V''
3) − dim(''V''
1+''V''
3) − dim(''V''
2+''V''
3) + dim(''V''
1+''V''
2+''V''
3)
# dim(''V''
1∩''V''
2∩''V''
3∩''V''
4) ≥ dim(''V''
1∩''V''
2∩''V''
3) + dim(''V''
1∩''V''
2∩''V''
4) − dim(''V''
1∩''V''
2)
# dim(''V''
1∩''V''
2∩''V''
3∩''V''
4) ≥ dim(''V''
1∩''V''
2) + dim(''V''
3) + dim(''V''
4) − dim(''V''
1+''V''
3) − dim(''V''
2+''V''
3) − dim(''V''
1+''V''
4) − dim(''V''
2+''V''
4) − dim(''V''
1+''V''
2+''V''
3) + dim(''V''
1+''V''
2+''V''
4)
# dim (''V''
1) + dim(''V''
2) + dim(''V''
1+''V''
2+''V''
3) + dim(''V''
1+''V''
2+''V''
4) + dim(''V''
3+''V''
4) ≤ dim(''V''
1+''V''
2) + dim(''V''
1+''V''
3) + dim(''V''
1+''V''
4) + dim(''V''
2+''V''
3) + dim(''V''
2+''V''
4)
Where ''V''
i+''V''
j represent the
direct sum
The direct sum is an operation between structures in abstract algebra, a branch of mathematics. It is defined differently, but analogously, for different kinds of structures. To see how the direct sum is used in abstract algebra, consider a more ...
of the two subspaces.
Proof (proposition): We will use frequently the standard vector space identity:
dim(''U'') + dim(''W'') = dim(''U''+''W'') + dim(''U''∩''W'').
1. It is clear that (''V''
1∩''V''
2) + ''V''
3 ⊆ (''V''
1+ ''V''
3) ∩ (''V''
2+''V''
3), then
2. It is clear that (''V''
1∩''V''
2∩''V''
3) + (''V''
1∩''V''
2∩''V''
4) ⊆ (''V''
1∩''V''
2), then
3. From (1) and (2) we have:
4. From (3) we have
If we add (dim(''V''
1)+dim(''V''
2)+dim(''V''
3+''V''
4)) at both sides of the last inequality, we get
Since the inequality dim(''V''
1∩''V''
2∩''V''
3∩''V''
4) ≤ dim(''V''
3∩''V''
4) holds, we have finished with the proof.♣
Proof (Ingleton's inequality): Suppose that ''M'' is a representable matroid and let ''A'' =
'v''1 ''v''2 … ''v''nbe a matrix such that ''M'' = ''M''(''A'').
For ''X'', ''Y'' ⊆ E(''M'') = , define ''U'' = <>, as the
span of the vectors in ''V''
i, and we define ''W'' = <> accordingly.
If we suppose that ''U'' = <> and ''W'' = <> then clearly we have <> = ''U'' + ''W''.
Hence:
''r''(''X''∪''Y'') = dim < ∪ > = dim(''V'' + ''W'').
Finally, if we define ''V''
i = for i = 1,2,3,4, then by last inequality and the item (4) of the above proposition, we get the result.
References
External links
* {{springer, title=Transmission rate of a channel, id=p/t093890
Inequalities
Matroid theory