\documentclass[12pt]{article}
\usepackage{amsmath,amsfonts}
\usepackage{amssymb}
\usepackage{mathabx}
\usepackage{graphicx}
%\usepackage{color}

\addtolength{\topmargin}{-.55in}
\addtolength{\textheight}{.9in}
\addtolength{\oddsidemargin}{-.2in}
\addtolength{\textwidth}{.4in}
\pagestyle{empty}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\F}{\mathcal{F}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\Q}{\mathcal{Q}}
\renewcommand{\S}{\mathcal{S}}
\renewcommand{\SS}{\mathfrak{S}}
\newcommand{\sgn}{\mathrm{sgn}}
\newcommand{\wt}{\mathrm{wt}}
\newcommand{\inv}{\mathrm{inv}}
\newcommand{\lam}{\lambda}
\newcommand{\cons}{\mathrm{cons}}
\newcommand{\Gr}{\mathrm{Gr}}
\newcommand{\Fl}{\mathrm{Flag}}
\newcommand{\Br}{
\mbox{\small 
$\smash{ 
  \stackrel {\text{deg}} {\leq}
}$
}}

%\newcommand{\multi}[2]{\left(\!\binom{#1}{#2}\!\right)}
%\newcommand{\multi}[2] { \genfrac {(} {)} {0em} {} {#1} {#2} }
\newcommand{\multi}[2]{\left(\!\left(\!
\genfrac{}{}{0pt}{}{#1}{#2}\!\right)\!\right)}

\newcommand{\stirling}[2]{\left\{
\genfrac{}{}{0pt}{}{#1}{#2}\right\}}

\newcommand{\cycle}[2]{\left[
\genfrac{}{}{0pt}{}{#1}{#2}\right]}

\newcommand{\form}[1]{[\![#1]\!]}

\newcommand{\actson}{\mathbin{\rotatebox[origin=c]{-90}{$\circlearrowright$}}}


\begin{document}
\centerline{\bf Math 880 \hfill{\large\bf \quad Homework 5}\hfill Due Mon 10/29}
\vspace{1em}

\noindent  
If you get significant help from a reference or a person, give explicit credit. 
\\[1em]
{\sc Notes} 
\\[.5em]
The Grassmannian $\Gr(k,F^n)$ 
is the parameter space whose points correspond to
$k$-dimensional subspaces $V$ in the $n$-dimensional
vector space $F^n$ over a given field $F$.
We specify a subspace $V=\mathrm{Span}_F(v_1,\ldots,v_k)$ 
by a $k{\times}n$ matrix of row vectors,
with change-of-basis symmetry group $\mathrm{GL}_k(F)$.
This matrix can be normalized 
by making a given $k\times k$ submatrix
into the identity, in columns $I=\{i_1<\cdots<i_k\}\subset [n]$,
provided the determinant of this submatrix is nonzero:
$$
V \ =\
\mathrm{GL}_k \actson 
\left[\begin{array}{c}
\text{\---------  $v_1$ \---------} \\
\text{\---------  $v_2$ \---------} \\[-.25em]
\vdots\\[-.25em]
\text{\---------  $v_k$ \---------} \\
\end{array}\right]
\ =\
\left[\begin{array}{@{\,}c@{\ }c@{\,}c@{\!\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\,}c@{\ }c@{\,}}
* & * & \cdots & 1 & \cdots & 0 & \cdots & 0 & \cdots & * & * 
\\
* & * & \cdots & 0 & \cdots & 1 & \cdots & 0 & \cdots & * & * 
\\[-.6em]
&&&&&\vdots\\[-.2em]
* & * & \cdots & 0 & \cdots & 0 & \cdots & 1 & \cdots & * & * 
\end{array}\right]
$$
The $*$'s denote $k(n{-}k)$ free parameters in $F$ defining a coordinate chart $U_I$ of the Grassmannian, 
an $F$-manifold (nonsingular algebraic variety): 
$\Gr(k,F^n) \ =\ \bigcup_I U_I$. 

We define the Schubert cell decomposition  
$\Gr(k,F^n) \ =\ \coprod_I X_I$
by letting $X_I$ consist of those $V\in U_I$ 
which have no $*$'s to the right of any $1$ (row-echelon form). 
Thus, $X_I$ is an affine space of dimension $\wt(I)=\sum_{j=1}^k (i_j{-}j)$.
We can define $X_I$ geometrically in terms of the standard basis
$\{e_1,\ldots,e_n\}$ of $F^n$ and the standard coordinate subspaces 
$E_r=\mathrm{Span}(e_1,\ldots,e_r)$:
$$
V\in X_I\quad\Longleftrightarrow\quad\dim(V{\cap} E_r)=\#(I{\cap} [r]) \text{ for } r=1,\ldots,n.
$$
That is, $I=[k]$ forces $V=E_k$, and larger $I$ makes $V\in X_I$ stick out further from the standard subspaces, until $I=\{n{-}k{+}1,\ldots,n\}$ corresponds to generic $V$'s in the open set $X_I=U_I$.
The topological closure $\overline{X}_I$ is defined by the closed conditions: 
$\dim(V{\cap} E_r)\geq \#(I{\cap} [r])$ for $r=1,\ldots,n$.
We keep track of how cells fit together using Bruhat degeneration order:
define $I\leq J$ to mean
${X}_I\subset \overline{X}_J$, or equivalently $\overline X_I \subset \overline X_J$.
\\[1em]
{\sc Example:} For $\Gr(2,F^4)$, we have:
$$
U_{34} \ = \ X_{34}\ =\ 
\left[\begin{array}{@{\,}c@{\ \ \ }ccc@{\,}}
* & * & 1 & 0 \\
* & * & 0 & 1 \\
\end{array}\right]
\ =\ 
\{V \,\mid\, V{\cap} E_2\,{=}\,0\,, \dim(V{\cap} E_3)\,{=}\,1\},
$$
$$
U_{14}  \ =\
\left[\begin{array}{@{\,}c@{\ \ \ }ccc@{\,}}
1 & * & * & 0 \\
0 & * & * & 1 \\
\end{array}\right],
\qquad\quad
X_{14}  \ =\
\left[\begin{array}{@{\,}c@{\ \ \ }ccc@{\,}}
1 & 0 & 0 & 0 \\
0 & * & * & 1 \\
\end{array}\right]
\ = \
\{V \ | \ E_1\,{\subset}\, V{\not\subset} E_3\}.
$$

\pagebreak

\noindent 
Here are the cells with defining conditions,
vertical dashes indicating Bruhat order: 
\\[.5em]
$$\begin{array}{c}
X_{34}=(V{\cap} E_2=0)
\\[0em]
|
\\[.2em]
X_{24}=(\dim(V{\cap} E_2)\geq 1, V{\not\subset} E_3)
\\[.2em]
/ \hspace{.5in} \backslash
\\[.2em]
X_{23}=( E_1{\not\subset}V{\subset} E_3)
\qquad\qquad
X_{14}=(E_1{\subset} V{\not\subset}E_3)
\\[.2em]
\backslash \hspace{.5in} /
\\[.2em]
X_{13} = (E_1{\subset} V{\subset} E_3, V{\neq} E_2)
\\
|
\\
X_{12}= (V{=} E_2)
\end{array}$$
\\[0em]
The closure of each cell is defined by keeping the closed conditions on $V$ 
such as $\dim(V{\cap} E_2)\geq 1$,
and ignoring the open conditions such as $V{\not\subset} E_3$.
The Bruhat order relations $\overline X_I\subset \overline X_J$
are thus evident from these closed conditions.
To verify in coordinates that $\{1,3\}\leq\{1,4\}$, 
we show each plane $V_\circ\in X_{13}$ is approached by
planes in $X_{14}$: we give a continuous $\mathcal{V}:F\to\Gr(2,F^4)$ 
with $\mathcal V(t)\in X_{14}$ for $t\neq 0$, and $\mathcal V(0)=V_\circ$\,.
$$
V_\circ  =
\left[\begin{array}{@{\,}c@{\ \ \ }ccc@{\,}}
1 & 0 & 0 & 0 \\
0 & a & 1 & 0 \\
\end{array}\right],
\qquad
\mathcal{V}(t)  =
\left[\begin{array}{@{\,}c@{\ \ \ }ccc@{\,}}
1 & 0 & 0 & 0 \\
0 & a & 1 & t \\
\end{array}\right]
 =
\left[\begin{array}{@{\,}c@{\ \ \ }ccc@{\,}}
1 & 0 & 0 & 0 \\
0 & \!a/t\! & \!1/t\! & 1 \\
\end{array}\right] 
\text{ for $t\neq 0$.}
$$

Next we consider the flag manifold $\Fl(F^n)$, the parameter space of flags 
$$V_\bullet=(0\subset V_1\subset\cdots\subset V_{n-1}\subset F^n),
\quad \dim(V_k) = k.
$$
We specify $V_\bullet$ 
by a basis $\{v_1,\ldots,v_n\}$ of $F^n$, with $V_k=\mathrm{Span}(v_1,\ldots,v_k)$; the basis forms an $n{\times}n$ matrix of row vectors. The change-of-basis 
symmetry group $B$ of $V_\bullet$ 
consists of all {\it lower}-triangular matrices (with non-zero diagonal entries) in $\mathrm{GL}_n(F)$, since we can add a multiple of $v_i$ to any later basis vector $v_j$ with $j>i$, leaving each $V_k$ invariant. 
We get a Schubert cell decomposition indexed by permutations
$w\in \SS_n$: $\mathrm{Fl}(F^n) = \coprod_{w} X_w$,
where $X_w$ consists of $V_\bullet$ whose
$B$-reduced form is a permutation matrix $w$ with 1 in positions $(i,w(i))$,
and free parameters $*$ in the positions $(i,j)$ of the R\"othe diagram:
$$
D(w) = \{(i,j) \mid j\,{<}\,w(i), \ i\,{<}\,w^{-1}(j)\}.
$$
Thus $\dim(X_w)$ is an affine space of dimension $\#D(w)$.

\pagebreak

\noindent
{\sc Problems}
\\[.5em]
{\bf 1.} For a permutation $w\in \SS_n$, define the inversion number 
$$
\inv(w) = \#\{(i,j)\mid i<j\text{ and } w(i)>w(j)\}.
$$ 
Prove that $\#D(w) = \inv(w)$. {\it Hint:} Bijection.
\\[.5em]
{\it Note:} The inversion number is also equal to 
the length $\ell(w)$, the minimum number $\ell$
of adjacent transpositions $s_i=(i,i+1)$ in a decomposition 
$w=s_{i_1}\cdots s_{i_\ell}$. 
Also $u\leq w$ whenever $u$ is equal to a subword of this decomposition,
for example $s_1s_3\leq s_1s_2s_3s_1$. 
\\[1em]
{\bf 2a.} Compute the Gaussian binomial coefficient
$\cycle63_q \!=\! \#\Gr(3,\FF_q^6)$ as
the number of $3{\times}6$ $V$-basis matrices divided by
the number of $3{\times}3$ change-of-basis matrices;
also as a quotient of $q$-integers $[n]_q=\frac{q^n-1}{q-1}$;
and finally as a polynomial by dividing through
(with computer).
\\[.5em]
{\bf b.} 
There are $\binom 63 = 20$ sets $I=\{i_1,i_2,i_3\}\subset [6]$ 
indexing the Schubert cells, in bijection with partitions
$\lam=(\lam_1\geq \lam_2\geq \lam_3\geq 0)$
with $\lam_1\leq 6{-}3$:
the Young diagrams fit in a $3{\times}3$ rectangle.
List all $I$'s and $\lam$'s, along
with the size measure $q^{\wt(I)}=q^{|\lam|}=\#X_I$.
Here $\wt(I)=|\lam|=\dim(X_I)$.
Compare with part (a).
\\[1em]
{\bf 3a.} Verify the $q$-Binomial Theorem:
$$
\prod\limits_{i=1}^n (1{+}q^i x) \ =\ \sum_{k=0}^n q^{\binom{k+1}2}\binom nk_{\!\!q} x^k
$$
for the special case $n=3$.  Multiply out by hand!
\\[.3em]
{\bf b.} Prove the $q$-Binomial Theorem for all $n$ by 
writing the lefthand side as a bivariate generating function for 
the class of all subsets $I\subset [n]$,
then using our expansion illustrated in Prob.~1, $\binom nk_{\!q} = \sum_I q^{\wt(I)}$,
where the sum is over all $I=\{i_1<\cdots<i_k\}$. 
\\[1em]
{\bf 4.} Find $q$-analogs of the recurrence $\binom nk = \binom{n-1}{k}+\binom{n-1}{k-1}$
using two analogs of deletion.
\\[.5em]
{\bf a.} Consider the mapping $\Gr(k,F^n)\to \Gr(k,F^{n-1})\coprod \Gr(k{-}1,F^{n-1})$
which takes $V$ to $V'= V\cap E_{n-1}$, intersecting with the coordinate subspace $E_{n-1}$.
Make this a bijection by keeping track of lost information needed to reconstruct the row-echelon basis of $V$ from $V'$. 
Deduce a recurrence for $\binom nk_{\!q}$.
\\[.3em]
{\bf b.} Let $P:F^n\to F^{n-1}$ be the projection map along $e_1$, so that $P(e_i)=e_i$
for $i=2,\ldots,n$. Consider the mapping $\Gr(k,F^n)\to \Gr(k,F^{n-1})\coprod \Gr(k{-}1,F^{n-1})$ 
of $V$ to $V'= P(V)$. Again make this a bijection, and find a different
recurrence for for $\binom nk_{\!q}$.
\\[1em]
{\bf 5a.}  For each Schubert cell $X_w\subset\Fl(F^3)$
corresponding to $w\in S_3$, 
write the $B$-reduced matrix form for $V_\bullet$ corresponding 
to the R\"othe diagram $D(w)$.
For $F = \FF_q$, explicitly verify:
$$
\#\Fl(\FF_q^3)
\ =\ \frac{\#\mathrm{GL}_3(\FF_q)}{\#B}
\ =\  [3]_q [2]_q [1]_q 
\ =\  \sum_{w\in S_3} q^{\mathrm{inv}(w)}.
$$
{\bf b.} For each Schubert cell closure $\overline X_w$ above, 
describe its flags $V_\bullet = (V_1\,{\subset}\,V_2)$
in terms of their relation to the standard flag $E_1\,{\subset}\,E_2$.
For example, the minimal cell closure is:
$\overline X_{123}  = X_{123}  = \{E_\bullet\}
= \{V_\bullet\mid V_1\,{=}\,E_1\,,\, V_2\,{=}\,E_2\}$.
By examining the implications among the defining conditions for the $\overline X_w$'s, 
arrange the $w$'s  according their Bruhat degeneration order,
defined by $\overline X_w\subset \overline X_u$.
\\[.3em]
{\bf c.}  The Bruhat order covering relations 
$u\lessdot w$ correspond to minimal containments 
$\overline X_{u}\,{\subset}\,\overline X_w$,
having $\dim X_{u}=\dim X_w - 1$. 
For each minimal containment in $\mathrm{Flag}(F^3)$ 
and any $(V_\bullet)\in X_{u}$, 
we can show the relation by giving
a continuous family $\mathcal{V}:F\to \mathrm{Fl}(F^3)$ with 
$\mathcal{V}(t)\in X_w$ for $t\neq 0$ and $\mathcal{V}(0)=V_\bullet$.
\\[.3em]
{\it Example:} I claim $u = 132 \lessdot w = 231$. By row-echelon reduction for $t\neq 0$:
$$
\mathcal{V}(t) = B\cdot\left[\begin{array}{ccc} 1 & \!-t\ & 0 \\ 0 & a &1 \\ 0 & 1 & 0 \end{array}\right] 
= B\cdot\left[\begin{array}{c@{\ }cc} \!\!\!-1/t\ & 1 & 0 \\ a/t & 0 &1 \\ 1 & 0 & 0 \end{array}\right] 
\in X_{231},
\quad
\mathcal{V}(0) = B\cdot\left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & a &1 \\ 0 & 1 & 0 \end{array}\right]
\in X_{132}.
$$
{\it Problem:} Similarly prove the covering $u = 213 < w = 312$.
\\[.5em]
{\bf d.} A combinatorial construction for the coverings $u\lessdot w$ 
is based on their permutation matrices:
for a pair of 1's making an inversion in $w$ ($i<j$ and $w(i)>j$), 
move them to form a non-inversion pair in $u=(i,j)\cdot w$.
 \\[.3em] 
 {\it Problem:} Find an additional condition on the matrices so that $u\lessdot w$
 is a covering, with $\inv(u)=\inv(w)-1$.
 For example, why does $213 = (2,3)\cdot 312$ give a covering, while $123 = (1,3)\cdot 321$ does not?

\end{document}



{\it Challenge Problems.}  You may substitute one of the following for one of \#1-4 above.
\\[.5em]
{\bf 5.}
Prove a criterion for the Bruhat order $u\leq w$ on $\SS_n$.
You might try:
\begin{itemize}
\item The subword criterion mentioned above.
\item The reflection rule: $u\lessdot w$ whenever $w = u\cdot (i,j)$ with $\ell(w) = \ell(u)+1$.
\item The pullback of the Grassmannian order under the projections
$\Fl_n\to \Gr(k,F^n)$.
This is the simplest combinatorially.
\end{itemize}

\noindent
{\bf 6.} Let $V,W\subset \F_q^n$ be subspaces of dimension $\dim(V)=k$ and $\dim(W)=\ell$ which are transverse, meaning $V\cap W=\{0\}$. 
For fixed $k,\ell,n$, find a formula for the number of such pairs $(V,W)$.


$$\begin{array}{c}
X_{34}=U_{34}=(\dim(V{\cap} E_3)\,{\geq}\,1\,, V{\cap} E_2\,{=}\,0)
\\[.5em]
X_{24}=(\dim(V{\cap} E_2){=}1\,, E_1{\not\subset} V)
\\[.5em]
X_{23}=(E_1{\not\subset} V{\subset} E_3)
\qquad\qquad
X_{14}=(E_1{\subset} V{\not\subset} E_3)
\\[.5em]
X_{13} = (E_1{\subset} V{\subset} E_3\,, V{\neq} E_2)
\\[.5em]
X_{12}= (V{=} E_2)
\end{array}$$

{c.} Redo part (b) in terms of partitions $\lam$
instead of subsets $I$,  
with size measurements 
$|\lam|=\sum_i \lam_i = \Sigma(I)-\binom{d+1}2$ and $\text{wt}(\lam)=\#I$.
\\[.3em]


Consider the bigraded class of all
$I\subset[3]$ with size measures 
$\Sigma(I)=\sum_{i\in I} i$ and $\#I$.
Write the bivariate generating function 
$F(x) = \sum_{I\subset [3]} q^{\Sigma(I)}x^{\#I}$
directly as a sum over all $I$,
and also using the bivariate Product Principle,
transforming sets into bit-strings.
Explain why this is equivalent to 
our Grassmannian counting formulas \smash{$\cycle 3k_q
=\sum_I q^{|I|}$} over $I\subset[3]$, $\#I=d$,
where \smash{$|I|=\Sigma(I)-\binom{d+1}2$}.
\\
REVISE: {\it Prove} the $q$-Binomial Theorem using the Prob 1 expansion
of $\cycle nk_q$.
\\
ALSO: Negative exponent $q$-Binomial Theorem:
$$
\sum_{d\geq 0}\frac{[n]_q^{\overline d}}{[d]_q^!} x^d = \prod_{i=1}^n\frac{1}{1-q^{i-1}x}.
$$
\\[.3em]
{\bf c.} Generalize the $q$-Binomial Theorem
to an infinite product: 
$$
\prod_{i= 1}^\infty (1{+}q^ix)
\ =\ \sum_{I} a_d(q)x^d,
$$
where the right summation runs over 
finite subsets $I\subset \Z_{>0}$, 
and the coefficients are certain rational functions $a_d(q)\in\mathbb{C}(q)\subset \mathbb{C}[[q]]$.
%Explain why the formal $\lim_{n\to\infty}\prod_{i=1}^n(1{+}q^ix)$ exists in $\mathbb{C}[[q,x]]$.
{\it Hint}: To find $a_d(q)$,
transform $I=\{i_1{<}\ldots{<}i_d\}$ into a partition $\lam
=(\lam_1{\geq} \cdots{\geq} \lam_d{\geq} 0)$,
then further into exponential notation
$1^{m_1}2^{m_2}\cdots$, recording
multiplicities $m_j = \#\{i\mid \lam_i=j\}$.
\\[.3em]
{\bf d.} Repeat part (c) for the product: 
$\prod_{i= 1}^\infty (1{-}q^ix)^{-1}$.
{\it Hint:} The transformation is simpler in this case,
since a multiset $I=\{i_1{\leq}\cdots{\leq} i_d\}$ 
is already the same thing as a partition.
\\
Ans:  $$
\prod_{i= 1}^\infty (1{-}q^ix)^{-1}=
\sum_{k\geq 0}\frac{x^kq^k}{(1-q)\cdots(1-q^k)}
=\sum_{k\geq 0}\frac{x^k(1-q)^kq^k}{[k]^!_q}
=\exp_q (q(1{-}q)x)
$$
$$
=\sum_{k\geq0} \frac{x^kq^k^2}{(1-xq)\cdots(1-xq^k)}
\quad\text{Durfree square decomposition}
$$
Also: 
$$
\prod_{i=1}^\infty (1+xq^i) =\sum_{k\geq 0}\frac{x^kq^{\binom k2}}{(1-q)\cdots(1-q^k)
$$
Jacobi Triple Product:
$$
\sum_{k\geq 0} x^kq^{k^2}= \prod{i=1}^\infty (1-q^{2k})(1+xq^{2k-1})(1+x^{-1}q^{2k+1}).
$$