\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Selected Solutions and Comments -- Problem Set 8}
\centerline{April 22, 2005}
\bigskip
\noindent
I.  A)  We begin by adapting the Hall's Theorem argument done
in class for (0,1)-matrices to this case.  If $M$ is an 
$n\times n$ non-negative integer magic square with row and 
column sum $s > 0$.  For each $i$, $i = 1, \ldots, n$, let 
$$A_i = \{j : m_{ij} \ne 0\}.$$
We claim that the ``marriage condition'' is satisfied for
the family of sets ${\cal A} = (A_1,\ldots, A_n)$.  To see this,
consider $I \subseteq \{1,\ldots,n\}$.  If the marriage condition
fails, then
$|\cup_{i\in I} A_i| < |I|$.  This says that the nonzero
entries in the rows labeled by the elements of $I$ are contained
in some number $\ell < |I|$ of columns.  Adding up the entries in 
those rows, 
since the row sums are all the same, equal to $s$,
we get $s|I|$.  But those entries are contained in only $\ell$
columns, and the total column sum for those columns is $s\ell$.  This
gives $s|I| \le s\ell$ for some $\ell < |I|$.  This is clearly a 
contradiction, so the marriage condition must hold.  
Hence by Hall's Theorem, there
is an SDR for the family ${\cal A}$, or what is the same:
\medskip
\item{} (*) {\it There is 
a permutation matrix $P$ whose 1's occur in locations where $M$
has nonzero entries}.  
\medskip
\noindent
We are now ready for the ``main part of the proof''.  We argue by
induction on the row and column sum $s \ge 1$.  The base case is
$s = 1$.  If we have $M$ with $s = 1$, then since all entries are
nonnegative, there is exactly one nonzero entry (a 1) in each row and 
each column, so $M$ {\it is} a permutation matrix.  

Now assume that all $M$ with row and column sum $s = k$ can be written
as nonnegative integer linear combinations of the permutation matrices.
Then consider $M$ with row and column sum $s = k+1$.  By the statement (*)
above, there exists a permutation matrix $P$ such that $M - P = M'$
has all entries nonnegative still.  This says 
$M = P + M'$.  Now $M'$ is clearly also a magic square, and has
row and column sum $s = k$.  Hence by induction we have
$M' = \sum_{j} a_j P_j$ where $a_j \ge 0$ are integers, and 
$P_j$ are permutation matrices.  Hence 
$$M = P + M' = P + \sum_{j} a_j P_j$$
also has the form as claimed. 
\bigskip
\noindent
{\it Comment:}  A slightly different induction on the 
number of nonzero entries in the matrix can also be used here.
That version is a {\it finite} induction argument, since
the smallest possible number of nonzero entries in $M$ is $n$ and
the largest number is $n^2$.  
\bigskip
\noindent
B)  If $aI + bS + cS^2 + dT_{12} + eT_{13} + fT_{23} = 0$, then 
from the 9 entries in the matrix we get equations
$$\eqalign{ a + f = 0 \quad c + d &= 0 \quad b + e = 0\cr
            b + d = 0 \quad a + e &= 0 \quad c + f = 0\cr
            c + e = 0 \quad b + f &= 0 \quad a + d = 0\cr}$$
By inspection, $a = b = c = 1, d = e = f = -1$ is one nontrivial solution,
so we get a linear dependence:
$$I + S + S^2 - dT_{12} - eT_{13} - fT_{23} = 0$$
This corresponds to the matrix equations:
$$I + S + S^2 = \pmatrix{1 & 1 & 1\cr
1 & 1 & 1\cr
1 & 1 & 1\cr} = T_{12} + T_{13} + T_{23}.\leqno(1)$$

To show that the $3\times 3$ permutation matrices span a 5-dimensional
vector subspace of the $3\times 3$ matrices, it suffices to show
that some 5 of them are {\it linearly independent}.  This can
be seen from the above if we omit one term, for instance $fT_{23}$.
Then $a = b = c = d = e = f =0$.  So $\{I,S,S^2,T_{12},T_{13}\}$
is linearly independent.
\bigskip
\noindent
C and D)  By part A, every magic square $M$ can be written 
as $aI + bS + cS^2 + dT_{12} + eT_{13} + fT_{23}$ where
$a,\ldots,f$ are nonnegative integers.  That implies 
$s = a + b + c + d + e + f$.  If the 6 matrices were linearly 
independent, then we could apply the usual formula for counting
nonnegative integer solutions of an equation $a_1 + \cdots + a_k = s$,
namely ${s + k-1\choose k-1}$.  But the linear dependence from part
B shows that this approach needs to be modified because it is 
possible for different linear combinations to give the same
matrix.  The key idea here is that because of the last part of B, any
duplications are a result of the equation (1) above.  We get
duplicate linear combinations yielding magic squares of sum $s$
by adding any magic square of sum $s - 3$ to both sides of (1).
This means that the number of distinct magic squares is
$${s + 5 \choose 5} + {s - 3 + 5 \choose 5} = 
{s + 5 \choose 5} + {s + 2 \choose 5}$$
With $s = 2$, we get ${7\choose 5} = 21$, with $s = 3$ (the first
time (1) comes into play) ${8\choose 5} - {5\choose 5} = 55$, and 
with $s = 4$, we get ${9\choose 5} - {6\choose 5} = 120$.

\bigskip
\noindent 
Chapter 11/22, 23, 24.  
\bigskip
\noindent
22 (i)  $x\sim x$ is true because $x = x$ (see the 
definition of the $\sim$ relation on $V$).  (ii)  Suppose $x\sim y$.
Then $x = y$ or there is a walk from $x$ to $y$.  If $x = y$, then
$y = x$ also.  If there is a walk from $x$ to $y$, we can just reverse
the order in which the edges are traversed in the walk to obtain a 
walk from $y$ to $x$.  Hence $y \sim x$.  Reversing the roles of $x$
and $y$ in this argument also shows $y \sim x \Rightarrow x \sim y$.
(iii) Let $x\sim y$ and $y\sim z$.  If $x = y$ and $y = z$, then 
clearly $x = z$.  If $x = y$ and there is a walk from $y$ to $z$,
then there is also a walk from $x$ to $z$.  Similarly, if 
there is a walk from $x$ to $y$ and $y = z$, there is also a 
walk from $x$ to $z$.  Finally, if there are walks from $x$ to $y$
and $y$ to $z$, then we can put the two walks together to form a walk
from $x$ to $z$.  In all cases, $x \sim z$.
\bigskip
\noindent
23.  Let $C(x) = \{ z : x \sim z\}$.  (i) Assume we have vertices
$x$ and $y$ and $C(x) \cap C(y) \ne \emptyset$.  Then there is 
some $z \in C(x) \cap C(y)$, so $z \sim x$ and $z \sim y$.  By 
22 parts (ii) and (iii), this implies $x \sim y$.  Hence $C(x) = C(y)$,
since when $x \sim y$, it follows that $z \sim x \Leftrightarrow z \sim y$.
(ii)  Assume $C(x) \cap C(y) = \emptyset$, but there are some
vertices $u\in C(x)$ and $v \in C(y)$ which are connected by an edge.
By definition and 22, we have $x \sim u$, $u\sim v$ and $v \sim y$, 
so $x \sim y$.  As in part (i), this implies $C(x) = C(y)$ which
is a contradiction.  Hence no vertex in $C(x)$ is connected by 
an edge to any vertex in $C(y)$.
\bigskip
\noindent
24.  Let $V_i$ be the distinct sets $C(x)$ in the graph.  For each 
$x\in V$, 22 (i) shows $x \in C(x)$, so all the vertices are included.
Furthermore, if $i \ne j$, then 23 part (i) shows $V_i \cap V_j = 
\emptyset$.  So the $V_i$ form a partition of $V$.
(ii)  We must show that $(V_i,E_i)$ are all connected graphs.
So let $u\ne v \in V_i = C(x)$.  Then $u\sim x$ and $v\sim x$.
So by 22 (ii) and (iii), $u\sim v$.  This means that $u$ and $v$
are connected by a walk, which must lie entirely in $V_i$ (since 
all the vertices on the walk are also connected to $x$ by walks).  Hence
$G_i=(V_i,E_i)$ is connected.
\bigskip
\noindent
Comments on Chapter 11/22,23,24.  Note that these problems are dealing with 
general concepts about {\it equivalence relations}.  The three
parts of 22 ask you to show that the $\sim$ relation satisfies
the reflexive, symmetric, and transitive properties.  Hence,
it {\it is} an equivalence relation on the set of vertices of
the graph $G$.  Then, in problem 23, the $C(x)$ is just
the {\it equivalence class} of the vertex $x$ -- the set
of all vertices $z$ such that $z \sim x$.  Part (i) is actually
a {\it general property} of equivalence classes.  Two equivalence
classes for an equivalence relation $\sim$ are always either
{\it identical, or disjoint}.  Similarly, problem 24 also 
comes from a general fact about equivalence relations.
Namely, the equivalence classes for an equivalence 
relation $\sim$ on a set form a partition of the set.  Note
that 24 (i) follows directly from 23 (i).

\bigskip
\noindent
Chapter 11/28.  We argue by induction on $k$.  The base case
is $k = 1$.  By definition,
the adjacency matrix of a graph $G$ of order $n$ 
is the $n\times n$ matrix $A = (a_{ij})$
with rows and columns labeled by the vertices in the graph, where
$a_{ij}$ is the number of edges from vertex $i$ to vertex $j$.  A
walk of length 1 is just an edge going from one vertex to another, so
by definition, the $a_{ij}$ entry in $A$ is the number of walks of 
length 1 from vertex $i$ to vertex $j$.

Now assume that in $A^k = (m_{pq})$, the entry $m_{pq}$ is the number
of walks of length $k$ from vertex $p$ to vertex $q$.  In the 
power $A^{k+1} = A A^k$, the $i,j$ entry is 
$$\sum_{p=1}^n a_{ip} m_{pj} = a_{i1}m_{1j} + a_{i2}m_{2j} + \cdots
+ a_{in}m_{nj}\leqno(2)$$
 The product
$a_{ip} m_{pj}$ then gives the number of walks of 
length $k+1$ from vertex $i$ to 
vertex $j$ {\it which start out with an edge from vertex $i$ to vertex $p$},
and then continue from there to vertex $j$ by a walk of length $k$. 
Every walk of length $k+1$ from vertex $i$ starts out with 
an edge from vertex $i$ to vertex $p$ for some $1\le p\le n$.  
Walks that start with edges to different vertices are different,
so the Addition Rule applies, and the sum in (2) gives the total 
number of walks of length $k+1$ from vertex $i$ to vertex $j$
as claimed. 
\bigskip
\noindent
Chapter 11/57.  a) First, if we have a tree with 
vertex degrees $d_1,\ldots, d_n$ (all $>0$, since
trees are connected), then as we said in class,
$$\sum_{i=1}^n d_i = 2|E| = 2(|V| - 1) = 2n - 2,$$
since in a tree we always have $|E| = |V| - 1$. 

Conversely, we need to show that if $d_1,\ldots,d_n$ satisfy
$\sum_{i=1}^n d_i = 2n - 2$, then there is a tree with these
vertex degrees.  We argue by induction on $n = $ the order of the 
tree (the number of vertices).  The base case is $n=2$ if we 
want trees with actual edges.  The only solution of $d_1 + d_2 = 2$
with $d_i > 0$ is $d_1 = d_2 = 1$.  There is clearly a tree with
these degrees:  Just take two vertices and connect them by an 
edge(!)

For the induction step, we assume that for $n = k$ and 
{\it all} sets of positive integers $d_1,\ldots,d_k$ with 
$\sum_{i=1}^k d_i = 2k - 2$,
there exist trees with those degrees.  Then consider $d_1,\ldots,d_{k+1}$
with $\sum_{i=1}^{k+1} d_i = 2(k+1) - 2 = 2k$.  We will show how
to produce a tree of order $k+1$ with these degrees (and our method
can be used to produce a {\it recursive} algorithm for part b).  
First note that if we have $k+1$ positive numbers adding up to $2k$,
then at least one (in fact at least two) have to equal 1, and at least
one is $> 1$.  For simplicity, we will order the $d_i$ so that
$d_{k+1} = 1$ and $d_k > 1$.  

Key step: Drop the last number $d_{k+1}=1$ and reduce $d_k$ by 1
to get $d_k - 1$ ($d_k > 1$, so $d_k - 1$ is still $>0$). Leave the first $k-1$ unchanged. (See below for
the motivation for doing this(!)) The resulting list 
of numbers: $d_1,d_2,\ldots,d_k-1$ contains $k$ numbers and satisfies
$$d_1 + d_2 + \cdots + (d_k - 1) = 2k - 2.$$
By the induction hypothesis, there exists a tree $T = (V,E)$
 with vertices $V = \{v_1, \ldots, v_k\}$ and degrees
$d_1,d_2,\ldots,d_k-1$.  Then we get a tree with degrees
$d_1,d_2,\ldots,d_k,d_{k+1}$ by attaching a new ``leaf''
vertex $v_{k+1}$ to $v_k$ by a single edge.  
\bigskip
\noindent
{\it Comment:} The procedure of attaching new leaves
 to existing trees in every possible way could also be used to generate
all trees, up to isomorphism of graphs.
\bye


 


