---
tag: QTSQR7130G
kind: concept
name: Basis of a matroid
msc: [05B35]
sources:
  - url: https://en.wikipedia.org/wiki/Basis_of_a_matroid
same_as:
  wikidata: Q104866035
  wikipedia: Basis of a matroid
---

## Summary

A basis of a [[matroid|PX31ZNYS3Z]] is a maximal independent set.
All bases of a matroid have the same size, the [[rank|SYRCTH853H]] of the matroid, and they satisfy an exchange property.
The bases determine the matroid, and they generalize both [[bases|0KCQ9Y3QKA]] of a vector space and [[spanning trees|0S4ZEZM7KE]] of a connected graph.

## Explanations

### L1 human

Keep adding elements to an independent set as long as it stays independent; when you cannot add any more, you have a basis.
For vectors in a plane, any two non-parallel vectors form a basis.
For a connected graph with the matroid of forests, the bases are exactly the spanning trees.
Any two bases have the same number of elements.