Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Matroid representation
Résumé
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).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.