\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#15: Solutions
\end{center}
\medskip
\begin{enumerate}
\item
{\it
Using the combinatorial definition of the determinant,
prove that for all $n$-by-$n$ matrices $A,B$,
$\det(AB)=\det(A) \det(B)$.}
Let $C=AB$, so that $C_{i,k} = \sum_j A_{i,j} B_{j,k}$.
Then $$\det(C) =
\sum_{\pi} \sign(\pi) \sum_{\mu} \prod_{i} A_{i,\mu(i)} B_{\mu(i),\pi(i)},$$
where $\pi$ ranges over all permutations of $\{1,...n\}$
and $\mu$ ranges over all mappings from $\{1,...,n\}$ to itself.
Let's interchange the order of summations.
We'll show that for each fixed $\mu$,
the sum
$$\sum_{\pi} \sign(\pi) \prod_{i} A_{i,\mu(i)} B_{\mu(i),\pi(i)}$$
vanishes unless $\mu$ is a permutation.
Suppose that $\mu$ is not a permutation;
then $\mu(i_1)=\mu(i_2)$ for some $i_1 \neq i_2$.
For notational simplicity and definiteness, assume $i_1=1$ and $i_2=2$
and write $m=\mu(1)=\mu(2)$.
Let $\tau$ be the transposition that swaps 1 and 2.
Then it is easy to check that the map $\pi \mapsto \pi' = \tau \circ \pi$
is a weight-reversing involution on the terms of the sum.
Specifically, $\mu(1)=m=\mu(2)$ implies
\begin{eqnarray*}
\prod_{i=1}^{2} A_{i,\mu(i)} B_{\mu(i),\pi(i)}
&=& A_{1,m} B_{m,\pi(1)} A_{2,m} B_{m,\pi(2)} \\
&=& A_{1,m} B_{m,\pi(2)} A_{2,m} B_{m,\pi(1)} \\
&=& A_{1,m} B_{m,\pi'(1)} A_{2,m} B_{m,\pi'(2)} \\
&=& \prod_{i=1}^{2} A_{i,\mu(i)} B_{\mu(i),\pi'(i)},
\end{eqnarray*}
and since $\pi(i)=\pi'(i)$ for all $i>2$ we have
$$\prod_{i=3}^{n} A_{i,\mu(i)} B_{\mu(i),\pi(i)}
=\prod_{i=3}^{n} A_{i,\mu(i)} B_{\mu(i),\pi'(i)}.$$
Combining these facts, we have
$$\prod_{i=1}^{n} A_{i,\mu(i)} B_{\mu(i),\pi(i)}
=\prod_{i=1}^{n} A_{i,\mu(i)} B_{\mu(i),\pi'(i)}.$$
But $\sign(\pi)=-\sign(\pi')$,
so the two terms cancel.
$\det(C)$ is therefore equal to
$$\sum_{\pi} \sign(\pi) \sum_{\rho}
\prod_{i} A_{i,\rho(i)} B_{\rho(i),\pi(i)}.$$
Letting $\sigma = \pi \circ \rho^{-1}$
(so that $\pi = \sigma \circ \rho$),
we can write
\begin{eqnarray*}
\prod_{i} \left( A_{i,\rho(i)} B_{\rho(i),\pi(i)} \right)
&=& \left( \prod_{i} A_{i,\rho(i)} \right)
\left( \prod_{i} B_{\rho(i),\pi(i)} \right) \\
&=& \left( \prod_{i} A_{i,\rho(i)} \right)
\left( \prod_{i} B_{i,\sigma(i)} \right) \\
&=& \prod_{i} \left( A_{i,\rho(i)} B_{i,\sigma(i)} \right),
\end{eqnarray*}
so that $\det(C)$ equals
$$\sum_{\rho} \sum_{\sigma} \sign(\rho) \sign(\sigma)
\prod_{i} A_{i,\rho(i)} B_{i,\sigma(i)}.$$
But this factors as
$$\sum_{\rho} \sign(\rho) \prod_{i} A_{i,\rho(i)}$$
times
$$\sum_{\sigma} \sign(\sigma) \prod_{i} B_{i,\sigma(i)},$$
or $\det(A)$ times $\det(B)$.
\item
{\it Use Lindstrom's lemma,
the interpretation of domino tilings as routings,
and a computer,
in order to count the domino tilings of an 8-by-8 square,
as well as the domino tilings of an 8-by-8 square
from which two (non-opposite) corners have been removed.}
Checkerboard-color the squares in the grid, so that the
upper-left square is shaded. Mark the mid-point of every vertical
edge that has a black square to its left or a white square to its
right (or both). It's easy to check that every possible placement
of a domino yields either zero or two marked points on its boundary.
Hence, if one fixes a domino tiling and draws connections between
all pairs of marked points that share a domino, one gets four
non-intersecting left-to-right lattice paths joining the four leftmost
marked points to the four rightmost marked points. Conversely, given
four such lattice paths, one can construct a tiling by taking all those
dominoes that cover an edge of the lattice path, along with all dominoes
that are centered on those marked points that do not lie on any of the
lattice paths. Hence there is a bijection between domino-tilings of the
8-by-8 grid and families of non-intersecting lattice paths joining the
sources $s_1,s_2,s_3,s_4$ to the sinks $t_1,t_2,t_3,t_4$ in a trellis-like
directed graph, with directed edges corresponding to the vectors $(1,1)$,
$(1,-1)$, and $(2,0)$. It is easy to see that the only way to connect
the $s_i$'s and the $t_j$'s via non-intersecting paths in this directed
graph is to connect $s_i$ to $t_i$ for $1 \leq i \leq 4$. Hence Lindstrom's
Lemma applies, and the number of families of non-intersecting lattice paths
is equal to the determinant of the 4-by-4 matrix $M$ whose $i,j$th entry
equals the number of lattice paths from $s_i$ to $t_j$.
To determine the entries of $M$, we introduce new vertices in a shifted
lattice that fills the holes in the lattice of marked points. (That is
to say, we now associated a point with every vertical edge.) The points
$s_1,s_2,s_3,s_4$ are the 2nd, 4th, 6th, and 8th points on the left edge
(and similarly for $t_1,t_2,t_3,t_4$). Then the $i,j$th entry of $M$
is equal to the $2i,2j$th entry of $AA^TAA^TAA^TAA^T$, where
$$
A = \left( \begin{array}{cccccccc}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1
\end{array} \right) .
$$
Using Maple, one gets
%\pagebreak
\begin{verbatim}
[ 22 68 30 48 10 12 1 1 ]
[ ]
[ 68 236 116 216 60 84 13 14 ]
[ ]
[ 30 116 62 128 41 61 11 12 ]
[ ]
[ 48 216 128 320 129 230 60 70 ]
[ ]
[ 10 60 41 129 63 128 40 48 ]
[ ]
[ 12 84 61 230 128 306 116 146 ]
[ ]
[ 1 13 11 60 40 116 52 68 ]
[ ]
[ 1 14 12 70 48 146 68 90 ]
\end{verbatim}
Extracting the sub-matrix
\begin{verbatim}
[ 236 216 84 14 ]
[ ]
[ 216 320 230 70 ]
[ ]
[ 84 230 306 146 ]
[ ]
[ 14 70 146 90 ]
\end{verbatim}
and taking its determinant, one gets 12988816.
To solve the other part of the problem, in which two non-opposite
corners (say the two lower corners) get removed, one can just get
rid of $s_4$ and $t_4$, obtaining thereby the three-by-three matrix
\begin{verbatim}
[ 236 216 84 ]
[ ]
[ 216 320 230 ]
[ ]
[ 84 230 306 ]
\end{verbatim}
whose determinant is 2436304.
\end{enumerate}
\end{document}