Vector Matroid

linear-algebra discrete-mathematics combinatorics

Definition

Vector Matroid

A vector matroid (also called a linear matroid) is a matroid $M=(E,\mathcal{I})$ whose ground set $E$ is a finite set of vectors in a vector space $V$ over a field $F$, and whose independent sets are the linearly independent subsets of $E$:

$$\mathcal{I}=\{X\subseteq E\mid X\text{ is linearly independent}\}.$$

Why the axioms hold

• Non-emptiness: the empty set of vectors is linearly independent.
• Heredity: a subset of a linearly independent set is linearly independent.
• Exchangeability: if $|X|<|Y|$ with both independent, then $\mathrm{span}(X)$ has smaller dimension than $\mathrm{span}(Y)$, so some $e\in Y$ lies outside $\mathrm{span}(X)$, and $X\cup \{e\}$ is independent.