---
title: Homework 0
---
\newcommand\R{\mathbb{R}}
\newcommand\bbE{\mathbb{E}}
\newcommand\cA{\mathcal{A}}
\newcommand\cC{\mathcal{C}}
\newcommand\cF{\mathcal{F}}
\newcommand\cM{\mathcal{M}}
\newcommand\cR{\mathcal{R}}
\newcommand{\tr}{\text{tr}}
\newcommand\qed{\qquad\square}
\renewcommand\Pr{\textup{Pr}}
\newcommand\1{\mathbf{1}}
\newcommand\conv{\textup{conv}}
\newcommand{\ip}[2]{\left\langle #1, #2 \right \rangle}
\newcommand{\argmin}{\textup{arg\,min}}
\newcommand{\argmax}{\textup{arg\,max}}
**Due:** Wednesday, August 31, at 11am.
This is a ``callibration'' homework (for both of us).
**This homework, unlike the others, must be done individually.**
It is worth a $\varepsilon$-fraction of your grade, where $\varepsilon > 0$ is a insignificantly small.
Please give this assignment a serious effort but don't let it ruin your day.
**Pro-tip:** cheating on this assignment makes the class harder.
1. **(Matrices.)**
a. Given matrices $A\in\R^{n \times m}$ and $B\in \R^{m \times n}$,
show $\tr(AB) = \tr(BA)$.
b. Given a square symmetric matrix $C\in \R^{n\times n}$, show
$\tr(C) = \sum_i \lambda_i$, where $\lambda_i$ is the $i^{\text{th}}$
eigenvalue of $C$.
2. **(Cauchy-Schwarz.)** The Cauchy-Schwarz inequality says that every pair of vectors
$a,b\in \R^n$ satisfy $|a^\top b| \leq \|a\| \|b\|$ (and there are more general versions).
a. Given reals $(c_1,\ldots,c_k)$, show
$$
\sum_{i=1}^k \frac{c_i}{i} \leq \sqrt{2} \sqrt{\sum_{i=1}^k c_i^2}.
\notag
$$
(**Note:** if you are ambitious, the $\sqrt{2}$ can be replaced with $\pi/\sqrt{6}$.)
b. Prove the following inequality which is similar to Cauchy-Schwarz:
$|a^\top b| \leq \|a\|_1 \|b\|_\infty$, where $\|a\|_1 = \sum_i |a_i|$
and $\|b\|_\infty = \max_i |b_i|$.
3. **(Geometric puzzle.)**
Consider the following game: you are given a set of points in the
plane, and you must either establish that for every subset there exists an axis-aligned rectangle
which contains just the points in that subset (and avoids the points outside the subset),
or you must prove that this is impossible.
a. First find a set of 4 points such that the game is impossible; namely, find a set of 4 points
in the plane and a subset of them and then prove that that any
axis-aligned rectangle containing the subset must also contain some other
points. **(Feel free to include a scan of a hand-drawn figure.)**
b. Next find a set of 4 points in the plane where the game is successful:
show that every subset can be exactly captured by some axis-aligned rectangle.
c. Now prove that for *any* (distinct) set of 5 points, the game must fail.
**Congratulations!** You have proved the VC-dimension of axis-aligned rectangles is 4.
(I realize this makes the question google-able; please see the ``pro-tip'' above.)
(**Hints.** (1b) Real square symmetric matrices always have real eigenvalues and eigenvectors.
(3c) Take *any* five (distinct) points, and consider their bounding box.)