%\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 One: Due Friday, September 11}

\begin{Problem}
This problem is meant to give you some practice using the Lindstr\"om-Gessel-Vienott lemma. 
\begin{enumerate}
\item Consider the $n \times n$ matrix $X_{ij} = \binom{i+j}{i}$ for $0 \leq i,j \leq n-1$. Show that $X$ is totally nonnegative.
\item Consider the $n \times n$ matrix $Y_{ij} = \binom{i}{j}$ for $0 \leq i,j \leq n-1$. Show that $Y$ is totally nonnegative.
\end{enumerate}
\end{Problem}

\begin{Problem}
Let $X$ be a $p \times q$ matrix and $Y$ a $q \times r$ matrix. Show that, if $X$ and $Y$ are totally nonnegative, then $XY$ is a totally nonnegative.
\end{Problem}

\begin{Problem}
This next problem features some lemmas about the symmetric group which we will want soon. Given a permutation $\sigma$ of $\{1,2,\ldots, n\}$, we set $\ell(\sigma) = \# \{ (i,j) \ :\  1 \leq i < j \leq n \ \mbox{and}\ \sigma(i) > \sigma(j) \}$. For $1 \leq i \leq n-1$, let $s_i$ be the permutation with $s_i(i) = i+1$, $s_i(i+1) = i$ and $s_i(j)=j$ for $j \neq i$, $i+1$.

\begin{enumerate}
\item Let $\sigma$ be any permutation and let $1 \leq i \leq n-1$. Show that $\ell(s_i \sigma) = \ell(\sigma) \pm 1$ and $\ell(\sigma s_i) = \ell(\sigma) \pm 1$ for some choice of signs. (The two signs don't have to be the same.
\item Let $\sigma$ be a permutation other than the identity. Show that there is some $i$ with $\ell(\sigma s_i) = \ell(\sigma) -1$ and that there is some $j$ with $\ell(s_j \sigma) = \ell(\sigma)-1$.
\item Let $\sigma$ be a permutation. A \newword{word} for $\sigma$ is a sequence $j_1$, $j_2$, \dots, $j_r$ such that $\sigma = s_{j_1} s_{j_2} \cdots s_{j_r}$; the length of this word is $r$. Show that there is a word for $\sigma$ with length $\ell(\sigma)$, and that there are no words with any shorter length.
\end{enumerate}
\end{Problem}

\begin{Problem}
This next problem features some lemmas about ranks of submatrices which we will want soon. Let $X$ be a $n \times n$ matrix. For $0 \leq a,b \leq n$, let $r_{ab}(X)$ be the rank of the $a \times b$ submatrix in the upper left of $X$. (If $a$ or $b$ is $0$, then $r_{ab}=0$.)
\begin{enumerate}
\item Show that $0 \leq r_{(a+1)b}(X)-r_{ab}(X) \leq 1$ and $0 \leq r_{a(b+1)}(X) - r_{ab}(X) \leq 1$.
\item Show that we cannot have $r_{ab}(X)+1 = r_{(a+1)b}(X) = r_{a(b+1)}(X) = r_{(a+1)(b+1)}(X)$.
\item Show that there are precisely $n!$ matrices $r_{ab}$ with $r_{k0}=r_{0k}=0$, $r_{kn} = r_{nk} = k$ and obeying the conditions of parts~(1) and~(2).
\end{enumerate}
\end{Problem}

\end{document}


