\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
\newcommand{\Z}{{\bf Z}}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 491, Problem Set \#20: Solutions \\
\end{center}
\medskip
\begin{enumerate}
\item
{\it (from unpublished work of Douglas Zare)
Let $G_{m,n}$ be the directed graph with vertex set
$\{(i,j) \in \Z \times \Z: 0 \leq i \leq m, \ 0 \leq j \leq n\}$,
with an arc from $(i,j)$ to $(i',j')$ iff $(j'-j,i'-i)$ is
$(1,0)$, $(0,1)$, or $(1,1)$.}
\begin{itemize}
\item[(a)] {\it For any legal path $P$ in $G_{m,n}$ from $(0,0)$ to $(m,n)$,
define $d(P)$ as the number of diagonal steps in $P$
plus the number of upward steps in $P$ that are followed
{\it immediately\/} by a rightward step.
Show that the number of paths $P$ with $d(P)=k$
is exactly $2^k {m \choose k} {n \choose k}$.}
Given such a path $P$,
shade each of the $k$ squares
that either is bisected by a diagonal step in $P$
or is adjacent to two consecutive steps in $P$
of which the first is vertical and the second is horizontal.
No two of the shaded squares
can be in the same row or column of the square grid,
so the shaded squares occupy $k$ rows and $k$ columns.
Moreover, if two squares are shaded,
the one that is to the right is also strictly higher.
Conversely, given any $k$ rows and $k$ columns in $G_{m,n}$,
shade in the grid-cell that lies in
the $i$th selected row and the $i$th selected column
for $i$ going from 1 to $k$.
For each such shading,
there are exactly $2^k$ paths $P$ in $G_{m,n}$
with those shaded squares.
Specifically,
for each shaded square we may freely choose
either to have $P$ bisect the square with a single diagonal step
or to have $P$ circumvent the square
with a vertical step followed by a horizontal step,
and between two successive shaded squares
(or between $(0,0)$ and the first shaded square,
or between the last shaded square and $(m,n)$)
include a run of horizontal steps
followed by a run of vertical steps.
Each path is accounted for exactly once by this reckoning,
so the number of paths $P$ with $d(P)=k$
is $2^k {m \choose k} {n \choose k}$.
\item[(b)] {\it Let $M$ be the $(n+1)$-by-$(n+1)$ matrix
with rows and columns indexed from 0 through $n$
whose $i,j$th entry is the total number
of paths in $G_{i,j}$ from $(0,0)$ to $(i,j)$.
Use the result of part (a) to find the LDU decomposition of $M$.
That is: find square matrices $L$, $D$, $U$ such that
$LDU=M$, where
$L$ (resp.\ $U$) is a lower (resp.\ upper) triangular matrix
with 1's on the diagonal
and where $D$ is a diagonal matrix
(whose diagonal entries are permitted to be different).
Use this in turn to compute $\det(M)$.}
Put $L_{i,j} = {i \choose j}$,
$U_{i,j} = {j \choose i}$,
and $D_{i,i} = 2^{i}$
with $D_{i,j} = 0$ for $i \neq j$.
Then $(LDU)_{i,j} = \sum_{k} L_{i,k} D_{k,k} U_{k,j}
= \sum_{k} {i \choose k} 2^{k} {j \choose k} = M_{i,j}$,
so $LDU=M$.
Clearly $\det(L)=\det(U)=1$
and $\det(D) = 1 \times 2 \times \cdots \times 2^n = 2^{n(n+1)/2}$,
so $\det(M) = \det(L) \det(D) \det(U) = 2^{n(n+1)/2}$ as well.
\item[(c)] {\it Interpret $M$ as the Lindstrom matrix
of some directed graph and use this in turn to interpret $\det(M)$
as the number of perfect matchings of some graph $H_n$.
Be explicit about what $H_n$ looks like.}
The relevant graph for the first part of the problem
is just $G_{n,n}$ itself,
with the points $(0,j)$ ($0 \leq j \leq n$) serving as sources
and the points $(i,n)$ ($0 \leq i \leq n$) serving as sinks.
Note that one of the sources coincides with the one of the sinks;
these two must be ``joined'' by a path of length 0
in any routing,
and so may be ignored by computational purposes
(though conceptually they are helpful
inasmuch as they make the description of routings
appear more symmetrical).
Each $n$-routing through this directed graph
corresponds to a perfect matching of the deleted double of $G_{n,n}$,
in which every vertex $v$ gets replaced by two vertices $v^-$ and $v^+$
deemed adjacent to one another,
every directed edge $v \rightarrow w$ gets replaced by
an undirected edge joining $v^+$ and $w^-$,
and the vertex $v^-$ (resp.\ $v^+$) is deleted
whenever $v$ is a source (resp.\ sink).
If we do this to $G_{n,n}$
we obtain a bipartite planar graph made up out of trapezoids;
if we rectify the graph so that the trapezoids become squares,
we find that the graph $H_n$
is just the Aztec diamond graph of order $n$.
Thus we have shown that the number of perfect matchings
of the Aztec diamond graph is $2^{n(n+1)/2}$.
\end{itemize}
\item
{\it Fix positive integers $a,b,m,n$ with $n>m$ and $a+n \leq b$,
and let $M(a+1),M(a+2),\dots,M(b+n-1)$ be arbitrary $m$-by-$m$ matrices.
Show that the $n$-by-$n$ matrix
whose $i,j$th entry (for $1 \leq i,j \leq n$) is
the upper left entry of the product matrix $M(a+i) M(a+i+1) \cdots M(b+j-1)$
has determinant zero.}
Create a directed graph with vertices of the form $(i,j)$
for $a+1 \leq i \leq b+n$ and $1 \leq j \leq m$;
for all $i,j,j'$ with $a+1 \leq i \leq b+n-1$ and $1 \leq j,j' \leq m$,
create an edge from $(i,j)$ to $(i+1,j')$
with weight equal to the $j,j'$ entry of the matrix $M(i)$.
Then the upper left entry of
$M(a+i) M(a+i+1) \cdots M(b+j-1)$
is the sum of the weights of all the paths
from $(a+i,1)$ to $(b+j,1)$.
Hence, by Lindstrom's lemma,
the $n$-by-$n$ determinant we are considering
is equal to the number of $n$-routings in the digraph
that join $(a+1,1)$, \dots, $(a+n,1)$,
to $(b+1,1)$, \dots, $(b+n,1)$.
But all $n$ of these paths would have to contain
distinct vertices of the form $(a+n,k)$ for some $k$,
which is impossible since there are only $m