Editing Matroid (section)

=== Rank functions <span class="anchor" id="rank_func_anchor"></span> ===
It is a basic result of matroid theory, directly analogous to a similar theorem of [[basis (linear algebra)|bases in linear algebra]], that any two bases of a matroid <math> M </math> have the same number of elements.  This number is called the ''[[matroid rank|rank]]'' {{nobr|of <math> M</math>.}} If <math> M </math> is a matroid on <math>E</math>, and <math>A</math> is a subset of <math>E</math>, then a matroid on <math> A </math> can be defined by considering a subset of <math> A </math> to be independent if and only if it is independent in <math> M</math>. This allows us to talk about ''submatroids'' and about the rank of any subset of <math> E</math>. The rank of a subset <math>A</math> is given by the ''[[matroid rank|rank function]]'' <math> r(A) </math> of the matroid, which has the following properties:<ref name=w7-9/>

*(R1) The value of the rank function is always a non-negative [[integer]].

*(R2) For any subset <math>A\subset E</math>, we have <math>r(A) \le |A|</math>. 

*(R3) For any two subsets <math>A, B\subset E</math>, we have: <math> r(A \cup B) + r(A \cap B) \le r(A) + r(B)</math>. That is, the rank is a [[submodular function]].

*(R4) For any set <math>A</math> and element <math> x</math>, we have: <math> r(A) \le r( A \cup \{x\} ) \le r(A) + 1</math>. From the first inequality it follows more generally that, if <math> A \subseteq B \subseteq E</math>, then <math> r(A) \leq r(B )\leq r(E)</math>. That is, rank is a [[monotonic function]].

These properties can be used as one of the alternative definitions of a finite matroid: If <math> (E,r) </math> satisfies these properties, then the independent sets of a matroid over <math> E </math> can be defined as those subsets <math> A </math> of <math>E</math> with <math> r(A) = |A|</math>. In the language of [[partially ordered set]]s, such a matroid structure is equivalent to the [[geometric lattice]] whose elements are the subsets <math> A \subset M</math>, partially ordered by inclusion.

The difference <math>|A| - r(A)</math> is called the ''nullity'' of the subset <math> A</math>. It is the minimum number of elements that must be removed from <math> A </math> to obtain an independent set. The nullity of <math>E</math> in <math>M</math> is called the nullity of <math> M</math>. The difference <math>r(E) - r(A)</math> is sometimes called the ''corank'' of the subset <math>A</math>.