\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsthm,amsmath,amssymb} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}{\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