# The Alon-Tarsi basis conjecture

**Conjecture**If are invertible matrices with entries in for a prime , then there is a submatrix of so that is an AT-base.

**Definition:** If is an matrix over a field of characteristic , then we say that is an *Alon-Tarsi basis* (or AT-basis) if the permanent of the matrix obtained by stacking copies of is nonzero.

It follows from the Alon-Tarsi polynomial technique that if is an AT-base then for every of size 2 and for every , there exists a vector so that (using the notation from A nowhere-zero point in a linear mapping, is (2,1)-choosable). It follows from this that every Alon-Tarsi base over is also an additive basis. Thus, the above conjecture, if true, would imply The additive basis conjecture. The following strengthening of this conjecture was suggested in [D]

**Conjecture (The strong Alon-Tarsi basis conjecture (DeVos))**If are invertible matrices with entries in a field of characteristic , then we may partition the columns of into an matrix and an matrix so that is an AT-base and is invertible.

In addition to implying the conjecture, above, if true, this conjecture would imply both The permanent conjecture and The choosability in conjecture.