\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\providecommand{\abs}[1]{\lvert#1\rvert}
\providecommand{\norm}[1]{\lVert#1\rVert}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{fact}[thm]{Fact}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{eg}{Example}
\newtheorem{ex}{Exercise}
\newtheorem{defi}{Definition}
\newtheorem{hw}{Problem}
\newenvironment{sol}
  {\par\vspace{3mm}\noindent{\it Solution}.}
  {\qed}

\newcommand{\ov}{\overline}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\ch}{{\cal H}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cz}{{\cal Z}}
\newcommand{\eps}{\varepsilon}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\dist}{\mbox{\rm dist}}
\newcommand{\bn}{{\mathbf N}}
\newcommand{\br}{{\mathbf R}}
\newcommand{\bz}{{\mathbf Z}}
\newcommand{\expe}{{\mathsf E}}
\newcommand{\prob}{{\mathsf{Pr}}}

\setlength{\parindent}{0pt}
%\setlength{\parskip}{2ex}
\newenvironment{proofof}[1]{\bigskip\noindent{\itshape #1. }}{\hfill$\Box$\medskip}

\begin{document}

$\;$\hfill Do not need to hand in

\begin{center}
{\LARGE\bf Homework 14}
\end{center}

\begin{hw}
Let $A$ be the adjacency matrix of the complete bipartite graph $K_{3,3}$,
compute the eigenvalues of $A$.
\end{hw}

\begin{sol} One form of the adjacency matrix is
\[ A = \left( \begin{array}{cccccc}
0 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0
\end{array} \right)\]
It has rank 2, so the null space has dimension 4, therefore $A$ has eigenvalue 0 with multiplicity 4.
For the other two eigenvalues, notice that
\[
A \left( \begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{array} \right) =
3 \left( \begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{array} \right)
\]
and
\[
A \left( \begin{array}{c} 1 \\ 1 \\ 1 \\ -1 \\ -1 \\ -1 \end{array} \right) =
-3 \left( \begin{array}{c} 1 \\ 1 \\ 1 \\ -1 \\ -1 \\ -1 \end{array} \right)
\]
So $A$ has eigenvalues $3, 0, 0, 0, 0, -3$.
\end{sol}


\begin{hw} Let $n$ be a positive integer. Consider
\[ S = \{ (x, y, z) : x, y, z \in [n] \cup \{0\}, x + y + z > 0 \}\]
as a set of $(n+1)^3 - 1$ points in $\br^3$.
We proved that $3n$ planes are needed to touch all the points if none of the
planes is allowed to touch $(0,0,0)$. Shorten the proof using Combinatorial Nullstellensatz.
\end{hw}

\begin{proof}
Suppose we have $k$ planes cover $S$ but not the origin, the $i$-th plane being $a_i x + b_i y + c_i z + d_i = 0$.
Define
\[P(x,y,z) := \prod_{1\leq i \leq n}(x-i)(y-i)(z-i)/C - \prod_{1 \leq i \leq k} (a_i x + b_i y + c_i z + d_i),\]
where
\[ C = -\frac{\prod_{1\leq i \leq n} i^3}{\prod_{1\leq i \leq k} d_i}.\]
So $P$ vanishes on the set $A^3$, where $A = \{0, 1, ..., n\}$.

If $k < 3n$, the degree of $P$ is $3n$, and the coefficient of $x^ny^nz^n$ is $1/C \neq 0$. This contradicts the Combinatorial Nullstellensatz with $S_1 = S_2 = S_3 = A$ and $t_1 = t_2 = t_3 = n$.
\end{proof}

\begin{hw}
Let $A_1$, $A_2$, ..., $A_m$ be $m$ distinct subsets of $[n]$ such that each $|A_i|$ is even and
for any $i \neq j$, $|A_i \cap A_j|$ is odd. How big can $m$ be? Prove your answer. (i.e., Prove the bound, and
show examples where the bound is reached.)
\end{hw}

\begin{lemma} The matrix $J_n - I_n$ over the binary field has rank $n$ if $n$ is even, and $n-1$ if $n$ is odd.
\end{lemma}

\begin{proof} In the binary field, plus and minus are the same, so the determinant (by its $n!$ terms expansion)
equals the number of derangements. It is 1 iff $n$ is even.
When $n$ is odd, the rank is less than $n$, but the first $n-1$ rows and columns has full rank, so its ranks is $n-1$.
\end{proof}

\begin{sol} For $n$ odd, the set $\binom{[n]}{n-1}$ satisfies the requirement and has size $n$. For $n$ even, the
set $\binom{[n-1]}{n-2}$ satisfies the requirement and has size $n-1$. We prove this is best possible.

As in class, take the incidence matrix $M$ where $M_{i,j} = 1$ if $A_i$ contains $j$. As matrices over the binary field,
$M M^T = J_m - I_m$.

If $n$ is odd, there cannot be $n+1$ such sets. Otherwise, the $(n+1) \times (n+1)$ matrix
$M M^T = J-I$ has full rank according to the lemma.
But $M$ has only $n$ columns. A contradiction.

If $n$ is even, there cannot be $n$ such sets. Otherwise, the $n \times n$ matrix $J - I$
has full rank, but the columns vectors of $M$ add up to the all 0 vector, so $M$ has rank less than $n$.
\end{sol}

\begin{hw}
Prove that, for any $n$, there is a two-distance set of size at least $\binom{n+1}{2}$
in $\br^n$.
\end{hw}

\begin{sol} Let $e_i$ be the point in $\br^{n+1}$ where all the coordinates are 0, excpet there is a 1 on the $i$-th coordinate. For any $i < j$, $e_{ij} := e_i + e_j$. There are $\binom{n+1}{2}$ such $e_{ij}$'s. The distances among them are $\sqrt{2}$ and $2$.

Furthermore, all those points satisfy $x_1 + x_2 + ... + x_n = 2$. So they lie in the hyperplane which is isomorphic to $\br^n$.
\end{sol}

\medskip

As usual, the last problem is always a little harder than usual.

\begin{hw} (extra)
Prove that, any two-distance set in $\br^n$ has size at most $\binom{n+2}{2}$.
\end{hw}

{\em Hint.} This is $n+1$ less than the bound we proved in class. Try to add $n+1$ new
polynomials to the polynomials we used, and show that they are still linearly independent.

\begin{sol}
As in the notes, define, for each $1 \leq i \leq m$, a polynomial $\br^n \rightarrow \br$
\[
f_i(x) = (\norm{x - a_i}^2 - \delta_1^2)(\norm{x - a_i}^2 - \delta_2^2).
\]
Expanding the polynomials, it is easy to see each $f_i$ is a linear combination of
the following $(n+1)(n+4)/2$ polynomials
\[ (\sum x_i^2)^2, \; (\sum x_i^2)x_j, \; x_ix_j, \; x_i, \; 1. \]
So are the polynomials $g_0 := 1$, $g_1 := x_1$, ..., $g_n := x_n$.
We have $m \leq \binom{n+2}{2}$ if the $f_i$'s and $g_i$'s a linearly independent.

Suppose
\[ P := \sum_i \lambda_i f_i = u + \sum_j \mu_j x_j,\]
we want to prove the $\lambda$'s are all 0 (therefore $u$ and $\mu$'s are all 0, since the $g_i$'s are clearly independent).

Consider the degree 4 terms in $P$, e.g. $x_1^4$, it's cooefficient
\[ \sum_i \lambda_i = 0. \]

Consider the cooefficient for $x_k^3$ in $P$, we have
\[ \forall k, \sum_i \lambda_i a_{i,k} = 0.\]

Define the matrix

\[ A = \left( \begin{array}{cccc}
1 & 1 & ... & 1 \\
a_{11} & a_{21} & ... & a_{m1} \\
a_{12} & a_{22} & ... & a_{m2} \\
\vdots & \vdots &  & \vdots  \\
a_{1n} & a_{2n} & ... & a_{mn}
\end{array} \right)\]

and the vector $v = (\lambda_1, \lambda_2, ..., \lambda_m)$
The above two equations says $A v^T = 0$.

On the otherhand, $f_i(a_i) = \delta_1^2 \delta_2^2$ and $f_i(a_j) = 0$ whenever $i \neq j$.
We have
\[ P(a_i) = u + \sum_{1 \leq j \leq n} u_j a_{ij} = \lambda_i \delta_1^2 \delta_2^2 .\]
In the matrix form, let $w = (u, \mu_1, ..., \mu_n)$, we have $wA = \delta_1^2 \delta_2^2 v$.
So,
\[ w 0 = w A v^T = \delta_1^2 \delta_2^2 v v^T = \delta_1^2 \delta_2^2 \sum_i \lambda_i^2,\]
which implies that the $\lambda_i$'s are all 0.
\end{sol}

\end{document}

