Biostat 216 Homework 3

Due Oct 23 @ 11:59pm

Submit a PDF (scanned/photographed from handwritten solutions, or converted from RMarkdown or Jupyter Notebook or Quarto) to Gradescope in BruinLearn.

1 BV exercises

7.12, 7.13, 8.4, 8.5, 8.6, 10.9 (also describe \(\mathbf{C}=\mathbf{A} \mathbf{D}\)), 10.11, 10.19, 10.23, 10.36, 10.42, 10.44

2 Q1. Computational complexity of matrix multiplication

Let \(\mathbf{A} \in \mathbb{R}^{m \times n}\), \(\mathbf{B} \in \mathbb{R}^{n \times p}\). Consider four ways of computing the matrix product \(\mathbf{C} = \mathbf{A} \mathbf{B}\). Calculate the flop count in each of these four algorithms.

  1. (Inner products) Evaluate entries \(c_{ij} = \mathbf{a}_i' \mathbf{b}_j\) for all \(i, j\).

  2. (Matrix vector products) Evaluate columns \(\mathbf{c}_j = \mathbf{A} \mathbf{b}_j\) for all \(j\).

  3. (Vector matrix products) Evaluate rows \(\mathbf{c}_i' = \mathbf{a}_i' \mathbf{B}\) for all \(i\).

  4. (Vector outer products) Evaluate \(\mathbf{C}\) as the sum of outer prodcuts \(\mathbf{a}_1 \mathbf{b}_1' + \cdots + \mathbf{a}_n \mathbf{b}_n'\).

3 Q2.

Show the following three claims.

  1. If \(\mathcal{S}_1\) and \(\mathcal{S}_2\) are two vector spaces of same order, then their intersection \(\mathcal{S}_1 \cap \mathcal{S}_2\) is a vector space.

  2. If \(\mathcal{S}_1\) and \(\mathcal{S}_2\) are two vector spaces of same order, then their union \(\mathcal{S}_1 \cup \mathcal{S}_2\) is not necessarily a vector space.

  3. The span of a set of \(\mathbf{x}_1,\ldots,\mathbf{x}_k \in \mathbb{R}^n\), defined as the set of all possible linear combinations of \(\mathbf{x}_i\)s \[ \text{span} \{\mathbf{x}_1,\ldots,\mathbf{x}_k\} = \left\{\sum_{i=1}^k \alpha_i \mathbf{x}_i: \alpha_i \in \mathbb{R} \right\}, \] is a vector space in \(\mathbb{R}^n\).

4 Q3.

Let \[ \mathbf{A}_1 = \begin{pmatrix} 1 & 3 & -2 \\ 3 & 9 & -6 \\ 2 & 6 & -4 \end{pmatrix}, \quad \mathbf{A}_2 = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}. \]

  1. Find the matrices \(\mathbf{C}_1\) and \(\mathbf{C}_2\) containing independent columns of \(\mathbf{A}_1\) and \(\mathbf{A}_2\).

  2. Find a rank factorization \(\mathbf{A} = \mathbf{C} \mathbf{R}\) of each of \(\mathbf{A}_1\) and \(\mathbf{A}_2\).

  3. Produce a basis for the column spaces of \(\mathbf{A}_1\) and \(\mathbf{A}_2\). What are the dimensions of those column spaces (the number of independent vectors)? What are the ranks of \(\mathbf{A}_1\) and \(\mathbf{A}_2\)? How many independent rows in \(\mathbf{A}_1\) and \(\mathbf{A}_2\)?

5 Q4.

How is the null space of \(\mathbf{C}\) related to the nullspaces of \(\mathbf{A}\) and \(\mathbf{B}\), if \[ \mathbf{C} = \begin{pmatrix} \mathbf{A} \\ \mathbf{B} \end{pmatrix}. \]

6 Q5.

In this exercise, we show the fact \[ \text{rank}(\mathbf{A} + \mathbf{B}) \le \text{rank}(\mathbf{A}) + \text{rank}(\mathbf{B}) \] for any two matrices \(\mathbf{A}\) and \(\mathbf{B}\) of same size in steps.

  1. Show that the sum of two vector spaces \(\mathcal{S}_1\) and \(\mathcal{S}_2\) of same order \[ \mathcal{S}_1 + \mathcal{S}_2 = \{\mathbf{x}_1 + \mathbf{x}_2: \mathbf{x}_1 \in \mathcal{S}_1, \mathbf{x}_2 \in \mathcal{S}_2\} \] is a vector space.

  2. Show that \(\text{dim}(\mathcal{S}_1 + \mathcal{S}_2) \le \text{dim}(\mathcal{S}_1) + \text{dim}(\mathcal{S}_2)\).

  3. Show that \(\mathcal{C}(\mathbf{A} + \mathbf{B}) \subseteq \mathcal{C}(\mathbf{A}) + \mathcal{C}(\mathbf{B})\).

  4. Conclude that \(\text{rank}(\mathbf{A} + \mathbf{B}) \le \text{rank}(\mathbf{A}) + \text{rank}(\mathbf{B})\).