linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrices ...

and

matroid theory In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

, Rota's basis conjecture is an unproven conjecture concerning rearrangements of bases, named after

Gian-Carlo Rota Gian-Carlo Rota (April 27, 1932 – April 18, 1999) was an Italian-American mathematician and philosopher. He spent most of his career at the Massachusetts Institute of Technology, where he worked in combinatorics, functional analysis, proba ...

. It states that, if ''X'' is either a

vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...

of dimension ''n'' or more generally a matroid of rank ''n'', with ''n'' disjoint bases ''B_i'', then it is possible to arrange the elements of these bases into an ''n'' × ''n''

matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

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 ''C_i'', each of which consists of one element from each of the bases ''B_i''.

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 In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts are ...

of the vectors (

x_,y_,1

) in a three-dimensional

real Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...

vector space (where (

x_,y_

) 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. 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 , crediting it (without citation) to Rota in 1989.. See in particular Conjecture 4, p. 226. The basis conjecture has been proven for

paving matroid In the mathematical theory of matroids, a paving matroid is a matroid in which every circuit has size at least as large as the matroid's rank. In a matroid of rank r every circuit has size at most r+1, so it is equivalent to define paving matroids ...

s (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 Ω() 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 square In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin sq ...

s by Alon and Tarsi. Based on this implication, the conjecture is known to be true for linear algebras over the

real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...

s for infinitely many values of ''n''.

Related problems

In connection with

Tverberg's theorem In discrete geometry, Tverberg's theorem, first stated by , is the result that sufficiently many points in ''d''-dimensional Euclidean space can be partitioned into subsets with intersecting convex hulls. Specifically, for any set of :(d + 1)(r ...

, conjectured that, for every set of ''r'' (''d'' + 1) points in ''d''-dimensional

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...

, 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 ..

References

{{reflist

External links

Rota's basis conjecture
Open Problem Garden. Linear algebra Matroid theory Conjectures Unsolved problems in geometry

Examples

Partial results

Related problems

See also

References

External links