\documentclass[11pt]{amsart}
\usepackage{amssymb, amsmath, amsfonts, amsthm, graphics, epstopdf}
\usepackage[hmargin=1 in, vmargin = 1 in]{geometry}
\usepackage{youngtab}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\usepackage[normalem]{ulem}
\usepackage[all]{xy}


% When you first define a new word, use this macro to make it stand out
% EG We say that an abelian group $I$ is \newword{injective} if, for any
% injection $G \to H$, and any map $G \to I$, there is a map $H \to I$ making the
% obvious diagram commute.
\newcommand{\newword}[1]{\textbf{\emph{#1}}}

%Arrows
\newcommand{\into}{\hookrightarrow}
\newcommand{\onto}{\twoheadrightarrow}

%Things LaTeX names by appearance, rather than meaning
% By now, I've learned the standard LaTeX names, but I remember they used to give me trouble, so here are some macros
\newcommand{\isom}{\cong} %The isomorphism symbol
\newcommand{\union}{\cup}
\newcommand{\intersection}{\cap}
\newcommand{\bigunion}{\bigcup}
\newcommand{\bigintersection}{\bigcap}
\newcommand{\disjointunion}{\sqcup}
\newcommand{\bigdisjointunion}{\bigsqcup}


%Some multiletter functions
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\End}{End}
\DeclareMathOperator{\Tor}{Tor}
\DeclareMathOperator{\Ker}{Ker}
\DeclareMathOperator{\CoKer}{CoKer}
\DeclareMathOperator{\Spec}{Spec}
\DeclareMathOperator{\Proj}{Proj}
\renewcommand{\Im}{\mathop{\mathrm{Im}}}
%Their calligraphic versions; use these for the sheaf constructions
\DeclareMathOperator{\HHom}{\mathcal{H}\emph{om}}
\DeclareMathOperator{\EExt}{\mathcal{E}\emph{xt}}
\DeclareMathOperator{\EEnd}{\mathcal{E}\emph{nd}}
\DeclareMathOperator{\TTor}{\mathcal{T}\emph{or}}
\DeclareMathOperator{\KKer}{\mathcal{K}\emph{er}}
\DeclareMathOperator{\CCoKer}{\mathcal{C}\emph{o}\mathcal{K}\emph{er}}
\newcommand{\IIm}{\mathop{\mathcal{I}\emph{m}}}

%This makes alternating tensors look right in displayed equations
\newcommand{\Alt}{\bigwedge\nolimits}


%Blackboard bold letters.
\renewcommand{\AA}{\mathbb{A}}
\newcommand{\BB}{\mathbb{B}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\DD}{\mathbb{D}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\GG}{\mathbb{G}}
\newcommand{\HH}{\mathbb{H}}
\newcommand{\II}{\mathbb{I}}
\newcommand{\JJ}{\mathbb{J}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\LL}{\mathbb{L}}
\newcommand{\MM}{\mathbb{M}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\OO}{\mathbb{O}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\renewcommand{\SS}{\mathbb{S}}
\newcommand{\TT}{\mathbb{T}}
\newcommand{\UU}{\mathbb{U}}
\newcommand{\VV}{\mathbb{V}}
\newcommand{\WW}{\mathbb{W}}
\newcommand{\XX}{\mathbb{X}}
\newcommand{\YY}{\mathbb{Y}}
\newcommand{\ZZ}{\mathbb{Z}}

%Calligraphic letters

\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}

\newcommand{\SSYT}{\text{SSYT}}
\newcommand{\GL}{\text{GL}}

\theoremstyle{definition}
\newtheorem{Problem}{Problem}


\pagestyle{empty}


\title{Math 668 Problem Set 4: \\ Due Friday, October 7 because of Yom Kippur}


%% NOTE TO SELF: Almost all the problems from 2012 PSet 3 aren't appropriate yet but will be in a week or two; check in then.



\begin{document}

\maketitle
\thispagestyle{empty}


\begin{Problem}
The goal of this problem is to give a representation theoretic meaning to the power sum symmetric functions. Let $V = \CC^n$. Let $\GL_n \times S_d$ act on $V^{\otimes d}$ by:
\[ (g, \sigma)  \cdot (v_1 \otimes v_2 \otimes \cdots \otimes v_d) = (gv_{\sigma^{-1}(1)}) \otimes (g v_{\sigma^{-1}(2)}) \otimes \cdots \otimes (g v_{\sigma^{-1}(d)}). \]
(The inverses are just to make this a left action, and aren't important for this problem.)
Let $\sigma$ be a permutation in $S_d$ with cycle lengths $\lambda_1$, $\lambda_2$, \dots, $\lambda_{\ell}$. 
Let $g$ be a diagonalizable matrix with eigenvalues $x_1$, $x_2$, \ldots, $x_n$. Show that the trace of $(g, \sigma)$, for this action, is $p_{\lambda}(x_1, x_2, \ldots, x_n)$.
\end{Problem}


\begin{Problem}
As on Problem Set $3$, define $\alpha \rightarrow \beta$ to mean that $\beta$ is obtained from $\alpha$ by adding a vertical strip.
\begin{enumerate}
\item Prove the dual Pieri formula. I recommend using the ratio of alternants formula, but multiple proofs exist.
\[ e_k s_{\lambda} = \sum_{\substack{\lambda \rightarrow \mu \\ |\mu| = |\lambda| + k}} s_{\mu}. \]
\item Prove the Pieri formula:
\[ h_k s_{\lambda} = \sum_{\substack{\lambda \uparrow \mu \\  |\mu| = |\lambda| + k}} s_{\mu}. \]
\end{enumerate}
\end{Problem}

\begin{Problem}
%Here is a different, more visual way to describe the Jacobi-Trudi identity.
Let $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_{\ell})$ be a partition. We define a \newword{special rim hook tableau} to be a labeling of the boxes of $\lambda$ with the colors $1$, $2$, \ldots, $\ell$ such that 
\begin{enumerate}
\item In each row and column, the numbers increase weakly from left to right and top to bottom.
\item The set of boxes of each color is either connected or empty, and contains no $2 \times 2$ boxes.
\item If the color $k$ is used, then the lower-left-most box colored $k$ is in column $1$ and row $k$.
\end{enumerate}
For example, here are the $6$ special rim hook tableau of shape $(6,5,3)$:
\[ \young(111111,22222,333)\  \young(111122,22222,333)\ \young(111111,22333,333)\ \young(122222,22333,333)\  \young(111133,22333,333)\  \young(122233,22333,333) . \]
And here are the $6$ special rim hook tableau of shape $(2,2,2)$:
\[ \young(11,22,33)\  \young(12,22,33)\  \young(11,23,33)\  \young(22,23,33)\  \young(13,23,33)\  \young(23,23,33). \]
Let $c_j(T)$ be the number of $j$'s in $T$, and let $h(T)$ be the number of places where $T$ has two vertically stacked boxes with the same entry.
Show that:
\[ s_{\lambda} = \sum_T (-1)^{h(T)} h_{c_1(T)} h_{c_2(T)} \cdots h_{c_{\ell}(T)} . \]
\end{Problem}

\hfill \textbf{Turn over for one more problem!}

\newpage

\begin{Problem}
Let $A$ be an $n \times n$ matrix of nonnegative integers. There are $\binom{2n-2}{n-1}$ paths through this matrix from $A_{11}$ to $A_{nn}$ where each step either moves from $A_{ij}$ to $A_{i(j+1)}$ or from $A_{ij}$ to $A_{(i+1)j}$. For example, the diagram below shows the $6$ paths in the case $n=3$:
\[ 
\left[    \vcenter{\vbox{\xymatrix@R=0.1 in@C=0.1 in{ A_{11} \ar[r] & A_{12} \ar[r] & A_{13} \ar[d] \\ A_{21} & A_{22} & A_{23} \ar[d] \\ A_{31} & A_{32} & A_{33} \\ }}} \right]\quad
\left[    \vcenter{\vbox{\xymatrix@R=0.1 in@C=0.1 in{ A_{11} \ar[r] & A_{12} \ar[d] & A_{13} \\ A_{21} & A_{22} \ar[r] & A_{23} \ar[d] \\ A_{31} & A_{32} & A_{33} \\ }}} \right]\quad
\left[    \vcenter{\vbox{\xymatrix@R=0.1 in@C=0.1 in{ A_{11}\ar[r] & A_{12}\ar[d] & A_{13} \\ A_{21} & A_{22} \ar[d] & A_{23} \\ A_{31} & A_{32} \ar[r] & A_{33} \\ }}} \right] 
\] \[
\left[    \vcenter{\vbox{\xymatrix@R=0.1 in@C=0.1 in{ A_{11} \ar[d] & A_{12} & A_{13} \\ A_{21}  \ar[r]& A_{22}  \ar[r]& A_{23} \ar[d] \\ A_{31} & A_{32} & A_{33} \\ }}} \right]\quad
\left[    \vcenter{\vbox{\xymatrix@R=0.1 in@C=0.1 in{ A_{11} \ar[d]  & A_{12} & A_{13} \\ A_{21} \ar[r] & A_{22} \ar[d] & A_{23} \\ A_{31} & A_{32} \ar[r] & A_{33} \\ }}} \right]\quad
\left[    \vcenter{\vbox{\xymatrix@R=0.1 in@C=0.1 in{ A_{11} \ar[d] & A_{12} & A_{13} \\ A_{21} \ar[d] & A_{22} & A_{23} \\ A_{31} \ar[r] & A_{32} \ar[r] & A_{33} \\ }}} \right]
\] 
We define $L(A)$ to be the maximum of $\max_{\gamma} \left( \sum_{(i,j) \in \gamma} A_{ij} \right)$ where the maximum runs over these $\binom{2n-2}{n-1}$ paths. For example, in the $n=3$ case, 
\begin{multline*} L(A) = \max( A_{11}+A_{12} + A_{13} + A_{23} + A_{33} , \ A_{11}+A_{12} + A_{22} + A_{23} + A_{33} ,\  A_{11}+A_{12} + A_{22} + A_{32} + A_{33} , \\  A_{11}+A_{21} + A_{22} + A_{23} + A_{33} ,\  A_{11}+A_{21} + A_{22} + A_{32} + A_{33} ,\  A_{11}+A_{21} + A_{31} + A_{32} + A_{33} ). \end{multline*}


\begin{enumerate}
\item Use the RSK bijection to turn $A$ into a pair $(T,U)$ of SSYTs of shape $\lambda$. Show that $\lambda_1 = L(A)$. 
\item If $A$ is a permutation matrix, meaning that there is a permutation $w$ such that $A_{w(j) j} = 1$ and $A_{ij}=0$ for all other $(i,j)$, what is the relation between $L(A)$ and the longest increasing subsequence of $w$?
\end{enumerate}
\end{Problem}

\end{document}