A Colorful Determinantal Identity, a Conjecture of Rota, and Latin Squares

Shmuel Onn ^{∗}

Technion - Israel Institute of Technology 32000 Haifa, Israel onn@ie.technion.ac.il

1 Rota’s Colorful Conjecture and the Latin Square Conjecture

The following outstanding conjecture in combinatorial linear algebra is due to Gian-Carlo Rota.

Rota’s Colorful Conjecture. Let ^{1}W, …, ^{n}W be bases of an n-dimensional vector space. Then their multiset union can be repartitioned into bases ^{1}U, …, ^{n}U such that | ^{i}U ∩ ^{j}W | = 1 for all i, j.

Regarding the vectors in each ^{i}W as colored in color i, the sought new bases are colorful, namely contain one vector of each color. So Rota’s Colorful Conjecture is that any n colored bases of an n-dimensional vector space could be repartitioned into n colorful bases.

A Latin square of order n is an n by n matrix L = (L_{i}^{j}) in which each row and each column is a permutation of {1, …, n}. More precisely, there are permutations σ_{1}, …, σ_{n} and π_{1}, …, π_{n} such that L_{i}^{j} = σ_{i}(j) = π_{j}(i) for all i, j. The sign of the Latin square is defined as the product of all signs of its row and column permutations

sgn(L) = ∏_{i=1}^{n} sgn(σ_{i}) · sgn(π_{i}).

A Latin square is even if its sign is positive, and odd otherwise. Let l(n) be the number of even Latin squares of order n minus the number of odd ones. It is easy to see that l(n) = 0 for all odd n. The following conjecture is due to Noga Alon and Michael Tarsi.

Latin Square Conjecture. The number of even Latin squares of order n minus the number of odd ones satisfies l(n) ≠ 0 for all even n.

∗Partially supported by the Alexander von Humboldt Stiftung, and by Technion VPR Funds no. 191-181 and 191-198

This conjecture has been recently proved by Drisko for all n = p + 1 where p is a prime. The exact values of l(n) are known only for n ≤ 8 [?]. It is plausible that l(n) is in fact nonnegative for all n.

In this note we establish an identity, the Colorful Determinantal Identity, which links the two conjectures. It shows that for any n, the Latin Square Conjecture implies Rota’s Colorful Conjecture. In particular, Rota’s Colorful Conjecture is true for any n = p + 1 where p is a prime. To compactly express the identity, denote by S_{n} the symmetric group of permutations on {1, …, n} and by S^{n} = ×_{n}S_{n} the collection of n-tuples ρ = (ρ_{1}, …, ρ_{n}) of permutations. For ρ ∈ S^{n} let sgn(ρ) = ∏_{i=1}^{n} sgn(ρ_{i}). For a matrix W over a field F, denote by W_{i} its i-th row vector and by W^{j} its j-th column vector, regarded as elements of the vector space F^{n}, and by W_{i}^{j} its (i, j)-th entry. The proof of the following theorem is given in Section 2.

Theorem 1 (Colorful Determinantal Identity). For any n matrices ^{1}W, …, ^{n}W of order n over any field F there holds

∑_{ρ∈S^{n}} sgn(ρ) ∏_{i=1}^{n} det ( ^{1}W^{ρ_{1}(i)}, …, ^{n}W^{ρ_{n}(i)}) = l(n) · ∏_{j=1}^{n} det( ^{j}W).

Note that for each ρ ∈ S^{n}, the tuples (^{1}W^{ρ_{1}(i)}, …, ^{n}W^{ρ_{n}(i)}) , i = 1, …, n, which appear in the left hand side of the identity, give a colorful repartition of the multiset of column vectors of the ^{j}W.

Corollary 1. For any even n the Latin Square Conjecture implies Rota’ Colorful Conjecture over any field F whose characteristic does not divide l(n) (in particular characteristic zero).

Proof of Corollary 1 from Theorem 1. Suppose that l(n) ≠ 0 and let ^{1}W, …, ^{n}W be given bases, i.e. nonsingular matrices of order n over a field satisfying the hypothesis. Then the right hand side of the Colorful Determinantal Identity is nonzero. Therefore, on the left hand side, there must exist a nonzero summand

∏_{i=1}^{n} det ( ^{1}W^{ρ_{1}(i)}, …, ^{n}W^{ρ_{n}(i)}) , and so the sets ^{i}U = {^{1}W^{ρ_{1}(i)}, …, ^{n}W^{ρ_{n}(i)}} , i = 1, …, n,

give the desired repartition into colorful bases.

Corollary 1 had been independently obtained by Huang and Rota, but their derivation is quite complex and indirect and involves an intermediate conjecture of Rota on a certain straightening coefficient in the so-called supersymmetric bracket algebra [?].

Rota’s Colorful Conjecture has an obvious generalization to matroids. Also, it has a generalization due to Jeff Kahn that concerns n^{2} bases, for which we have derived an identity reminiscent of Theorem 1. See [?] for the precise statement of Kahn’s conjecture, [?] for a recent proof of a very special case of Kahn’s conjecture, known as the Dinitz problem, and [?] for some related algorithmic problems and ordered relatives of Rota’s conjecture.

2 The Colorful Determinantal Identity

Proof of Theorem 1. Given n square matrices ^{1}W, …,^{n} W of size n, define the following polynomial in their entries:

Δ = ∑_{σ,ρ∈S^{n}} sgn(σ)sgn(ρ) ∏_{i,j=1}^{n} ^{j}W_{σ_{i}(j)}^{ρ_{j}(i)}.

For each ρ and σ in S^{n} define

Δ^{ρ} = ∑_{σ∈S^{n}} sgn(σ) ∏_{i,j=1}^{n} ^{j}W_{σ_{i}(j)}^{ρ_{j}(i)} = ∏_{i=1}^{n} ∑_{σ_{i}∈S_{n}} sgn(σ_{i}) ∏_{j=1}^{n} ^{j}W_{σ_{i}(j)}^{ρ_{j}(i)} = ∏_{i=1}^{n} det ( ^{1}W^{ρ_{1}(i)}, …, ^{n}W^{ρ_{n}(i)}) ,

Δ_{σ} = ∑_{ρ∈S^{n}} sgn(ρ) ∏_{i,j=1}^{n} ^{j}W_{σ_{i}(j)}^{ρ_{j}(i)} = ∏_{j=1}^{n} ∑_{ρ_{j}∈S_{n}} sgn(ρ_{j}) ∏_{i=1}^{n} ^{j}W_{σ_{i}(j)}^{ρ_{j}(i)} = ∏_{j=1}^{n} det ( ^{j}W_{σ_{1}(j)}, …, ^{j}W_{σ_{n}(j)}) .

Now Δ_{σ} is nonzero only for σ = (σ_{1}, …, σ_{n}) ∈ S^{n} for which there exists an element π = (π_{1}, …, π_{n}) in S^{n} such that σ_{i}(j) = π_{j}(i) for all i, j, in which case

Δ_{σ} = ∏_{j=1}^{n} det ( ^{j}W_{π_{j}(1)}, …, ^{j}W_{π_{j}(n)}) = sgn(π) ∏_{j=1}^{n} det ( ^{j}W_{1}, …, ^{j}W_{n}) = sgn(π) ∏_{j=1}^{n} det( ^{j}W).

Each σ ∈ S^{n} for which such π ∈ S^{n} exists gives a Latin square L via L_{i}^{j} = σ_{i}(j) = π_{j}(i), whose sign is given by sgn(L) = sgn(σ)sgn(π). Denote by L the set of all Latin squares of order n. Then

∑_{ρ∈S^{n}} sgn(ρ)Δ^{ρ} = Δ = ∑_{σ∈S^{n}} sgn(σ)Δ_{σ} = ∑_{L∈L} sgn(L) ∏_{j=1}^{n} det( ^{j}W) = l(n) ∏_{j=1}^{n} det( ^{j}W),

which is precisely the Colorful Determinantal Identity.

Acknowledgement

The author thanks Noga Alon and Ron Holzman for some related discussions.

References

[1] I. Bárány and S. Onn, Colorful linear programming, Lecture Notes in Computer Science, Vol. 1084, 15 pages, Springer-Verlag, June 1996, in press.

[2] F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B, 63:153-158, 1995.

[3] R. Huang and G.C. Rota, On the relations of various conjectures on Latin squares and straightening coefficients, Discr. Math., 128:225–236, 1994.

[4] J.C.M. Janssen, On even and odd Latin squares, J. Combin. Theory Ser. A, 69:173–181, 1995.