Section 2.9
Linear algebra in combinatorics
The theory of bases and dimension is difficult and delicate, as you have seen. This also means that it is a powerful tool that turns many difficult problems into trivialities. Linear algebra is fundamental to many areas of mathematics, such as algebraic geometry, differential geometry, real analysis, and so on. It is even used in combinatorics to solve seemingly unrelated problems. We will see some of those problems where linear algebra is a powerful tool. If you are not interested in such applications, you may skip this section entirely. Also, the exercises in this section are going to be hard, so feel free to move on without solving all of them.
Let $V$ be a $k$-vector space with $\dim V = n$ finite. If $v_1, \ldots, v_{n+1} \in V$, there exist $a_1, \ldots, a_{n+1} \in k$, not all zero, such that
$$ a_1 v_1 + a_2 v_2 + \cdots + a_{n+1} v_{n+1} = 0. $$
Let $x_1, \ldots, x_n$ be $n$ variables, and consider $n-1$ equations
$$ a_{j,1} x_1 + a_{j,2} x_2 + \cdots + a_{j,n} x_n = 0 $$
for $1 \le j \le n-1$, where $a_{j,i} \in k$. Show that there always exists a nonzero solution $(x_1, \ldots, x_n) \in k^n$ satisfying all the $n-1$ equations. (Nonzero means that $(x_1, \ldots, x_n) \neq (0, \ldots, 0)$.)
A lot of the examples will rely on these two results, that $n+1$ elements in an $n$-dimensional vector space are always linearly dependent, and that any $n-1$ equations with $n$ variables have a nonzero solution. In each situation, a clever choice of the base field $k$ and the vectors $v_i$ will give us some useful information. The first example is called the “Oddtown problem”.
Let $A_1, \ldots, A_m \subseteq \lbrace 1, 2, \ldots, n\rbrace $ be subsets such that $\lvert A_i \rvert$ is odd for each $1 \le i \le m$ and $\lvert A_i \cap A_j \rvert$ is even for each $1 \le i < j \le m$. Then $m \le n$.
Consider $k = \mathbb{F}_2$, the field with two elements with addition and multiplication modulo $2$. For each set $A_i$, consider the vector $v_i \in \mathbb{F}_2^{n}$ such that $(v_i)_j = 1$ if $j \in A_i$ and $(v_i)_j = 0$ if $j \notin A_i$. Using the standard inner product on $\mathbb{F}_2^n$, we can write the condition $\lvert A_i \rvert$ odd simply as $v_i \cdot v_i = 1 \in \mathbb{F}_2$, and the condition $\lvert A_i \cap A_j \rvert$ can be translated to $v_i \cdot v_j = 0 \in \mathbb{F}_2$.
We are now going to prove that the vectors $v_1, \ldots, v_m$ are linearly independent in $\mathbb{F}_2^n$. This will immediately show that $m \le n$. Suppose that
$$ a_1 v_1 + a_2 v_2 + \cdots + a_m v_m = 0 $$
in $\mathbb{F}_2^n$. Then taking the dot product with $v_i$, we get
$$ 0 = v_i \cdot 0 = v_i \cdot (a_1 v_1 + \cdots + a_m v_m) = \sum_{j=1}^{m} a_j (v_i \cdot v_j) = a_i. $$
Therefore $a_i = 0$ for all $i$, and this shows that $v_1, \ldots, v_m$ are indeed linearly independent.
Let $A_1, \ldots, A_m \subseteq \lbrace 1, 2, \ldots, n\rbrace $ be subsets such that $\lvert A_i \rvert$ is even for each $1 \le i \le m$ and $\lvert A_i \cap A_j \rvert$ is odd for each $1 \le i < j \le m$. Show that $m \le n$.
Let $A_1, \ldots, A_m, B_1, \ldots, B_p \subseteq \lbrace 1, \ldots, n \rbrace $ be subset such that $\lvert A_i \cap B_j \rvert$ is odd for all $1 \le i \le m$ and $1 \le j \le p$. Show that $mp \le 2^{n-1}$.
Let $A_1, \ldots, A_{n+1} \subseteq \lbrace 1, 2, \ldots, n\rbrace $ be arbitrary nonempty subsets. Show that there exist nonempty disjoint subsets $I, J \subseteq \lbrace 1, 2, \ldots, n\rbrace $ such that
$$ \bigcup_{i \in I} A_i = \bigcup_{j \in J} A_j. $$
Suppose that the edges of a complete graph $K_n$ are partitioned into the edges of $m$ complete bipartite graphs. Then $m \ge n-1$.
Label the vertices of $K_n$ by $1, 2, \ldots, n$, and let $A_i$ and $B_i$ be the set of vertices on each side of the $i$th complete bipartite graph. Then we have the identity
$$ \sum_{1 \le i < j \le n}^{} x_i x_j = \sum_{t=1}^{m} \biggl( \sum_{j \in A_t}^{} x_j \biggr) \biggl( \sum_{j \in B_t}^{} x_j \biggr). $$
If $m \le n-2$, then $m + 1 \le n-1$ and so there exists a nonzero solution to the $m+1$ equations
$$ \sum_{j \in A_t}^{} x_j = 0, \quad x_1 + x_2 + \cdots + x_n = 0, $$
where we work over $k = \mathbb{R}$. Then we have
$$ \begin{aligned} 0 = (x_1 + \cdots + x_n)^2 &= \sum_{i=1}^{n} x_i^2 + 2 \sum_{1 \le i < j \le n}^{} x_i x_j \\ &= \sum_{i=1}^{n} x_i^2 + 2 \sum_{t=1}^{m} 0 \cdot \sum_{j \in B_t}^{} x_j = \sum_{i=1}^{n} x_i^2. \end{aligned} $$
But $x_i \in \mathbb{R}$, and so the only way this can be satisfied is $x_1 = \cdots = x_n = 0$. This contradicts that $(x_1, \ldots, x_n) \neq (0, \ldots, 0)$. Therefore $m \ge n-1$.
Let $1 \le k \le n$ be positive integers. Suppose $A_1, \ldots, A_m \subseteq \lbrace 1, 2, \ldots, n\rbrace $ are distinct subsets such that $\lvert A_i \cap A_j \rvert = k$ for each $1 \le i < j \le m$. Show that $m \le n$.
Sometimes, it is very useful to set the base field as $\mathbb{Q}$, although the vector spaces become messy.
Let $r > 0$ be a positive real number. It is possible to partition a $1 \times r$ rectangle into finitely many squares if and only if $r$ is a rational number.
If $r$ is rational, it is clear that the $1 \times r$ rectangle can be cut into finitely many squares. Now suppose that $r$ is irrational and there is a partition of the rectangle into finitely many squares. Consider a $\mathbb{Q}$-linear function $f : \mathbb{R} \to \mathbb{R}$ such that $f(1) = 1$ and $f(r) = -1$. (Such a map exists because we can take a $\mathbb{Q}$-linear map $\vspan(1, r) \to \mathbb{R}$ with $f(1) = 1, f(r) = -1$ and then extend it to $\mathbb{R}$ by choosing a basis.) Now if a rectangle of side-length $a$ and $b$ is partitioned into rectangles with side-length $a_i$ and $b_i$, we have the equality
$$ f(a) f(b) = \sum_{i}^{} f(a_i) f(b_i) $$
because dividing along a side splits $f(a)$ into $f(x) + f(a-x) = f(a)$. Now if the $1 \times r$ rectangle is partitioned into squares of side-length $a_i$, then
$$ -1 = f(1) f(r) = \sum_{i}^{} f(a_i) f(a_i) = \sum_{i}^{} f(a_i)^2 \ge 0. $$
This is clearly a contradiction.
Let $A$ be a finite set of real numbers strictly between $0$ and $1$, such that for each $x \in A$, there exist $a, b \in A \cup \lbrace 0, 1 \rbrace $ such that $a, b \neq x$ and $x = \frac{1}{2}(a+b)$. Show that all elements of $A$ are rational numbers.
Let $S \subseteq [0, 1]$ be a finite subset containing $0$ and $1$. Suppose that every distance between elements of $S$ occurs in at least two different ways, except for the distance $1$. Prove that $S$ contains only rational numbers.
We end the chapter by a recent result that was proved in an elegant way using linear algebra.
Let $p$ be a prime and $n$ be a positive integer. Consider the $\mathbb{F}_p$-vector space
$$ V = \lbrace \text{polynomials } P \text{ in } x_1, \ldots, x_n \text{ with coefficients in } \mathbb{F}_p \text{ and } \deg_{x_i} P \le p-1 \rbrace . $$
(For instance, $x_1^{p-1} x_2^{p-1} \in V$ because separately the degree are at most $p-1$, even though the total degree is $2(p-1)$.) Consider the linear map
$$ V \to \mathbb{F}_p^{(\mathbb{F}_p^n)}; \quad P \mapsto (P(A))_{A \in \mathbb{F}_p^n}. $$
Show that this map is an isomorphism, by showing that it is a surjection between vector spaces of equal dimension. Conclude that if a polynomial $P \in V$ vanishes at all points in $\mathbb{F}_p^n$ then $P = 0$ as a polynomial.
Let $p$ be a prime and $n$ be a positive integer. Consider a subset $K \subseteq \mathbb{F}_p^n$ such that for each $x \in \mathbb{F}_p^n$, there exists a $y \in \mathbb{F}_p^n$ such that
$$ y, y + x, y + 2x, \ldots, y + (p-1) x \in K. $$
Then $\lvert K \rvert \ge \binom{p+n-1}{n}$.
Suppose that $\lvert K \rvert < \binom{p+n-1}{n}$. Consider the space
$$ V = \lbrace \text{polynomials in } x_1, \ldots, x_n \text{ with coefficients in } \mathbb{F}_p \text{ and total degree} \le p-1 \rbrace . $$
This is a vector space over $\mathbb{F}_p$, and $\dim_{\mathbb{F}_p} V = \binom{p+n-1}{n}$. Consider the linear map
$$ V \to \mathbb{F}_p^{K}; \quad P(x_1, \ldots, x_n) \mapsto (P(A))_{A \in K}. $$
Because the dimension of the right hand side is smaller, it cannot be injective. Therefore there is a nonzero polynomial $P \in V$ such that $P(A) = 0$ for all $A \in K$.
Now for each $x$, find a $y \in \mathbb{F}_p^n$ such that $y + ix \in K$ for all $0 \le i < p$. Consider the polynomial
$$ P_{x,y}(t) = P(y + tx), $$
which is a polynomial with one variable and coefficients in $\mathbb{F}_p$. We have $\deg P_{x,y} \le p-1$ but $P_{x,y}(t) = 0$ for all $t \in \mathbb{F}_p$. This shows that $P_{x,y}$ must be the zero polynomial. Let $0 \le \deg P = d \le p-1$, and consider the homogeneous degree $d$ part of $P$, denoted by $\overline{P}$. If we look at the degree $d$ coefficient of $P_{x,y}$, it is going to be $\overline{P}(x)$. This shows that $\overline{P}(x) = 0$ for all $x \in \mathbb{F}_p^n$, and by Exercise 2.9.I, we see that $\overline{P} = 0$ as a polynomial. This contradicts $\deg P = d$.
Consider a simple graph $G$, and suppose that all the vertices are colored white. We are allowed to do the following operation: pick a vertex $v$ of $G$, change the color of $v$ from white to black or from black to white, and also change the color of all neighbors of $v$. Show that it is possible to make all the vertices black after a finite number of operations.
At a certain mathematical conference, every pair of mathematicians is either friends or strangers. At mealtime, every participant eats in one of two large dining rooms. Each mathematician insists upon eating in a room which contains an even number of his or her friends. Prove that the number of ways that the mathematicians may be split between the two rooms is a power of two (i.e., is of the form $2^k$ for some positive integer $k$).
The $30$ edges of a regular icosahedron are distinguished by labeling them $1, 2, \ldots, 30$. How many ways are there to paint each edge red, white, or blue, such that each of the $20$ triangular faces of the icosahedron has two edges of the same color and third edge of a different color?