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

**(Matrices.)**Given matrices \(A\in{\mathbb{R}}^{n \times m}\) and \(B\in {\mathbb{R}}^{m \times n}\), show \({\text{tr}}(AB) = {\text{tr}}(BA)\).

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

**(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).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}\).)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|\).

**(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.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.)**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.

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