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.)
1. Given matrices $$A\in{\mathbb{R}}^{n \times m}$$ and $$B\in {\mathbb{R}}^{m \times n}$$, show $${\text{tr}}(AB) = {\text{tr}}(BA)$$.

2. Given a square symmetric matrix $$C\in {\mathbb{R}}^{n\times n}$$, show $${\text{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 {\mathbb{R}}^n$$ satisfy $$|a^\top b| \leq \|a\| \|b\|$$ (and there are more general versions).
1. 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}$$.)

2. 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.

1. 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.)

2. 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.

3. 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.)