Discrete and Algorithmic Mathematics Red de Matemática Discreta y Algorítmica

Recent Trends XIII: Classification of matroid representations

15 Jan 2026

Matroids are a combinatorial object that capture the essence of linear dependence beyond the setting of vector spaces. They generalize notions of independence in linear algebra and graph theory [23]. A matroid is an ordered pair $M=(E,r)$ where $E$ is a finite set called the ground set and $r:2^E\to\mathbb{Z}_{\geq 0}$ is the rank function satisfying the following conditions, called the matroid axioms:

  1. For any $A\subseteq E$, $r(A) \leq \lvert A \rvert$ (normalization).

  2. For any $A\subseteq B \subseteq E$, $r(A)\leq r(B)$ (monotonicity).

  3. For any $A,B\subseteq E$ $r(A\cup B)+ r(A\cap B)\leq r(A) + r(B)$ (submodularity).

Independent sets in a matroid are the subsets $S\subseteq E$ such that $r(S)=|S|$ and maximal independent sets are called bases, whereas minimal dependent sets are called circuits. The terminology used for these two type of objects reflects the origins of matroids as a generalization of linear algebra (bases) and graph theory (circuits).

Configuration of vectors in a vector space $V$ over a field in terms of its linear independence defines a matroid. The dimension of the subspaces that span the set of vectors is the rank function of a matroid and matroids obtained in this way are called linear or representable matroids. A natural generalization of this class are multilinear matroids, which are defined from configurations of subspaces of a vector space. Results on characterization of representable matroids are based on techniques that use rank inequalities [12, 18] and common information [1, 8].

When trying to generalize these objects, representations over skew fields are considered. Skew-linear matroids are those representable over a division ring and they were recently characterized in [9] using tensor products. A simultaneous generalization of representability was done in [19] where they defined representation on skew partial fields as a proper generalization of skew-linear matroids. This new class of matroids proportioned a correspondence between multilinear representation of matroids over a field $\mathbb{F}$ and representations over a skew partial field whose elements are invertible matrices $n\times n$ over $\mathbb{F}$.

In the information theoretic study of matroids, Fujishige [11] observed that the entropic vector of a set of discrete random variables $X_1,\ldots,X_n$ is the rank function of a polymatroid with ground set $E={1,\ldots,n}$, i.e. for any $A\subseteq E$,

\[r(A)=H(\{X_i:i\in A\}).\]

Matroids with rank function being multiple an entropic vector are called entropic, or partition representable. Rank functions of matroids can also be limits of entropic vectors, this is the case of almost entropic matroids. Non-Shannon inequalities are used to deduce that a matroid does not admit an entropic representation. Almost entropic matroids satisfy the Ahlswede-Körner property and this can be used to characterize matroids out of the entropic cone closure.

In the transcendental field extension theory, the algebraic dependence exhibits a matroid structure as well. Let $\mathbb{H}$ be a purely transcendental field extension of a field $\mathbb{G}$. A family of elements $(a_i)_{i\in E}$ in $\mathbb{H}$ determines an algebraic matroid with rank function given by

\[r(A)=\mathop{\mathrm{trdeg}}_\mathbb{G}(a_i:i\in A)\]

where $\mathop{\mathrm{trdeg}}_\mathbb{G}$ denotes the transcendence degree of $\mathbb{G}(a_i:i\in A)$ over $\mathbb{G}$. In this case, independent sets are algebraically independent transcendental elements over a field. An equivalent definition of algebraic matroids that establishes connections with matroids and algebraic geometry is given in [20] where the circuits are determined by some circuit polynomials of a prime ideal. A subclass of algebraic matroids that satisfies the desired properties of matroids as preservation duality, deletion and contraction are algebraic matroids arising from one-dimensional groups [2]. Several techniques for detecting non-algebraic matroids appear in the literature. First, Bollen used Frobenius flocks to show that there are non-algebraic matroids on 9 points [10]. Second, information theoretic properties are used in [6] to find non-algebraic matroids on 9 and 10 points.

The way that these three families of classes connect gives us a better understanding of how far can we go with this combinatorial object. The figure below illustrates the current knowledge about the connections of the aforementioned classes of matroids.

First, it is well known that linear matroids and multilinear matroids are entropic. Multilinear matroids that are not representable exist but and the problem whether there exists an entropic non multilinear matroid is an open problem [21]. More general representations over partial or skew fields are still object to study [19, 4, 13, 9] since it is not fully characterized how do these more general classes relate with algebraic, entropic or almost entropic matroids.

The relations between algebraic and entropic representations are due to Matúš, that showed that there exist algebraic matroids that are not entropic [16] and recently proved that algebraic matroids are almost entropic [17]. This result was used later in [6] to find some non-algebraic matroids using Ahlswede-Körner extension properties that characterize almost entropic matroids. Also, algebraic matroids generalize linear representations but do not generalize multilinear ones. Ben-Efraim [5] showed the existence of a non-algebraic multilinear matroid, presenting the first known case of an entropic matroid non-algebraic.

[16] [21] [5] [22]

This combinatorial object is widely connected to the cryptographic primitive of secret sharing schemes [3] and related to the almost affine codes in coding theory [21]. A secret sharing scheme is a method to protect a secret. Given a secret, the scheme consists on generating pieces of information, called shares, in such a way that the secret can be recovered from some subsets of shares, called authorized. The collection of authorized subsets is the access structure of the scheme.

Brickell and Davenport [3] proved that the access structure of an ideal secret sharing scheme determines a matroid. As a consequence, matroids that admit ideal secret sharing schemes are indeed entropic [16] while ports of linear matroids are precisely the access structures of ideal linear secret sharing schemes [3]. This connection has been partially extended to polynomial schemes and algebraic matroids [7].

Characterizing whether an access structure is entropic or not is determining in the problem of finding ideal secret sharing schemes for a given access structure. Algorithmically the problem is proven to be undecidable [14, 15]. However, the problem of finding more general representations, like algebraic or skew-field ones for a given matroid is still open.

Overall, the interrelation between matroid theory and secret sharing not only enriches the combinatorial theory of matroids but also provides a rigorous framework for determining the feasibility and efficiency of secret sharing schemes. Further progress will require new insights into the representability and entropy properties of matroids beyond the linear and multilinear settings.

References

  1. Bamiloshin, M., Ben-Efraim, A., Farràs, O. and Padró, C. Common Information, Matroid Representation, and Secret Sharing for Matroid Ports. Designs, Codes, And Cryptography. pp. 1-24 (2021)
  2. Bollen, G., Cartwright, D. and Draisma, J. Matroids Over One-Dimensional Groups. International Mathematics Research Notices. 2022(3):2298-2336 (2020)
  3. Brickell, E. and Davenport, D. On the Classification of Ideal Secret Sharing Schemes. Journal of Cryptology, 4(73):123-134 (1991)
  4. Bollen, G., Draisma, J. and Pendavingh, R. Algebraic matroids and Frobenius flocks. Advances In Mathematics. 323 pp. 688-719 (2018)
  5. Ben-Efraim, A. Secret-sharing matroids need not be algebraic. Discrete Mathematics. 339(8):2136-2145 (2016)
  6. Bamiloshin, M. and Farràs, O. Optimizing extension techniques for discovering non-algebraic matroids. Journal Of Algebraic Combinatorics. 62(3) (2025)
  7. Beimel, A., Farràs, O. and Moya, A. Polynomial Secret Sharing Schemes and Algebraic Matroids. TCC 2025. 16269 pp. 428-461 (2025)
  8. Bamiloshin, M., Farràs, O. and Padró, C. A note on extension properties and representations of matroids. Discrete Applied Mathematics.376 pp. 270-280 (2025)
  9. Bérczi, K., Gehér, B., Imolay, A., László, L., Padro, C. and Schwarcz, T. Interaction between skew-representability, tensor products, extension properties, and rank inequalities. arxiv.org (2025), https://arxiv.org/abs/2507.10709 (to appear in SODA 2026)
  10. Bollen, G. Frobenius flocks and algebraicity of matroids. Phd thesis, Mathematics and Computer Science, Technische Universiteit Eindhoven, (2018)
  11. Fujishige, S. Polymatroidal dependence structure of a set of random variables. Information and Control, 39(1-3):55-72 (1978)
  12. Ingleton, A. Conditions for representability and transversality of matroids. Théorie Des Matroïdes. pp. 62-66 (1971)
  13. Kühne, L., Pendavingh, R. and Yashfe, G. Von Staudt constructions for skew-linear and multilinear matroids. Combinatorial Theory. (2023)
  14. Kühne, L. and Yashfe, G. Representability of matroids by c-arrangements is undecidable. Israel Journal Of Mathematics. 252, 95-147 (2022)
  15. Kühne, L. and Yashfe, G. On entropic and almost multilinear representability of matroids. arxiv.org (2025), https://arxiv.org/abs/2206.03465
  16. Matúš, F. Matroid representations by partitions. Discrete Mathematics. 203 pp. 169-194 (1999)
  17. Matúš, F. Algebraic matroids are almost entropic. Proc. Amer. Math. Soc. 152 pp. 1-6 (2024)
  18. Mayhew, D. and Royle, G. Matroids with nine elements. Journal Of Combinatorial Theory, Series B. 98, 415-431 (2008)
  19. Pendavingh, R. and Zwam, S. Skew partial fields, multilinear representations of matroids, and a matrix tree theorem. Advances In Applied Mathematics. 50, 201-227 (2013)
  20. Rosen, Z., Sidman, J. and Theran, L. Algebraic matroids in action. arxiv.org, (2019), https://arxiv.org/abs/1809.00865
  21. Simonis, J. and Ashikhmin, A. Almost Affine Codes. Designs, Codes and Cryptography, 14(2):179-197 (1998)
  22. Seymour, P. On secret-sharing matroids. Journal Of Combinatorial Theory, Series B. 56, 69-73 (1992)
  23. Whitney, H. On the Abstract Properties of Linear Dependence. American Journal Of Mathematics. 57, 509-533 (1935)

The author of this post, Adriana Moya Viñas is a doctoral researcher at the Universitat Rovira i Virgili.

Related posts