---
title: Homework 9
author: 36-462/662, Spring 2022
date: Due at 6 pm on Thursday, 31 March 2022
output: pdf_document
---

```{r, include=FALSE}
total.points <- 0
# Can't think of a good way to do this w/o a global variable assignment
this.prob <- function(x) { total.points <<- total.points+x; x }
silent <- TRUE
```

\newcommand{\Cov}[1]{\mathrm{Cov}\left[ #1 \right]}
\newcommand{\Var}[1]{\mathrm{Var}\left[ #1 \right]}

> **Agenda**: Practice with pieces of linear algebra which are important for dimension reduction, especially for principal components analysis.  There are a lot of problems, but they're small.


Reminders (which you can use without proving):

- The **trace** of a square matrix is the sum of its diagonal entries.
- The trace of a matrix is always equal to the sum of its eigenvalues.
- The eigenvalues of a symmetric matrix are all real (not complex) numbers,
  and all of the eigenvectors can be chosen to be orthogonal to each other.
- For any (scalar) random variables $X$ and $Y$, $\Var{X+Y} = \Var{X} +
  \Var{Y} + 2\Cov{X,Y}$.  More generally, $\Var{\sum_{i=1}^{p}{X_i}} =
  \sum_{i=1}^{p}{\sum_{j=1}^{p}{\Cov{X_i, X_j}}}$.
- When $\vec{X}$ is a $p$-dimensional vector, $\Var{\vec{X}}$ is a $p\times
  p$ matrix, where $\Var{\vec{X}}_{ij} = \Cov{X_i, X_j}$.
- If $\mathbf{a}$ is a $q\times p$ matrix, then $\Var{\mathbf{a} \vec{X}} =
  \mathbf{a} \Var{\vec{X}} \mathbf{a}^T$.


Unless otherwise noted, you can assume:

- every vector $\vec{v}$ is a $p\times 1$ column matrix, so the inner or
  dot product $\vec{v}\cdot \vec{v}$ could also be written $\vec{v}^T \vec{v}$;
- $\mathbf{1}$ is the $p\times 1$ matrix whose entries are all 1.
- $\tilde{u}$ is a vector of length 1, and if $\vec{v}$ is a vector of arbitrary length, $\tilde{v} = \vec{v}/\|\vec{v}\|$, the length-1 vector in the same direction[^hat].

[^hat]: The more usual notation in linear algebra would be $\hat{u}$, but in statistics we use hats for estimation.


1. **Online questions** (`r this.prob(10)`) were online and due on Monday.
2. **Idempotency** (`r this.prob(5)`) A matrix $\mathbf{w}$ is **idempotent**
  when
  $\mathbf{w} = \mathbf{w}^2$. Show that every eigenvalue of an idempotent
  matrix is either 0 or 1.  _Hint_: Pretend another eigenvalue was
  possible, and derive a contradiction.
3. **Projecting on to a line (experiment)**
    a. (`r this.prob(2)`) Generate 100 random two-dimensional vectors.
       The exact distribution you use doesn't matter, so long as it's not all
       concentrated on a single line.  Give the command(s) you use to create the
       vectors, explain why that command generates vectors from that
	   distribution, and a plot showing the locations of the vectors on the
	   plane.
    b. (`r this.prob(3)`) Multiply all vectors by the matrix
       $\left[ \begin{array}{cc} 1/2 & 1/2\\ 1/2 & 1/2 \end{array}\right]$. 
	   Give the commands you used to do this, and plot the new vectors.
    c. (`r this.prob(2)`) Check numerically that the matrix from the
       previous part has two eigenvalues, 0 and 1, and that the eigenvector with
       eigenvalue 1 is (proportional to) $\left[ \begin{array}{c} 1 \\
        1\end{array}\right]$.  _Hint_: `eigen()`.
    d. (`r this.prob(3)`) Explain, in words, where the new vectors are
       located, and the geometric relationship between the old vectors and the
       new.  (It may help to draw lines between the old and new vectors.)
4. **Projecting on to a line (theory)**
    a. (`r this.prob(3)`) Let $\tilde{u}$ be an arbitrary vector of length 1,
       and $\vec{v}$ be any vector, of any length.  Explain (in your own words)
       the meaning of the following statement: "$\tilde{u} \tilde{u}^T \vec{v}$
       projects $\vec{v}$ on to the line defined by $\tilde{u}$".
    b. (`r this.prob(2)`) Show that the $p\times p$ matrix
	   $\mathbf{w} \equiv \tilde{u} \tilde{u}^T$ is idempotent.
    c. (`r this.prob(2)`) Show that $\tilde{u}$ is an eigenvector of
       $\mathbf{w}$ with eigenvalue 1.
    d. (`r this.prob(1)`) Are there any other eigenvectors of $\mathbf{w}$
       with non-zero eigenvalues?
    e. (`r this.prob(2)`) Explain (in your own words) why it makes sense
       that projecting on to a line should be idempotent and have only one
       non-zero eigenvalue.
5. **Projecting on to a plane (experiment)** For plotting in three
   dimensions, you may find the `scatterplot3d` library helpful.
    a. (`r this.prob(2)`) Generate 100 random vectors in three
       dimensions.  (The exact distribution doesn't matter very much.)  Give the
       command(s) you used to create the vectors, explaining how they create the
       distribution you want.  Plot the points in 3D space.
    b. (`r this.prob(2)`) Multiply all your random vectors by the matrix
       $\left[\begin{array}{ccc} 0.5 & 0 & 0.5\\ 0 & 1 & 0\\ 0.5 & 0 &
       0.5 \end{array}\right]$.  Give the commands you used to do this, and
       plot the new vectors in 3D space.
    c. (`r this.prob(1)`) Check numerically that of this matrix's three
       eigenvalues, two of them equal 1 and the other equals 0.  Also check that
	   it has two orthogonal value-1 eigenvectors.
    d. (`r this.prob(1)`) Check that 
       $\left[ \begin{array}{c} 1\\ \sqrt{2}\\ 1 \end{array} \right]$, and
	   $\left[ \begin{array}{c} -1\\ \sqrt{2}\\ -1\end{array}\right]$ are
	   both eigenvectors, with eigenvalue 1.
    e. (`r this.prob(1)`) Explain why your numerical answer from Q5c didn't
	   have to be (proportional to) the vectors in Q5d, but they're all
	   nonetheless eigenvectors with eigenvalue 1.
    f. (`r this.prob(3)`) Explain, in words, where the new vectors are
       located, and the geometric relationship between the old vectors and the
       new.  (It may help to draw lines between the old and new vectors.)
6. **Projecting on to a plane (theory)** For any two-dimensional plane, we can
   always find two vectors $\tilde{u}_1$ and $\tilde{u}_2$ which are in the plane,
   have length 1, and are orthogonal to each other, $\tilde{u}_1 \cdot \tilde{u}_2 =
   0$.  Let $\mathbf{u}$ be the $p\times 2$ matrix whose columns are $\tilde{u}_1$
   and $\tilde{u}_2$.  Finally, let $\mathbf{w} = \mathbf{u} \mathbf{u}^T$.
    a. (`r this.prob(4)`) Explain, in your own words, the meaning of the
       following statement: "$\mathbf{w} \vec{v}$ projects $\vec{v}$ on to the
       plane defined by $\tilde{u}_1$ and $\tilde{u}_2$".
    b. (`r this.prob(2)`) Show that $\mathbf{w}$ is idempotent.  _Hint_: Use
       the properties of the vectors $\tilde{u}_1$ and $\tilde{u}_2$.
    c. (`r this.prob(3)`) Show that $\mathbf{w}$ has two non-zero
       eigenvalues, and that $\tilde{u}_1$ and $\tilde{u}_2$ are both
       eigenvectors of eigenvalue 1.
7. **Projecting on to a linear subspace** (`r this.prob(5)`) Suppose
   we want to project on to a $q$-dimensional linear subspace, $q < p$.  Explain
   how to construct the matrix to do this projection, and why the matrix will be
   idempotent and have $q$ non-zero eigenvalues.
8. **Linear regression is projection** Suppose we linearly regress an
   $n\times 1$ vector $\vec{y}$ on an $n\times p$ matrix of regressors
   $\mathbf{x}$ by ordinary least squares.  As you recall from your regression
   class, the vector of fitted values is $\vec{m} =
   \mathbf{x}(\mathbf{x}^T\mathbf{x})^{-1}\mathbf{x}^T \vec{y}$.  The matrix
   $\mathbf{x}(\mathbf{x}^T\mathbf{x})^{-1}\mathbf{x}^T$ is called the **hat
   matrix**, or **influence matrix**, or just $\mathbf{h}$.
    a. (`r this.prob(2)`) Show that $\mathbf{h}$ is idempotent.
    b. (`r this.prob(3)`) Show that $\mathbf{h}$ has $p$ non-zero
       eigenvalues.  (Remember that $\mathbf{x}$ is $n\times p$.)
    c. (`r this.prob(4)`) Explain, in your own words, the meaning of the
       following statement: "The actual response vector is $n$ dimensional, but
       ordinary least squares projects it into a $p$-dimensional subspace".
9. **Variance of linear combinations and positive-semi-definite matrices**
   $X_1, X_2, \ldots X_p$ are random variables, with $\Cov{X_i, X_j} = c_{ij}$
   (and so $\Var{X_i} = c_{ii}$).  We say that the collection of variables has
   variance (or covariance) matrix $\mathbf{c}$, of dimension $p\times p$.
     a. (`r this.prob(1)`) Show that $\Var{\sum_{i=1}^{p}{X_i}} = \mathbf{1}^T \mathbf{c} \mathbf{1}$.
    b. (`r this.prob(2)`) Show that $\Var{\sum_{i=1}^{p}{a_i X_i}} =
        \vec{a}^T \mathbf{c} \vec{a}$, for any vector of coefficients $\vec{a}$.
    c. (`r this.prob(3)`) A matrix $\mathbf{b}$ is called
       **positive-semi-definite**
       when for any vector $\vec{v}$, $\vec{v}^T \mathbf{b}\vec{v} \geq 0$. 
	   (Some people say **non-negative-definite** instead.)  Explain why every
       variance matrix must be positive-semi-definite.
    d. (`r this.prob(1)`) If  $\vec{v}^T \mathbf{b} \vec{v} > 0$ for all
       vectors $\vec{v} \neq \vec{0}$, the matrix  is **positive-definite**
	   (not just semi-definite).  Give an example of random variables where the
	   variance matrix is non-negative definite, but _not_ positive definite. 
	   _Hint_: Consider negative correlations between some of the variables, 
	   and find a linear combination of the variables with zero variance.
    e. (`r this.prob(2)`) Show that if a matrix is non-negative definite,
       then all its eigenvalues are $\geq 0$.
    f. (`r this.prob(2)`) Show that if a matrix is positive-definite, then
       all its eigenvalues are $> 0$.
    g. (`r this.prob(1)`) Suppose every linear combination of the
       variables has a variance $> 0$.  Show that all the eigenvalues of the
       variance matrix are $> 0$.
10. **Correlating and decorrelating by matrix multiplication** Suppose a
    matrix $\mathbf{b}$ is a symmetric, positive-definite matrix with
    eigendecomposition $\mathbf{b} = \mathbf{v}\mathbf{d}\mathbf{v}^T$, where
    $\mathbf{d}$ is the diagonal matrix of eigenvalues, and $\mathbf{v}$ is the
    matrix whose columns are the eigenvectors.
    a. (`r this.prob(3)`) Define $\mathbf{b}^{1/2} = 
       \mathbf{v}\mathbf{d}^{1/2}$, where $\mathbf{d}^{1/2}$ is the diagonal
	   matrix with the (positive) square roots of eigenvalues of $\mathbf{b}$ on
	   the diagonal.  Show that $\mathbf{b} =
	   (\mathbf{b}^{1/2}) (\mathbf{b}^{1/2})^T$.
    b. (`r this.prob(3)`) Suppose that $\vec{Z}$ is a $p$-dimensional
       random vector where each dimension has variance 1 and the dimensions
       are uncorrelated, so $\Var{\vec{Z}} = \mathbf{I}$.
       Show that $\Var{ \mathbf{b}^{1/2} \vec{Z}} = \mathbf{b}$.
    c. (`r this.prob(3)`) Suppose that $\Var{\vec{X}} = \mathbf{b}$.  Show
       that $\Var{\mathbf{b}^{-1/2} \vec{X}} = \mathbf{I}$.
11. **Timing** (`r this.prob(1)`) How long, roughly, did you spend on this
problem set?



**Presentation rubric** (`r this.prob(10)`): The text is laid out cleanly, with
clear divisions between problems and sub-problems.  The writing itself is
well-organized, free of grammatical and other mechanical errors, and easy to
follow.  Plots are carefully labeled, with informative and legible titles, axis
labels, and (if called for) sub-titles and legends; they are placed near the
text of the corresponding problem.  All plots and tables are generated by code
included in the R Markdown file.  All quantitative and mathematical claims are
supported by appropriate derivations, included in the text, or calculations in
code.  Numerical results are reported to appropriate precision. All parts of
all problems are answered with actual coherent sentences, and raw computer code
or output are only shown when explicitly asked for.  **Text from the homework
assignment, including this rubric, is included only when relevant, not
blindly copied.**




```{r, echo=FALSE, include=TRUE}
if(!silent || (total.points != 100)) {   total.points }
```


**Extra credit**

a. (`r this.prob(2)`) In Q6, we built the projection matrix for _one_ choice of
  two orthonormal vectors lying in plane.  Show that we get the _same_
  projection matrix no matter what vectors we start with, so long as they've
  got length 1, are orthogonal to each other, and lie in the plane.
