mathematics

Rota's basis conjecture

Rota's basis conjecture is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Rota's basis conjecture rather than just read about it. In short: In linear algebra and matroid theory, Rota's basis conjecture is an unproven conjecture concerning rearrangements of bases, named after Gian-Carlo Rota. It states that, if X is either a vector space of dimension n or more generally a matroid of rank n, with n disjoint bases Bi, then it is possible to arrange the elements of these bases into an n × n matrix in such a way that the rows of the matrix are exactly the gi…

Key takeaways

Rota's basis conjecture belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Rota's basis conjecture to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Rota's basis conjecture from memory before moving on to harder problems.

Reference excerpt

In linear algebra and matroid theory, Rota's basis conjecture is an unproven conjecture concerning rearrangements of bases, named after Gian-Carlo Rota. It states that, if X is either a vector space of dimension n or more generally a matroid of rank n, with n disjoint bases Bi, then it is possible to arrange the elements of these bases into an n × n matrix in such a way that the rows of the matrix are exactly the given bases and the columns of the matrix are also bases. That is, it should be possible to find a second set of n disjoint bases Ci, each of which consists of one element from each of the bases Bi.

Examples

Rota's basis conjecture has a simple formulation for points in the Euclidean plane: it states that, given three triangles with distinct vertices, with each triangle colored with one of three colors, it must be possible to regroup the nine triangle vertices into three "rainbow" triangles having one vertex of each color. The triangles are all required to be non-degenerate, meaning that they do not have all three vertices on a line. To see this as an instance of the basis conjecture, one may use either linear independence of the vectors ( x i , y i , 1 {\displaystyle x_{i},y_{i},1} ) in a three-dimensional real vector space (where ( x i , y i {\displaystyle x_{i},y_{i}} ) are the Cartesian coordinates of the triangle vertices) or equivalently one may use a matroid of rank three in which a set S of points is independent if either |S| ≤ 2 or S forms the three vertices of a non-degenerate triangle. For this linear algebra and this matroid, the bases are exactly the non-degenerate triangles. Given the three input triangles and the three rainbow triangles, it is possible to arrange the nine vertices into a 3 × 3 matrix in which each row contains the vertices of one of the single-color triangles and each column contains the vertices of one of the rainbow triangles.s Analogously, for points in three-dimensional Euclidean space, the conjecture states that the sixteen vertices of four non-degenerate tetrahedra of four different colors may be regrouped into four rainbow tetrahedra.

Partial results The statement of Rota's basis conjecture was first published by Huang & Rota (1994), crediting it (without citation) to Rota in 1989. The basis conjecture has been proven for paving matroids (for all n) and for the case n ≤ 3 (for all types of matroid). For arbitrary matroids, it is possible to arrange the basis elements into a matrix the first Ω(√n) columns of which are bases. The basis conjecture for linear algebras over fields of characteristic zero and for even values of n would follow from another conjecture on Latin squares by Alon and Tarsi. Based on this implication, the conjecture is known to be true for linear algebras over the real numbers for infinitely many values of n.

Related problems In connection with Tverberg's theorem, Bárány & Larman (1992) conjectured that, for every set of r (d + 1) points in d-dimensional Euclidean space, colored with d + 1 colors in such a way that there are r points of each color, there is a way to partition the points into rainbow simplices (sets of d + 1 points with one point of each color) in such a way that the convex hulls of these sets have a nonempty intersection. For instance, the two-dimensional case (proven by Bárány and Larman) with r = 3 states that, for every set of nine points in the plane, colored with three colors and three points of each color, it is possible to partition the points into three intersecting rainbow triangles, a statement similar to Rota's basis conjecture which states that it is possible to partition the points into three non-degenerate rainbow triangles. The conjecture of Bárány and Larman allows a collinear triple of points to be considered as a rainbow triangle, whereas Rota's basis conjecture disallows this; on the other hand, Rota's basis conjecture does not require the triangles to have a common intersection. Substantial progress on the conjecture of Bárány and Larman was made by Blagojević, Matschke & Ziegler (2009).

See also Rota's conjecture, a different conjecture by Rota about linear algebra and matroids

References

External links Rota's basis conjecture, Open Problem Garden.

Worked examples

Example 1 — a first encounter with Rota's basis conjecture

Start with the simplest possible case. Write down what Rota's basis conjecture claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Rota's basis conjecture before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Rota's basis conjecture ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Rota's basis conjecture

In research: Rota's basis conjecture appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Rota's basis conjecture in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Rota's basis conjecture is common in secondary-school and first-year university syllabi. It links to neighbouring topics Conjectures, Linear algebra, Matroid theory, so understanding it makes those chapters shorter.
In everyday life: Look for Rota's basis conjecture outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Rota's basis conjecture” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Rota's basis conjecture in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Rota's basis conjecture means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Rota's basis conjecture out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Rota's basis conjecture in simple terms?

Why does Rota's basis conjecture matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Rota's basis conjecture?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Rota's basis conjecture.