---
title: Biostat 216 Homework 3
subtitle: 'Due Oct 23 @ 11:59pm'
format:
  html:
    theme: cosmo
    embed-resources: true
    number-sections: true
    toc: true
    toc-depth: 4
    toc-location: left
    code-fold: false
jupyter:
  jupytext:
    formats: 'ipynb,qmd'
    text_representation:
      extension: .qmd
      format_name: quarto
      format_version: '1.0'
      jupytext_version: 1.15.2
  kernelspec:
    display_name: Julia 1.9.3
    language: julia
    name: julia-1.9
---

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

## 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

## 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'$.

## 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$.

## 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$?

## 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}.
$$

## 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})$.