\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
\newcommand{\Z}{{\bf Z}}
\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#18 \\
(due 12/4/01)
\end{center}
\medskip

\begin{enumerate}

\item
(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)] 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}$.

\item[(b)] 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)$.

\item[(c)] 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.
\end{itemize}

\item
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.

\end{enumerate}

\end{document}
