{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "title: Biostat 216 Homework 3\n",
    "subtitle: 'Due Oct 23 @ 11:59pm'\n",
    "format:\n",
    "  html:\n",
    "    theme: cosmo\n",
    "    embed-resources: true\n",
    "    number-sections: true\n",
    "    toc: true\n",
    "    toc-depth: 4\n",
    "    toc-location: left\n",
    "    code-fold: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Submit a PDF (scanned/photographed from handwritten solutions, or converted from RMarkdown or Jupyter Notebook or Quarto) to Gradescope in BruinLearn. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BV exercises\n",
    "\n",
    "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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q1. Computational complexity of matrix multiplication\n",
    "\n",
    "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.\n",
    "\n",
    "1. (Inner products) Evaluate entries $c_{ij} = \\mathbf{a}_i' \\mathbf{b}_j$ for all $i, j$.\n",
    "\n",
    "2. (Matrix vector products) Evaluate columns $\\mathbf{c}_j = \\mathbf{A} \\mathbf{b}_j$ for all $j$.\n",
    "\n",
    "3. (Vector matrix products) Evaluate rows $\\mathbf{c}_i' = \\mathbf{a}_i' \\mathbf{B}$ for all $i$.\n",
    "\n",
    "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'$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q2. \n",
    "\n",
    "Show the following three claims.\n",
    "\n",
    "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.\n",
    "    \n",
    "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.\n",
    "\n",
    "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\n",
    "$$\n",
    "    \\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\\},\n",
    "$$\n",
    "is a vector space in $\\mathbb{R}^n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q3.\n",
    "\n",
    "Let\n",
    "$$\n",
    "\\mathbf{A}_1 = \\begin{pmatrix}\n",
    "1 & 3 & -2 \\\\\n",
    "3 & 9 & -6 \\\\\n",
    "2 & 6 & -4\n",
    "\\end{pmatrix}, \\quad \\mathbf{A}_2 = \\begin{pmatrix}\n",
    "1 & 2 & 3 \\\\\n",
    "4 & 5 & 6 \\\\\n",
    "7 & 8 & 9\n",
    "\\end{pmatrix}.\n",
    "$$  \n",
    "\n",
    "1. Find the matrices $\\mathbf{C}_1$ and $\\mathbf{C}_2$ containing independent columns of $\\mathbf{A}_1$ and $\\mathbf{A}_2$.  \n",
    "    \n",
    "2. Find a rank factorization $\\mathbf{A} = \\mathbf{C} \\mathbf{R}$ of each of $\\mathbf{A}_1$ and $\\mathbf{A}_2$.  \n",
    "    \n",
    "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$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q4.\n",
    "\n",
    "How is the null space of $\\mathbf{C}$ related to the nullspaces of $\\mathbf{A}$ and $\\mathbf{B}$, if\n",
    "$$\n",
    "\\mathbf{C} = \\begin{pmatrix}\n",
    "\\mathbf{A} \\\\\n",
    "\\mathbf{B}\n",
    "\\end{pmatrix}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q5.\n",
    "\n",
    "In this exercise, we show the fact \n",
    "$$\n",
    "\\text{rank}(\\mathbf{A} + \\mathbf{B}) \\le \\text{rank}(\\mathbf{A}) + \\text{rank}(\\mathbf{B})\n",
    "$$ \n",
    "for any two matrices $\\mathbf{A}$ and $\\mathbf{B}$ of same size in steps.\n",
    "\n",
    "1. Show that the sum of two vector spaces $\\mathcal{S}_1$ and $\\mathcal{S}_2$ of same order\n",
    "$$\n",
    "\\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\\}\n",
    "$$\n",
    "is a vector space.  \n",
    "\n",
    "2. Show that $\\text{dim}(\\mathcal{S}_1 + \\mathcal{S}_2) \\le \\text{dim}(\\mathcal{S}_1) + \\text{dim}(\\mathcal{S}_2)$.\n",
    "    \n",
    "3. Show that $\\mathcal{C}(\\mathbf{A} + \\mathbf{B}) \\subseteq \\mathcal{C}(\\mathbf{A}) + \\mathcal{C}(\\mathbf{B})$. \n",
    "    \n",
    "4. Conclude that $\\text{rank}(\\mathbf{A} + \\mathbf{B}) \\le \\text{rank}(\\mathbf{A}) + \\text{rank}(\\mathbf{B})$. "
   ]
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "hide_input": false,
  "jupytext": {
   "formats": "ipynb,qmd"
  },
  "kernelspec": {
   "display_name": "Julia 1.9.3",
   "language": "julia",
   "name": "julia-1.9"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.9.3"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "87px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}