Mathematics 357 – Combinatorics Selected Solutions and Comments – Problem Set 8 April 22, 2005

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 × n non-negative integer magic square with row and column sum s > 0. For each i, i = 1, …, n, let

A_{i} = {j : m_{ij} ≠ 0}.

We claim that the “marriage condition” is satisfied for the family of sets A = (A_{1}, …, A_{n}). To see this, consider I ⊆ {1, …, n}. If the marriage condition fails, then | ∪_{i∈I} A_{i}| < |I|. This says that the nonzero entries in the rows labeled by the elements of I are contained in some number ℓ < |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 ℓ columns, and the total column sum for those columns is sℓ. This gives s|I| ≤ sℓ for some ℓ < |I|. This is clearly a contradiction, so the marriage condition must hold. Hence by Hall’s Theorem, there is an SDR for the family A, or what is the same:

(*) There is a permutation matrix P whose 1’s occur in locations where M has nonzero entries.

We are now ready for the “main part of the proof”. We argue by induction on the row and column sum s ≥ 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 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′ = ∑_{j} a_{j}P_{j} where a_{j} ≥ 0 are integers, and P_{j} are permutation matrices. Hence

M = P + M′ = P + ∑_{j} a_{j}P_{j}

also has the form as claimed.

Comment: A slightly different induction on the number of nonzero entries in the matrix can also be used here. That version is a finite induction argument, since the smallest possible number of nonzero entries in M is n and the largest number is n^{2}.

B) If aI + bS + cS^{2} + dT_{12} + eT_{13} + fT_{23} = 0, then from the 9 entries in the matrix we get equations

\begin{aligned}a + f = 0 c + d & = 0 b + e = 0 \\ b + d = 0 a + e & = 0 c + f = 0 \\ c + e = 0 b + f & = 0 a + d = 0 \end{aligned}

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:

(1)  I + S + S^{2} = ( \begin{matrix}1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix} ) = T_{12} + T_{13} + T_{23}.

To show that the 3 × 3 permutation matrices span a 5-dimensional vector subspace of the 3 × 3 matrices, it suffices to show that some 5 of them are 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.

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, …, 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} + ⋯ + a_{k} = s, namely \binom{s+k−1}{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

\binom{s + 5}{5} + \binom{s − 3 + 5}{5} = \binom{s + 5}{5} + \binom{s + 2}{5}

With s = 2, we get \binom{7}{5} = 21, with s = 3 (the first time (1) comes into play) \binom{8}{5} − \binom{5}{5} = 55, and with s = 4, we get \binom{9}{5} − \binom{6}{5} = 120.

Chapter 11/22, 23, 24.

22 (i) x ∼ x is true because x = x (see the definition of the ∼ relation on V). (ii) Suppose x ∼ 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 ∼ x. Reversing the roles of x and y in this argument also shows y ∼ x ⇒ x ∼ y. (iii) Let x ∼ y and y ∼ 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 ∼ z.

23. Let C(x) = {z : x ∼ z}. (i) Assume we have vertices x and y and C(x) ∩ C(y) ≠ ∅. Then there is some z ∈ C(x) ∩ C(y), so z ∼ x and z ∼ y. By 22 parts (ii) and (iii), this implies x ∼ y. Hence C(x) = C(y), since when x ∼ y, it follows that z ∼ x ⇔ z ∼ y. (ii)

Assume C(x) ∩ C(y) = ∅, but there are some vertices u ∈ C(x) and v ∈ C(y) which are connected by an edge. By definition and 22, we have x ∼ u, u ∼ v and v ∼ y, so x ∼ 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).

24. Let V_{i} be the distinct sets C(x) in the graph. For each x ∈ V, 22 (i) shows x ∈ C(x), so all the vertices are included. Furthermore, if i ≠ j, then 23 part (i) shows V_{i} ∩ V_{j} = ∅. 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 ≠ v ∈ V_{i} = C(x). Then u ∼ x and v ∼ x. So by 22 (ii) and (iii), u ∼ 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.

Comments on Chapter 11/22,23,24. Note that these problems are dealing with general concepts about equivalence relations. The three parts of 22 ask you to show that the ∼ relation satisfies the reflexive, symmetric, and transitive properties. Hence, it is an equivalence relation on the set of vertices of the graph G. Then, in problem 23, the C(x) is just the equivalence class of the vertex x – the set of all vertices z such that z ∼ x. Part (i) is actually a general property of equivalence classes. Two equivalence classes for an equivalence relation ∼ are always either identical, or disjoint. Similarly, problem 24 also comes from a general fact about equivalence relations. Namely, the equivalence classes for an equivalence relation ∼ on a set form a partition of the set. Note that 24 (i) follows directly from 23 (i).

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 × 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} = AA^{k}, the i, j entry is

(2)  ∑_{p=1}^{n} a_{ip}m_{pj} = a_{i1}m_{1j} + a_{i2}m_{2j} + ⋯ + a_{in}m_{nj}

The product a_{ip}m_{pj} then gives the number of walks of length k + 1 from vertex i to vertex j 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 ≤ p ≤ 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.

Chapter 11/57. a) First, if we have a tree with vertex degrees d_{1}, …, d_{n} (all > 0, since trees are connected), then as we said in class,

∑_{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}, …, d_{n} satisfy ∑_{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 all sets of positive integers d_{1}, …, d_{k} with ∑_{i=1}^{k} d_{i} = 2k − 2, there exist trees with those degrees. Then consider d_{1}, …, d_{k+1} with ∑_{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 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}, …, d_{k} − 1 contains k numbers and satisfies

d_{1} + d_{2} + ⋯ + (d_{k} − 1) = 2k − 2.

By the induction hypothesis, there exists a tree T = (V, E) with vertices V = {v_{1}, …, v_{k}} and degrees d_{1}, d_{2}, …, d_{k} − 1. Then we get a tree with degrees d_{1}, d_{2}, …, d_{k}, d_{k+1} by attaching a new “leaf” vertex v_{k+1} to v_{k} by a single edge.

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.