Home » Subject » Combinatorics » Matrices

The permanent conjecture

Importance: Medium ✭✭
Author(s): Kahn, Jeff
Subject: Combinatorics
» Matrices
Keywords: invertible
matrix
permanent
Recomm. for undergrads: no
Prize: none
Posted by: mdevos
on: March 8th, 2007
Conjecture   If $ A $ is an invertible $ n \times n $ matrix, then there is an $ n \times n $ submatrix $ B $ of $ [A A] $ so that $ perm(B) $ is nonzero.

If true, this conjecture would imply the nowhere-zero point in a linear mapping conjecture via the Alon-Tarsi polynomial technique. I believe Yang Yu was the first to suggest the following generalization of the permanent conjecture.

Conjecture  (Yu)   If $ A,B $ are invertible $ n \times n $ matrices over the same field, then there is an $ n \times n $ submatrix $ C $ of $ [A B] $ so that $ perm(C) $ is nonzero.

This conjecture when restricted to the field $ {\mathbb Z}_3 $ is a consequence of the Alon-Tarsi basis conjecture. In addition to implying the above conjecture, the truth of this conjecture for matrices over the field $ {\mathbb Z}_3 $ would imply that every 6-edge-connected graph has a nowhere-zero 3-flow, thus resolving The weak 3-flow conjecture.

add new comment