\documentclass[12pt]{article}
\newcommand{\sign}{{\rm sign}}
%\pagestyle{empty}
\begin{document}
\begin{center}
Math 192r, Problem Set \#16: Solutions
\end{center}
\medskip
\begin{enumerate}
\item
{\it Use Dodgson condensation to prove the
Vandermonde determinant formula 
$$\det(M)=\prod_{1 \leq i < j \leq n} (x_j-x_i)$$
where $M$ is the $n$-by-$n$ matrix
whose $i,j$th entry (for $1 \leq i,j \leq n$)
is $x_j^{i-1}$.}

The claim is easily verified for $n=0$ and $n=1$.
We will prove higher cases by induction;
hence hereafter we will assume that the formula is true
for $n-1$ and $n-2$ in order to prove it for $n>1$.
Write the determinant of $M$ as $d_n(x_1,x_2,\dots,x_n)$.
If we apply Dodgson condensation to this matrix, we get
\begin{eqnarray*}
d_n(x_1,\dots,x_n) e_{n-2}(x_2,\dots,x_{n-1})
& = & d_{n-1}(x_1,\dots,x_{n-1}) e_{n-1}(x_2,\dots,x_n) \\
& & - d_{n-1}(x_2,\dots,x_n) e_{n-1}(x_1,\dots,x_{n-1}),
\end{eqnarray*}
where $e_m(y_1,\dots,y_m)$
is the determinant of the $m$-by-$m$ matrix
whose $i,j$th entry is $x_j^i$.
By the multilinearity of the determinant,
$$e_m(y_1,\dots,y_m) = y_1 \cdots y_m \, d_m(y_1,\dots,y_m),$$
so the condensation relation may be written as
$$ x_2 \cdots x_{n-1} D_1^n D_2^{n-1}
= x_2 \cdots x_n D_1^{n-1} D_2^n
- x_1 \cdots x_{n-1} D_2^n D_1^{n-1},$$
where $D_i^j$ is short for $d_{j-i+1}(x_i,\dots,x_j)$.
Simplifying, we obtain
$$D_1^n D_2^{n-1} = x_n D_1^{n-1} D_2^n - x_1 D_2^n D_1^{n-1}$$
or
$$D_1^n D_2^{n-1} = (x_n-x_1) D_1^{n-1} D_2^n.$$
Our induction hypothesis implies that
$D_1^{n-1} = \left( \prod_{j=2}^{n-1} (v_j-v_1) \right) D_2^{n-1}$
and
$D_2^{n} = \left( \prod_{i=2}^{n-1} (v_n-v_i) \right) D_2^{n-1}$,
so the right hand side of the preceding inset equation
can be rewritten as
$$(x_n-x_1) 
\left( \prod_{j=2}^{n-1} (v_j-v_1) \right) \left( D_2^{n-1} \right)
\left( \prod_{i=2}^{n-1} (v_n-v_i) \right) \left( D_2^{n-1} \right) .$$
Hence
\begin{eqnarray*}
D_1^n & = &
(x_n-x_1) 
\left( \prod_{j=2}^{n-1} (v_j-v_1) \right) 
\left( \prod_{i=2}^{n-1} (v_n-v_i) \right)
D_2^{n-1} \\
& = &
(x_n-x_1) 
\left( \prod_{j=2}^{n-1} (v_j-v_1) \right) 
\left( \prod_{i=2}^{n-1} (v_n-v_i) \right)
\left( \prod_{2 \leq i < j \leq n-1} (v_j-v_i) \right) \\
& = &
\prod_{1 \leq i < j \leq n} (v_j-v_i), 
\end{eqnarray*}
which was to be proved.

Someone reading the above might object that
there is a flaw in the proof,
inasmuch as we are dividing by an expression $D_2^n$
that can vanish
(and indeed will vanish if any two of $x_2,\dots,x_{n-1}$ are equal),
and that it is invalid to divide by zero.
But this objection has no force,
since we our conducting our proof in the realm of formal polynomials
and formal rational functions.
In the field of rational functions in the two variables $x$ and $y$, 
the expressions $(x^2-y^2)/(x-y)$ and $x+y$
are actually equal;
one does not substitute actual values for $x$ and $y$,
so one need not worry about ``what if'' $x=y$.

On the other hand, once one has proved
that a pair of polynomials are equal
as formal expressions
(namely, the determinant of a certain matrix
and a certain product of differences),
one can treat the two polynomials as functions
and make substitutions for the variables.
So the Vandermonde identity that we have proved
isn't just true for one particular $n$-by-$n$ matrix 
in the ring of polynomials in the variables $x_1,\dots,x_n$;
it's true for every $n$-by-$n$ matrix
whose entries are particular values satisfying certain relations.

\item
{\it Using Dodgson condensation, Lindstrom's lemma,
and the bijection between tilings and routings discussed in class,
prove that for all $a,b,c \geq 0$, 
the number of ways to tile an $a,b,c,a,b,c$
semiregular hexagon with unit rhombuses is equal to
$$\frac{H(a+b+c)H(a)H(b)H(c)}{H(a+b)H(a+c)H(b+c)}$$
where
$H(0)=H(1)=1$ and
$H(n)=1!2!3! \cdots (n-1)!$ for $n > 1$.}

Let $T(a,b,c)$ denote the number of rhombus tilings
of the $a,b,c,a,b,c$ semiregular hexagon.
It is easy to check that for all $a,b \geq 0$,
$T(a,b,0) = 1 = \frac{H(a+b+0)H(a)H(b)H(0)}{H(a+b)H(a+0)H(b+0)}$
and
$T(a,b,1) = \frac{(a+b)!}{(a)!(b)!} =
\frac{H(a+b+1)/H(a+b)}{(H(a+1)/H(a))(H(b+1)/H(b)}$ 
%kludge
$=\frac{H(a+b+1)H(a)H(b)H(1)}{H(a+b)H(a+1)H(b+1)}$.
We will prove the claim for $c>1$ using induction on $c$.

Rhombus-tilings of the $a,b,c,a,b,c$ semiregular hexagon
correspond to routings with $c$ sources and $c$ sinks
in a directed graph
in which the number of paths from the $i$th source to the $j$th sink
equals $a+b \choose b-i+j$.
Therefore by Lindstrom's lemma we have
$T(a,b,c) = \det M(a,b,c)$
where $M(a,b,c)$ denotes the $c$-by-$c$ matrix
whose $i,j$th entry is $a+b \choose b-i+j$.
In view of the this,
Dodgson condensation tells us that
\begin{eqnarray*}
T(a,b,c) T(a,b,c-2) &=& T(a,b,c-1)^2 \\
& & - T(a+1,b-1,c-1) T(a-1,b+1,c-1).
\end{eqnarray*}
For slight notational convenience,
I'll re-index this as
$$T(a,b,c+1) T(a,b,c-1) = T(a,b,c)^2 - T(a+1,b-1,c) T(a-1,b+1,c).$$
The problem now reduces to algebraically verifying
that $T(a,b,c+1)$ must be given by the $H(\ )$-formula
if $T(a,b,c-1)$, $T(a,b,c)$, $T(a+1,b-1,c)$ and $T(a-1,b+1,c)$ are.
Equivalently, we must verify that if all five of these $T(\ )$-values
are as given by the $H(\ )$-formula, then the expression
$$T(a,b,c+1) T(a,b,c-1) - T(a,b,c)^2 + T(a+1,b-1,c) T(a-1,b+1,c)$$
must vanish.

If we trust Maple, then we can prove this
by noting that the final command in the string of commands
\begin{verbatim}
H := proc(n) product(k!,k=1..n-1); end;
T := proc(a,b,c) H(a+b+c)*H(a)*H(b)*H(c)
        /H(a+b)/H(a+c)/H(b+c); end;
U := T(a,b,c)*T(a-2,b,c)-T(a-1,b,c)^2
        +T(a-1,b-1,c+1)*T(a-1,b+1,c-1);
simplify(expand(U));
\end{verbatim}
gives the output {\tt{0}}.
However, if you're more skeptical, 
here's a sketch of how you can show by hand
that the expression
$T(a,b,c+1) T(a,b,c-1) - T(a,b,c)^2 + T(a+1,b-1,c) T(a-1,b+1,c)$
vanishes
when each $T(\ )$ is expanded using the $H(\ )$-formula.
Write each of the three terms as a fraction,
and in each of the terms
divide the numerator by
$H(a+b+c-1)H(a+b+c)H(a-1)H(a)H(b-1)H(b)H(c-1)H(c)$
and the denominator by
$H(a+b)^2 H(a+c-1)H(a+c) H(b+c-1)H(b+c)$,
obtaining another messy expression.
But we have made progress:
where before we had a sum each term of which was a ratio of products
each factor of which was a value of the $H$-function,
we now have a sum each term of which is a ratio of products
each factor of which is a value of the factorial function,
Moreover, there are now some factors common to all three terms;
removing them gives
\begin{eqnarray*}
&   \frac{(a+b+c)!(a-1)!(b-1)!(c)!}{(a+c)!(b+c)!} & \\
& - \frac{(a+b+c-1)!(a-1)!(b-1)!(c-1)!}{(a+c-1)!(b+c-1)!} & \\
& + \frac{(a+b+c-1)!(a)!(b)!(c-1)!}{(a+c)!(b+c)!}. & 
\end{eqnarray*}
Removing common factors again gives us
$$(a+b+c-1)(c-1) - (a+c-1)(b+c-1) + (a)(b),$$
which vanishes.
\end{enumerate}

\end{document}
