Matroid Theory

Here we introduce matroidal concepts related to Rigidity Theory.

Definition 45 (Matroid)

A matroid \(\mathcal{M}=(E, \mathcal{I})\) is a pair consisting of a finite set \(E\) (called the ground set) and \(\mathcal{I}\) is a family of subsets of \(E\) (called the independent sets) with the following properties:

  • \(\emptyset \in \mathcal{I}\);

  • for every \(A \subset B \subset E\), if \(B \in \mathcal{I}\) then \(A \in \mathcal{I}\); and

  • if \(A,B\in \mathcal{I}\) and \(|A|>|B|\) then there exists \(x\in A\setminus B\) such that \(B\cup \{x\}\in \mathcal{I}\).

A subset of the ground set \(E\) that is not independent is called dependent. A maximal independent set – that is, an independent set that becomes dependent upon adding any element of \(E\) – is called a basis for the matroid. A circuit is a minimal dependent subset of \(E\) – that is, a dependent set whose proper subsets are all independent.

Definition 46 (Rank function and closure)

The rank function \(r\) of a matroid \(\mathcal{M}\) is the function \(r \colon E \rightarrow \NN\) such that \(r(A)=\max\{|I| \colon I\subset A, I \in \mathcal{I} \}\). The rank function has the following properties:

  • for any \(A\subset E\), \(0\leq r(A) \leq |A|\);

  • any two subsets \(A,B\subset E\), \(r(A\cap B) + r(A\cup B) \leq r(A)+r(B)\); and

  • any \(A\subset E\) and any \(x\notin A\), \(r(A) \leq r(A\cup \{x\}) \leq r(A)+1\).

For \(A\subset E\), the closure of \(A\) is the set \(\textrm{cl}(A)=\{x\in E: r(A)=r(A\cup \{x\}) \}\).

Definition 47 (Rigidity matroid)

The \(d\)-dimensional rigidity matroid of a framework \((G, p)\) in \(\mathbb{R}^d\) is the row matroid of the rigidity matrix \(R_d(G,p)\). That is, a set \(F\subseteq E\) is independent whenever the corresponding rows of \(R_d(G,p)\) are linearly independent.

Definition 48 (Generic rigidity matroid)

The generic \(d\)-dimensional rigidity matroid of a graph \(G=(V,E)\) is the matroid \(\mathcal{R}_d(G)\) on \(E\) in which a set of edges \(F\subseteq E\) is independent whenever the corresponding rows of \(R_d(G,p)\) are independent, for some (or equivalently every) generic realization \(p\) of \(G\).