Biostat 216 Midterm

Nov 4, 2021, 10am-11:50am.

In class, closed-book, one page (double-sided, letter size) cheat sheet allowed.

Make sure to write your name and UID on your answer sheets. Also number the answer sheets.

  • Q1. (5pts). Show that the Gram matrix $\mathbf{A}'\mathbf{A}$ has the same null space as $\mathbf{A}$.

  • Q2. (5pts). Let $\mathcal{A} = \{\mathbf{a}_1, \ldots, \mathbf{a}_k\}$ be a basis of a vector space $\mathcal{S}$. Show that any vector $\mathbf{x} \in \mathcal{S}$ can be expressed uniquely as a linear combination of vectors in $\mathcal{A}$.

  • Q3. (5pts) Triangular equality. When does the triangular inequality hold with equality, i.e., what are the conditions on $\mathbf{a}$ and $\mathbf{b}$ to have $\|\mathbf{a} + \mathbf{b}\| = \|\mathbf{a}\| + \|\mathbf{b}\|$?

  • Q4. (6pts) A few flop count problems. Assume your computer can do 1TFLOP/S, i.e., $10^{12}$ flops per second. For flop count, you don't need to derive it and just giving the dominant term (e.g., $2mn$) is fine.

    1. Inner product. For $\mathbf{a}, \mathbf{b} \in \mathbb{R}^n$, how many flops does it take to compute $\mathbf{a}' \mathbf{b}$? If $n=10^6$ (a million), how long do you estimate your computer to compute this?
    2. Axpy. For $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$ and $\alpha \in \mathbb{R}$, how many flops does it take to compute $\alpha \mathbf{x} + \mathbf{y}$? If $n=10^6$ (a million), how long do you estimate your computer to compute this?
    3. Matrix-vector multiplication. For $\mathbf{A} \in \mathbb{R}^{m \times n}$ and $\mathbf{x} \in \mathbb{R}^n$, how many flops to compute $\mathbf{A} \mathbf{x}$? If $m=n=10^6$, how long do you estimate your computer to compute this?
    4. Matrix-matrix multiplication. For $\mathbf{A} \in \mathbb{R}^{m \times n}$ and $\mathbf{B} \in \mathbb{R}^{n \times p}$, how many flops to compute $\mathbf{A} \mathbf{B}$? If $m=n=p=10^6$, how long does it take your computer to do this?
    5. Quadratic form. For $\mathbf{A} \in \mathbb{R}^{m \times n}$, $\mathbf{x} \in \mathbb{R}^{m}$, and $\mathbf{y} \in \mathbb{R}^n$, how many flops to compute $\mathbf{x}' \mathbf{A} \mathbf{y}$? If $m=n=10^6$, how long does it take your computer to do this?
    6. Multiplication by rank-1 matrix. For $\mathbf{A} \in \mathbb{R}^{m \times n}$ and $\mathbf{B} = \mathbf{x} \mathbf{y}' \in \mathbb{R}^{n \times p}$. How many flops to compute $\mathbf{A} \mathbf{B}$ efficiently? If $m=n=p=10^6$, how long does it take your computer to do this?

  • Q5. (5pts) Nearest nonnegative vector. Let $\mathbf{x}$ be an arbitrary but fixed $n$-vector. Suppose $\mathbf{y}$ is the nonnegative vector (i.e., $y_i \ge 0$ for all $i$) closest to $\mathbf{x}$. Give an expression for the elements of $\mathbf{y}$. Show that the vector $\mathbf{z} = \mathbf{y} - \mathbf{x}$ is also nonnegative and that $\mathbf{z}' \mathbf{y} = 0$.

  • Q6. (5pts) Let $\mathbf{a}_1, \ldots, \mathbf{a}_k \in \mathbb{R}^n$ be a set of orthonormal vectors. Show that they are linearly independent.

  • Q7. (5pts) Matrix $\mathbf{A} \in \mathbb{R}^{n \times n}$ has entries $a_{ij} = j^2$. Write down a rank factorization $\mathbf{A} = \mathbf{C} \mathbf{R}$ (write down $\mathbf{C}$ and $\mathbf{R}$). What is the rank of $\mathbf{A}$? What is the dim$(\mathcal{N}(\mathbf{A}))$? What is the row rank of $\mathbf{A}$?

  • Q8. (9pts) Let $\mathcal{S}_1$ and $\mathcal{S}_2$ be two vector spaces in $\mathbb{R}^n$. Which of the following are vector spaces? For the first three sets, just indicate each of them is a vector space or not (without proof). For the last set $\mathcal{S}_1^\perp$, either show this is a always vector space or find a counter-example to show that it is not a vector space.

    • [ ] $\mathcal{S}_1 \cap \mathcal{S}_2$.
    • [ ] $\mathcal{S}_1 \cup \mathcal{S}_2$.
    • [ ] $\mathcal{S}_1 + \mathcal{S}_2$.
    • [ ] $\mathcal{S}_1^\perp = \{\text{all vectors in } \mathbb{R}^n \text{ that are orthogonal to every vector in } \mathcal{S}_1\}$.

  • Q9. (5pts) Let $f: \mathbb{R}^3 \mapsto \mathbb{R}$ be defined as $$ f(\mathbf{x}) = f(x_1, x_2, x_3) = e^{2x_1 + x_2} - x_1 + x_2^2. $$

    1. What is the gradient of $f$? Evaluate the gradient at point $\mathbf{0}_3$.
    2. What is the first-order Taylor approximation, or affine approximation, of $f$ at point $\mathbf{0}_3$?