\documentclass[11pt]{article}

\textheight20cm
\textwidth16.7cm
\oddsidemargin-0.6cm
\topmargin-0.9cm

\newcommand{\bpr}{\par{\it Proof}. \ignorespaces}
\newcommand{\epr}{{\ \vbox{\hrule\hbox{%
\vrule height1.3ex\hskip0.8ex\vrule}\hrule
}}\\\par}
\newcommand{\mepr}{{\ \ \ \vbox{\hrule\hbox{%
\vrule height1.3ex\hskip0.8ex\vrule}\hrule
}}}

\title{\huge A Colorful Determinantal Identity, a Conjecture of Rota,
and Latin Squares}
\author{Shmuel Onn
\thanks{Partially supported by the Alexander von Humboldt Stiftung,
and by Technion VPR Funds no. 191-181 and 191-198}\\
{\small Technion - Israel Institute of Technology}\\
{\small 32000 Haifa, Israel}\\
{\small onn@ie.technion.ac.il}
}

\date{}

\begin{document}
\bibliographystyle{plain}
\maketitle

\renewcommand{\S}{{\cal S}^n}
\newcommand{\sgn}{\mbox{sgn}}
\newcommand{\F}{{\cal F}}
\renewcommand{\L}{{\cal L}}
\newcommand{\T}{{\cal T}}

\section{Rota's Colorful Conjecture and the Latin Square Conjecture}
The following outstanding conjecture in combinatorial linear algebra
is due to Gian-Carlo Rota.

\bigskip
\noindent
{\bf Rota's Colorful Conjecture.}
Let $^1W,\dots,\ ^nW$ be bases of an $n$-dimensional vector space.
Then their multiset union can be repartitioned into
bases $^1U,\dots,\ ^nU$ such that $|\ ^iU\cap\ ^jW|=1$ for all $i,j$.

\bigskip
\noindent
Regarding the vectors in each $^iW$ as {\em colored} in color $i$,
the sought new bases are {\em 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.

\bigskip
A {\em 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,\dots,n\}$.
More precisely, there are permutations $\sigma_1,\dots,\sigma_n$
and $\pi_1,\dots,\pi_n$ such that $L_i^j=\sigma_i(j)=\pi_j(i)$ for
all $i,j$. The {\em sign} of the Latin square is defined as the product of
all signs of its row and column permutations
$$\sgn(L)=\prod_{i=1}^n\sgn(\sigma_i)\cdot\sgn(\pi_i).$$
A Latin square is {\em even} if its sign is positive, and {\em 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.

\bigskip
\noindent
{\bf Latin Square Conjecture.}
The number of even Latin squares of order $n$ minus the number of odd ones
satisfies $l(n)\neq 0$ for all even $n$.

\bigskip
\noindent
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\leq 8$
\cite{Jan}. It is plausible that $l(n)$ is in fact nonnegative for all $n$.

\bigskip
In this note we establish an identity, the {\em 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,\dots,n\}$ and by $\S=\times_n S_n$ the collection of
$n$-tuples $\rho=(\rho_1,\dots,\rho_n)$ of permutations. For $\rho\in\S$
let $\sgn(\rho)=\prod_{i=1}^n\sgn(\rho_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.

\bigskip
\noindent
{\bf Theorem 1 (Colorful Determinantal Identity).}
For any $n$ matrices $^1W,\dots,\ ^nW$ of order $n$ over any field $\F$
there holds
\begin{eqnarray*}
\sum_{\rho\in\S}\sgn(\rho)
\prod_{i=1}^n\det\left(\ ^1W^{\rho_1(i)},\dots,\ ^nW^{\rho_n(i)}\right)=
l(n)\cdot\prod_{j=1}^n\det(\ ^jW).
\end{eqnarray*}

\vspace{.6cm}
\noindent
Note that for each $\rho\in\S$, the tuples
$\left(^1W^{\rho_1(i)},\dots,\ ^nW^{\rho_n(i)}\right),\ i=1,\dots,n,\ $ which
appear in the left hand side of the identity, give a colorful repartition
of the multiset of column vectors of the $^jW$.

\bigskip
\noindent
{\bf 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).

\bigskip
{\em Proof of Corollary 1 from Theorem 1.}
Suppose that $l(n)\neq 0$ and let $^1W,\dots,\ ^nW$ 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
$$\prod_{i=1}^n\det\left(\ ^1W^{\rho_1(i)},\dots,\ ^nW^{\rho_n(i)}\right),
\ \ \ \mbox{and so the sets}\ \ \
^iU=\left\{^1W^{\rho_1(i)},\dots,\ ^nW^{\rho_n(i)}\right\},\ \ \ i=1,\dots,n,$$
give the desired repartition into colorful bases.
\epr
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 {\em supersymmetric bracket algebra} \cite{HR}.

Rota's Colorful Conjecture has an obvious generalization to {\em 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 \cite{HR} for the precise statement of Kahn's conjecture, \cite{Gal}
for a recent proof of a very special case of Kahn's conjecture, known as
the {\em Dinitz problem}, and \cite{BO} for some related algorithmic
problems and ordered relatives of Rota's conjecture.

\pagebreak

\section{The Colorful Determinantal Identity}
{\em Proof of Theorem 1.}
Given $n$ square matrices $^1W,\dots, ^nW$ of size $n$, define
the following polynomial in their entries:
\begin{eqnarray*}
\Delta=\sum_{\sigma,\rho\in\S}\sgn(\sigma)\sgn(\rho)
\prod_{i,j=1}^n\ ^jW_{\sigma_i(j)}^{\rho_j(i)}.
\end{eqnarray*}
For each $\rho$ and $\sigma$ in $\S$ define
\begin{eqnarray*}
\Delta^{\rho}=\sum_{\sigma\in\S}\sgn(\sigma)
\prod_{i,j=1}^n\ ^jW_{\sigma_i(j)}^{\rho_j(i)}
=\prod_{i=1}^n\sum_{\sigma_i\in S_n}\sgn(\sigma_i)
\prod_{j=1}^n\ ^jW_{\sigma_i(j)}^{\rho_j(i)}
=\prod_{i=1}^n\det\left(\ ^1W^{\rho_1(i)},\dots,\ ^nW^{\rho_n(i)}\right),
\end{eqnarray*}
\begin{eqnarray*}
\Delta_{\sigma}=\sum_{\rho\in\S}\sgn(\rho)
\prod_{i,j=1}^n\ ^jW_{\sigma_i(j)}^{\rho_j(i)}
=\prod_{j=1}^n\sum_{\rho_j\in S_n}\sgn(\rho_j)
\prod_{i=1}^n\ ^jW_{\sigma_i(j)}^{\rho_j(i)}
=\prod_{j=1}^n\det\left(\ ^jW_{\sigma_1(j)},\dots,\ ^jW_{\sigma_n(j)}\right).
\end{eqnarray*}
Now $\Delta_{\sigma}$ is nonzero only for
$\sigma=(\sigma_1,\dots,\sigma_n)\in\S$ for which there exists
an element $\pi=(\pi_1,\dots,\pi_n)$ in $\S$ such that
$\sigma_i(j)=\pi_j(i)$ for all $i,j$, in which case
\begin{eqnarray*}
\Delta_{\sigma}
=\prod_{j=1}^n\det\left(\ ^jW_{\pi_j(1)},\dots,\ ^jW_{\pi_j(n)}\right)
=\sgn(\pi)\prod_{j=1}^n\det\left(\ ^jW_1,\dots,\ ^jW_n\right)
=\sgn(\pi)\prod_{j=1}^n\det(\ ^jW).
\end{eqnarray*}
Each $\sigma\in\S$ for which such $\pi\in\S$ exists gives a
Latin square $L$ via $L_i^j=\sigma_i(j)=\pi_j(i)$, whose
sign is given by $\sgn(L)=\sgn(\sigma)\sgn(\pi)$.
Denote by $\L$ the set of all Latin squares of order $n$. Then
\begin{eqnarray*}
\sum_{\rho\in\S}\sgn(\rho)\Delta^{\rho}=\Delta=
\sum_{\sigma\in\S}\sgn(\sigma)\Delta_{\sigma}
=\sum_{L\in\L}\sgn(L)\prod_{j=1}^n\det(\ ^jW)
=l(n)\prod_{j=1}^n\det(\ ^jW),
\end{eqnarray*}
which is precisely the Colorful Determinantal Identity.
\epr
\noindent
{\large\bf Acknowledgement}

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

\begin{thebibliography}{99}


\bibitem{BO} I. B\'ar\'any and S. Onn, Colorful linear programming,
Lecture Notes in Computer Science, Vol. 1084, 15 pages,
Springer-Verlag, June 1996, in press.

\bibitem{Gal} F. Galvin, The list chromatic index of a bipartite multigraph,
J. Combin. Theory Ser. B, 63:153-158, 1995.

\bibitem{HR} R. Huang and G.C. Rota, On the relations of various
conjectures on Latin squares and straightening coefficients,
Discr. Math., 128:225--236, 1994.

\bibitem{Jan} J.C.M. Janssen, On even and odd Latin squares, J. Combin. Theory
Ser. A, 69:173--181, 1995.

\end{thebibliography}

\end{document}
