A matroid is an object which encodes independence structure on a set $E$. Familiar examples include linear independence, or algebraic independence. Every matroid has a collection $\mathrm{Ind}$ of subsets of $E$ which are called independent sets. These subsets must satisfy several axioms (see Matroid from Independent Sets). Given $\mathrm{Ind}$, we have the following definitions:

Bases : a subset of $E$ is a basis if it is a maximal independent set.

Dependent Sets : a subset of $E$ is a dependent set if it is not an independent set.

Circuits : a subset of $E$ is a circuit if it is a minimal dependent set.

Rank : a subset of $E$ has rank equal to the size of its largest independent subset.

Flats : a subset of $E$ is a flat if it is inclusionwise maximal among sets with the same rank.

Hyperplanes : a subset of $E$ is a hyperplane if it is a flat of rank one less than the rank of the matroid.

The information encoded in any of the above properties of a matroid defines the matroid. To construct a matroid explicitly from this information, certain axioms must hold, as detailed in the sections below. Alternatively, one may construct a matroid from a collection of other mathematical objects - in these cases, the axioms always hold.

Currently, there are three mathematical objects from which you can directly construct a matroid.

To define a matroid directly, you provides a ground set, $E$, and one or more of the independent sets, bases, dependent sets, circuits, rank, flats, and hyperplanes. If you provide the rank function, you specify it as a procedure $r$ that maps a subset of $E$ to a nonnegative integer. The other items are provided as a list $s$ of subsets of $E$.

If you know more than one way to define the same matroid, you can provide them all. This may allow Maple to more efficiently do subsequent computations.

For each direct construction of a matroid, certain axioms on $s$ (or $r$) must hold; a different set of axioms for each of the types of information you can provide. For completeness, we give these axioms below. See [OXL] for more details.

Warning: Currently, the Matroid constructor does not validate these axioms. It is the responsibility of the user to verify that the input is valid, and that, if more than one item is provided, they define the same matroid.

A gallery of example matroids can be loaded using the command with(ExampleMatroids).

$\mathrm{with}\left(\mathrm{Matroids}\right)\:$

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{with}\left(\mathrm{PolynomialIdeals}\right)\:$

$\mathrm{with}\left(\mathrm{ExampleMatroids}\right)\:$

$A≔\mathrm{Matrix}\left(\left[\left[1\,1\,1\,0\,0\,0\right]\,\left[0\,0\,0\,1\,1\,1\right]\,\left[1\,0\,0\,1\,0\,0\right]\,\left[0\,1\,0\,0\,1\,0\right]\,\left[0\,0\,1\,0\,0\,2\right]\right]\right)$

$A≔\left[\begin{array}{cccccc}1& 1& 1& 0& 0& 0\\ 0& 0& 0& 1& 1& 1\\ 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 1& 0\\ 0& 0& 1& 0& 0& 2\end{array}\right]$

$M≔\mathrm{Matroid}\left(A\right)$

$M≔⟨\begin{array}{c}\mathrm{th\ⅇ\; lin\ⅇar\; matroi\ⅆ\; whos\ⅇ\; groun\ⅆ\; s\ⅇt\; is\; th\ⅇ\; s\ⅇt\; of\; column\; v\ⅇctors\; of\; th\ⅇ\; matrix:}\\ \left[\begin{array}{cccccc}1& 1& 1& 0& 0& 0\\ 0& 0& 0& 1& 1& 1\\ 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 1& 0\\ 0& 0& 1& 0& 0& 2\end{array}\right]\end{array}⟩$

$B≔\mathrm{Bases}\left(M\right)$

$B≔\left[\left\{1\,2\,3\,4\,6\right\}\,\left\{1\,2\,3\,5\,6\right\}\,\left\{1\,3\,4\,5\,6\right\}\,\left\{2\,3\,4\,5\,6\right\}\right]$

$A≔\mathrm{Matrix}\left(\left[\left[1\,-1\,0\right]\,\left[1\,1\,0\right]\,\left[1\,1\,1\right]\right]\right)$

$A≔\left[\begin{array}{ccc}1& \mathrm{-1}& 0\\ 1& 1& 0\\ 1& 1& 1\end{array}\right]$

$\mathrm{Bases}\left(\mathrm{Matroid}\left(A\right)\right)$

$\left[\left\{1\,2\,3\right\}\right]$

$\mathrm{Bases}\left(\mathrm{Matroid}\left(A\,2\right)\right)$

$\left[\left\{1\,3\right\}\,\left\{2\,3\right\}\right]$

$G≔\mathrm{Graph}\left(\left\{\left\{a\,x\right\}\,\left\{a\,y\right\}\,\left\{b\,x\right\}\,\left\{b\,y\right\}\,\left\{c\,x\right\}\,\left\{c\,y\right\}\right\}\right)$

$G≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 5\; vertices\; and\; 6\; edge(s)}$

$\mathrm{DrawGraph}\left(G\right)$

$M≔\mathrm{Matroid}\left(G\right)$

$M≔⟨\begin{array}{c}\mathrm{th\ⅇ\; graphic\; matroi\ⅆ\; on\; th\ⅇ\; graph:}\\ \mathrm{PLOT}\left(\mathrm{...}\right)\end{array}⟩$

$C≔\mathrm{Circuits}\left(M\right)$

$C≔\left[\left\{''a\_x''\,''a\_y''\,''b\_x''\,''b\_y''\right\}\,\left\{''a\_x''\,''a\_y''\,''c\_x''\,''c\_y''\right\}\,\left\{''b\_x''\,''b\_y''\,''c\_x''\,''c\_y''\right\}\right]$

$J≔⟨x^2-y\,xz-y^2\,xy-z⟩$

$J≔⟨x^2-y\,xz-y^2\,xy-z⟩$

$M≔\mathrm{Matroid}\left(J\right)$

$M≔⟨\begin{array}{c}\mathrm{th\ⅇ\; alg\ⅇbraic\; matroi\ⅆ\; on\; th\ⅇ\; polynomial\; i\ⅆ\ⅇal:}\\ ⟨x^2-y\,xz-y^2\,xy-z⟩\end{array}⟩$

$\mathrm{Bases}\left(M\right)$

$\left[\left\{1\right\}\,\left\{2\right\}\,\left\{3\right\}\right]$

$M≔\mathrm{Matroid}\left(\left[1\,2\,3\right]\,\mathrm{bases}=\left[\left\{1\,2\right\}\,\left\{1\,3\right\}\,\left\{2\,3\right\}\right]\right)$

$M≔⟨\mathrm{th\ⅇ\; uniform\; matroi\ⅆ\; of\; rank\; 2\; on\; 3\; \ⅇl\ⅇm\ⅇnts}⟩$

$M≔\mathrm{Matroid}\left(\left[1\,2\,3\right]\,\mathrm{bases}=\left[\left\{1\,2\right\}\,\left\{1\,3\right\}\,\left\{2\,3\right\}\right]\,\mathrm{circuits}=\left[\left\{1\,2\,3\right\}\right]\right)$

$M≔⟨\mathrm{th\ⅇ\; uniform\; matroi\ⅆ\; of\; rank\; 2\; on\; 3\; \ⅇl\ⅇm\ⅇnts}⟩$

James G. Oxley. Matroid Theory (Oxford Graduate Texts in Mathematics). New York: Oxford University Press. 2006.