%~Mouliné par MaN_auto v.0.29.1 2023-10-23 12:00:28
\documentclass[CRMATH,Unicode,XML]{cedram}

\TopicFR{Algèbre, Combinatoire}
\TopicEN{Algebra, Combinatorics}

\usepackage[noadjust]{cite}

\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\srank}{slice-rank}
\DeclareMathOperator{\SL}{SL}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\diag}{diag}

%\newcommand{\sgn}{\mathrm{sgn}}
%\newcommand{\srank}{\mathrm{slice}\text{-}\mathrm{rank}}

\graphicspath{{./figures/}}

\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}

\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}

\newcommand*{\relabel}{\renewcommand{\labelenumi}{(\theenumi)}}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}\relabel}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}\relabel}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}\relabel}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}\relabel}
\let\oldforall\forall
\renewcommand*{\forall}{\mathrel{\oldforall}}
\newcommand*{\meqref}[1]{(\ref{#1})}

\newcommand*{\Esf}{\mathsf{E}}
\newcommand*{\Dsf}{\mathsf{D}}
\newcommand*{\Tsf}{\mathsf{T}}

\newcommand*{\ibf}{\mathbf{i}}
\newcommand*{\ebf}{\mathbf{e}}
\newcommand*{\vbf}{\mathbf{v}}

\title[Stability of the Levi-Civita tensors and an Alon--Tarsi type theorem] {Stability of the Levi-Civita tensors and an Alon--Tarsi type theorem}

\author{\firstname{Damir} \lastname{Yeliussizov}}
\address{Kazakh-British Technical University, Almaty, Kazakhstan}
\address{Institute of Mathematics and Mathematical Modeling, Almaty, Kazakhstan}
\email{yeldamir@gmail.com}
\subjclass[2020]{14L24, 15A72, 13A50, 05E14, 05B15, 05B35}

\thanks{This research was funded by the Science Committee of the Ministry of Science and Higher Education of the Republic of Kazakhstan (Grants No. AP09259551)}
\CDRGrant[Science Committee of the Ministry of Science and Higher Education of the Republic of Kazakhstan]{AP09259551}

\begin{abstract}
We show that the Levi-Civita tensors are semistable in the sense of Geometric Invariant Theory, which is equivalent to an analogue of the Alon--Tarsi conjecture on Latin squares. The proof uses the connection of Tao's slice rank with semistable tensors. We also show an application to an asymptotic saturation-type version of Rota's basis conjecture.
\end{abstract}

\begin{document}
\maketitle

\section{Introduction}

The \emph{Levi-Civita symbol} $\varepsilon$ is defined for $i_1,\ldots, i_n \in [n] := \{1,\ldots, n\}$ as follows
\[
\varepsilon(i_1,\ldots, i_n) :=
\begin{cases}
\sgn(i_1,\ldots, i_n), & \text{ if $(i_1,\ldots, i_n) \in S_n$ is a permutation},\\
0, & \text{ otherwise}.
\end{cases}
\]
For a map $I : [M] \to [n]$, where $M$ is divisible by $n$, we denote
\[
\varepsilon(I) := \varepsilon(I(1), \ldots, I(n)) \cdot \varepsilon(I(n+1), \ldots, I(2n)) \cdot \ldots \cdot \varepsilon(I(M - n + 1), \ldots, I(M)) \in \{0, \pm 1\}.
\]

Consider the following multidimensional generalizations of determinants for \emph{$d$-tensors} (viewed as functions cf. Section~\ref{prelim}) $X : [n]^d \to \mathbb{C}$
\begin{align}\label{detx}
\Delta_{M, \vec \pi}(X) := \sum_{J_1,\ldots, J_d\, :\, [M] \to [n]} \varepsilon(J_1 \circ \pi_1) \cdots \varepsilon(J_d \circ \pi_d)\, \prod_{i = 1}^{M} X(J_1(i), \ldots, J_d(i)),
\end{align}
where $M$ is divisible by $n$ and $\vec \pi = (\pi_1,\ldots, \pi_d) \in (S_M)^d $ is a $d$-tuple of permutations from $S_M$. In~\cite[Prop.~3.10]{widg} it is shown that these functions span the space of $\SL(n)^d$-invariant homogeneous degree $M$ polynomials on $d$-tensors. For the minimal $M = n$ degree, $\Delta_{n, \vec \pi}(X)$ is (up to a sign) \emph{Cayley's first hyperdeterminant}~\cite{cay}, a simple generalization of determinants for tensors (here $\vec \pi$ affect $\Delta_{n, \vec \pi}(X)$ only by a sign; and $\Delta_{n, \vec \pi}(X)$ is a nonzero function only for even $d$).

The \emph{Levi-Civita $n$-tensor} $\Esf_n : [n]^n \to \mathbb{C}$ is the function given by $
\Esf_n(i_1,\ldots, i_n) = \varepsilon(i_1,\ldots, i_n). $ The \emph{Alon--Tarsi conjecture} on Latin squares~\cite{at} can be reformulated via hyperdeterminants as follows, see also Remark~\ref{latin}.

\begin{conj}[Alon--Tarsi]
For every $n$ even, $\Delta_{n, \vec \pi}(\Esf_n) \ne 0$.
\end{conj}

In this note we prove the following Alon--Tarsi-type result.

\begin{theo}\label{at0}
For every $n$, there exist $M$ divisible by $n$ and $\vec \pi \in (S_M)^n$ such that $\Delta_{M, \vec \pi}(\Esf_n) \ne 0$.
\end{theo}

This result is equivalent to the statement that the Levi-Civita tensor $\Esf_n$ is \emph{semistable} in the sense of Geometric Invariant Theory, see Section~\ref{sss}. We prove it using \emph{Tao's slice rank}~\cite{tao} and its connection with semistable tensors as developed in~\cite{blasiak, widg}.

Note that the Alon--Tarsi conjecture is known to hold for specific values $n = p \pm 1$ where $p$ is any prime~\cite{dri1, glynn}. The Alon--Tarsi conjecture also implies \emph{Rota's basis conjecture}~\cite{hr, onn}, and we discuss a similar connection derived from
Theorem~\ref{one} in Section~\ref{sec:rota}.
%Theorem~\ref{at0} in Section~\ref{sec:rota}.


\section{Tensors}\label{prelim}

Let $V = \mathbb{C}^n$. We consider \emph{tensors} as elements of the space $V^{\otimes d} = V \otimes \cdots \otimes V$ ($d$ times). Each tensor of $V^{\otimes d}$ can be represented in coordinates as
\[
\sum_{1 \le i_1,\ldots, i_d \le n} T(i_1,\ldots, i_d)\, \ebf_{i_1} \otimes \cdots \otimes \ebf_{i_d},
\]
where $T : [n]^d \to \mathbb{C}$ which we call a \emph{$d$-tensor}, and $(\ebf_i)$ is the standard basis of $V$. We denote by $\Tsf^d(n) := \{T : [n]^d \to \mathbb{C} \}$ the set of $d$-tensors.

Let $A_1,\ldots A_d \in \Tsf^2(n)$ viewed as $n \times n$ matrices and $X \in \Tsf^d(n)$ be a $d$-tensor. The \emph{multilinear product} is defined as follows
\[
(A_1,\ldots, A_d) \cdot X = Y \in \Tsf^d(n),
\]
where
\[
Y(i_1,\ldots, i_d) = \sum_{j_1,\ldots, j_d \in [n]} A_1(i_1,j_1) \cdots A_d(i_d, j_d)\, X(j_1,\ldots, j_d).
\]
The multilinear product defines the natural $\GL(V)^d$ action\footnote{We use the notation $G^d := G \times \cdots \times G$ ($d$ times) for a group $G$.} on $\Tsf^d(n)$, and simply expresses change of bases of $V$ for a tensor. Note that for matrices $B_1,\ldots, B_d \in \Tsf^2(n)$ we have
\[
(A_1 B_1, \ldots, A_d B_d) \cdot X = (A_1,\ldots, A_d) \cdot ((B_1,\ldots, B_d) \cdot X).
\]

The \emph{tensor product} of $X \in \Tsf^{d}(n), Y \in \Tsf^d(m)$ is defined as $T = X \otimes Y \in \Tsf^d(nm)$ given by
\[
T(k_1,\ldots, k_d) = X(i_1,\ldots, i_d) \cdot Y(j_1,\ldots, j_d), \quad k_{\ell} = i_{\ell} (m-1) + j_{\ell}.
\]
Alternatively, we can view the $\ell$-th coordinate of $T$ as a pair $(i_{\ell}, j_{\ell}) \mapsto k_{\ell}$ ordered lexicographically, for $\ell \in [d]$. For $X \in \Tsf^d(n)$, the tensor $X^{\otimes k} = X \otimes \cdots \otimes X \in \Tsf^d(n^k)$ denotes the $k$-th tensor power of $k$ copies of $X$.


\section{The slice rank}

A nonzero $d$-tensor $T \in \Tsf^d(n)$ has \emph{slice rank} $1$ if it can be decomposed in a form
\[
T(i_1,\ldots, i_d) = \vbf(i_k) \cdot T_1(i_1,\ldots, i_{k-1}, i_{k+1}, \ldots, i_d),
\]
for some $k \in [d]$, a vector $\vbf \in V$ and a $(d-1)$-tensor $T_1 \in \Tsf^{d-1}(n)$. The \emph{slice rank} of $T \in \Tsf^d(n)$, denoted by $\srank(T)$, is then the minimal $r$ such that
\[
T = T_1 + \ldots + T_r,
\]
where each summand $T_{i}$ has slice rank $1$. (Note that each $T_i$ can be decomposed differently and along different coordinates $k$.)

For $T \in \Tsf^d(n)$ we have the inequality
\[
\srank(T) \le n,
\]
since $T$ can always be expressed as the sum of slice rank 1 tensors as follows
\[
T(i_1,\ldots, i_d) = \sum_{\ell = 1}^n \delta(i_1,\ell) \cdot T(\ell, i_2,\ldots, i_d),
\]
where $\delta$ is the Kronecker delta function.

The following lemma is useful for finding the slice rank of some sparse tensors.
\begin{lemm}[\cite{st}]\label{saw}
Equip the set $[n]$ with $d$ total orderings $\le_i$ for $i \in [d]$, which define the product partial order $\le$ on $[n]^d$. Let $T \in \Tsf^d(n)$ whose support $\Gamma = \{(i_1,\ldots, i_d) : T(i_1,\ldots, i_d) \ne 0\}$ is an antichain w.r.t. $\le$. Then
\[
\srank(T) = \min_{\Gamma = \Gamma_1 \cup \cdots \cup \Gamma_d } |\pi_1(\Gamma_1)| + \ldots + |\pi_d(\Gamma_d)|,
\]
where the minimum is over set partitions $\Gamma = \Gamma_1 \cup \cdots \cup \Gamma_d $ and $\pi_i : [n]^d \to [n]$ is the projection map on the $i$-th coordinate.
\end{lemm}

\begin{rema}
The slice rank was introduced by Tao in~\cite{tao} and studied in~\cite{st}. This notion found many applications especially in additive combinatorics, see~\cite{gro} for a related survey.
\end{rema}

\begin{rema}
For $d = 2$, the slice rank coincides with the usual matrix rank. For $d \ge 3$, it significantly differs from the more common \emph{tensor rank} (e.g.~\cite{lands}) which can be way larger.
\end{rema}

\subsection{The slice rank of the Levi-Civita tensors} Now we find the slice rank of the {Levi-Civita $n$-tensor} $\Esf_n \in \Tsf^n(n)$ and its $k$-th tensor power $\Esf_n^{\otimes k} \in \Tsf^n(n^k)$.

\begin{lemm}\label{five}
We have: $\srank(\Esf_n^{\otimes k}) = n^k$ is full for all $k$.
\end{lemm}
\begin{proof}
The support of $\Esf_n^{\otimes k} \in \Tsf^{n}(n^k)$ can be identified with the following set
\[
\Gamma = \left\{(\ibf_1,\ldots, \ibf_n)\, :\, \ibf_{\ell} = (i_{\ell, 1}, \ldots, i_{\ell, k}) \in [n]^k \text{ for } \ell \in [n], \text{ and } (i_{1,j}, \ldots, i_{n,j}) \in S_n \text{ for } j \in [n]\right\}.
\]
Take the lexicographic ordering $\le_{\ell}$ on $\ibf_{\ell} \in [n]^k$ for each $\ell \in [n]$, which define the product partial order $\le$ on $\Gamma$. Let us show that $\Gamma$ is an antichain w.r.t. this partial order. Assume we have $(\ibf_1,\ldots, \ibf_n) \le (\ibf'_1,\ldots, \ibf'_n)$ for elements of $\Gamma$, which means $\ibf_{\ell} = (i_{\ell, 1}, \ldots, i_{\ell, k})\, \le_{\ell}\, \ibf'_{\ell} = (i'_{\ell, 1}, \ldots, i'_{\ell, k})$ for all $\ell \in [n]$. In particular, $i_{\ell, 1} \le i'_{\ell, 1}$ for all $\ell \in [n]$ but both $(i_{1,1}, \ldots, i_{n,1}), (i'_{1,1}, \ldots, i'_{n,1}) \in S_n$ are permutations which is only possible when $(i_{1,1}, \ldots, i_{n,1}) = (i'_{1,1}, \ldots, i'_{n,1})$. Since $\le_{\ell}$ are lexicographic, we then have $i_{\ell, 2} \le i'_{\ell, 2}$ for all $\ell \in [n]$ and by the same argument we get $(i_{1,2}, \ldots, i_{n,2}) = (i'_{1,2}, \ldots, i'_{n,2})$. Proceeding the same way we obtain that $(i_{1,j}, \ldots, i_{n,j}) = (i'_{1,j}, \ldots, i'_{n,j})$ for all $j \in [n]$ and hence $(\ibf_1,\ldots, \ibf_n) = (\ibf'_1,\ldots, \ibf'_n)$ which shows that $\Gamma$ is indeed an antichain.

Let $\rho : [n]^k \to [n]^k$ be the (bijective) cyclic shift map given by
\[
\rho : (i_1,\ldots, i_k) \longmapsto (i'_1,\ldots, i'_k) = (i_1 + 1,\ldots, i_k + 1) \bmod n.
\]
Consider the following subset of $\Gamma$
\[
S = \left\{(\ibf, \rho\, \ibf, \ldots, \rho^{n-1} \ibf) : \ibf \in [n]^k \right\} \subset \Gamma.
\]
Take any partition $\Gamma = \Gamma_1 \cup \cdots \cup \Gamma_n$. Note that for each $j \in [n]$ we have
\[
|\pi_j(\Gamma_j)| \ge |\pi_j(\Gamma_j \cap S)| \ge |\Gamma_j \cap S|
\]
since the elements of $S$ differ in the $j$-th coordinate. Hence we have
\[
|\pi_1(\Gamma_1)| + \ldots + |\pi_n(\Gamma_n)| \ge |\Gamma_1 \cap S| + \ldots + |\Gamma_n \cap S| = |S| = n^k,
\]
which by Lemma~\ref{saw} implies that $\srank(\Esf_n^{\otimes k}) \ge n^k$. On the other hand, we know that $\srank(\Esf_n^{\otimes k}) \le n^k$ and hence the equality follows.
\end{proof}

\begin{rema}
It was noticed in~\cite{gow} that $\srank(\Esf_3) = 3$.
\end{rema}


\section{Semistable tensors}\label{sss}

The notion of semistable tensors comes from Geometric Invariant Theory~\cite{mumf}. A polynomial $P(X)$ is \emph{$\SL(n)^d$-invariant} on $\Tsf^d(n)$ if $P(g \cdot X) = P(X)$ for all $g \in \SL(n)^d$ and $X \in \Tsf^d(n)$. A tensor $X \in \Tsf^d(n)$ is called \emph{semistable} (for the action of $\SL(n)^d$) if $P(X) \ne 0$ for some nonconstant $\SL(n)^d$-invariant homogeneous polynomial~$P$. The following important characterization of semistable tensors shows their connection with the slice rank.

\begin{theo}[{\cite[Cor.~6.5]{widg}}]
A tensor $X \in \Tsf^d(n)$ is semistable iff $\srank(X^{\otimes k}) = n^k$ is full for all~$k$.
\end{theo}

Lemma~\ref{five} with this Theorem give the following result.

\begin{theo}\label{cor0}
The Levi-Civita $n$-tensor $\Esf_n$ is semistable.
\end{theo}

To show the equivalence of Theorem~\ref{cor0} with Theorem~\ref{at0}, we use the following concrete description of SL-invariant generating polynomials.

\begin{lemm}[{\cite[Prop.~3.10]{widg}, cf.~\cite[Ex.~7.18]{widg2}}]
The space of $\SL(n)^d$-invariant homogeneous degree $M$ polynomials on $\Tsf^d(n)$ is nonzero only if $M$ is divisible by $n$, in which case it is spanned by the polynomials $\{ \Delta_{M, \vec{\pi}} \} $ (defined in eq. \eqref{detx}) indexed by $d$-tuples of permutations $\vec \pi = (\pi_1,\ldots, \pi_d) \in (S_M)^d$.
\end{lemm}

\begin{coro}\label{cor1}
Let $X \in \Tsf^d(n)$ be semistable. Then $\Delta_{M, \vec{\pi}}(X) \ne 0$ for some $M$ divisible by $n$ and permutations $\vec \pi \in (S_M)^d$.
\end{coro}

\begin{rema}
The connection of slice rank with semistable tensors was first established in~\cite{blasiak}, where it was shown that $\srank(X) < n$ implies $X$ is unstable~(i.e. not semistable), and if $X$ is unstable then $\srank(X^{\otimes k}) < n^k$ for some $k$. In~\cite{blasiak} these results are given for $d = 3$ and for any $d$ the statements are in~\cite{widg}; the proofs use the Hilbert--Mumford criterion.
\end{rema}

\begin{rema}
The formula~\eqref{detx} is given in exactly this form in~\cite[Ex.~7.18]{widg2}, and in~\cite[Prop.~3.10]{widg} it is stated in a slightly different form.
\end{rema}

\begin{rema}\label{lbd}
The degree $M$ can be bounded above using a result from~\cite{derk}, see~\cite[Lem.~7.11]{widg} for a precise statement, which gives $M \le d^{d n^2 - d} n^d$.
\end{rema}

\begin{rema}\label{latin}
Let us see how to get the original formulation of the Alon--Tarsi conjecture~via Latin squares~\cite{at}. Let $\vec \pi$ be the $n$-tuple of identity permutations from $S_n$. We then have
\[
\Delta_{n, \vec \pi}(\Esf_n) = \sum_{J_1,\ldots, J_n : [n] \to [n]} \varepsilon(J_1) \cdots \varepsilon(J_n) \prod_{i = 1}^n \varepsilon(J_1(i), \ldots, J_n(i)).
\]
The maps $J_1,\ldots, J_n$ corresponding to nonzero terms in this sum are in one-to-one correspondence with the $n \times n$ Latin squares (i.e. matrices whose every row and column is a permutation from $S_n$) formed by the rows $J_1,\ldots, J_n$. The nonzero terms define the \emph{signs} for these Latin squares. Then the conjecture states that for each even $n$, the number of Latin squares with the odd sign is \emph{not} equal to the number of Latin squares with the even sign, i.e. $\Delta_{n, \vec \pi}(\Esf_n) \ne 0$. A similar formulation via Latin-type $n \times M$ matrices can be given for our result $\Delta_{M, \vec \pi}(\Esf_n) \ne 0$.
\end{rema}

\begin{rema}
It can be shown that the results in~\cite{kum, kl} combined with the eventual surjectivity of the Hadamard--Howe map~\cite{bri1, bri2} lead to similar sums over Latin-type matrices with column signs.
\end{rema}


\section{A version of Rota's basis conjecture}\label{sec:rota}

As an application we show the following asymptotic version of Rota's basis conjecture.

\begin{theo}\label{one}
Let $B_1,\ldots, B_n$ be $n$ bases of $V = \mathbb{C}^n$. There is $\ell \ge 1$ and $n \times \ell n$ matrix $A$ such that:
\begin{itemize}
\item in the $i$-th row of $A$ each element of $B_i$ appears $\ell$ times, for $i =1, \ldots, n$
\item every column of $A$ forms a basis of $V$.\footnote{To be precise, each entry of $A$ is a vector in $V$. Here $V$ can be any $n$-dimensional vector space over a field of characteristic $0$.}
\end{itemize}
\end{theo}

Rota's basis conjecture~\cite{hr, rot10} states that this holds for $\ell = 1$ thus presenting the problem as a saturation-type\footnote{By analogy with algebraic notions of saturation for monoids or ideals.} question.

\subsection{Relative invariance}

We use the polynomials $\Delta_{M, \vec \pi}$ as relative $\GL$-invariants which is well known.

\begin{lemm}\label{pgl}
Let $X \in \Tsf^d(n)$ and $A_1,\ldots, A_d \in \GL(n)$. We have
\begin{align*}
\Delta_{M, \vec{\pi}}((A_1,\ldots, A_d) \cdot X) = \Delta_{M, \vec{\pi}}(X) \cdot \det(A_1)^{M/n} \cdots \det(A_d)^{M/n}.
\end{align*}
\end{lemm}

\begin{proof}
It is enough to check the identity for one matrix $A = A_1$. Write $A = BD$ for $B \in \SL(n)$ and $D = \diag(\det(A), 1, \ldots, 1)$. Then as $\Delta_{M, \vec{\pi}}$ is $\SL(n)^d$-invariant, we get
\[
\Delta_{M, \vec{\pi}}((BD,I, \ldots, I) \cdot X) = \Delta_{M, \vec{\pi}}((B, I, \ldots, I) \cdot ((D,I, \ldots, I) \cdot X))= \Delta_{M, \vec{\pi}}((D,I, \ldots, I) \cdot X).
\]
Let $Y = (D,I, \ldots, I) \cdot X$. We have
\[
Y(i_1,\ldots, i_d) = \sum_{j} D(i_1, j) X(j, i_2,\ldots, i_d) =
\begin{cases}
\det(A) \cdot X(i_1, \ldots, i_d), & \text{ if $i_1 = 1$},\\
X(i_1, \ldots, i_d), & \text{ otherwise}.
\end{cases}
\]
From the formula~\eqref{detx} we can see that each nonzero term $\prod_{k = 1}^d \varepsilon(J_k \circ \pi_k) \prod_{i = 1}^M X(J_1(i), \ldots, J_d(i))$ of $\Delta_{M, \vec{\pi}}(X)$ has exactly $M/n$ variables $X(1, * \ldots, *)$. Hence, $\Delta_{M, \vec{\pi}}(Y) = \Delta_{M, \vec{\pi}}(X) \cdot \det(A)^{M/n}$ as needed.
\end{proof}



\subsection{Determinantal tensors} For a matrix $A$ denote by $A[i]$ the $i$-th column vector of $A$. For matrices $A_1,\ldots, A_n \in \GL(n)$ define the \emph{determinantal $n$-tensor} $\Dsf = {\Dsf}(A_1,\ldots, A_n) \in \Tsf^n(n)$ given by
\[
\Dsf(i_1,\ldots, i_n) := \det(A_1[i_1], \ldots, A_n[i_n]), \quad \forall i_1,\ldots, i_n \in [n].
\]

\begin{lemm}\label{16}
We have:
\begin{enumerate}\romanenumi
\item \label{19i} Let $A_1,\ldots, A_n, B_1,\ldots, B_n \in \GL(n)$. Then
\[
\Dsf(A_1 B_1,\ldots, A_n B_n) = (B^T_1,\ldots, B^T_n) \cdot \Dsf(A_1,\ldots, A_n).
\]
\item \label{19ii} $\Dsf(I_n, \ldots, I_n) = \Esf_n, $ where $I_n$ is the identity $n \times n$ matrix.
\end{enumerate}
\end{lemm}

\goodbreak
\begin{proof}\ 
\begin{proof}[\meqref{19i}]
It is enough to check the identity for one matrix $B_1 = B$. By definition and multilinearity of determinants we have
\begin{align*}
\Dsf(A_1 B, A_2,\ldots, A_n) (i_1,\ldots, i_n) &= \det(A_1 B [i_1], A_2[i_2], \ldots, A_n[i_n]) \\
&= \det\left(\sum_{j = 1}^n A_1^{}[j] \cdot B(j, i_1), A_2[i_2], \ldots, A_n[i_n] \right)\\
&= \sum_{j = 1}^n B(j, i_1) \cdot \det(A_1[j], A_2[i_2], \ldots, A_n[i_n])\\
&= (B^T, I_n, \ldots, I_n) \cdot \Dsf(A_1,\ldots, A_n) (i_1,\ldots, i_n).
\end{align*}
\let\qed\relax
\end{proof}

\begin{proof}[\meqref{19ii}]
We have
\[
\Dsf(I_n, \ldots, I_n) (i_1,\ldots, i_n) = \det(\ebf_{i_1}, \ldots, \ebf_{i_n}) = \varepsilon(i_1,\ldots, i_n)
\]
and the equality follows.
\end{proof}
\let\qed\relax
\end{proof}

\begin{coro}
Let $B_1,\ldots, B_n \in \GL(n)$. We have
\[
\Dsf(B_1,\ldots, B_n) = (B^T_1,\ldots, B^T_n) \cdot \Dsf(I_n,\ldots, I_n) = (B^T_1,\ldots, B^T_n) \cdot \Esf_n.
\]
\end{coro}

\begin{rema}
Determinantal tensors are implicitly used in~\cite{onn}; an explicit formulation appears in~\cite{al}.
\end{rema}

\subsection*{Proof of Theorem~\ref{one}}

We have $B_1, \ldots, B_n \in \GL(n)$ whose elements are given by column vectors. Consider the determinantal tensor
\[
\Dsf = \Dsf(B_1,\ldots, B_n) = (B^T_1,\ldots, B^T_n) \cdot \Esf_n.
\]
Since $\Esf_n$ is semistable, there exist $M = \ell n$ and $\vec \pi \in (S_M)^n$ such that $\Delta_{M, \vec \pi}(\Esf_n) \ne 0$ (Corollary~\ref{cor1}). By Lemmas~\ref{pgl} and~\ref{16} we have
\[
\Delta_{M, \vec \pi}(\Dsf) = \Delta_{M, \vec \pi}(\Esf_n) \cdot \det(B_1)^{\ell} \cdots \det(B_n)^{\ell} \ne 0.
\]
On the other hand, let us check the expansion of this polynomial, which is given by
\begin{align*}
\Delta_{M, \vec{\pi}}(\Dsf) &= \sum_{J_1,\ldots, J_n\, :\, [M] \to [n]}\, \prod_{k = 1}^n \varepsilon(J_k \circ \pi_k) \prod_{i = 1}^M \Dsf(J_1(i), \ldots, J_n(i)) \\
&= \sum_{J_1,\ldots, J_n\, :\, [M] \to [n]}\, \prod_{k = 1}^n \varepsilon(J_k \circ \pi_k) \prod_{i = 1}^M \det(B_1[J_1(i)], \ldots, B_n[J_n(i)]).
\end{align*}
Since $\Delta_{M, \vec{\pi}}(\Dsf) \ne 0$, at least one term in this expansion is also nonzero, which will give a desired arrangement. Indeed, if
\[
\prod_{k = 1}^n \varepsilon(J_k \circ \pi_k) \prod_{i = 1}^M \det(B_1[J_1(i)], \ldots, B_n[J_n(i)]) \ne 0
\]
then we can arrange the columns of $B_1,\ldots, B_n$ into an $n \times M$ matrix $A$ w.r.t. the maps $J_1,\ldots, J_n : [M] \to [n]$ such that the $i$-th column of $A$ has the entries $B_1[J_1(i)], \ldots, B_n[J_n(i)]$ of the corresponding columns of $B_1,\ldots, B_n$. Since $\det(B_1[J_1(i)], \ldots, B_n[J_n(i)]) \ne 0$ they are all bases as needed. The rows of $A$ also satisfy the needed property, i.e. each entry appears exactly $\ell$ times, since $\varepsilon(J_k \circ \pi_k) \ne 0$ for all $k = 1,\ldots, n$ which is clear from the definition of the sign $\varepsilon(J)$.
\qed

\begin{rema}
In the case $M = n$, this is the method of~\cite{onn} showing how the Alon--Tarsi conjecture implies Rota's basis conjecture.
\end{rema}


\begin{rema}
From Remark~\ref{lbd}, we can see that an upper bound on the multiplicity $\ell = M/n$ is large, it gives $\ell \le n^{n^3}$.
\end{rema}

\begin{rema}\label{22}
It can be shown that Theorem~\ref{one} is equivalent to a \emph{fractional} version of Rota's basis conjecture, which holds for matroids and follows from a more general result in~\cite[Thm.~10.4]{ab} on fractional coloring.
\end{rema}


Note: This paper supersedes author's preprint~\cite{dy}.

\subsection*{Acknowledgements} I am grateful to Alimzhan Amanov for useful comments and many interesting conversations. I thank Asaf Ferber, Matthew Kwan, and Lisa Sauermann for telling me about Remark~\ref{22}. I~am also grateful to a referee for useful comments.

%\subsection*{Funding}


\bibliographystyle{crplain}
\bibliography{CRMATH_Yeliussizov_20220139}
\end{document}