Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Matroid representation
Summary
In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of representation provide abstract algebraic structures (matroids and groups respectively) with concrete descriptions in terms of linear algebra.
A linear matroid is a matroid that has a representation, and an F-linear matroid (for a field F) is a matroid that has a representation using a vector space over F. Matroid representation theory studies the existence of representations and the properties of linear matroids.
A (finite) matroid is defined by a finite set (the elements of the matroid) and a non-empty family of the subsets of , called the independent sets of the matroid. It is required to satisfy the properties that every subset of an independent set is itself independent, and that if one independent set is larger than a second independent set then there exists an element that can be added to to form a larger independent set. One of the key motivating examples in the formulation of matroids was the notion of linear independence of vectors in a vector space: if is a finite set or multiset of vectors, and is the family of linearly independent subsets of , then is a matroid.
More generally, if is any matroid, then a representation of may be defined as a function that maps to a vector space , with the property that a subset of is independent if and only if is injective and is linearly independent. A matroid with a representation is called a linear matroid, and if is a vector space over field F then the matroid is called an F-linear matroid. Thus, the linear matroids are exactly the matroids that are isomorphic to the matroids defined from sets or multisets of vectors. The function will be one-to-one if and only if the underlying matroid is simple (having no two-element dependent sets).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.