%\documentclass{amsart}
\documentclass[11pt]{amsart}
\usepackage[hmargin=0.75 in, vmargin = 0.75 in]{geometry}

\parindent=0 in
\parskip=0.05 in



\usepackage[normalem]{ulem}
%\usepackage{graphbox}
\usepackage[all]{xy}
\usepackage{times}
\usepackage[leqno]{amsmath}
\usepackage{amssymb}
\usepackage{tabu}
\usepackage{longtable}
%\usepackage{hyperref} 
\usepackage{textcomp}
\usepackage[perpage]{footmisc}
\usepackage{tabulary}
%\usepackage{wasysym}
\usepackage{enumitem}
\usepackage{mathtools}
%\usepackage{url}
\usepackage{hyperref}
\usepackage{tikz-cd}
\usepackage{array}
%\usepackage{mathalfa}

\newcommand{\isom}{\cong} %The isomorphism symbol
\newcommand{\union}{\cup}
\newcommand{\intersection}{\cap}
\newcommand{\bigunion}{\bigcup}
\newcommand{\bigintersection}{\bigcap}
\newcommand{\disjointunion}{\sqcup}
\newcommand{\bigdisjointunion}{\bigsqcup}

\newcommand{\join}{\vee}
\newcommand{\meet}{\wedge}
\newcommand{\bigjoin}{\bigvee}
\newcommand{\bigmeet}{\bigwedge}


%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{\fm}{\mathfrak{m}}

\newcommand{\Stab}{\mathrm{Stab}}
\newcommand{\Fix}{\mathrm{Fix}}
\newcommand{\Conj}{\mathrm{Conj}}
\newcommand{\Aff}{\mathrm{Aff}}
\newcommand{\PSL}{\mathrm{PSL}}

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

\newtheorem*{Theorem}{Theorem}
\newtheorem*{Remark}{Remark}
\newtheorem*{Definition}{Definition}






\newcommand{\into}{\hookrightarrow}
\newcommand{\onto}{\twoheadrightarrow} 
\newcommand{\from}{\leftarrow}

\newenvironment{sbm}
    {\left[ \begin{smallmatrix}
    }
    { 
     \end{smallmatrix} \right]
    }
    
\newcommand{\newword}[1]{\textbf{\emph{#1}}}


% This makes quotients G\X typeset with spacing similar to X/G, which neither \backslash nor \setminus will do. Thanks to Philippe Goulet at https://tex.stackexchange.com/a/7110/5034 for this solution.

\def\leftquot{\delimiter"526E30F\mathopen{}} 




        \DeclareMathOperator{\diag}{diag}
      \DeclareMathOperator{\dist}{dist}
      \DeclareMathOperator{\nilrad}{Nil}
            \DeclareMathOperator{\Ker}{Ker}
                        \DeclareMathOperator{\CoKer}{CoKer}
                        \renewcommand{\Im}{\mathrm{Im}}
      \DeclareMathOperator{\spec}{Spec}
    \DeclareMathOperator{\jeff}{mod}
     \DeclareMathOperator{\alg}{alg}
   \DeclareMathOperator{\Tor}{Tor}
      \DeclareMathOperator{\ring}{ring}
        \DeclareMathOperator{\grp}{grp}
     \DeclareMathOperator{\dExt}{Ext}
        \DeclareMathOperator{\GCD}{GCD}
                \DeclareMathOperator{\LCM}{LCM}
     
     
%This command puts the words "Worksheet" before the number in the header. Thanks to David Carlisle at https://tex.stackexchange.com/questions/136527/
     
     
\makeatletter
\def\@seccntformat#1{%
  \expandafter\ifx\csname c@#1\endcsname\c@section
 Worksheet \thesection:
  \else
  \csname the#1\endcsname\quad
  \fi}
\makeatother
     
%     \theoremstyle{definition}
%\newtheorem{Problem}
\pagestyle{empty}
\begin{document}

\thispagestyle{empty}
\centerline{\sc Problem Set Four: Due Friday, October 9}

\begin{Problem}
Show the following equality of polynomials in $q$:
\[ \sum_{q \in S_n} q^{\ell(w)} = (1+q) (1+q+q^2) (1+q+q^2+q^3) \cdots (1+q+q^2+ \cdots + q^{n-1}) . \]
\end{Problem}


\begin{Problem}

Consider the sequence of matrices:
\[ \begin{bmatrix} 1&& \\ &1& \\ && 1 \end{bmatrix} \quad  \begin{bmatrix} 1&u& \\ &1& \\ && 1 \end{bmatrix} \quad  \begin{bmatrix} 1&u&uv \\ &1&v \\ && 1 \end{bmatrix}  \quad  \begin{bmatrix} 1&u+w&uv \\ &1&v \\ && 1 \end{bmatrix} .  \]
These are the partial products of our factorization $x_1(u) x_2(v) x_3(w)$.

Factor each of these matrices into the form $(N_- w \cap w N_+) B_-$ for the appropriate permutation $w$.


\end{Problem}

\begin{Problem}
This problem introduces \newword{wiring diagrams}, a graphical way to display words in $S_n$. Let $s_{i_1} s_{i_2} \cdots s_{i_r}$ be a word in $S_n$. A wiring diagram consists of $n$ paths in $\RR^2$, starting at $\{ (0,y) : 1 \leq y \leq n \}$ and ending at $\{ (r, y) : 1 \leq y \leq n \}$. In the region between $x=k$ and $x={k+1}$, the paths at height $i_k$ and $i_k+1$ cross and all the others continue straight across. For example, here is a wiring diagram for the word $s_1 s_2 s_3 s_2$ in $S_4$:

\bigskip

\centerline{\begin{tikzpicture}
\node (1L) at (-0.5,1) {$1$};
\node (2L) at (-0.5,2) {$2$};
\node (3L) at (-0.5,3) {$3$};
\node (4L) at (-0.5,4) {$4$};
\node (1R) at (4.5,1) {$1$};
\node (2R) at (4.5,2) {$2$};
\node (3R) at (4.5,3) {$3$};
\node (4L) at (4.5,4) {$4$};
\draw (0,1) to (1,2) to (2,3) to (3,4) to (4,4);
\draw (0,2) to (1,1) to (2,1) to (3,1) to (4,1);
\draw (0,3) to (1,3) to (2,2) to (3,2) to (4,3);
\draw (0,4) to (1,4) to (2,4) to (3,3) to (4,2);
\end{tikzpicture}}

\begin{enumerate}
\item Which is the correct statement: The path starting at $(0,y)$ ends at $(0, w(y))$, or the path starting at $(0,y)$ ends at $(0, w^{-1}(y))$?
\item Show that a word $s_{i_1} s_{i_2} \cdots s_{i_r}$ is reduced if and only if there is no pair of paths that cross more than once.
\end{enumerate}
\end{Problem}

\begin{Problem}
This problem introduces the \newword{strong order} (also called Bruhat order) on the symmetric group. Given a permutation matrix $w$, let $r_{ab}(w)$ be the rank of the upper left $a \times b$ submatrix of $w$. We define $u \leq v$ in strong order iff $r_{ab}(u) \geq r_{ab}(v)$ for all $(a,b)$.

\begin{enumerate}
\item Put a partial order on the set of $k$ element subsets of $[n]$ as follows: Let $I = \{ i_1 < i_2 < \cdots < i_k \}$ and $J = \{ j_1 < j_2 < \cdots < j_k \}$; we define $I \leq J$ iff $i_a \leq j_a$ for all $a$. Show that $u \leq v$ in strong order if and only if $u [k] \leq v [k]$ for $1 \leq k \leq n$.
\item Let $w \in S_n$. For any transposition $(a \ b)$ with $a<b$, show that $w (a\ b) \geq w$ if $w(a) < w(b)$ and that $w(a\ b) \leq w$ if $w(a) \geq w(b)$.
\item Let $u < v$. Show that there is a transposition $(a \ b)$ for which $u < u (a\ b) \leq v$. I am going to leave this one without a hint, because I am curious to see how you'll do it; it is a bit harder than I would ask without one.
\end{enumerate}
\end{Problem}



\end{document}


