Rota's basis conjecture, named after the mathematician Gian-Carlo Rota, is an unproven conjecture in linear algebra and matroid theory concerning rearrangements of bases of a vector space. Rota formulated the conjecture in 1989, though its statement was first published by Tim Huang and Rota in a 1994 paper.
Facts
StatementIf X is a vector space of dimension n, or more generally a matroid of rank n, with n disjoint bases, then it is possible to arrange the elements of these bases into an n by n matrix so that the rows of the matrix are exactly the given bases and the columns of the matrix are also bases. 1 Proposed Year Difficulty Hint Partially Attested
Progress Toward ResolutionThe conjecture has been proven for paving matroids for all n, and for the case n less than or equal to 3 for all types of matroid; for arbitrary matroids it is possible to arrange the basis elements so the first Omega(sqrt n) columns are bases. 1 Full conjecture remains open for general matroids; only special cases and partial bounds are proven. Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source Rota's Basis Conjecture (Wikipedia)
Posed By
Source Rota's Basis Conjecture (Wikipedia)
Sources
1. Rota's Basis Conjecture (Wikipedia)
Lead section
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.
Partial results
The statement of Rota's basis conjecture was first published by Huang & Rota (1994), crediting it (without citation) to Rota in 1989.
Partial results
The basis conjecture has been proven for paving matroids (for all n) and for the case n ≤ 3 (for all types of matroid).
Lead section, difficulty hint
an unproven conjecture concerning rearrangements of bases
Posed By: Gian-Carlo Rota, Lead sentence
In linear algebra and matroid theory, Rota's basis conjecture is an unproven conjecture concerning rearrangements of bases, named after Gian-Carlo Rota.
In Branch: Linear Algebra, Lead sentence
In linear algebra and matroid theory, Rota's basis conjecture is an unproven conjecture concerning rearrangements of bases, named
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.