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