Matroid Rank¶

Matroid rank assigns each subset the maximum size of an independent subset, encoding a finite matroid as an integer-valued set function.

Version: v1 · 2026-10-03 · History
Domain-specific #: 13421
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Matroid Theory → Mathematics
Aliases: Rank Function of a Matroid

Core Idea¶

For a finite matroid \(M=(E,\mathcal I)\), matroid rank is the function \(r:2^E\to\mathbb Z_{\ge0}\) given by \(r(S)=\max\{|I|:I\subseteq S,\ I\in\mathcal I\}\). It asks how many elements of a selected subset can be retained without dependence. The rule applies to every subset, not merely to the entire ground set. In a vector matroid it counts the dimension of a span; in a graphic matroid it counts edges of a maximal forest. These are different independence tests that instantiate the same rank relation.^[1]^[2]

Rank is an equivalent description of a finite matroid: its normalized bounds, monotonicity and submodularity constrain the integers in a way that recovers matroid independence. This does not make rank and matroid synonymous. A matroid is the whole independence structure; rank is one precise functional presentation of it.^[1]^[2]

Structural Signature¶

Sig role-phrases:

Ground set and query subset: a finite \(E\) supplies elements and each \(S\subseteq E\) is a separate rank query. Restricting to \(r(E)\) alone discards the function's structure.
Independence criterion: \(\mathcal I\) determines which contained sets are feasible. Replace linear independence by acyclicity and one gets a different matroid but the same rank construction.
Maximum-cardinality operation: rank uses a largest independent subset of \(S\), not an arbitrary selected set. Picking a nonmaximal forest would undercount graph rank.
Coherent rank values: \(0\le r(S)\le |S|\), monotonicity, and \(r(A\cup B)+r(A\cap B)\le r(A)+r(B)\) link all subset answers. A table of unrelated numbers is not a rank function.^[1]^[2]

Condensed: subset \(S\) + independence rule → greatest feasible cardinality \(r(S)\) → coherent set function.

What It Is Not¶

Not only total rank. \(r(E)\) is one value; two matroids can share it while differing on proper subsets.
Not matrix rank as an unqualified synonym. Matrix-column rank realizes this function only after columns form the ground set and linear independence defines feasibility.
Not cardinality. When a chosen set contains dependent vectors or a graph cycle, \(r(S)<|S|\).
Not any submodular score. The finite matroid characterization also requires integer-valued rank, normalization/bounds and monotonicity; a real-valued coverage score may be submodular without being matroid rank.
Not automatically an infinite-matroid formula. This entry states the finite-ground-set axioms; infinite matroids need separate rank treatment.

Scope of Application¶

The home is finite matroid theory and the combinatorial settings it models. For columns of a matrix, \(r(S)\) is the dimension of the span of columns selected by \(S\). For a graph with fixed vertex set \(V\), \(r(S)=|V|-c(V,S)\), where \(c(V,S)\) is the number of connected components of the spanning subgraph containing precisely the chosen edges; isolated vertices count. For uniform \(U(k,n)\), any at most \(k\) elements are independent and \(r(S)=\min(k,|S|)\). Each expression answers the same maximum-independent-subset question by a different concrete test.^[1]^[2]

The live Matroid entry already includes rank among its equivalent invariants. A rank-function article is justified at a narrower level because its subset argument, inequalities, marginal gains and computation merit their own explanation; it must not recast the entire matroid entry as its child.^[1]

Clarity¶

Rank resolves a common conflation between number of selected elements and number of independent degrees of choice. Three nonzero vectors in a plane can give \(|S|=3\) yet \(r(S)=2\); three edges of a triangle have the same count/rank gap. It also separates the value \(r(E)\) from the function \(S\mapsto r(S)\). State the ground set and independence rule before quoting a rank: “rank two” alone cannot say which subset or which matroid is meant.

Manages Complexity¶

Independent-set lists can be large. Rank compresses their essential maximal-cardinality information into one integer for each subset, while its axioms summarize how those integers fit together. In a graph, a component count computes rank without enumerating every forest. The compression has a price: \(r(S)=2\) does not identify which two vectors form a basis or which edge closes a cycle. A witness basis or circuit is needed when the task is selection or diagnosis rather than capacity measurement.^[2]

Abstract Reasoning¶

Given an independence test, evaluate \(r(S)\) by finding a maximal independent subset. Conversely, for a valid finite rank function, classify \(S\) as independent exactly when \(r(S)=|S|\). This makes dependence testable without listing \(\mathcal I\). Monotonicity says adding candidates cannot reduce attainable independent size. Submodularity says overlap matters when comparing combined subsets; the marginal rank gain of an added element cannot increase as the starting set grows. A zero marginal gain in a vector example means the added column lies in the current span; in a graphic example it means the added edge joins vertices already connected by the selected edges.^[1]^[2]

Those deductions require the finite matroid axioms. A generic monotone score does not license the independence inference, and a particular algorithm for finding \(r(S)\) depends on the concrete representation.

Knowledge Transfer¶

Within matroid theory the rank lens carries from linear to graphic to uniform independence without replacing their domain-specific tests. The formula \(r(S)=\max |I|\) stays literal; “independent” changes its realization. This is stronger than a metaphor about organizational “rank.” Outside a matroid or proven rank-axiom setting, the same word does not transfer the theorem. The live Matroid parent bears the broader exchange structure, while this entry explains its rank-function presentation.

Examples¶

Three columns in a plane¶

Let \(E=\{a,b,c\}\) with columns \(a=(1,0)\), \(b=(0,1)\), \(c=(1,1)\) in \(\mathbb R^2\). Each nonzero singleton has rank one; \(r(\{a,b\})=2\); \(r(E)=2\) because \(c=a+b\). The third column increases \(|E|\) but not dimension. This is a small constructed instance of the linear-matroid rule in the Stanford notes, not a claim about an observed dataset.^[1]

Mapped back: the three columns are the ground set and any chosen columns are \(S\); linear independence is the criterion; the maximum independent subset of \(E\) has size two; boundedness and a zero marginal gain when \(c\) joins \(\{a,b\}\) exhibit coherent rank values.

Triangle edges¶

Let \(E\) be the three edges of a triangle on vertex set \(V=\{u,v,w\}\). Every one- or two-edge subset is acyclic and has rank equal to its size. All three edges contain a cycle, so a maximal forest has two edges and \(r(E)=2=|V|-1\). If one counts a spanning subgraph on more vertices, isolated vertices enter both \(|V|\) and the component count; the result remains the forest size.^[1]^[2]

Mapped back: the edges form the ground set and an edge selection is \(S\); acyclicity is the independence criterion; a largest forest supplies maximum cardinality; the cycle-closing edge adds zero rank, matching the rank axioms.

Uniform two-of-four constraint¶

In \(U(2,4)\), the four labeled elements are \(E\) and any subset of size at most two is independent. Thus \(r(S)=\min(2,|S|)\); a third or fourth element is available but cannot raise feasible independent size. Unlike the vector and triangle examples, no geometry or connectivity determines dependence—only the cardinality cap does.^[1]

Mapped back: the four labels are the ground set; “size at most two” is the independence criterion; the maximum feasible subset has size \(\min(2,|S|)\); additional elements past the cap have zero marginal rank gain.

Structural Tensions¶

Numerical compression versus dependence witness. A rank oracle answers how many independent elements can be taken from each \(S\), making proofs and comparisons compact. Selecting an actual basis or explaining a failed addition requires the elements and often a circuit; carrying those witnesses costs more computation and exposition than quoting \(r(S)\). Diagnostic: does the user need attainable size, or the specific independent choice and reason for exclusion?

Abstract equivalence versus concrete computation. Rank axioms give one mathematics for vector spaces, graphs and uniform systems. To calculate a value, however, one must use span/dimension, graph components, or a cardinality cap; treating the common axioms as a ready-made efficient oracle conceals that work. Leaning entirely on a concrete implementation helps calculation but obscures transferable rank deductions. Diagnostic: is the present task proving a rank-law claim or obtaining \(r(S)\) for this representation?

Structural–Framed Character¶

Matroid rank sits near the structural end: the function and axioms determine membership independent of whether a human likes a result. Evaluative weight enters when one selects a modeling criterion for “independence,” not in the rank inequalities once a matroid is fixed. Human practice supplies the choice of vectors, graph edges or uniform constraints, but no institution constitutes the mathematical function; historical teaching conventions merely standardize notation. The vocabulary travels literally among matroid realizations because \(S\mapsto r(S)\) obeys the same definition. Importing “rank” into a job hierarchy without a matroid independence system is only word reuse, whereas recognizing an actual rank-axiom structure in a new finite system is genuine transfer. Its character: a formal structural function whose applicability is bounded by the finite matroid axioms rather than by analogy with any ranking.

Structural Core vs. Domain Accent¶

The skeletal relation is an admissibility rule assigning each subset its maximal feasible cardinality. In the live catalog this belongs under the broader Matroid structure, which supplies exchange and the independence family. The domain-bound mechanism is the integer rank function on a finite ground set with matroid-specific normalization, monotonicity and submodularity; vector dimension and graph forest size are concrete computations. The named entry does not clear the prime bar because replacing matroid independence with a generic capacity, organizational rank or arbitrary submodular valuation loses the characterization and deductions. A more portable “maximum feasible subset size” idea would need a separate, tested future-prime question, not an asserted parent here.

This entry presupposes Matroid.

The live Matroid entry is a strict prerequisite under composition/presupposes, not a subtype genus: rank requires an underlying independence structure satisfying matroid axioms, while a matroid can be described by bases or circuits without treating its rank-function presentation as the whole bearer. No prime edge follows merely from the words “measure” or “independence.”

Relationships to Other Abstractions¶

Current abstraction Matroid Rank Domain-specific

Parents (1) — more general patterns this builds on

Matroid Rank presupposes Matroid Domain-specific

Matroid rank requires a matroid independence structure but is not itself a matroid subtype.

Hierarchy path (1) — routes to 1 parentless root

Matroid Rank → Matroid

Neighborhood in Abstraction Space¶

Matroid Rank sits in a sparse region of the domain-specific corpus (74^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Codes, Matrices & Combinatorial Problems (30 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Matroid is the whole independence structure. Generic rank may mean matrix rank, order, hierarchy or another invariant without the all-subsets matroid function. Submodular function is a broader class; submodularity alone is insufficient. Dual-matroid rank is a rank function of the dual matroid, not a synonym for the original \(r\). A graph's edge count is \(|S|\), which differs from rank when \(S\) contains a cycle.

References¶

[1] Jan Vondrák, Stanford matroid lecture notes, §2.3 and examples, definition and linear, graphic, uniform instances. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i

[2] Michel Goemans, MIT matroid notes, rank properties, graphic formula and submodularity. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g