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
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. 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 Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source Rota's Basis Conjecture (Wikipedia)
Sources
1. Rota's Basis Conjecture (Wikipedia)
Lead section, formal statement
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 x 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.
History section
first published by Huang and Rota (1994), crediting it (without citation) to Rota in 1989.
Partial results section
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 Omega(sqrt(n)) columns of which are bases.
- Lead section
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.