Jump to content

User:Obelixm2/Ingleton Inequality

From Wikipedia, the free encyclopedia

Ingleton's inequality is an inequality that is satisfied by the rank function of any representable matroid in this sense it is a necessary condition for representability of a matroid over a finite field. Let M be a matroid and let ρ be its ran function, Ingleton inequality states that for any subsets X1, X2, X3 and X4 in the support of M, the inequality

ρ(X1)+ρ(X2)+ρ(X1∪X2∪X3)+ρ(X1∪X2∪X4)+ρ(X3∪X4) ≤ ρ(X1∪X2)+ρ(X1∪X3)+ρ(X1∪X4)+ρ(X2∪X3)+ρ(X2∪X4)

is satisfied.


Aubrey William Ingleton, an english mathematician, wrote an important paper in 1969[1] 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, Matroid Theory, and Network Coding[2].


Importance of inequality

[edit]

There are interesting connections between matroids, the entropy region and group theory. 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 capacities. Linear coding solutions are constrained by the inequality and it has an important consequence:

The region of achievable rates using linear network coding could be, in some cases, strictly smaller than the region of achievable rates using general network coding [3] [4][5] .


For definitions see, e.g. [6]


Proof

[edit]

Theorem (Ingleton's Inequality)[7]: Let M be a representable matroid with rank function ρ and let X1, X2, X3 and X4 be subsets of the support set of M, denoted by the symbol E(M). Then:


ρ(X1)+ρ(X2)+ρ(X1∪X2∪X3)+ρ(X1∪X2∪X4)+ρ(X3∪X4) ≤ ρ(X1∪X2)+ρ(X1∪X3)+ρ(X1∪X4)+ρ(X2∪X3)+ρ(X2∪X4).


To prove the inequality we have to show the following result:


Proposition: Let V1,V2, V3 and V4 be subspaces of a vector space V, then

  1. dim(V1∩V2∩V3) ≥ dim(V1∩V2) + dim(V3) - dim(V1+V3) - dim(V2+V3) + dim(V1+V2+V3)
  2. dim(V1∩V2∩V3∩V4) ≥ dim(V1∩V2∩V3) + dim(V1∩V2∩V4) - dim(V1∩V2)
  3. dim(V1∩V2∩V3∩V4) ≥ dim(V1∩V2) + dim(V3) + dim(V4) - dim(V1+V3) - dim(V2+V3) - dim(V1+V4) - dim(V2+V4) - dim(V1+V2+V3) + dim(V1+V2+V4)
  4. dim (V1) + dim(V2) + dim(V1+V2+V3) + dim(V1+V2+V4) + dim(V3+V4) ≤ dim(V1+V2) + dim(V1+V3) + dim(V1+V4) + dim(V2+V3) + dim(V2+V4)

Where Vi+Vj represent the direct sum 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 (V1∩V2) + V3 ⊆ (V1+ V2) ∩ (V2+V3), then

dim((V1∩V2)+V3) ≤ dim((V1+V2)∩(V2+V3)), hence
dim(V1∩V2∩V3) = dim(V1∩V2) + dim(V3) - dim((V1∩V2)+V3)
≥ dim(V1∩V2) + dim(V3) - dim((V1+V3)∩(V2+V3))
= dim(V1∩V2) + dim(V3) – {dim(V1+V3) + dim(V2+V3) – dim(V1+V2+V3)}
= dim(V1∩V2) + dim(V3) – dim(V1+V3) - dim(V2+V3) + dim(V1+V2+V3)

2. It is clear that (V1∩V2∩V3) + (V1∩V2∩V4) ⊆ (V1∩V2), then

dim{(V1∩V2∩V3)+(V1∩V2∩V4)} ≤ dim(V1∩V2), hence
dim(V1∩V2∩V3∩V4) = dim(V1∩V2∩V3) + dim(V1∩V2∩V4) - dim{(V1∩V2∩V3) + (V1∩V2∩V4)}
≥ dim(V1∩V2∩V3) + dim(V1∩V2∩V4) - dim(V1∩V2)

3. From (1) and (2) we have:

dim(V1∩V2∩V3∩V4) ≥ dim(V1∩V2∩V3) + dim(V1∩V2∩V4) - dim(V1∩V2)
≥ dim(V1∩V2) + dim(V3) - dim(V1+V3) - dim(V2+V3) + dim(V1+V2+V3) + dim(V1∩V2) + dim(V4) - dim(V1+V4) - dim(V2+V4) + dim(V1+V2+V4) - dim(V1∩V2)
= dim(V1∩V2) + dim(V3) + dim(V4) - dim(V1+V3) - dim(V2+V3) - dim(V1+V4) - dim(V2+V4) + dim(V1+V2+V3) + dim(V1+V2+V3)

4. From (3) we have

dim(V1+V2+V3) + dim(V1+V2+V4) ≤ dim(V1∩V2∩V3∩V4) - dim(V1∩V2) - dim(V3) - dim(V4) + dim(V1+V3)+ dim(V2+V3) + dim(V1+V4) + dim(V2+V4)

If we add (dim(V1)+dim(V2)+dim(V3+V4)) at both sides of the last inequality, we get

dim(V1) + dim(V2) + dim(V1+V2+V3) + dim(V1+V2+V4) + dim(V3+V4) ≤ dim(V1∩V2∩V3∩V4) - dim(V1∩V2) + dim(V1+dim(V2) + dim(V3+V4) - dim(V3) - dim(V4) + dim(V1+V3) + dim(V2+V3) + dim(V1+V4) + dim(V2+V4)

Since the inequality dim(V1∩V2∩V3∩V4) ≤ dim(V3∩V4) holds, we have finished with the proof.♣

Proof (Ingleton's inequality): Suppose that M is a representable matroid and let A = [v1 v2 … vn] be a matrix such that M = M(A). For X, Y ⊆ E(M) = {1,2, … ,n}, define U = <{Vi : i ∈ X }>, as the span of the vectors in Vi, and we define W = <{Vj : j ∈ Y }> accordingly.

If we suppose that U = <{u1, u2, … ,um}> and W = <{w1, w2, … ,wr}> then clearly we have <{u1, u2, …, um, w1, w2, …, wr }> = U + W.

Hence: r(X∪Y) = dim <{vi : i ∈ X } ∪ {vj : j ∈ Y }> = dim(V + W).

Finally, if we define Vi = {vr : r ∈ Xi } for i = 1,2,3,4, then by last inequality and the item (4) of the above proposition, we get the result.♣

Biography Note

[edit]

(Taken by [8])

Abrey William Ingleton (1920-2000) was born in Chester, London. He studied Mathematics at King’s College London where excelled as student. As mathematician his contributions were numerous and impressive. His works are realted to many different topics in Analysis, Geometry, Algebra, Topology, Combinatorics and Algebraic Geometry. It is said that many of his contributions emerged from discussions with colleagues, he had the ability of detecting the essential points.

We are interested in his works on matroids and specifically the paper "Representation of matroids" published in 1969. In his work Ingleton studied matroids as a generalization of the concept of linear independence. The paper aforementioned is a survey about representable matroids as it exhibited matroids representable over C but not over R and similarly over R but not over Q. He included in his paper a single theorem which is a necessary condition of the representability of matroids. This condition is known in the literature as Ingleton's Inequality.

Ingleton's papers

[edit]
  1. ‘Hahn-Banach theorem for non-Archimedean-valued fields’. Proc. Cambridge Philos. Soc. 48 (1) (1952) 41-45.
  2. ‘The Lorentz transformation’. Nature 171 (1953) 618.
  3. ‘The rank f circulant matrices’. J. London Math. Soc. 31 (19569 455-460.
  4. ‘A note on independence function and rank’. J. London Math. Soc. 34 (1959) 49-56.
  5. (with D. B. Scott) ‘The tangent direction bundle of an algebraic variety and generalized Jacobians of linear systems’. Ann. Mat. Pura Appl. (4) 56 (1961) 359-373.
  6. ‘A problem in linear inequalities’. Proc. London Math. Soc. (3) 16 (1966) 519-536.
  7. ‘Tangent flag bundles and generalized Jacobian varieties I’. Atti. Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. (8) 46 (1969) 323-329.
  8. ‘Tangent flag bundles and generalized Jacobian varieties II’. Atti. Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. (8) 46 (1969) 505-510.
  9. ‘The linear cmplementary problem’. J. London Math. Soc. (2) 2 (1970) 330-336.
  10. ‘Representation of matroids’. Combinatorial mathematics and its applications, Proc. Conf., Oxford, 1969 (Academic Press, London, 1971) 149-167.
  11. ‘A geometrical characterization of transversal independence structures’. Bull. London Math. Soc. 3 (1971) 47-51.
  12. ‘Conditions for representability and transversality of matroids’. Théorie des matroïdes (Rencontre Franco-Britannique, Brest, 1970), Lecture Notes in Mathematics 211 (Springer, Berlin, 1971) 62-66.
  13. (with F. D. J. Dunstan and D. J. A. Welsh) ‘Supermatroids’. Combinatorics, Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972 (Inst. Math. Appl., Southend-on-Sea, 1972) 72-122.
  14. Notes on integration, revised edition (Mathematical Institute, Oxford University, Oxford, 1972).
  15. (with M. J. Piff) ‘Gammoids and transversal matroids’. J. Combin. Theory Ser. B 15 (1973) 51-68.
  16. (with S. A. Ilori and A. T. Lascu) ‘On a formula of D. B. Scott’. J. London Math. Soc. (2) 8 (1974) 539-544.
  17. (with R. A. Main) ‘Non-algebraic matroids exist’. Bull. London Math Soc. 7 (1975) 144-146.
  18. ‘Non-base-ordenable matroids’. Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975). Congr. Numer. 15 (1976) 355-359.
  19. (with J. A. Bondy) ‘Pancyclic graphs II’. J. Combin. Theory Ser. B 20 (1976) 41-46.
  20. ‘Transversal maroids and related structures’. Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 31 (1977) 117-131.
  21. (with S. A. Ilori) ‘Tangent flag bundles and Jacobian varieties I’. Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. (8) 67 (1979) 259-302.
  22. (with S. A. Ilori) ‘Tangent flag bundles and Jacobian varieties II’. Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. (8) 68 (1980) 52-62.
  23. (with S. A. Ilori) ‘Tangent flag bundles and Jacobian varieties III’. Atti Accad. Naz. Lincei Cl. Sci. Fis. Mat. Natur. (8) 68 (1980) 106-110.
  24. ‘An introduction to nonstandard analysis’. Bull. Inst. Math. Appl. 18 (1982) 34-37.
[edit]
  • "Transmission rate of a channel", Encyclopedia of Mathematics, EMS Press, 2001 [1994]

References

[edit]
  1. ^ Ingleton, A.W. (1971), "Representation of matroids", in Welsh, D.J.A. (ed.), Combinatorial mathematics and its applications. Proceedings, Oxford, 1969, Academic Press, pp. 149–167, ISBN 0-12-743350-3, Zbl 0222.05025
  2. ^ Ahlswede, R.; Ning Cai; Li, S.-Y.R.; Yeung, R.W. (2000). "Network Information Flow". IEEE Transactions on Information Theory, IT-46. 46 (4): 1204–1216. doi:10.1109/18.850663.{{cite journal}}: CS1 maint: date and year (link)
  3. ^ Dougherty, R. (2005). "Insufficiency of Linear Network Codes". IEEE International Symposium on Information Theory Adelaide, Australia: 264–267. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
  4. ^ Dougherty, R. (2007). "Networks, matroids, and non-Shannon information inequalities". IEEE Transactions on Information Theory. 53 (6): 1949–1969. doi:10.1109/TIT.2007.896862. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
  5. ^ S.-Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE Trans. Inf. Theory, vol. 49, no. 2, pp. 371–381, Feb. 2003
  6. ^ Bassoli, R.B.; Marques, H.M.; Rodriguez, J.; KS Shum; R. T. Tafazolli; "Network Coding Theory: A Survey", IEEE Communications Surveys and Tutorials, Vol. 99, No. 0, pp. 1 - 29, February, 2013
  7. ^ Oxley, James (1992), Matroid Theory, Oxford: Oxford University Press, ISBN 0-19-853563-5, MR 1207587, Zbl 0784.05002.
  8. ^ Barnard, A. D. (2004). "Aubrey William Ingleton (1920–2000)". Bulletin of the London Mathematical Society. 36: 119–129. doi:10.1112/S0024609303002443.
Retrieved from "https://en.wikipedia.org/w/index.php?title=User:Obelixm2/Ingleton_Inequality&oldid=1259443883"