\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}
