\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsthm,amsmath,amssymb}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\CC{\mathbb{C}}
\def\GL{\operatorname{GL}}
\def\Row{\operatorname{Row}}
\def\Col{\operatorname{Col}}
\def\sign{\operatorname{sign}}
\def\Fix{\operatorname{Fix}}
\def\ch{\operatorname{ch}}
\def\ee{\mathbf{e}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\newtheorem*{mainTheorem}{Theorem 2}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Vanishing of doubly symmetrized tensors}
\author{Andrew Berget\\\small Department of Mathematics\\\small University of Washington\\\small Seatle, WA, USA\\ \small \tt{aberget@uw.edu}
\and J.A. Dias da Silva\qquad Am\'elia Fonseca \\
\small Departamento de Matem\'atica\\
\small Universidade de Lisboa\\
\small Lisboa, PT\\
\small \tt
japsilva@fc.ul.pt, afonseca@ptmat.fc.ul.pt}
\date{\dateline{ToDo}{ToDoToo}\\
\small Mathematics Subject Classifications: 15A69, 05E10, 20C30, 05B35}
\begin{document}
\begin{abstract}
Symmetrizations of tensors by irreducible characters of the
symmetric group serve as natural analogues of symmetric and
skew-symmetric tensors. The question of when a symmetrized
decomposable tensor is non-zero is intimately related to the rank
partition of a matroid extracted from the tensor. In this paper we
characterize the non-vanishing of the symmetrization of certain {\em
partially symmetrized} decomposable tensors. Our answers are
phrased in terms of rank partitions of matroids.
\bigskip\noindent \textbf{Keywords:} symmetrizations of tensors,
matroid, rank partition.
\end{abstract}
\maketitle
\pagestyle{plain}
\section{Introduction}
Let $V$ be a finite dimensional complex vector space. Consider the
(left) action of the symmetric group $S_n$ on the $n$-fold tensor
power $V^{\otimes n}$ by permuting tensor factors,
\[
\sigma (v_1 \otimes \dots \otimes v_n) =
v_{\sigma^{-1}(1)} \otimes \dots \otimes v_{\sigma^{-1}(n)}.
\]
Given a partition $\lambda \vdash n$, let $T_\lambda \in \CC[S_n]$
denote the projector of the symmetric group algebra $\CC[S_n]$ to its
isotypic component indexed by $\lambda$.
The image of a decomposable tensor $v^\otimes := v_1 \otimes \dots
\otimes v_n$ under $T_\lambda$ is called a \textbf{symmetrized
decomposable tensor}. These are closely related to irreducible
character immanants of positive semi-definite matrices \cite[Chapters 6--7]{merris}. A fundamental
question is when a symmetrized decomposable tensor is zero. This
question was first answered by Gamas \cite{gamas} and later
characterized in terms of the matroid of the vectors $v_1,\dots, v_n$,
as we now describe.
We will let $v = (v_1,\dots,v_n)$ denote a configuration of $n$
vectors in $V$, and $M(v)$ the corresponding matroid. Given any
matroid $M$, the \textbf{rank partition} of $M$ is the sequence of
numbers $\rho(M) = (\rho_1, \rho_2,\dots )$ determined by the
condition that its $k$th partial sum is the size of the largest union
of $k$ independent sets of $M$.
\begin{theorem}[{\cite[Theorem A$'$]{colorings}}]\label{thm:DdS}
The symmetrized decomposable tensor $T_\lambda v^\otimes $ is
non-zero if and only if $\lambda^t \leq \rho(M(v))$.
\end{theorem}
Here, $\lambda^t$ denotes the conjugate partition of $\lambda$, and $\leq$ denotes
dominance order on the set of partitions of size $n$.
The main result of the current paper is a generalization of this
result, where one first partially symmetrizes $v^\otimes$.
\begin{theorem}\label{thm:main}
Let $\lambda$ and $\mu$ be partitions of $n$.
\begin{itemize}
\item[(1)] Then there is a
permutation $\pi \in S_n$ such that
\[
T_\lambda \left( (v_{\pi(1)} \wedge \dots \wedge v_{\pi(\mu_1)})
\otimes \dots \otimes (v_{\pi(n-\mu_r+1)} \wedge \dots \wedge
v_{\pi(n)}) \right)\neq 0
\]
if and only if $\mu \leq \lambda^t \leq \rho(M(v))$.
\item[(2)] Dually, there
is a permutation $\pi \in S_n$ such that
\[
T_\lambda \left( (v_{\pi(1)} \cdot \dots \cdot v_{\pi(\mu_1)})
\otimes \dots \otimes (v_{\pi(n-\mu_r+1)} \cdot \dots \cdot
v_{\pi(n)}) \right)\neq 0
\]
if and only if $\mu \leq \lambda$ and $\lambda^t \leq \rho(M(v))$.
\end{itemize}
\end{theorem}
Here we are viewing the tensor product of the exterior and symmetric
powers of $V$ as subspaces of $V^{\otimes n}$.
The outline of this paper is as follows: We first present some
background on representations of the symmetric group and
matroids. Then we consider the notion of compatible pairs of tableaux.
With these preliminaries, we next prove Theorem~\ref{thm:main}. We end
with a brief discussion of a conjecture that motivated the theorem.
\section{Background}
In this section we review some relevant notions from representation
theory, and matroid theory.
\subsection{Representation theory}
We refer to the book of James and Kerber \cite{james} for a thorough
treatment of the representation theory of the symmetric group.
The group of permutations of the set $[n]:=\{1,2,\dots,n\}$ is denoted
$S_n$. The irreducible representations of $S_n$ are parametrized by
partitions $\lambda = (\lambda_1 \geq \lambda_2 \geq \dots
\lambda_\ell \geq 0)$ of $n$; $\sum_i \lambda_i = n$. We construct
these representations as follows.
A \textbf{tableau} is a filling $T$ of the Young diagram of $\lambda$
with the numbers in $[n]$, each number being used exactly once. A
tableau is said to be standard if the numbers in the filling increase
across rows and columns. Given a tableau $T$, define two elements of
the group algebra $\CC[S_n]$ by
\[
p_T = \sum_{\sigma \in \Row(T)} \sigma, \qquad n_T = \sum_{\sigma \in
\Col(T)} \sign(\sigma)\sigma.
\]
Here, $\Row(T)$ is the group of permutations that take each row of $T$
into itself, and $\Col(T)$ is likewise defined for the columns of
$T$. These elements are, respectively, the \textbf{row symmetrizer}
and \textbf{column anti-symmetrizer} of $T$.
The product $ p_Tn_T$ is called a \textbf{Young symmetrizer}, and we
will call the product $n_Tp_T$ a dual Young symmetrizer. It is a
theorem that the left ideal in $\CC[S_n]$ generated by a (dual) Young
symmetrizer is an irreducible representations of $S_n$. Further, if
$S$ and $T$ are two tableaux, then the representations generated by
$p_Sn_S$ and $p_Tn_T$ are isomorphic if and only if the shape of $S$
equals the shape of $T$. We say that an irreducible representation of
$S_n$ has shape $\lambda$ if it is isomorphic to the ideal generated
by some $p_Tn_T$ for a tableau $T$ of shape $\lambda$. It is a fact
that $p_Tn_T$ and $n_T p_T$ generate isomorphic representations.
The projection of $\CC[S_n]$ onto its isotypic component of shape
$\lambda$ is denoted $T_\lambda$. It is fact that
\[
T_\lambda = \frac{\chi^\lambda(1)}{n!}\sum_{\sigma \in S_n}
\chi(\sigma)\sigma \in \CC[S_n],
\]
and that $T_\lambda$ is a scalar multiple of $\sum_T p_Tn_T = \sum_T
n_T p_T$, the sum over all tableaux of shape $\lambda$. Indeed,
$P_\lambda:=\sum_T p_T n_T$ is central since $\sigma p_T n_T
\sigma^{-1} = p_{\sigma T} n_{\sigma T}$, and hence Schur's lemma
implies that $P_\lambda$ acts on each irreducible representation of
$S_n$ by a scalar determined only by the isomorphism type. Since
$P_\lambda$ annihilates Young symmetrizers of shapes other than
$\lambda$ and it is non-zero in the group algebra, it must act on an
irreducible of shape $\lambda$ by a non-zero scalar. In particular,
this means $P_\lambda$ is essentially idempotent. Similar reasoning
shows that $\sum_T p_T n_T$ satisfies these properties too.
Let $V$ be a finite dimensional complex vector space. The symmetric
group $S_n$ acts on the left of $V^{\otimes n}$ via permutation of
tensor factors, as in the introduction. We conclude that $T_\lambda$
acts on $V^{\otimes n}$ as projection to its isotypic component of
shape $\lambda$; the image of $T_\lambda$ is referred to as a
\textbf{symmetry class of tensors} of shape $\lambda$. Such tensors
are important from the point of view of representation theory of the
general linear group, invariant theory and algebraic geometry
\cite[Chapters 8--9]{fulton}.
\subsection{Matroid theory}
Given a finite collection of vectors $v_1,\dots,v_n$ selected from a
fixed vector space, we construct a simplicial complex $M(v)$ as
follows. The vertex set of $M(v)$ is $[n]$ and the faces of $M(v)$ are
those subsets $I \subset[n]$ such that $\{v_i: i \in I\}$ is a
linearly independent set. $M(v)$ is the \textbf{matroid of $v$}. The
faces of $M(v)$ are referred to as independent sets, while non-faces
are said to be dependent.
The matroid of $v$ is an example of a matroid complex (or simply,
matroid). These are simplicial complexes whose faces satisfy the
\textit{exchange axiom}: If $I$ and $I'$ are faces and $|I|<|I'|$,
then there is $e \in I' \setminus I$ such that $I \cup \{e\}$ is a still a
face. We will assume from now on that all matroids considered are
loopless, meaning that there are no singleton dependent sets, in
particular, $v_i \neq 0$ for all $i$.
Given a matroid $M$ with ground set $[n]$ and a partition $\lambda$ of
$n$, we define a \textbf{$\lambda$-coloring} of $M$ to be a set
partition of $[n]$ into blocks of size $\lambda_1$, $\lambda_2$, \dots
each of which is an independent set of $M$. Thus, $M$ is
$\lambda$-colorable if there is a tableau of shape $\lambda$ whose
rows index independent sets of $M$.
As in the introduction, the \textbf{rank partition} of $M$, $\rho(M)$,
is defined by the condition that the $k$th partial sum of its parts is
equal to the size of the largest union of $k$ independent sets of
$M$. In \cite{colorings} it is proved that $\rho(M)$ is actually a
partition of $M$. Further, it is shown that $M$ is $\lambda$-colorable
if and only if $\lambda \leq \rho(M)$.
The length of the rank partition appears in the graph theory
literature under the guise of \textit{arboricity}. Recently, the third
author has studied the rank partition in the context of multi-graded
Hilbert series of projective equivalence classes.
\section{Compatible pairs of tableaux}
In this section we define the notion of a compatible pair of
tableaux. We then investigate the combinatorics of such pairs relevant
to the proof of Theorem~\ref{thm:main}.
For each tableau $T$ of shape $\lambda$, we define a function $c_T :
[n] \to [\lambda_1]$ by the rule $c_T(i) = $ the column number of $T$
that contains $i$. We say that a pair of tableaux $(S,T)$ is
\textbf{compatible} if whenever $i$ and $j$ are in the same row of
$S$, $c_S(i) < c_S(j)$ implies $c_T(i) < c_T(j)$. It is clear that if
$(S,T)$ is a compatible pair, then $ \Row(S)\cap \Col(T)= \{1\}$. The
converse is false, but we offer the following in lieu of it.
\begin{proposition}\label{prop:1} Let $(S,T)$ be a pair of tableaux such that $\Row(S)\cap \Col(T)= \{1 \}$. Then, there exists $\pi \in \Row(S)$ such
that $(\pi S,T)$ is a compatible pair of tableaux.
\end{proposition}
\begin{proof}
The hypothesis implies that any two numbers $i,j$ that occur in the
same row of $S$ occur in different columns of $T$. Denote the
entries in the $i$th row (in order) of $S$ by $s_1,\dots,s_r$ and
rearrange them to $s_1',\dots,s_r'$ so that $c_T(s'_j) <
c_T(s'_{j+1})$. Doing this procedure for each row proves the
proposition.
\end{proof}
\begin{proposition} \label{pr:2} Let $(S,T)$ be a compatible pair of
tableaux. Suppose that $\tau \in \Col(S)$, $\sigma \in \Row(S)$ and
$ \tau \sigma \in \Col(T)$. Then, we must have $\sigma =1$.
\end{proposition}
We will employ the following notation in the proof: If $T$ is a
tableau, then $K_i(T)$ denotes the set of entries in column $i$ of
$T$.
\begin{proof}
For $\sigma \in S_n $ let $\Fix(\sigma)$ denote its set of fixed points.
Say that $S$ and $T$ are tableaux of shape $\lambda $ and $\mu$, respectively.
Let $\tau \in \Col(S)$, $\sigma \in \Row(S)$ and $s \in
\{1,\ldots,\mu_1\}$. We will prove by induction on $s$ that if, for
$i=1,\ldots, s$,
\[
\tau \sigma (K_i(T))=K_i(T),
\]
then
\[
\bigcup_{i=1}^{s}K_i(T)\subseteq \Fix(\sigma).
\]
Suppose that $\tau \sigma (K_1(T))=K_1(T)$. Observe that
$K_1(T)\subseteq K_1(S)$, since $(S,T)$ is a compatible pair of
tableaux. Let $a \in K_1(T).$ Then $\tau \sigma (a) \in K_1(T)$ and
hence $a, \tau \sigma (a) \in K_1(S)$. Let $t$ be such that $\sigma (a)
\in K_t(S)$. Since $\tau \in \Col(S)$, we have that $\tau \sigma (a)
\in K_t(S)$. Therefore $t=1$ and hence $a, \sigma (a) \in
K_1(S)$. Since $\sigma \in \Row(S)$, we have $\sigma (a)=a.$
Assume that $s>1$ and that $\tau \sigma (K_i(T))=K_i(T)$, for every
$i=1,\ldots, s$. By the induction hypothesis,
$\bigcup_{t=1}^{s-1}K_t(T)\subseteq \Fix(\sigma )$. It remains to prove
that $K_s(T)\subseteq \Fix(\sigma ).$
Let $H_i=K_s(T)\cap K_i(S),$ for $ i=1,\ldots, \lambda _1.$ Then
$K_s(T)=\bigcup_{i=1}^{\lambda _1}H_i.$
Suppose that $K_s(T) \not \subseteq \Fix(\sigma)$. Let $p=\max\{i:
H_i\not \subseteq \Fix(\sigma )\}.$ Choose $a \in H_p$ such that
$\sigma (a) \not =a.$ As $\sigma \in \Row(S),$ $a \in K_p(S),$ and
$\sigma (a)\not =a,$ we have $\sigma (a)\not \in K_p(S).$ Let $q$ such
that $\sigma (a) \in K_q(S).$ We have $q \not =p$. Since $\tau \in
\Col(S),$ $\tau \sigma (a) \in K_q(S).$ As $a \in H_p,$ $a \in
K_s(T),$ thus $\tau \sigma (a) \in K_s(T).$ Therefore $\tau \sigma (a)
\in H_q.$ We consider two cases.
\begin{itemize}
\item[Case 1.] Assume that $q