Solutions to Part I Problems.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "D:\\git\\Linear-Algebra-and-Learning-from-Data\n"
     ]
    }
   ],
   "source": [
    "# Add lib input sys.path\n",
    "import os\n",
    "import sys\n",
    "nb_dir = os.getcwd() #os.path.split(os.getcwd())\n",
    "print(nb_dir)\n",
    "if nb_dir not in sys.path:\n",
    "    sys.path.append(nb_dir)\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import lib.matrix as mat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem Set I.1\n",
    "#### Problem I.1.1\n",
    "\n",
    "The example\n",
    "\n",
    "\\begin{align*}\n",
    "1\\times \\begin{bmatrix}0\\\\1\\\\2\\\\ 3\\end{bmatrix} + 1 \\times \\begin{bmatrix}1\\\\2\\\\-1\\\\-3\\end{bmatrix} - 1 \\times \\begin{bmatrix}1\\\\3\\\\1\\\\0\\end{bmatrix} &= \\begin{bmatrix}0\\\\0\\\\0\\\\0\\end{bmatrix}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "Let $A=\\begin{bmatrix}0&1 &1 \\\\1 &2 &3\\\\ 2 & -1 & 1\\\\3 & -3 & 0\\end{bmatrix}$ and $x = \\begin{bmatrix}1\\\\1\\\\-1\\end{bmatrix}$, we have $A_{4\\times 3}x_{3\\times 1}=0_{4\\times 1}$.\n",
    "\n",
    "#### Problem I.1.2 \n",
    "\n",
    "The two solutions for $Az=0$ are: $z = x-y$ and $z=y-x$.\n",
    "\n",
    "#### Problem I.1.3\n",
    "\n",
    "* (1) $Ac = 0$, where $A = \\begin{bmatrix}a_1 & a_2 & \\dots & a_n\\end{bmatrix}_{m \\times n}$, and $c = \\begin{bmatrix}c_1 \\\\ c_2\\\\ \\vdots \\\\ c_n\\end{bmatrix}_{n \\times 1}$\n",
    "\n",
    "* (2) $\\sum^n_{j=1} a_{ij}c_j = 0$ for $i = 1, 2, \\dots, m$\n",
    "\n",
    "#### Problem I.1.4\n",
    "\n",
    "We have two solutions $x = \\begin{bmatrix}0 \\\\ 1 \\\\ -1\\end{bmatrix}$ and $y=\\begin{bmatrix}1 \\\\ 0 \\\\ -1\\end{bmatrix}$.\n",
    "\n",
    "\\begin{align*}\n",
    "0\\times \\begin{bmatrix}1 \\\\ 1 \\\\ 1\\end{bmatrix} + 1 \\times \\begin{bmatrix}1 \\\\ 1 \\\\ 1\\end{bmatrix} - 1 \\times \\begin{bmatrix}1 \\\\ 1 \\\\ 1\\end{bmatrix} &= \\begin{bmatrix}0 \\\\ 0 \\\\ 0\\end{bmatrix}\n",
    "\\end{align*}\n",
    "\n",
    "Any other solutions are linear combinations of the first two independent vectors $x$ and $y$. \n",
    "\n",
    "#### Problem I.1.5\n",
    "\n",
    "* (a) let $z=\\begin{bmatrix}z_1\\\\z_2\\\\z_3\\end{bmatrix}$, and for every linear combination of $v$ and $w$, i.e. $cv+dw$, we let $(cv+dw)^Tz = 0$, so we have\n",
    "\n",
    "\\begin{align*}\n",
    "(cv+dw)^Tz &= cv^Tz + dw^Tz\\\\\n",
    "&= c(z_1 + z_2) + d(z_2 + z_3)\\\\\n",
    "&= cz_1 + (c+d)z_2 + dz_3\\\\\n",
    "&= 0\n",
    "\\end{align*}\n",
    "\n",
    "Solve this for any $c$ and $d$, we see that $z=\\begin{bmatrix}-1\\\\1\\\\-1\\end{bmatrix}$ solves the equation.\n",
    "\n",
    "* (b) We see that $cv+dw = \\begin{bmatrix}c\\\\c+d\\\\d\\end{bmatrix}$, it's easy to see that $u=\\begin{bmatrix}1\\\\3\\\\1\\end{bmatrix}$ is not on theplane, and we have $u^Tz = \\begin{bmatrix}1 &3&1\\end{bmatrix}\\begin{bmatrix}-1\\\\1\\\\-1\\end{bmatrix} = 1 \\ne 0$\n",
    "\n",
    "#### Problem I.1.6\n",
    "\n",
    "Let the corners of the parallelogram are: $A=(1,1)$,  $B=(1,3)$, $C=(4,2)$, the fourth corner is $D$. There are three possible values for $D$:\n",
    "* If $BC = AD$, then $D = A + AD = A + BC = A + (C-B) = (1,1)+(3,-1) = (4,0)$.\n",
    "* If $BD=AC$, then $D = B + BD = B + AC =  B + (C-A) = (4,2) + (3, 1) = (7, 3)$\n",
    "* If $AD=CB$, then $D = A + AD = A + CB = A + (B-C) = (1,1) + (-3,1) = (-2, 2)$\n",
    "\n",
    "#### Problem I.1.7\n",
    "\n",
    "$A=\\begin{bmatrix}v & w & v + 2w\\end{bmatrix}$, the column space is a plane defined by the combination of vectors $v$ and $w$, i.e. $cv+dw$.\n",
    "\n",
    "Now compute the nullspace of $A$, we let $Ax=0$, that is\n",
    "\n",
    "\\begin{align*}\n",
    "Ax &= \\begin{bmatrix}v & w & v + 2w\\end{bmatrix}\\begin{bmatrix}x_1\\\\x_2\\\\x_3\\end{bmatrix}\\\\\n",
    "&= x_1v + x_2 w + x_3 (v+2w)\\\\\n",
    "&= (x_1 + x_3)v + (x_2 + 2x_3)w\\\\\n",
    "&= 0\n",
    "\\end{align*}\n",
    "\n",
    "The solution is thus $x=\\begin{bmatrix}x_1\\\\2x_1\\\\-x_1\\end{bmatrix}$ and the nullspace of $A$ is the line defined by $x$. \n",
    "\n",
    "It's easy to see that the dimension of column space + dimension of null space = number of columns in $A$.\n",
    "\n",
    "#### Problem I.1.8\n",
    "\n",
    "Since $A_{ij}=j^2$, so we have $A=\\begin{bmatrix}1&4&9\\\\1&4&9\\\\1&4&9\\end{bmatrix}$, we see that $C=\\begin{bmatrix}1\\\\1\\\\1\\end{bmatrix}$, because the other two columns are just multiplier of this one. It's easy to see that $R=\\begin{bmatrix}1 & 4 & 9\\end{bmatrix}$\n",
    "\n",
    "#### Problem I.1.9\n",
    "\n",
    "If the column space space of an $m$ by $n$ matrix is all of $R^3$, then the dimension of column space is 3, i.e. the rank $r=3$. Also because the dimension of the column space is less or equal to the number of columns, we have $m\\ge 3$. Also we know that column rank = row rank, so we also have $n\\ge 3$.\n",
    "\n",
    "#### Problem I.1.10\n",
    "\n",
    "* For $A_1$, we have $C_1=\\begin{bmatrix}1 \\\\ 3 \\\\ 2\\end{bmatrix}$ because the other two columns are multiple of the first column. \n",
    "* Fro $A_2$, we have $C_2= \\begin{bmatrix}1 & 2\\\\ 4 &5\\\\ 7 & 8\\end{bmatrix}$ because the third column is $-1$ multiply first column plus 2 multiply the second column.\n",
    "\n",
    "#### Problem I.1.11\n",
    "\n",
    "* $A_1 = \\begin{bmatrix}1 \\\\ 3 \\\\ 2\\end{bmatrix}\\begin{bmatrix}1 & 3 & -2\\end{bmatrix}$\n",
    "\n",
    "* $A_2 = \\begin{bmatrix}1 & 2\\\\ 4 &5\\\\ 7 & 8\\end{bmatrix}\\begin{bmatrix}1 & 0 & -1\\\\ 0 &1 &2\\end{bmatrix}$\n",
    "\n",
    "#### Problem I.1.12\n",
    "\n",
    "* The basis for $A_1$ are columns in $C_1$ and the basis for $A_2$ are columns in $C_2$.\n",
    "* The dimension of column space for $A_1$ is 1, for $A_2$ is 2.\n",
    "* The rank of $A_1$ is 1, for $A_2$ is 2.\n",
    "* There are 1 independent row in $A_1$, and 2 independent rows in $A_2$.\n",
    "\n",
    "#### Problem I.1.13\n",
    "\n",
    "Let $A=\\begin{bmatrix}1 &0 & 1 &1 \\\\ 0 & 1 & 1 & -1 \\\\ 0 &0 & 0 &0 \\\\ 0&0&0&0\\end{bmatrix}$, $A$ has a rank of $2$. \n",
    "\n",
    "$C$ has dimension $4\\times 2$, and $R$ has a dimension of $2\\times 4$.\n",
    "\n",
    "#### Problem I.1.14\n",
    "\n",
    "* (a) We just need to give an example of two matrices $A$ and $B$ that have the same column space but different row spaces.\n",
    "Consider vectors in $R^2$, let $A=\\begin{bmatrix}1 &2 \\\\ 1 & 2\\end{bmatrix}$, and $B=\\begin{bmatrix}2 &1 \\\\ 2 & 1\\end{bmatrix}$. Their column spaces are the same, i.e. the line $x\\begin{bmatrix}1 \\\\ 1\\end{bmatrix}$. \n",
    "\n",
    "If we write them in $A=CR$ format, we have $A=\\begin{bmatrix}1\\\\1\\end{bmatrix}\\begin{bmatrix}1 & 2 \\end{bmatrix}$ and  $B =\\begin{bmatrix}1\\\\1\\end{bmatrix}\\begin{bmatrix}2 & 1 \\end{bmatrix}$, we can see that the row space of $A$ is line $x\\begin{bmatrix}1 & 2 \\end{bmatrix}$, whic is different from the row space of $B$ is line $\\begin{bmatrix}2 & 1 \\end{bmatrix}$.\n",
    "\n",
    "* (b) The matrix $C$ for $A$ is $\\begin{bmatrix}1\\\\1\\end{bmatrix}$, while it is $\\begin{bmatrix}2\\\\2\\end{bmatrix}$ for $B$.\n",
    "\n",
    "* (c) $A$ and $B$ have the same rank because their column spaces are the same.\n",
    "\n",
    "#### Problem I.1.15\n",
    "\n",
    "If $A=CR$, the first row of $A$ is a combination of the rows of $R$, each element of the first row in $C$ corresponds to the coefficient to each row in $R$. That is, $C_{11}$ multiply row 1 of $R$, $C_{12}$ multiply row 2 of $R$, etc. and the sum of these products are the first row of $A$.\n",
    "\n",
    "#### Problem I.1.16\n",
    "\n",
    "The rows of $R$ are a basis for the row space of $A$, this means that for any vector in the row space of $A$, it is a linear combination of the row vectors in $R$. The row vectors in $R$ are independent as well.\n",
    "\n",
    "#### Problem I.1.17\n",
    "\n",
    "* $A_1 = C_1R_1 = \\begin{bmatrix}0 & 1\\\\0 & 1 \\\\ 1 & 1 \\\\ 1 & 1\\end{bmatrix}\\begin{bmatrix}1 & 1 & 0 & 0 \\\\ 0 & 0 & 1 & 1\\end{bmatrix}$\n",
    "\n",
    "* $A_2 = C_2R_2 = \\begin{bmatrix}A_1 \\\\ A_1 \\end{bmatrix} = \\begin{bmatrix}C_1R_1 \\\\ C_1R_1 \\end{bmatrix} = \\begin{bmatrix}C_1 \\\\ C_1 \\end{bmatrix}R_1$. So $C_2 = \\begin{bmatrix}C_1 \\\\ C_1 \\end{bmatrix}$ and $R_2=R_1$.\n",
    "\n",
    "* $A_3 = C_3R_3 = \\begin{bmatrix}A_1 &A_1 \\\\ A_1 & A_1 \\end{bmatrix} = \\begin{bmatrix}C_1R_1 & C_1R_1 \\\\ C_1R_1 & C_1R_1\\end{bmatrix} = \\begin{bmatrix}C_1 \\\\ C_1 \\end{bmatrix}\\begin{bmatrix}R_1 & R_1\\end{bmatrix}$\n",
    "So $C_3 = \\begin{bmatrix}C_1 \\\\ C_1 \\end{bmatrix}$ and $R_3 = \\begin{bmatrix}R_1 & R_1\\end{bmatrix}$\n",
    "\n",
    "All matrices have $rank=2$\n",
    "\n",
    "#### Problem I.1.18\n",
    "\n",
    "\\begin{align*}\n",
    "\\begin{bmatrix}\n",
    "0 & A\\\\\n",
    "0 & A\\\\\n",
    "\\end{bmatrix} &= \\begin{bmatrix}\n",
    "0 & CR \\\\\n",
    "0 & CR\\\\\n",
    "\\end{bmatrix} \\\\ \n",
    "&= \\begin{bmatrix}\n",
    "C \\\\\n",
    "C\\\\\n",
    "\\end{bmatrix}\\begin{bmatrix}\n",
    "0 & R \\\\\n",
    "0 & R \\\\\n",
    "\\end{bmatrix}\n",
    "\\end{align*}\n",
    "\n",
    "#### Problem I.1.19\n",
    "\n",
    "\\begin{align*}\n",
    "A &= \\begin{bmatrix}\n",
    "1 & 3 & 8 \\\\\n",
    "1 & 2 & 6 \\\\\n",
    "0 & 1 & 2 \\\\\n",
    "\\end{bmatrix}\\\\\n",
    "&= \\begin{bmatrix}\n",
    "1 & 3 & 8 \\\\\n",
    "0 & -1 & -2 \\\\\n",
    "0 & 1 & 2 \\\\\n",
    "\\end{bmatrix}\\\\\n",
    "&= \\begin{bmatrix}\n",
    "1 & 3 & 8 \\\\\n",
    "0 & -1 & -2 \\\\\n",
    "0 & 0 & 0 \\\\\n",
    "\\end{bmatrix}\\\\\n",
    "&= \\begin{bmatrix}\n",
    "1 & 0 & 2 \\\\\n",
    "0 & -1 & -2 \\\\\n",
    "0 & 0 & 0 \\\\\n",
    "\\end{bmatrix}\\\\\n",
    "&= \\begin{bmatrix}\n",
    "1 & 0 & 2 \\\\\n",
    "0 & 1 & 2 \\\\\n",
    "0 & 0 & 0 \\\\\n",
    "\\end{bmatrix}\\\\\n",
    "&= \\text{rref}(A)\\\\\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.1.20\n",
    "\n",
    "We have $C=\\begin{bmatrix}2\\\\3\\end{bmatrix}$, $R=\\begin{bmatrix}2 & 4 \\end{bmatrix}$, so $C^TC= \\begin{bmatrix}2&3\\end{bmatrix}\\begin{bmatrix}2\\\\3\\end{bmatrix} = 13$, and $RR^T=\\begin{bmatrix}2&4\\end{bmatrix}\\begin{bmatrix}2\\\\4\\end{bmatrix} = 20$, $C^TAR^T = \\begin{bmatrix}2&3\\end{bmatrix}\\begin{bmatrix}2&4\\\\3&6\\end{bmatrix}\\begin{bmatrix}2\\\\4\\end{bmatrix}=130$\n",
    "\n",
    "\n",
    "Then we get $M=(C^TC)^{-1}(C^TAR^T)(RR^T)^{-1} = \\frac{1}{13}130\\frac{1}{20}=\\frac{1}{2}$\n",
    "\n",
    "#### Problem I.1.21\n",
    "\n",
    "We have $C=\\begin{bmatrix}1&3\\\\1&2\\\\0&1\\end{bmatrix}$ and $R=\\begin{bmatrix}1&3&8\\\\1&2&6\\end{bmatrix}$, and compute $(C^TC)^{-1}=\\frac{1}{16}\\begin{bmatrix}13&-5\\\\-5&2\\end{bmatrix}$, and $(RR^T)^{-1} = \\frac{1}{9}\\begin{bmatrix}41&-55\\\\-55&74\\end{bmatrix} $\n",
    "\n",
    "Also $C^TAR^T = \\begin{bmatrix}129&96\\\\351&261\\end{bmatrix}$\n",
    "\n",
    "So we have $M=(C^TC)^{-1}(C^TAR^T)(RR^T)^{-1} = \\begin{bmatrix}-\\frac{7}{16}&\\frac{1}{2}\\\\\\frac{3}{16}&-\\frac{3}{16}\\end{bmatrix}$\n",
    "\n",
    "#### Problem I.1.22\n",
    "\n",
    "If we have $\\begin{bmatrix}b\\\\d\\end{bmatrix}=m\\begin{bmatrix}a\\\\c\\end{bmatrix}$, then $ad-bc = amc - mac = 0$, then the inversion of 2x2 matrix doesn't exist.\n",
    "\n",
    "#### Problem I.1.23\n",
    "\n",
    "We pick $A=\\begin{bmatrix}1 &2\\\\2&4\\\\3&6\\end{bmatrix}$, then we have $A=CR=\\begin{bmatrix}1\\\\2\\\\3\\end{bmatrix}\\begin{bmatrix}1&2\\end{bmatrix}$. \n",
    "\n",
    "Then we have $(C^TC)^{-1} = \\frac{1}{14}$, and pick $R=\\begin{bmatrix}1&2\\end{bmatrix}$, so $(RR^T)^{-1} = \\frac{1}{5}$\n",
    "and $C^TAR^T = 70$, so we have $M= \\begin{bmatrix}1\\end{bmatrix}$\n",
    "\n",
    "#### Problem I.1.24\n",
    "\n",
    "We pick $A=\\begin{bmatrix}1 &3\\\\2&5\\\\3&6\\end{bmatrix}$, then we have $A=CR=\\begin{bmatrix}1 &3\\\\2&5\\\\3&6\\end{bmatrix}I$. \n",
    "\n",
    "and pick $R=\\begin{bmatrix}1&3\\\\2&5\\end{bmatrix}$, so we have $M= \\begin{bmatrix}-8&11\\\\-15&23\\end{bmatrix}$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[ 3.68421053, -1.63157895],\n",
       "        [-1.63157895,  0.73684211]]), array([[ 29., -17.],\n",
       "        [-17.,  10.]]), array([[ 8969, 15334],\n",
       "        [20187, 34513]]), array([[ -8.,  11.],\n",
       "        [-15.,  23.]]))"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "#C = np.array([1,2,3]).reshape(3,1)\n",
    "R = np.array([[1, 3], [2,5]])#.reshape(1,2)\n",
    "A = np.array([[1,3],[2,5],[3,6]])\n",
    "C = A\n",
    "\n",
    "a = np.matmul(C.transpose(), A)\n",
    "b = np.matmul(a, R.transpose())\n",
    "k = np.matmul(C.transpose(), C)\n",
    "invc = np.linalg.inv(k)\n",
    "invr = np.linalg.inv(np.matmul(R, R.transpose()))\n",
    "m = np.matmul(a, b)\n",
    "f = np.matmul(invc, m)\n",
    "f = np.matmul(f, invr)\n",
    "invc, invr, m, f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.2.1\n",
    "\n",
    "$AB=A\\begin{bmatrix}x & y\\end{bmatrix}=\\begin{bmatrix}0 & 0\\end{bmatrix}$. So If $A$ is $m$ by $n$, then $B$ is $n$ by $2$, and $C$ is $m$ by $2$.\n",
    "\n",
    "#### Problem I.2.2\n",
    "Yes, you can multiply $a$ times $b^T$, the shape of the answer $ab^T$ is $m$ by $p$. The number is row $i$, column $j$ of $ab^T$ is $a_ib_j$\n",
    "\n",
    "$aa^T$ is symmetric with the diagonal elements the squares of the elements in $a$. \n",
    "\n",
    "#### Problem I.2.3\n",
    "\n",
    "* (a) Sum of rank on formula for the matrix-matrix product $AB$\n",
    "\n",
    "$AB=\\sum^n_{j=1} a_jb^T_j$\n",
    "\n",
    "* (b) $c_{ij} = \\sum^n_{k=1} a_{ki}b_{kj}$\n",
    "\n",
    "#### Problem I.2.4\n",
    "\n",
    "If $B$ has only 1 column, $AB=\\sum^n_{j=1} a_jb_j$ where $b_j$ is a number. The $m$ by $1$ column vector $AB$ is a combination of the columns in $A$.\n",
    "\n",
    "#### Problem I.2.5\n",
    "\n",
    "$(AB)C = \\begin{bmatrix}b_1+ab_3 & b_2+ab_4\\\\b_3 & b_4\\end{bmatrix}\\begin{bmatrix}1 &0 \\\\ c& 1\\end{bmatrix} = \\begin{bmatrix}b_1+ab_3+cb_2+acb_4 & b_2+ab_4\\\\b_3 +cb_4& b_4\\end{bmatrix}$\n",
    "\n",
    "$A(BC) = \\begin{bmatrix}1 & a\\\\0 & 1\\end{bmatrix}\\begin{bmatrix}b_1+cb_2 & b_2\\\\b_3+cb_4 & b_4\\end{bmatrix} = \\begin{bmatrix}b_1+ab_3+cb_2+acb_4 & b_2+ab_4\\\\b_3 +cb_4& b_4\\end{bmatrix}$\n",
    "\n",
    "So we verified $(AB)C=A(BC)$\n",
    "\n",
    "#### Problem I.2.6\n",
    "If $B=I$, then the rank-one matrices $a_1b^*_1 = \\begin{bmatrix}a_1 & 0 & 0\\end{bmatrix}$, $a_2b^*_2 = \\begin{bmatrix}0 & a_2 & 0 \\end{bmatrix}$ and $a_3b^*_3 = \\begin{bmatrix}0 & 0 & a_3 \\end{bmatrix}$, they add up to $AI=A$.\n",
    "\n",
    "#### Problem I.2.7\n",
    "\n",
    "Example of $A$ and $B$ for which $AB$ has a smaller column space than $A$. \n",
    "Let $A=\\begin{bmatrix}1 & 4\\\\2 & 5 \\\\3 & 6\\end{bmatrix}$, it has a column space of dimension 2, and $B=\\begin{bmatrix}1 \\\\ 0\\end{bmatrix}$, then $AB=\\begin{bmatrix}1 \\\\ 2 \\\\ 3\\end{bmatrix}$, which is clearly has a column space of dimension 1, and is smaller than $A$.\n",
    "\n",
    "#### Problem I.2.8\n",
    "\n",
    "To get columns times rows, we do: \n",
    "\n",
    "* (1) For $k=1$ to $n$\n",
    "* (2) For $i=1$ to $m$\n",
    "* (3) For $j=1$ to $p$\n",
    "* (4) $C(i,j) = C(i,j) + A(i,k)B(k,j)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[12.],\n",
       "       [26.]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#### Test the multiplication of columns times rows\n",
    "\n",
    "#### Test cases\n",
    "a = np.array([1,2])\n",
    "b = np.array([3,4])\n",
    "my_outer = mat.outer_product(a, b)\n",
    "np_outer = np.outer(a,b)\n",
    "assert(np.array_equal(my_outer, np_outer))\n",
    "\n",
    "A = np.array([[1,2],[3,4]])\n",
    "B = np.array([[2,1],[5,6]])\n",
    "np_prod = np.matmul(A, B)\n",
    "my_prod_outer = mat.columns_times_rows_outer(A, B)\n",
    "my_prod_rc = mat.rows_times_columns(A, B)\n",
    "my_prod_cr = mat.columns_times_rows(A, B)\n",
    "assert(np.array_equal(my_prod_outer, np_prod))\n",
    "assert(np.array_equal(my_prod_rc, np_prod))\n",
    "assert(np.array_equal(my_prod_cr, np_prod))\n",
    "\n",
    "A = np.array([[1,2],[3,4]])\n",
    "B = np.array([[2],[5]])\n",
    "mat.columns_times_rows(A, B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.3.1\n",
    "\n",
    "For any vector $x$ in the nullspace of $B$, we have $Bx=0$, so we also have $ABx=A0=0$, so $x$ is also in the nullspace of $AB$. We showed that the nullspace of $AB$ contains the nullspace of $B$.\n",
    "\n",
    "#### Problem I.3.2\n",
    "\n",
    "We choose $A=\\begin{bmatrix}-4 &-8 \\\\ 2 & 4\\end{bmatrix}$, so $A^2 = \\begin{bmatrix}0 &0 \\\\ 0 & 0\\end{bmatrix}$. \n",
    "We have $\\text{rank}(A)=1$, $\\text{rank}(A^2)=0 \\lt \\text{rank}(A)$.\n",
    "We also can prove that $A^TA=\\begin{bmatrix}20 &40 \\\\ 40 & 80\\end{bmatrix}$, so we see that $rank(A^TA)=rank(A)$.\n",
    "You can find such $A$ by making assumptions on its columns and the columns of $A^2$.\n",
    "\n",
    "#### Problem I.3.3\n",
    "\n",
    "If $x$ belongs to the nullspace of $C$, then we have $Cx=\\begin{bmatrix}A\\\\B\\end{bmatrix}x=\\begin{bmatrix}Ax\\\\Bx\\end{bmatrix}=0$ so it makes $Ax=0$ and $Bx=0$ at the same time. So the $x$ belongs to both the nullspace of $A$ and $B$. \n",
    "\n",
    "The opposite is also true, i.e. if $x$ belongs to both the nullspace of $A$ and $B$, it also belongs to the nullspace of $C$. \n",
    "So we conclude that the nullspace of $C$ is the intersection of the nullspaces of $A$ and $B$.\n",
    "\n",
    "#### Problem I.3.4\n",
    "\n",
    "Suppose for matrix $A$, its rank is $r$, since $N(A)=N(A^T)$, we know that the dimension of $N(A)$ and $N(A^T)$ spaces are equal, i.e. $m-r=n-r$, so we have $m=n$, $A$ is a square matrix. \n",
    "\n",
    "For any given vector $x$ in the nullspace $N(A)$, it is also in the left-nullspace $N(A^T)$, so we have $Ax=0$ and $A^Tx=0$, combine both equations, we have $(A-A^T)x=0$, so unless $x$ is zero, we have $A=A^T$. So if the nullspace has dimension $>0$, we can say $A$ is symmetric. \n",
    "\n",
    "If, however, the nullspace of $A$ has dimension 0, i.e. $r=m=n$, then we may not have a symmetric matrix $A$. \n",
    "\n",
    "For example, let $A=\\begin{bmatrix}1&3\\\\2&4\\end{bmatrix}$, this matrix has a rank of 2, and row space = column space, since both span the full $R^2$ plane, but clearly, $A$ is not symmetric.\n",
    "\n",
    "#### Problem I.3.5\n",
    "\n",
    "* $r=m=n$, $A_1=\\begin{bmatrix}1&3\\\\2&4\\end{bmatrix}$. $A_1$ is invertible, so $A_1x=b$ has 1 solution for every $b$. Or we can say that the column space is the full $R^2$, so for every $b$ in $R^2$, it's in the column space, and we have a solution.\n",
    "\n",
    "* $r=m<n$, $A_2=\\begin{bmatrix}1&2&3\\\\2&4&1\\end{bmatrix}$, since the column 1 and column 2 are dependent, we have $\\text{rank}(A_2)=m = 2$. For $A_2x=b$, we have two equations and 3 unknowns, which generally gives us infinitely many solutions. Or we can say that the column space is $R^2$ in $R^2$, so every $b$ from $R^2$ is in the column space and we always have a solution corresponding to the basis matrix. Since column 2 is a multiple of column 1, there are infinitely many solutions. \n",
    "However, if one of the columns is 0, e.g. $A_2=\\begin{bmatrix}0&2&3\\\\0&4&1\\end{bmatrix}$, we still have $rank(A_2)=2$, but there's only one solution for $A_2x=b$ now.\n",
    "* $r=n<m$, $A_3=\\begin{bmatrix}1&3\\\\2&4\\\\3&6\\end{bmatrix}$, so $rank(A_3)=2$, for $A_3x=b$, If $b$ is in the column space. For example, $b=\\begin{bmatrix}4\\\\6\\\\9\\end{bmatrix}$, we'll have a solution, but if $b$ is not in the column space, there's no solution.\n",
    "* $r<m,r<n$, $A_4=\\begin{bmatrix}1&2\\\\2&4\\\\3&6\\end{bmatrix}$, $rank(A_4)=1 < m, n$. for $A_4x=b$, we have 3 equations and 1 unknown. If $b$ is in the column space (a line along $\\begin{bmatrix}1\\\\2\\\\3\\end{bmatrix}$), we have infinitely many solutions, otherwise there's no solution at all.\n",
    "\n",
    "#### Problem I.3.6\n",
    "\n",
    "If $Ax$ equals zero, then $A^TAx=0$ as well. This shows that every vector in the $N(A)$ is also in $N(A^TA)$, so we have $N(A)\\subset N(A^TA)$. \n",
    "\n",
    "On the other hand, if $A^TAx=0$, then $x^TA^TAx=0$, i.e. $\\|Ax\\|^2=0$ and we see $Ax=0$, so if a vector is in $N(A^TA)$, it's also in $N(A)$, and we have $N(A^TA) \\subset N(A)$. \n",
    "\n",
    "We conclude from above that $N(A)=N(A^TA)$, i.e. $A^TA$ has the same nullspace as $A$.\n",
    "\n",
    "#### Problem I.3.7\n",
    "\n",
    "From problem I.3.2, we see that for a square matrix, we can have the case that $rank(A^2)\\lt rank(A)$, since the dimension of nullspace is $n-r$, so the dimensions of nullspace between $A^2$ and $A$ can be different, and the nullspaces can of course be different.\n",
    "\n",
    "#### Problem I.3.8\n",
    "\n",
    "We have $A=\\begin{bmatrix}0&1\\\\0 &0\\end{bmatrix}$, it's easy to see that $C=\\begin{bmatrix}1\\\\0\\end{bmatrix}$ and let $Ax=0$, and solve for $x$, we have $x=\\begin{bmatrix}c\\\\0\\end{bmatrix}$, where $c$ is any number. It's clear that the column space and nullspace are the same in such case.\n",
    "\n",
    "#### Problem I.3.9\n",
    "\n",
    "$A=\\begin{bmatrix}-1&1&0&0&0\\\\0&-1&1&0&0\\\\0&0&1&-1&0\\\\1&0&0&-1&0\\\\1&0&0&0&-1\\\\0&1&0&0&-1\\\\0&0&1&0&-1\\\\0&0&0&1&-1\\end{bmatrix}$\n",
    "\n",
    "One vector in $N(A)$ is $\\begin{bmatrix}1\\\\1\\\\1\\\\1\\\\1\\end{bmatrix}$\n",
    "\n",
    "The four independent vectors in $N(A^T)$ are identified from the four loops in the graph:\n",
    "\n",
    "$v_1=\\begin{bmatrix}-1\\\\0\\\\0\\\\0\\\\-1\\\\1\\\\0\\\\0\\end{bmatrix}$\n",
    "$v_2=\\begin{bmatrix}0\\\\-1\\\\0\\\\0\\\\0\\\\-1\\\\1\\\\0\\end{bmatrix}$\n",
    "$v_3=\\begin{bmatrix}0\\\\0\\\\1\\\\0\\\\0\\\\0\\\\-1\\\\1\\end{bmatrix}$\n",
    "$v_4=\\begin{bmatrix}0\\\\0\\\\0\\\\-1\\\\1\\\\0\\\\0\\\\-1\\end{bmatrix}$\n",
    "\n",
    "#### Problem I.3.10 \n",
    "\n",
    "If $N(A)$ is zero vector, the for $B=\\begin{bmatrix}A&A&A\\end{bmatrix}$, its nullspace is also zero vector, since for $Bx=0$, we need to make $\\begin{bmatrix}Ax&Ax&Ax\\end{bmatrix}=0$, which dictates each $Ax=0$, which has only zero solution. So the $N(B)$ is also zero vector.\n",
    "\n",
    "#### Problem I.3.11\n",
    "\n",
    "* (i) $S\\cap T$: the possible dimension is 7 if $S \\subset T$, or 0 if no such vector exists. \n",
    "* (ii) $S+T$: 7 if $S \\subset T$, 8,9 if there's vector in $S$ but not in $T$.\n",
    "If we think about matrices $A$ and $B$, both with 10 rows. If $rank(A)=2$ and $rank(B)=7$, then $A$'s column space is a dimension 2 subspace in $R^{10}$, and $B$'s column space is dimension 7 subspace in $R^{10}$. So for $Ax$ and $By$ are vectors in subspaces $S$ and $T$ separately. Then $Ax+By=\\begin{bmatrix}A&B\\end{bmatrix}\\begin{bmatrix}x\\\\y\\end{bmatrix}$ is a vector of $s+t$. So we need find the column space of $\\begin{bmatrix}A&B\\end{bmatrix}$. The maximum number of independent columns is thus 9, and minimum number of independent columns is 7. \n",
    "* (iii) All vectors in $R^{10}$ that are perpendicular to every vector in $S$: If we think about $S$ as column space in $R^{10}$, the space that perpendicular to a column space is the left nullspace, whose dimension is $m-r=10-2=8$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.4.1\n",
    "\n",
    "$A=\\begin{bmatrix}2 &1 \\\\6 & 7\\end{bmatrix}=\\begin{bmatrix}1 &0 \\\\3 & 1\\end{bmatrix}\\begin{bmatrix}2 &1 \\\\0 & 4\\end{bmatrix}$\n",
    "\n",
    "$A=\\begin{bmatrix}1 &1 &1\\\\1 & 1 &1 \\\\ 1 & 1 & 1\\end{bmatrix}=\\begin{bmatrix}1 &0 &0 \\\\1 & 1 & 0\\\\1 &0 & 1\\end{bmatrix}\\begin{bmatrix}1 &1 &1 \\\\0 & 0 &0 \\\\ 0 & 0 &0\\end{bmatrix}$\n",
    "\n",
    "$A=\\begin{bmatrix}2 &-1 &0\\\\-1 & 2 &-1 \\\\ 0& -1 & 2\\end{bmatrix}=\\begin{bmatrix}1 &0 &0 \\\\-\\frac{1}{2} & 1 & 0\\\\0 &-\\frac{2}{3} & 1\\end{bmatrix}\\begin{bmatrix}2 &-1 &0 \\\\0 & \\frac{3}{2} &-1 \\\\ 0 & 0 &\\frac{4}{3}\\end{bmatrix}$\n",
    "\n",
    "#### Problem I.4.2\n",
    "\n",
    "Suppose the rank-1 matrix $A$ is created by two vectors: $xy^T$, so we have for row $i$ and column $j$, $a_{ij} = x_iy_j$. Since we know $a_{11},\\dots, a_{1n}$ and $a_{11}, \\dots, a_{m1}$, so if we assume $x_1$ is known, then it's easy to see that $y_{j} = \\frac{a_{1j}}{x_1}$ and $x_{i} = \\frac{a_{i1}}{y_1}=\\frac{a_{i1}x_1}{a_{11}}$. In the end, we have $a_{ij} = \\frac{a_{i1}a_{1j}}{a_{11}}$.\n",
    "\n",
    "\n",
    "For $a_{11}=2$, $a_{12}=3$, $a_{21}=4$, we have $a_{22}=\\frac{a_{21}a_{12}}{a_{11}}=6$. \n",
    "\n",
    "This formula breaks down when $x_1=0$, i.e. $a_{11}, \\dots, a_{1n}$ are all zeros. The same happens when $y_1=0$. Then rank 1 is impossible (when both are zeros) or not unique.\n",
    "\n",
    "#### Problem I.4.3\n",
    "\n",
    "Notice that when we apply 'elimination' process on a matrix $A$, at the end of the process, it becomes an upper triangular matrix. So we can search for matrices that when left multiply the $A$, they reduce the $A$ to $U$. We look for one matrix for each step in an 'elimination' process. \n",
    "\n",
    "Suppose $A$ is $n$ by $n$ matrix. The first step is to transform the first elements of all rows except the first row to be zeros. We achieve this by multiply a number to the first row and subtract from each row below. Represented by a left multiply matrix, we have\n",
    "\n",
    "$E_1 = \\begin{bmatrix}1 &0 &\\dots &0\\\\-l_{21} & 1 &\\dots &0 \\\\ -l_{31} & 0 & 1 & \\dots\\\\\\dots& \\dots & \\dots & \\dots \\\\ -l_{n1} & 0 & \\dots & 1\\end{bmatrix}$\n",
    "\n",
    "Now apply step 2 of 'elimination' to change all the second elements for rows below the second row to zero, we have \n",
    "$E_2 = \\begin{bmatrix}1 &0 &\\dots &0\\\\0 & 1 & \\dots &0 \\\\ 0 & -l_{32} & 1 & 0\\\\\\dots& \\dots & \\dots & \\dots \\\\ 0 & -l_{n2} & \\dots & 1\\end{bmatrix}$\n",
    "\n",
    "Continue this until we have \n",
    "$E_{n-1} = \\begin{bmatrix}1 &0 &\\dots &0\\\\0 & 1 & \\dots &0 \\\\ 0 & 0 & 1 & 0\\\\\\dots& \\dots & \\dots & \\dots \\\\ 0 & \\dots & -l_{n,n-1} & 1\\end{bmatrix}$\n",
    "\n",
    "Now it's clear that $E=E_{n-1}\\dots E_{2}E_{1}$.\n",
    "\n",
    "For $A=\\begin{bmatrix}2 &1 &0\\\\0 & 4 &2 \\\\ 6 & 3 & 5\\end{bmatrix}$, we have $n=3$, so \n",
    "$E_1 = \\begin{bmatrix}1 &0 &0\\\\-l_{21} & 1 &0 \\\\ -l_{31} & 0 & 1\\end{bmatrix}$\n",
    "and \n",
    "$E_2 = \\begin{bmatrix}1 &0 &0\\\\0 & 1 & 0 \\\\ 0 & -l_{32} & 1\\end{bmatrix}$\n",
    "\n",
    "so $E=E_2E_1 = \\begin{bmatrix}1 &0 &0\\\\-l_{21} & 1 & 0 \\\\ -l_{31}+l_{21}l_{32} & -l_{32} & 1\\end{bmatrix}=\\begin{bmatrix}1 &0 &0\\\\0 & 1 & 0 \\\\ -3 & 0 & 1\\end{bmatrix}$\n",
    "\n",
    "And $L=E^{-1} = \\begin{bmatrix}1 &0 &0 \\\\0 & 1 & 0\\\\3 &0 & 1\\end{bmatrix}$\n",
    "\n",
    "$A=\\begin{bmatrix}2 &1 &0\\\\0 & 4 &2 \\\\ 6 & 3 & 5\\end{bmatrix}=\\begin{bmatrix}1 &0 &0 \\\\0 & 1 & 0\\\\3 &0 & 1\\end{bmatrix}\\begin{bmatrix}2 &1 &0 \\\\0 & 4 &2 \\\\ 0 & 0 &5\\end{bmatrix}$， \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.4.4\n",
    "\n",
    "* (a) $E=E_2E_1=\\begin{bmatrix}1 & 0 & 0\\\\ -a & 1 & 0 \\\\ ac -b & -c & 1\\end{bmatrix}$, and we have \n",
    "$EA = I$.\n",
    "\n",
    "* (b) $E^{-1}_1 = \\begin{bmatrix}1 & 0 & 0\\\\ a & 1 & 0 \\\\ b & 0 & 1\\end{bmatrix}$ and $E^{-1}_2 = \\begin{bmatrix}1 & 0 & 0\\\\ 0 & 1 & 0 \\\\ 0 & c & 1\\end{bmatrix}$\n",
    "\n",
    "So $L=E^{-1}_1E^{-1}_2 =\\begin{bmatrix}1 & 0 & 0\\\\ a & 1 & 0 \\\\ b & c & 1\\end{bmatrix} = A$\n",
    "\n",
    "We notice that the multipliers $a$, $b$, $c$ are mixed up in $E=L^{-1}$ but  they are perfect in $L$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.4.5\n",
    "\n",
    "$\\begin{bmatrix}1 & 0 \\\\ l & 1\\end{bmatrix}\\begin{bmatrix}d & e \\\\ 0 & f\\end{bmatrix} = \\begin{bmatrix}d & e \\\\ ld & le+f\\end{bmatrix} = \\begin{bmatrix}0 & 1 \\\\ 2 & 3\\end{bmatrix}$\n",
    "\n",
    "So we have $d=0$, $e=1$, but also $ld=0$, which doesn't equal to 2, and contradicts. \n",
    "\n",
    "$\\begin{bmatrix}1 & 0 & 0\\\\ l & 1 & 0 \\\\ m & n & 1\\end{bmatrix}\\begin{bmatrix}d & e & g\\\\ 0 & f & h \\\\ 0 & 0 & i\\end{bmatrix} = \\begin{bmatrix}d & e & g\\\\ ld & le+f & lg + h \\\\md & me + nf & mg + nh + i \\end{bmatrix} = \\begin{bmatrix}1 & 1 & 0 \\\\1& 1 & 2 \\\\1 & 2 & 1\\end{bmatrix}$\n",
    "\n",
    "We get $d=e=1$, and $g=0$, from $ld=1$, we have $l=1$, and from $lg+h=2$, we have $h=2$, and from $le+f=1$, we have $f=0$, from $md=1$, we have $m=1$, but then $me+nf = 1 + 0 = 1$ which doesn't equal to $2$, contradicts. \n",
    "\n",
    "#### Problem I.4.6\n",
    "\n",
    "To make zero in the second pivot position, $c = 2$, then $A=\\begin{bmatrix}1 & 2 & 0\\\\2 & 4 & 1 \\\\ 3 & 5 & 1\\end{bmatrix} \\rightarrow \\begin{bmatrix}1 & 2 & 0\\\\0 & 0 & 1 \\\\ 0 & -1 & 1\\end{bmatrix}$, we exchange row 2 and row 3 to get an upper triangular matrix $U$. \n",
    "\n",
    "However, when $c=1$, then $A=\\begin{bmatrix}1 & 1 & 0\\\\2 & 4 & 1 \\\\ 3 & 5 & 1\\end{bmatrix}\\rightarrow \\begin{bmatrix}1 & 1 & 0\\\\0 & 2 & 1 \\\\ 0 & 2 & 1\\end{bmatrix}\\rightarrow\\begin{bmatrix}1 & 1 & 0\\\\0 & 0 & 1 \\\\ 0 & 0 & 0\\end{bmatrix}$. It's clear that no row exchange can generate an upper triangular matrix with non-zero pivot elements.\n",
    "\n",
    "#### Problem I.4.7\n",
    "\n",
    "$A=\\begin{bmatrix}a & a & a & a\\\\a & b & b & b\\\\ a & b & c & c \\\\ a & b & c & d\\end{bmatrix}\\rightarrow\\begin{bmatrix}a & a & a & a\\\\0 & b-a & b-a & b-a\\\\ 0 & b-a & c-a & c-a \\\\ 0 & b-a & c-a & d-a\\end{bmatrix} \\rightarrow\\begin{bmatrix}a & a & a & a\\\\0 & b-a & b-a & b-a\\\\ 0 & 0 & c-b & c-b \\\\ 0 & 0 & c-b & d-b\\end{bmatrix}\\rightarrow\\begin{bmatrix}a & a & a & a\\\\0 & b-a & b-a & b-a\\\\ 0 & 0 & c-b & c-b \\\\ 0 & 0 & 0 & d-c\\end{bmatrix}$\n",
    "\n",
    "and we have $A=LU=\\begin{bmatrix}1 & 0 & 0 & 0\\\\1 & 1 & 0 & 0\\\\ 1 & 1 & 1 & 0 \\\\ 1 & 1 & 1 & 1\\end{bmatrix}\\begin{bmatrix}a & a & a & a\\\\0 & b-a & b-a & b-a\\\\ 0 & 0 & c-b & c-b \\\\ 0 & 0 & 0 & d-c\\end{bmatrix}$\n",
    "\n",
    "For $U$ with non-zero pivot, we need $a\\ne 0$, and $b\\ne a$, $c\\ne b$, $d\\ne c$.\n",
    "\n",
    "#### Problem I.4.8\n",
    "\n",
    "$A=\\begin{bmatrix}1 & 1 & 0 \\\\1 & 2 & 1\\\\ 0 & 1 & 2\\end{bmatrix} = LU= \\begin{bmatrix}1 & 0 & 0 \\\\1 & 1 & 0 \\\\ 0 & 1 & 1 \\end{bmatrix}\\begin{bmatrix}1 & 1 & 0 \\\\0 & 1 & 1 \\\\ 0 & 0 & 1 \\end{bmatrix} = \\begin{bmatrix}1 & 0 & 0 \\\\1 & 1 & 0 \\\\ 0 & 1 & 1 \\end{bmatrix}\\begin{bmatrix}1 & 0 & 0 \\\\0 & 1 & 0 \\\\ 0 & 0 & 1 \\end{bmatrix}\\begin{bmatrix}1 & 1 & 0 \\\\0 & 1 & 1 \\\\ 0 & 0 & 1 \\end{bmatrix} = LDL^T$\n",
    "\n",
    "$A=\\begin{bmatrix}a & a & 0 \\\\a & a+b & b\\\\ 0 & b & b+c\\end{bmatrix} = LU= \\begin{bmatrix}1 & 0 & 0 \\\\1 & 1 & 0 \\\\ 0 & 1 & 1 \\end{bmatrix}\\begin{bmatrix}a & a & 0 \\\\0 & b & b \\\\ 0 & 0 & c \\end{bmatrix} = \\begin{bmatrix}1 & 0 & 0 \\\\1 & 1 & 0 \\\\ 0 & 1 & 1 \\end{bmatrix}\\begin{bmatrix}a & 0 & 0 \\\\0 & b & 0 \\\\ 0 & 0 & c \\end{bmatrix}\\begin{bmatrix}1 & 1 & 0 \\\\0 & 1 & 1 \\\\ 0 & 0 & 1 \\end{bmatrix} = LDL^T$\n",
    "\n",
    "#### Problem I.4.9\n",
    "\n",
    "The pivots for the upper left 2 by 2 submatrix $A_2$ are 5 and 9.\n",
    "\n",
    "#### Problem I.4.10\n",
    "\n",
    "$A_k$ factors into $L_kU_k$\n",
    "\n",
    "#### Problem I.4.11\n",
    "\n",
    "$A=\\begin{bmatrix}1 &3 \\\\ 2 &4 \\end{bmatrix}=\\begin{bmatrix}\\frac{3}{4} \\\\ 1 \\end{bmatrix}\\begin{bmatrix}2 &4 \\end{bmatrix} + \\begin{bmatrix}-\\frac{1}{2} &0 \\\\ 0 &0 \\end{bmatrix} = \\begin{bmatrix}\\frac{3}{4} &1 \\\\ 1 &0 \\end{bmatrix}\\begin{bmatrix}2 &4 \\\\ -\\frac{1}{2} & 0 \\end{bmatrix}$\n",
    "\n",
    "$P_1AP_2 = LU = \\begin{bmatrix}1 & 0 \\\\ \\frac{3}{4} & 1 \\end{bmatrix}\\begin{bmatrix}4 &2 \\\\ 0 & -\\frac{1}{2} \\end{bmatrix}$\n",
    "\n",
    "#### Problem I.4.12\n",
    "\n",
    "If the short wide matrix $A$ has $m < n$, we put $0$ as the extra  column of $A$, then go with 'elimination'. Since $m < n$, we only do $m-1$ eliminations, so there are going to be $n-(m-1)=n-m+1$ non zero elements at the last row (excluding the b=0 column). since $n-m+1 > 1$, this means that there are non-zero solution to the equations. The nullspace dimension is thus at least $n-m$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.5.1\n",
    "\n",
    "If $u$ and $v$ are orthogonal unit vectors, then we have $(u+v)^T(u-v)=(u^T+v^T)(u-v)=u^Tu-u^Tv+vu^T-v^Tv= 1 + 0 - 0 - 1 = 0$, so $u+v$ is orthogonal to $u-v$. \n",
    "\n",
    "$|u+v|^2=(u+v)^T(u+v)=(u^T+v^T)(u+v)=u^Tu + u^Tv + v^Tu + v^Tv = 1 + 0 + 0 + 1 = 2$, so the length of vector $u+v$ is $\\sqrt{2}$. \n",
    "\n",
    "Similarly\n",
    "\n",
    "$|u-v|^2=(u-v)^T(u-v)=(u^T-v^T)(u-v)=u^Tu - u^Tv - v^Tu + v^Tv = 1 - 0 - 0 + 1 = 2$, so the length of vector $u-v$ is $\\sqrt{2}$. \n",
    "\n",
    "#### Problem I.5.2\n",
    "\n",
    "Note $u$ and $v$ are unit vectors. \n",
    "$u^Tw=u^T\\left(v-u(u^Tv)\\right)=u^Tv - u^Tu(u^Tv)=u^Tv - u^Tv = 0$\n",
    "\n",
    "#### Problem I.5.3\n",
    "\n",
    "$w^Tw + z^Tz = (u+v)^T(u+v) + (u-v)^T(u-v) = (u^T+v^T)(u+v) + (u^T-v^T)(u-v) = u^Tu + u^Tv + v^Tu + v^Tv + u^Tu - u^Tv - v^Tu + v^Tv = 2u^Tu + 2v^Tv$.\n",
    "\n",
    "#### Problem I.5.4\n",
    "Since $Q$ is orthogonal matrix, we have $Q^TQ=I$.\n",
    "\n",
    "$(Qx)^T(Qy) = x^TQ^TQy=x^Ty$. \n",
    "\n",
    "#### Problem I.5.5\n",
    "\n",
    "If $Q$ is orthogonal, then there are $n$ bases for matrix $Q$, and they are all independent of each other because of the orthogonality property. So the rank of $Q$ is $n$, which says it is invertible. \n",
    "Since $Q^{-1}=Q^T$, we have $QQ^{-1}=QQ^T=I$, which says the columns of $Q^T$ i.e., the rows of $Q$ are orthogonal, rows of $Q$ are actually columns of $Q^{-1}$, so we know $Q^{-1}$ is also orthogonal. \n",
    "\n",
    "If $Q^T_1=Q^{-1}_1$ and $Q^T_2=Q^{-1}_2$, we have $(Q_1Q_2)^T(Q_1Q_2)=Q_2^TQ_1^TQ_1Q_2=Q_2^TQ^{-1}_1Q_1Q_2=Q^{-1}_2Q_2=I$.\n",
    "\n",
    "So $Q_1Q_2$ is an orthogonal matrix. \n",
    "\n",
    "#### Problem I.5.6\n",
    "\n",
    "Suppose the columns of $P$ are $p_1,\\dots, p_n$, then we have $p^T_ip_j = 0$ if $i\\ne j$, and $1$ is $i=j$. So $P^TP$=I$ and $P$ is square so it's orthogonal.\n",
    "\n",
    "$P$ is orthogonal, so $P^TP=I$ and $P^{-1}=P^T$. \n",
    "\n",
    "When a matrix is symmetric or orthogonal, it will have orthogonal eigenvectors.\n",
    "\n",
    "#### Problem I.5.7\n",
    "\n",
    "* $\\bar{x}^T_1x_1 = 4$\n",
    "* $\\bar{x}^T_2x_2 = \\begin{bmatrix}1 & -i & -1 & i \\end{bmatrix}\\begin{bmatrix}1 \\\\ i \\\\ -1 \\\\ -i \\end{bmatrix} = 4$\n",
    "* $\\bar{x}^T_3x_3 = \\begin{bmatrix}1 & -1 & 1 & -1 \\end{bmatrix}\\begin{bmatrix}1 \\\\ -1 \\\\ 1 \\\\ -1 \\end{bmatrix} = 4$\n",
    "* $\\bar{x}^T_4x_4 = \\begin{bmatrix}1 & i & -1 & i \\end{bmatrix}\\begin{bmatrix}1 \\\\ -i \\\\ -1 \\\\ -i \\end{bmatrix} = 4$\n",
    "* $\\bar{x}^T_1x_2 = \\begin{bmatrix}1 & 1 & 1 & 1 \\end{bmatrix}\\begin{bmatrix}1 \\\\ i \\\\ -1 \\\\ -i \\end{bmatrix} = 0$\n",
    "\n",
    "It's easy to check that for $i\\ne j$, $\\bar{x}^T_ix_j = 0$, so $\\bar{Q}^TQ=I$.\n",
    "\n",
    "#### Problem I.5.8\n",
    "\n",
    "$W^TW=\\begin{bmatrix}4 & 0 & 0 & 0 \\\\ 0 & 4 & 0 & 0 \\\\ 0 & 0 & 2 & 0 \\\\ 0 & 0 & 0 & 2\\end{bmatrix}$\n",
    "\n",
    "$W^{-1} = \\begin{bmatrix}\\frac{1}{4} & \\frac{1}{4} & \\frac{1}{4} & \\frac{1}{4} \\\\ \\frac{1}{4} & \\frac{1}{4} & -\\frac{1}{4} & -\\frac{1}{4} \\\\ \\frac{1}{2} & -\\frac{1}{2} & 0 & 0 \\\\ 0 & 0 & \\frac{1}{2} & -\\frac{1}{2}\\end{bmatrix}$\n",
    "\n",
    "The $n=8$ Harr wavelets are: (TODO)\n",
    "\n",
    "$W_8=\\begin{bmatrix}W_4 & 0 \\\\ 0 & W_4\\end{bmatrix}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.6.1\n",
    "\n",
    "$\\lambda_1 + \\lambda_2 = trace(Q) = 2\\cos\\theta$\n",
    "\n",
    "The determinant $|Q|=\\cos^2\\theta+\\sin^2\\theta=1$, whereas $\\lambda_1\\lambda_2 = (\\cos\\theta + i\\sin\\theta)(\\cos\\theta - i\\sin\\theta)=\\cos^2\\theta + \\sin^2\\theta = 1$. \n",
    "\n",
    "$\\bar{x}_1\\cdot x_2 = (1+i)\\cdot (1+i) = 1 + i^2 = 0$\n",
    "\n",
    "$Q^{-1} = \\begin{bmatrix}\\cos\\theta & \\sin\\theta \\\\-\\sin\\theta & \\cos\\theta\\end{bmatrix}$\n",
    "\n",
    "Its eigenvalues are $\\frac{1}{\\lambda_1}$ and $\\frac{1}{\\lambda_2}$\n",
    "\n",
    "#### Problem I.6.2\n",
    "\n",
    "The eigenvalues of $A$ are: $\\lambda_1 = 2$, $\\lambda_2 = -1$. The eigenvectors are $v_1 = \\begin{bmatrix}1 \\\\1 \\end{bmatrix}$, and $v_2 = \\begin{bmatrix}-2 \\\\ 1\\end{bmatrix}$.\n",
    "\n",
    "The eigenvalues of $A^{-1}$ are: $\\lambda_1 = \\frac{1}{2}$, $\\lambda_2 = -1$. The eigenvectors are $v_1 = \\begin{bmatrix}1 \\\\1 \\end{bmatrix}$, and $v_2 = \\begin{bmatrix}-2 \\\\ 1\\end{bmatrix}$\n",
    "\n",
    "$A^{-1}$ has the same eigenvectors as $A$. When $A$ has eigenvalues $\\lambda_1$ and $\\lambda_2$, its inverse has eigenvalues $\\lambda^{-1}_1$, and $\\lambda^{-1}_2$. \n",
    "\n",
    "#### Problem I.6.3\n",
    "\n",
    "Eigenvalues of $A$ are:  $\\lambda_1 = 3$, $\\lambda_2 = 1$.\n",
    "Eigenvalues of $B$ are:  $\\lambda_1 = 1$, $\\lambda_2 = 3$.\n",
    "Eigenvalues of $A+B$ are:  $\\lambda_1 = 5$, $\\lambda_2 = 3$.\n",
    "\n",
    "So eigenvalues $A+B$ are not equal to eigenvalues of $A$ plus eigenvalues of $B$.\n",
    "\n",
    "#### Problem I.6.4\n",
    "\n",
    "* Eigenvalues of $A$ are:  $\\lambda_1 = 1$, $\\lambda_2 = 1$.\n",
    "* Eigenvalues of $B$ are:  $\\lambda_1 = 1$, $\\lambda_2 = 1$.\n",
    "* Eigenvalues of $AB$ are:  $\\lambda_1 = 2+\\sqrt{3}$, $\\lambda_2 = 2-\\sqrt{3}$.\n",
    "* Eigenvalues of $BA$ are:  $\\lambda_1 = 2+\\sqrt{3}$, $\\lambda_2 = 2-\\sqrt{3}$.\n",
    "\n",
    "* (a) The eigenvalues of $AB$ are not equal to eigenvalues of $A$ times eigenvalues of $B$.\n",
    "* (b) The eigenvalues of $AB$ equal to the eigenvalues of $BA$.\n",
    "\n",
    "#### Problem I.6.5\n",
    "\n",
    "* (a) If you know that $x$ is an eigenvector, the way to find $\\lambda$ is to use $Ax=\\lambda x$ and solve for $\\lambda$.\n",
    "* (b) If you know that $\\lambda$ is an eigenvalue, the way to find $x$ is to solve $Ax=\\lambda x$.\n",
    "\n",
    "#### Problem I.6.6\n",
    "\n",
    "* The eigenvalues of $A$ are: $\\lambda_1 = 0.4$, $\\lambda_2 = 1$. The eigenvectors are $v_1=\\begin{bmatrix}1 \\\\ -1\\end{bmatrix}$ and $v_2=\\begin{bmatrix}1 \\\\ 2\\end{bmatrix}$\n",
    "* The eigenvalues of $A^{\\infty}$ are: $\\lambda_1 = 0$, $\\lambda_2 = 1$. The eigenvectors are $v_1=\\begin{bmatrix}1 \\\\ -1\\end{bmatrix}$ and $v_2=\\begin{bmatrix}1 \\\\ 2\\end{bmatrix}$\n",
    "\n",
    "The eigenvalues of $A^{100}$ are  $\\lambda_1 = 0.4^{100} = 1.6e-40$, $\\lambda_2 = 1^{100}=1$.\n",
    "\n",
    "Since $A=X\\Lambda X^{-1}$, $A^{100}=X\\Lambda^{100}X^{-1}$, the $\\Lambda^{100}$ approach the eigenvalues $\\Lambda_{\\infty}$ of $A^{\\infty}$, and $A$ and $A^{\\infty}$ both have the same eigenvectors, $A^{\\infty}=X\\Lambda_{\\infty}X^{-1}$, so $A^{100}$  is close to $A^{\\infty}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.6.7\n",
    "\n",
    "$det A = \\lambda_1\\lambda_2\\dots\\lambda_n$\n",
    "\n",
    "#### Problem I.6.8\n",
    "\n",
    "The quadratic formula gives the eigenvalues $\\lambda_1=\\frac{a+d + \\sqrt{(a+d)^2-4(ad-bc)}}{2}$ and $\\lambda_2=\\frac{a+d - \\sqrt{(a+d)^2-4(ad-bc)}}{2}$. Their sum is $a+d$. \n",
    "\n",
    "If $A$ has $\\lambda_1=3$ and $\\lambda_2=4$, then $det(A-\\lambda I)=(\\lambda - 3)(\\lambda - 4)$\n",
    "\n",
    "#### Problem I.6.9\n",
    "\n",
    "We select different combinations of $a$ and $d$ to have $a+d=9$, then make the determinant of $A$ equal to 20. \n",
    "\n",
    "* $A_1=\\begin{bmatrix}4 & 1 \\\\ 0 & 5\\end{bmatrix}$\n",
    "* $A_2=\\begin{bmatrix}5 & 0 \\\\ 1 & 4\\end{bmatrix}$\n",
    "* $A_3=\\begin{bmatrix}3 & -1 \\\\ 2 & 6\\end{bmatrix}$\n",
    "\n",
    "#### Problem I.6.10\n",
    "\n",
    "Apply $det(A-\\lambda I) = (\\lambda - \\lambda_1)\\dots(\\lambda - \\lambda_n)$\n",
    "\n",
    "* $A=\\begin{bmatrix}0 & 1 \\\\ -28 & 11\\end{bmatrix}$\n",
    "* $C=\\begin{bmatrix}0 & 1 & 0\\\\ 0 & 0& 1\\\\ 6 &-11 &6\\end{bmatrix}$\n",
    "\n",
    "#### Problem I.6.11\n",
    "\n",
    "The eigenvalues of $A$ equal the eigenvalues of $A^T$. This is because the determinant of a matrix $A$ equals to the determinant of its transpose $A^T$, so $det(A-\\lambda I ) = det(A-\\lambda I)^T = det(A^T - \\lambda I)$.\n",
    "\n",
    "Example, for $A=\\begin{bmatrix}0 & 2\\\\1 &1\\end{bmatrix}$\n",
    "\n",
    "The eigenvalues of $A$ are: $\\lambda_1 = 2$, $\\lambda_2 = -1$. The eigenvectors are $v_1 = \\begin{bmatrix}1 \\\\1 \\end{bmatrix}$, and $v_2 = \\begin{bmatrix}-2 \\\\ 1\\end{bmatrix}$.\n",
    "\n",
    "The eigenvalues of $A^T$ are: $\\lambda_1 = 2$, $\\lambda_2 = -1$. The eigenvectors are $v_1 = \\begin{bmatrix}1 \\\\2 \\end{bmatrix}$, and $v_2 = \\begin{bmatrix}1 \\\\ -1\\end{bmatrix}$.\n",
    "\n",
    "#### Problem I.6.12\n",
    "\n",
    "There are algebraic multiplicity of 2, where $\\lambda_{1,2}=0$ and $\\lambda_3=6$. \n",
    "\n",
    "We have eigenvectors from $Ax=\\lambda x$:\n",
    "* When $\\lambda=6$, the eigenvector is $v_1 = \\begin{bmatrix}1 \\\\ 2 \\\\1 \\end{bmatrix}$\n",
    "* When $\\lambda =0$, we have $Ax=0$, so the eigenvectors are in the nullspace of $A$, e.g. $v_2 = \\begin{bmatrix}1 \\\\ -1 \\\\-1 \\end{bmatrix}$ and $v_3 = \\begin{bmatrix}1 \\\\ 1 \\\\-3 \\end{bmatrix}$\n",
    "\n",
    "There are two independent eigenvectors for $\\lambda = 0$, so the geometric multiplicity = 2 as well.\n",
    "\n",
    "#### Problem I.6.13\n",
    "\n",
    "Any vector $x$ is a combination $x = c_1x_1+\\dots + c_nx_n$, then \n",
    "\n",
    "* $Ax = A(c_1x_1+\\dots + c_nx_n) = c_1Ax_1 + \\dots + c_nAx_n = c_1\\lambda_1x_1 + \\dots + c_n \\lambda_n x_n$\n",
    "\n",
    "* $Bx = B(c_1x_1+\\dots + c_nx_n) = c_1Bx_1 + \\dots + c_nBx_n = c_1\\lambda_1x_1 + \\dots + c_n \\lambda_n x_n$\n",
    "\n",
    "So we have $Ax=Bx$ for any $x$, take $x=1$, we have $A=B$.\n",
    "\n",
    "#### Problem I.6.14\n",
    "\n",
    "* (a) Since $Au=0$, so $u$ is a basis for the nullspace. Since $Av=3v$ and $Aw=5w$, also $v$ and $w$ are independent, so both $v$ and $w$ are bases for the column space. \n",
    "\n",
    "* (b) We have $x=\\frac{1}{3}v + \\frac{1}{5}w$, so $Ax = A(\\frac{1}{3}v + \\frac{1}{5}w)=\\frac{1}{3}Av+\\frac{1}{5}Aw=\\frac{1}{3}3v+\\frac{1}{5}5w = v + w$\n",
    "\n",
    "* (c) $Ax=u$ has no solution. If it did then $u$ would be in the column space, which contradicts with $Au=0$, meaning $u$ is in the nullspace.\n",
    "\n",
    "#### Problem I.6.15\n",
    "\n",
    "* (a) $A=\\begin{bmatrix}1 & 2 \\\\0 & 3\\end{bmatrix}$, it has eigenvalues $\\lambda_1 = 1$, and $\\lambda_2 = 3$. \n",
    "It has eigenvectors $v_1=\\begin{bmatrix}1 \\\\0\\end{bmatrix}$, $v_2=\\begin{bmatrix}1 \\\\1\\end{bmatrix}$. \n",
    "So we have $A=\\begin{bmatrix}1 & 1 \\\\0 & 1\\end{bmatrix}\\begin{bmatrix}1 & 0 \\\\0 & 3\\end{bmatrix}\\begin{bmatrix}1 & -1 \\\\0 & 1\\end{bmatrix}$\n",
    "\n",
    "$A=\\begin{bmatrix}1 & 1 \\\\3 & 3\\end{bmatrix}$, it has eigenvalues $\\lambda_1 = 0$, and $\\lambda_2 = 4$. \n",
    "It has eigenvectors $v_1=\\begin{bmatrix}1 \\\\-1\\end{bmatrix}$, $v_2=\\begin{bmatrix}1 \\\\3\\end{bmatrix}$. \n",
    "So we have $A=\\begin{bmatrix}1 & 1 \\\\-1 & 3\\end{bmatrix}\\begin{bmatrix}0 & 0 \\\\0 & 4\\end{bmatrix}\\begin{bmatrix}\\frac{3}{4} & -\\frac{1}{4} \\\\\\frac{1}{4} & \\frac{1}{4}\\end{bmatrix}$\n",
    "\n",
    "* (b) If $A=X\\Lambda X^{-1}$, then $A^3=X\\Lambda^3 X^{-1}$ and $A^{-1}=X\\Lambda^{-1}X^{-1}$\n",
    "\n",
    "#### Problem I.6.16\n",
    "\n",
    "If $A=X\\Lambda X^{-1}$, then $A+2I=X\\Lambda X^{-1} + 2XX^{-1} = X(\\Lambda + 2)X^{-1}$, the eigenvalue matrix is $\\Lambda + 2$. The eigenvector matrix is the same as $A$. \n",
    "\n",
    "#### Problem I.6.17 TODO\n",
    "\n",
    "If the columns of $X$, eigenvectors of $A$, are linearly independent, then \n",
    "\n",
    "* (a) $A$ is invertible: False, we need the columns of $A$ are independent\n",
    "* (b) $A$ is diagonalizable: True (wrong answer: False, we may have Geometric multiplicity < Algebraic multiplicity, so $A$ is not diagonalizable., well we already have $X$)\n",
    "* (c) $X$ is invertible: True\n",
    "* (d) $X$ is diagonalizable: False, we need the eigenvectors of $X$ now (wrong answer: True. for any $x$, we have $Xx=x$, the eigenvalues of $X$ are 1, and the diagonal matrix is $I$ for $X$).\n",
    "\n",
    "#### Problem I.6.18\n",
    "\n",
    "Assume $A=\\begin{bmatrix}a & b \\\\ c & d \\end{bmatrix}$, and take $Ax_1=\\lambda_1x_1$ and $Ax_2=\\lambda_2x_2$ for the two eigenvectors, solve for the $a,b,c,d$, we see that $a=d$, $b=c$, so $A=\\begin{bmatrix}a & b \\\\ b & a \\end{bmatrix}$\n",
    "\n",
    "#### Problem I.6.19 TODO\n",
    "If the eigenvalues of $A$ are 2, 2, 5 then\n",
    "\n",
    "* (a) $A$ is invertible: True since no zero eigenvalues, so nullspace has dimension zero. (wrong answer: False, only if $A$ has full rank.)\n",
    "* (b) $A$ is diagonalizable: False, if $GM < AM$ it's not diagonalizable.\n",
    "* (c) $A$ is not diagonalizable: False, if $GM=AM$, it diagonalizable.\n",
    "\n",
    "#### Problem I.6.20 TODO\n",
    "\n",
    "If the only eigenvectors of $A$ are multiples of $(1,4)$, then A has\n",
    "\n",
    "* (a) no inverse: False. It's possible that a matrix $A$ has full rank but with only one independent eigenvector. It may not have zero eigenvalue. \n",
    "* (b) a repeated eigenvalue: True, an eigenvector is missing which can only happen when there's repeated eigenvalue (wrong answer: False, the $GM=1$, so we have $AM \\ge GM=1$, if we have $AM=1$ as well, there no repeated eigenvalue.)\n",
    "* (c) no diagonalization $X\\Lambda X^{-1}$: True, we don't have $X^{-1}$ available.\n",
    "\n",
    "#### Problem I.6.21\n",
    "\n",
    "$A^k = X\\Lambda^{k}X^{-1}$ approaches the zero matrix as $k\\to \\infty$ if and only if every $\\lambda$ has absolute value less than $1$. The matrix $A_1$ has eigenvalues of $\\lambda_1 = 1$ and $\\lambda_2 = -0.3$, while $A_2$ has eigenvalues of $\\lambda_1 = 0.3$ and $\\lambda_2 = 0.9$ both of which have absolute value less than 1. \n",
    "\n",
    "So $A_2$ will has $A^k_2 \\to 0$. While $A_1$ has an eigenvalue of $1$, it won't go to zero.\n",
    "\n",
    "\n",
    "#### Problem I.6.22\n",
    "$A$ has eigenvalues of $\\lambda_1 = 1$ and $\\lambda_2=3$, with corresponding eigenvectors $v_1=\\begin{bmatrix}1 \\\\1 \\end{bmatrix}$ and $v_2=\\begin{bmatrix}1 \\\\-1 \\end{bmatrix}$. So we have\n",
    "\n",
    "$A=X\\Lambda X^{-1} = \\begin{bmatrix}1 &1 \\\\1 & -1 \\end{bmatrix}\\begin{bmatrix}1 &0 \\\\0 & 3 \\end{bmatrix}\\begin{bmatrix}\\frac{1}{2} &\\frac{1}{2} \\\\\\frac{1}{2} & -\\frac{1}{2} \\end{bmatrix}$\n",
    "\n",
    "$A^{k} = \\begin{bmatrix}1 &1 \\\\1 & -1 \\end{bmatrix}\\begin{bmatrix}1 &0 \\\\0 & 3^k \\end{bmatrix}\\begin{bmatrix}\\frac{1}{2} &\\frac{1}{2} \\\\\\frac{1}{2} & -\\frac{1}{2} \\end{bmatrix} = \\frac{1}{2}\\begin{bmatrix}1+3^k &1-3^k \\\\1-3^k & 1+3^k \\end{bmatrix}$\n",
    "\n",
    "#### Problem I.6.23\n",
    "\n",
    "The $X=\\begin{bmatrix}1 & 1 \\\\-1 & 1 \\end{bmatrix}$, so $X^{-1} = \\begin{bmatrix}\\frac{1}{2} & -\\frac{1}{2} \\\\\\frac{1}{2} & \\frac{1}{2} \\end{bmatrix}$. And $\\Lambda = \\begin{bmatrix}1 & 0 \\\\0 & 9 \\end{bmatrix}$.\n",
    "\n",
    "We have $A=X\\Lambda X^{-1}$ and square root of $A$ is: $R=X\\sqrt{\\Lambda} X^{-1}=\\begin{bmatrix}1 & 1 \\\\-1 & 1 \\end{bmatrix}\\begin{bmatrix}1 & 0 \\\\0 & 3 \\end{bmatrix}\\begin{bmatrix}\\frac{1}{2} & -\\frac{1}{2} \\\\\\frac{1}{2} & \\frac{1}{2} \\end{bmatrix} = \\begin{bmatrix}2 & 1 \\\\1 & 2 \\end{bmatrix}$.\n",
    "\n",
    "Ther is no real matrix square root of $B$ because the first eigenvalue is $-1 < 0$, so no real square root here.\n",
    "\n",
    "#### Problem I.6.24\n",
    "\n",
    "* $AB=X\\Lambda_1 X^{-1} X \\Lambda_2 X^{-1} = X \\Lambda_1\\Lambda_2X^{-1}$\n",
    "* $BA=X\\Lambda_2 X^{-1} X \\Lambda_1 X^{-1} = X \\Lambda_1\\Lambda_2X^{-1}$\n",
    "\n",
    "So $AB=BA$.\n",
    "\n",
    "#### Problem I.6.25\n",
    "\n",
    "Since the eigenvectors in $A^Ty=\\lambda y$ are the columns of that matrix $(X^{-1})^T$, so we have $Y=\\begin{bmatrix}y_1 & y_2 & \\dots & y_n\\end{bmatrix} = (X^{-1})^T$, thus $X^{-1} = \\begin{bmatrix}y^T_1  \\\\ y^T_2 \\\\ \\dots \\\\ y^T_n\\end{bmatrix}$. \n",
    "\n",
    "Note, $x_i$ and $y_i$ are all column vectors here. \n",
    "\n",
    "Thus $A=X\\Lambda X^{-1} = X \\Lambda \\begin{bmatrix}y^T_1  \\\\ y^T_2 \\\\ \\dots \\\\ y^T_n\\end{bmatrix} = \\begin{bmatrix}\\lambda_1x_1 & \\dots \\lambda_n x_n\\end{bmatrix}\\begin{bmatrix}y^T_1  \\\\ y^T_2 \\\\ \\dots \\\\ y^T_n\\end{bmatrix} = \\lambda_1 x_1 y^T_1 + \\dots + \\lambda_n x_n y^T_n$\n",
    "\n",
    "#### Problem I.6.26\n",
    "\n",
    "$A$ and $\\Lambda$ always have the same eigenvalues. But similarity requires a matrix $B$ with $A=B\\Lambda B^{-1}$. Then $B$ is the eigenvector matrix and $A$ must have $n$ independent eigenvectors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.7.1\n",
    "\n",
    "* $y^TSx = y^T\\lambda x = \\lambda y^Tx$\n",
    "* $x^TSy = x^T \\alpha y = \\alpha x^Ty$\n",
    "* Since $y^TSx$ is real number, it equals to its transpose, i.e. $y^TSx=x^TS^Ty=x^TSy$.\n",
    "So we have \n",
    "\n",
    "\\begin{align*}\n",
    "\\lambda y^Tx &= \\alpha x^Ty \\\\\n",
    "\\lambda y^Tx - \\alpha x^Ty &= 0\\\\\n",
    "\\lambda y^T - \\alpha y^Tx &=0\\\\\n",
    "(\\lambda - \\alpha ) y^Tx &= 0\\\\\n",
    "\\end{align*}\n",
    "\n",
    "So if $\\lambda \\ne \\alpha$, we have $y^Tx=0$, i.e. $y$ and $x$ are orthogonal eigenvectors. \n",
    "\n",
    "Note we used the fact that $y^Tx$ is a real number, so we have $y^Tx = (y^Tx)^T = x^Ty$\n",
    "\n",
    "#### Problem I.7.2\n",
    "\n",
    "* $S_4$ has two positive eigenvalues. Its first two leading determinants $D_1$ and $D_2$ are positive. \n",
    "\n",
    "* Let $x=(x_1, x_2)$, so $x^TS_1x = 5x^2_1 + 12x_1x_2 + 7x^2_2= (5x_1+7x_2)(x_1+x_2) \\lt 0 $. To make this less than zero, we let $x=(-4, 3)$\n",
    "\n",
    "#### Problem I.7.3\n",
    "\n",
    "* $S=\\begin{bmatrix}1 & b \\\\ b & 9 \\end{bmatrix}$, when $9-b^2 > 0$, i.e. $-3< b < 3$, $S$ is p.d. \n",
    "\n",
    "$S=LDL^T = \\begin{bmatrix}1 & 0 \\\\ b & 1 \\end{bmatrix}\\begin{bmatrix}1 & 0 \\\\ 0 & 9-b^2 \\end{bmatrix}\\begin{bmatrix}1 & b \\\\ 0 & 1 \\end{bmatrix}$\n",
    "\n",
    "* $S=\\begin{bmatrix}2 & 4 \\\\ 4 & c \\end{bmatrix}$, when $2c-16 > 0$, i.e. $c>8$, $S$ is p.d. \n",
    "\n",
    "$S=LDL^T = \\begin{bmatrix}1 & 0 \\\\ 2 & 1 \\end{bmatrix}\\begin{bmatrix}2 & 0 \\\\ 0 & c-8 \\end{bmatrix}\\begin{bmatrix}1 & 2 \\\\ 0 & 1 \\end{bmatrix}$\n",
    "\n",
    "* $S=\\begin{bmatrix}c & b \\\\ b & c \\end{bmatrix}$, when $c>0$ and $c^2-b^2 > 0$, i.e. $-c< b < c$, $S$ is p.d. \n",
    "\n",
    "$S=LDL^T = \\begin{bmatrix}1 & 0 \\\\ \\frac{b}{c} & 1 \\end{bmatrix}\\begin{bmatrix}c & 0 \\\\ 0 & c-\\frac{b^2}{c} \\end{bmatrix}\\begin{bmatrix}1 & \\frac{b}{c} \\\\ 0 & 1 \\end{bmatrix}$\n",
    "\n",
    "#### Problem I.7.4\n",
    "\n",
    "In the false proof, we have $\\lambda = \\frac{x^TAx}{x^Tx}$. However, it's possible that $x^Tx$ can be zero when $x\\ne 0$, for example, if $x=(i,1)$, then we have $x^x=0$. When this is true, we can't use the formula to solve for $\\lambda$. On the other hand, if we use conjugate of $x$, i.e. $\\bar{x}^Tx$, we only get zero when $x=0$, so for any nonzero $x$, we have $\\bar{x}^Tx > 0$, this is not true for $x^Tx$. \n",
    "\n",
    "#### Problem I.7.5\n",
    "\n",
    "* $S$ has eigenvalues of $\\lambda_1 = 4$ and $\\lambda_2 = 2$, with corresponding eigenvectors $x_1=\\frac{1}{\\sqrt{2}}\\begin{bmatrix}1 \\\\ 1\\end{bmatrix}$ and $x_2=\\frac{1}{\\sqrt{2}}\\begin{bmatrix}1 \\\\ -1\\end{bmatrix}$. So we have \n",
    "\n",
    "$S=Q\\Lambda Q^T = \\lambda_1 x_1 x^T_1 + \\lambda_2 x^2x^T_2 = 2 \\begin{bmatrix}1 & 1 \\\\ 1 & 1\\end{bmatrix} + \\begin{bmatrix}1 & -1 \\\\ -1 & 1\\end{bmatrix}$\n",
    "\n",
    "* $B$ has eigenvalues of $\\lambda_1 = 0$ and $\\lambda_2 = 25$, with corresponding eigenvectors $x_1=\\frac{1}{5}\\begin{bmatrix}-4 \\\\ 3\\end{bmatrix}$ and $x_2=\\frac{1}{5}\\begin{bmatrix}3 \\\\ 4\\end{bmatrix}$. So we have \n",
    "\n",
    "$B=Q\\Lambda Q^T = \\lambda_1 x_1 x^T_1 + \\lambda_2 x^2x^T_2 = \\begin{bmatrix}9 & 12 \\\\ 12 & 16\\end{bmatrix}$\n",
    "\n",
    "\n",
    "#### Problem I.7.6\n",
    "\n",
    "$M$ is antisymmetric and also orthogonal. Since all its eigenvalues are pure imaginary (Why? TODO), and the $trace(M)=0$, we have $\\sum^4_{i=1}\\lambda_i = 0$, so $M$ can only have eigenvalues $i$ or $-i$.\n",
    "\n",
    "#### Problem I.7.7\n",
    "\n",
    "$A=\\begin{bmatrix}i & 1 \\\\ 1 -i \\end{bmatrix}$, the column 1 equals to column 2 multiplies $i$. The matrix only has one eigenvector $x_1=(i, 1)$.\n",
    "\n",
    "#### Problem I.7.8\n",
    "\n",
    "$A$ has eigenvalues $\\lambda_1 = 1$ and $\\lambda_2 = 1+10^{-15}$, with corresponding eigenvectors: $x_1=\\begin{bmatrix}1 \\\\ 0\\end{bmatrix}$, and $x_2 = \\begin{bmatrix}1 \\\\ 1\\end{bmatrix}$. The angle between the eigenvectors are $45^o$.\n",
    "\n",
    "#### Problem I.7.9\n",
    "\n",
    "* (a) $S^2=SS=SS^T=SS^{-1}=I$\n",
    "* (b) Suppose we have $S=Q\\Lambda Q^T$, since $S^T=S^{-1}$, we have $Q\\Lambda Q^T = Q^{-T}\\Lambda^{-1}Q^{-1} = Q\\Lambda^{-1}Q^T$, so we see that $\\Lambda = \\Lambda^{-1}$, the eigenvalues are $+1$ or $-1$.\n",
    "\n",
    "#### Problem I.7.10\n",
    "\n",
    "If $S$ is symmetric, then we have $(A^TSA)^T = A^TS^TA = A^TSA$ so $A^TSA$ is also symmetric. \n",
    "$S$ has a dimension of $m$ by $m$, while $A^TSA$ has a dimension of $n$ by $n$, so their eigenvalues are not equal to each other. \n",
    "\n",
    "#### Problem I.7.11\n",
    "\n",
    "$det(S-\\lambda I) = \\lambda^2 - a \\lambda - c\\lambda + ac - b^2$, when $\\lambda = a$, we have $det(S-aI) = -b^2 < 0$ when $b\\ne 0$.\n",
    "\n",
    "#### Problem I.7.12\n",
    "\n",
    "Let $S=\\begin{bmatrix}a & b\\\\b & c\\end{bmatrix}$, solve for $x^TSx = ax^2_1 + 2bx_1x_2+dx^2_x = 2x_1x_2$, so we see $S=\\begin{bmatrix}0 & 1\\\\1 & 0\\end{bmatrix}$. The eigenvalues are $+1$ and $-1$.\n",
    "\n",
    "#### Problem I.7.13\n",
    "\n",
    "* $A=\\begin{bmatrix}1 & 2\\\\0 & 3\\end{bmatrix}$: $A^TA$ is positive definite since $A$ has independent columns\n",
    "* $A=\\begin{bmatrix}1 & 1\\\\1 & 2\\\\2 & 1\\end{bmatrix}$: : $A^TA$ is positive definite since $A$ has independent columns\n",
    "* $A=\\begin{bmatrix}1 & 1 & 2\\\\1 & 2 & 1\\end{bmatrix}$: : $A^TA$ is not positive definite since column 3 is a combination of column 1 and column 2\n",
    "\n",
    "#### Problem I.7.14\n",
    "\n",
    "Let $S=\\begin{bmatrix}a & d & e \\\\ d & b & f \\\\ e & f & c\\end{bmatrix}$, then we have\n",
    "\n",
    "\\begin{align*}\n",
    "x^TSx &= \\begin{bmatrix}x_1 & x_2 & x_3\\end{bmatrix} \\begin{bmatrix}a & d & e \\\\ d & b & f \\\\ e & f & c\\end{bmatrix}\\begin{bmatrix}x_1 \\\\x_2 \\\\x_3\\end{bmatrix}\\\\\n",
    "&= ax^2_1 + bx^2_2 + cx^2_3  + 2dx_1x_2 + 2ex_1x_3 + 2fx_2x_3 \\\\\n",
    "&= 4(x_1 - x_2 + 2x_3)^2 \\\\\n",
    "& = 4x^2_1 + 4x^2_2 + 16x^2_3 - 8 x_1x_2 + 16x_1x_3 - 16x_2x_3\\\\\n",
    "\\end{align*}\n",
    "\n",
    "Solve for $a,b,c,d,e,f$, we have $S=\\begin{bmatrix}4 & -4 & 8 \\\\ -4 & 4 & -8 \\\\ 8 & -8 & 16\\end{bmatrix}$\n",
    "\n",
    "This matrix has pivots of $4, 0, 0$, it has rank of $1$, it's determinant is zero. \n",
    "The eigenvalues are: $0, 0, 24$\n",
    "\n",
    "#### Problem I.7.15\n",
    "\n",
    "* $D_1$ = 2\n",
    "* $D_2$ = 6\n",
    "* $D_3$ = 30\n",
    "\n",
    "So the first pivot is 2, the second pivot is $\\frac{D_2}{D_1} = 3$ and the third pivot is $\\frac{D_3}{D_2} = 5$. This agrees with pivots computed from elimination.\n",
    "\n",
    "#### Problem I.7.16\n",
    "\n",
    "Using determinants we see that :\n",
    "* $S$: $c>0$, $c^2 -1 > 0$, and $c^3-3C+2>0$, we conclude $c>1$\n",
    "* $T$: $d-4>0$ and $5d+24+24 - 9d - 16 - 20 > 0$, i.e. $12-4d>0$, we conclude that no $d$ that can make $T$ positive definite.\n",
    "\n",
    "#### Problem I.7.17\n",
    "\n",
    "To have a negative eigenvalue, it means the matrix is not positive definite, so for matrix $S=\\begin{bmatrix}a & b \\\\ b & c \\end{bmatrix}$, we need $ac-b^2 > 0$, so $b > (ac)^{\\frac{1}{2}}$, on the other hand, we need $b < \\frac{a+c}{2}$. Pick $a=1$ and $c=4$, we see that $b=2.4$ satisfies the requirement. \n",
    "\n",
    "Solve for eigenvalues we have $\\lambda_1 = \\frac{25+\\sqrt{801}}{10} $, $\\lambda_2=\\frac{25-\\sqrt{801}}{10} < 0$.\n",
    "\n",
    "#### Problem I.7.18\n",
    "\n",
    "We have $x^TSx = 4x^2_1 + 5x^2_3 + 2x_1x_2 + 2x_1x_3 + 4x_2x_3$, it's not positive when $(x_1,x_2,x_3) = (1, -3, 0)$\n",
    "\n",
    "#### Problem I.7.19\n",
    "\n",
    "If a diagonal entry $s_{jj}$ of a symmetric matrix is smaller than all the $\\lambda$'s, then $S-s_{jj}I$ would have positive eigenvalues ($S-s{jj}I = Q\\Lambda Q^T - s_{jj}I = Q(\\Lambda - s_{jj})Q^T$) and would be positive definite. But $S-s_{jj}I$ has a $0$ on the main diagonal, impossible by Problem 18. \n",
    "\n",
    "#### Problem I.7.20\n",
    "\n",
    "* $S=\\begin{bmatrix}5 & 4 \\\\ 4 & 5\\end{bmatrix} = \\frac{1}{2}\\begin{bmatrix}1 & 1 \\\\ -1 & 1\\end{bmatrix}\\begin{bmatrix}1 & 0 \\\\ 0 & 9\\end{bmatrix}\\begin{bmatrix}1 & -1 \\\\ 1 & 1\\end{bmatrix} $, so $A=\\frac{1}{2}\\begin{bmatrix}1 & 1 \\\\ -1 & 1\\end{bmatrix}\\begin{bmatrix}1 & 0 \\\\ 0 & 3\\end{bmatrix}\\begin{bmatrix}1 & -1 \\\\ 1 & 1\\end{bmatrix} $\n",
    "\n",
    "* $S=\\begin{bmatrix}10 & 6 \\\\ 6 & 10\\end{bmatrix} = \\frac{1}{2}\\begin{bmatrix}1 & 1 \\\\ -1 & 1\\end{bmatrix}\\begin{bmatrix}4 & 0 \\\\ 0 & 16\\end{bmatrix}\\begin{bmatrix}1 & -1 \\\\ 1 & 1\\end{bmatrix} $, so $A=\\frac{1}{2}\\begin{bmatrix}1 & 1 \\\\ -1 & 1\\end{bmatrix}\\begin{bmatrix}2 & 0 \\\\ 0 & 4\\end{bmatrix}\\begin{bmatrix}1 & -1 \\\\ 1 & 1\\end{bmatrix} $\n",
    "\n",
    "#### Problem I.7.21 \n",
    "\n",
    "The corresponding matrix $S=\\begin{bmatrix}1 & \\frac{1}{2} \\\\ \\frac{1}{2} & 1\\end{bmatrix}$, the eigenvalues are $\\frac{1}{2}, \\frac{3}{2}$. So the half-lengths of its axes are : $\\sqrt{2}, \\sqrt{\\frac{2}{3}}$\n",
    "\n",
    "#### Problem I.7.22\n",
    "\n",
    "* $S=\\begin{bmatrix}9 & 0 & 0 \\\\ 0 & 1 & 2 \\\\ 0 & 2 & 8 \\end{bmatrix}$ has $L=\\begin{bmatrix}1 & 0 & 0 \\\\ 0 & 1 & 0 \\\\ 0 & 2 & 1 \\end{bmatrix}$ with $D=\\begin{bmatrix}9 & 0 & 0 \\\\ 0 & 1 & 0 \\\\ 0 & 0 & 4 \\end{bmatrix}$, so $A=\\begin{bmatrix}3 & 0 & 0 \\\\ 0 & 1 & 2 \\\\ 0 & 0 & 2 \\end{bmatrix}$\n",
    "\n",
    "* $S=\\begin{bmatrix}1 & 1 & 1 \\\\ 1 & 2 & 2 \\\\ 1 & 2 & 7 \\end{bmatrix}$ has $L=\\begin{bmatrix}1 & 0 & 0 \\\\ 1 & 1 & 0 \\\\ 1 & 1 & 1 \\end{bmatrix}$ with $D=\\begin{bmatrix}1 & 0 & 0 \\\\ 0 & 1 & 0 \\\\ 0 & 0 & 4 \\end{bmatrix}$, so $A=\\begin{bmatrix}1 & 1 & 1 \\\\ 0 & 1 & 1 \\\\ 0 & 0 & 2 \\end{bmatrix}$\n",
    "\n",
    "#### Problem I.7.23\n",
    "\n",
    "Since $A$ has independent columns, given a $x \\ne 0$, we have $y=Ax \\ne 0$, also since $C$ is positive definite, so $y^TCy=x^TA^TCAx > 0$, so $S=A^TCA$ is positive definite.\n",
    "\n",
    "#### Problem I.7.24\n",
    "\n",
    "* For $F_1$, we have $\\frac{\\partial{F_1}}{\\partial x}= x^3 + 2xy$, $\\frac{\\partial{F_1}}{\\partial y}= x^2+2y$, and $H_1 = \\begin{bmatrix}3x^2+2y & 2x \\\\ 2x & 2 \\end{bmatrix}$\n",
    "\n",
    "Since $F_1=\\frac{1}{4}x^4+x^2y + y^2 = (\\frac{1}{2}x^2 + y)^2 \\ge 0$, let the derivatives equal to 0, we have $(x,y) \\;\\text{satisfy}\\;x^2+2y=0$. it achieves minimum of $0$. \n",
    "At the minimum point we have $H_1 = \\begin{bmatrix}2x^2 & 2x \\\\ 2x & 2 \\end{bmatrix}$. One can notice that the determinants of $H_1$ are all larger than or equal to 0.\n",
    "\n",
    "$H_1$ is semi-positive definite.\n",
    "\n",
    "* For $F_2$, we have $\\frac{\\partial{F_2}}{\\partial x}= 3x^2 + y - 1$, $\\frac{\\partial{F_2}}{\\partial y}= x$, and $H_2 = \\begin{bmatrix}6x & 1 \\\\ 1 & 0 \\end{bmatrix}$.\n",
    "\n",
    "$H_2$ always has determinant less than 0 regardless of the $(x,y)$, so it's not positive definite. let the first derivatives to zero, we see $(x,y)=(0, 1)$ is the saddle point of $F_2$.\n",
    "\n",
    "#### Problem I.7.25\n",
    "\n",
    "The corresponding matrix $S=\\begin{bmatrix}4 & 6\\\\6 & c\\end{bmatrix}$.\n",
    "To have a bowl, we want the matrix $S$ to be positive definite, i.e. $4c-36 > 0$, $c>9$. \n",
    "To have a saddle point, we want to have both positive and negative eigenvalues, $c<9$.\n",
    "\n",
    "When $c=9$, we have $z=4x^2+12xy+9y^2 = (2x+3y)^2$. We have lines correspond to each fixed $z$. So the graph is a 'trough' which stays zero along the line $2x+3y=0$.\n",
    "\n",
    "#### Problem I.7.26\n",
    "* (a) The determinant of $S$ is the product of eigenvalues: 10\n",
    "* (b) The eigenvalues of $S$: $2,5$\n",
    "* (c) The eigenvectors of $S$: $x_1=\\begin{bmatrix}\\cos\\theta \\\\ \\sin\\theta\\end{bmatrix}$ and $x_2=\\begin{bmatrix}-\\sin\\theta \\\\ \\cos\\theta\\end{bmatrix}$\n",
    "* (d) A reason why $S$ is symmetric positive definite: This is because $S$ can be expressed as $A^TA$ where $A$ has independent columns. \n",
    "\n",
    "#### Problem I.7.27 \n",
    "\n",
    "Since the $det(S) = 0$ regardless of the values of $a$ and $c$, so the matrix is never positive definite. For $a\\ge 0$ and $c\\ge 0$ the matrix is positive semidefinite.\n",
    "\n",
    "#### Problem I.7.28\n",
    "\n",
    "* (a) $\\lambda_1 I - S = \\lambda_1I - Q\\Lambda Q^T = Q(\\lambda_1I - \\Lambda)Q^T$, The eigenvalues are $0, \\lambda_1 - \\lambda_2, \\dots, \\lambda_1 - \\lambda_n$, all $\\ge 0$, so it's positive semidefinite.\n",
    "\n",
    "* (b) For any $x$, we have $\\lambda_1x^Tx - x^TSx = x^T(\\lambda_1I - S)x \\ge 0$ by the property of a positive semidefinite matrix $\\lambda_1I - S$.\n",
    "\n",
    "* (c) Since $x^Tx > 0$ for nonzero $x$, so we conclude that the maximum value of $\\frac{x^TSx}{x^Tx}$ is $\\lambda_1$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.8.1\n",
    "\n",
    "* $x^Tx=(c_1v_1 + \\dots + c_nv_n)^T(c_1v_1 + \\dots + c_nv_n) = (c_1v^T_1 + \\dots + c_nv^T_n)(c_1v_1 + \\dots + c_nv_n) = \\sum^n_{i=1}\\sum^n_{j=1} c_iv^T_i c_jv_j = \\sum^n_{i=1} c_ic_iv^T_iv_i = c^2_1 + \\dots + c^2_n$\n",
    "\n",
    "* $x^TSx = x^TS(c_1v_1 + \\dots + c_nv_n) = x^T(c_1Sv_1 + \\dots + c_nSv_n) = x^T(c_1\\lambda_1v_1 + \\dots + c_n\\lambda_nv_n) = (c_1v_1 + \\dots + c_nv_n)^T(c_1\\lambda_1v_1 + \\dots + c_n\\lambda_nv_n) = \\lambda_1c^2_1 + \\dots + \\lambda_nc^2_n$\n",
    "\n",
    "If we take the symmetric matrix as $I$, which has eigenvalues of $1$, we can recover the first equation from the second one.\n",
    "\n",
    "#### Problem I.8.2\n",
    "\n",
    "The Rayleigh quotient $R(x) = \\frac{x^TSx}{x^Tx} = \\frac{\\lambda_1c^2_1 + \\dots + \\lambda_nc^2_n}{c^2_1 + \\dots + c^2_n} = \\frac{\\lambda_1\\left(c^2_1 + \\dots + c^2_n\\right) + \\left((\\lambda_2-\\lambda_1)c^2_2+\\dots + (\\lambda_n-\\lambda_1)c^2_n\\right)}{c^2_1 + \\dots + c^2_n} = \\lambda_1 + \\frac{(\\lambda_2-\\lambda_1)c^2_2+\\dots + (\\lambda_n-\\lambda_1)c^2_n}{c^2_1 + \\dots + c^2_n}$\n",
    "\n",
    "If $\\lambda_1 \\ge \\lambda_i$ for $i=2,3,\\dots, n$, then we see that the second term is less than or equal to zero. The maximum value is $\\lambda_1$ and it's achieved when $c_2=\\dots=c_n=0$ and $c_1=1$. (Actually, $c_1$ doesn't have to be $1$ here, any nonzero constant is fine)\n",
    "\n",
    "#### Problem I.8.3\n",
    "\n",
    "When $x^Tv_1=0$, it means $(c_1v_1 + \\dots + c_nv_n)^Tv_1 = c_1 = 0$. Under such condition, we have\n",
    "\n",
    "$R(x) =\\frac{\\lambda_2c^2_2 + \\dots + \\lambda_nc^2_n}{c^2_2 + \\dots + c^2_n}$, we see that $R(x)$ is maximized when $c_2=1$ and $c_1=c_3=\\dots=c_n=0$, and the maximal value is $\\lambda_2$.\n",
    "\n",
    "#### Problem I.8.4\n",
    "\n",
    "Following Problem 3, the maximum problem solved by $x=v_3$ is $R(x) = \\frac{\\lambda_3c^2_3 + \\dots + \\lambda_nc^2_n}{c^2_3 + \\dots + c^2_n}$, it's subject to two conditions on $x$: $x^Tv_1 = x^Tv_2 = 0$ or $c_1=c_2=0$.\n",
    "\n",
    "#### Problem I.8.5\n",
    "\n",
    "Suppose we have $A=U\\Sigma V^T$ where $U,V$ are square orthogonal matrices, $V^T=V^{-1}$ and $U^T=U^{-1}$, so we have $A^T=V\\Sigma U^T$, the matrix $A^T$ has the same singular values as $A$ but with right singular matrix $U$ and left singular matrix $V$ instead. So we have $||A||= ||A^T||$ for all matrices because $||A|| = ||U\\Sigma V^T|| = ||\\Sigma||$\n",
    "\n",
    "This is not true that $||Ax||=||A^Tx||$ for all vectors, because $||Ax||^2 = x^TA^TAx = x^TV\\Sigma^2V^Tx$ while $||A^Tx||^2 = x^TAA^Tx = x^TU\\Sigma^2U^Tx$.\n",
    "\n",
    "#### Problem I.8.6\n",
    "\n",
    "Here $A$ is the transpose of the original matrix $A$ in example 1, if $A=U\\Sigma V^T$, then we have $A^T=V\\Sigma U^T$, so the singular values of $A$ are the same as in the example 1, i.e. $\\Sigma = \\begin{bmatrix}\\sqrt{45} & 0 \\\\ 0 & \\sqrt{5}\\end{bmatrix}$, while the left singular vectors are $\\frac{1}{\\sqrt{2}}\\begin{bmatrix}1 & -1 \\\\ 1 & 1\\end{bmatrix}$ and the right singular vectors are $\\frac{1}{\\sqrt{10}}\\begin{bmatrix}1 & -3 \\\\ 3 & 1\\end{bmatrix}$\n",
    "\n",
    "#### Problem I.8.7\n",
    "\n",
    "$A-\\sigma_1u_1v^T_1  = U\\Sigma V^T - \\begin{bmatrix}u_1 & u_2 & \\dots & u_m\\end{bmatrix}\\begin{bmatrix}\\sigma_1 & 0 & \\dots & 0\\\\ 0 & 0 & \\dots & 0\\\\ \\dots & \\dots & \\dots & \\dots \\\\ 0 & 0 & \\dots & 0\\end{bmatrix}\\begin{bmatrix}v^T_1 \\\\ v^T_2 \\\\ \\dots \\\\ v^T_n\\end{bmatrix} = U\\Sigma V^T -U\\begin{bmatrix}\\sigma_1 & 0 & \\dots & 0\\\\ 0 & 0 & \\dots & 0\\\\ \\dots & \\dots & \\dots & \\dots \\\\ 0 & 0 & \\dots & 0\\end{bmatrix}V^T = U\\begin{bmatrix}0 & 0 & \\dots & 0\\\\ 0 & \\sigma_2 & \\dots & 0\\\\ \\dots & \\dots & \\sigma_r & \\dots \\\\ 0 & 0 & \\dots & 0\\end{bmatrix}V^T$\n",
    "\n",
    "So the norm of $||A-\\sigma_1u_1v^T_1|| = \\sqrt{\\sum^r_{i=2}\\sigma^2_i}$\n",
    "This can also be seen by : $A-\\sigma_1u_1v^T_1  = \\sigma_2u_2v^T_2 + \\dots + \\sigma_ru_rv^T_r$.\n",
    "\n",
    "The rank of the reduced matrix is: $r-1$.\n",
    "\n",
    "#### Problem I.8.8\n",
    "\n",
    "For $A=\\begin{bmatrix}0 & 2 & 0 \\\\ 0 & 0  & 3 \\\\ 0 & 0  &0\\end{bmatrix}$, we have $A^TA =\\begin{bmatrix}0 & 0 & 0 \\\\ 0 & 4  & 0\\\\ 0 & 0  &9\\end{bmatrix} $ and $AA^T = \\begin{bmatrix}4 & 0 & 0 \\\\ 0 & 9  & 0\\\\ 0 & 0  &0\\end{bmatrix}$. \n",
    "\n",
    "We compute the eigen values as $\\lambda_1 = 0, \\lambda_2 = 4, \\lambda_3 = 9$, so we have singular values as $\\sigma_1 = 0, \\sigma_2 = 2, \\sigma_3=3$.\n",
    "\n",
    "Let's now find the eigenvectors of $A^TA$ with eigenvalues $4,9$:\n",
    "$x_1 = \\begin{bmatrix}0 \\\\ 1\\\\ 0\\end{bmatrix}$ and $x_2 = \\begin{bmatrix}0 \\\\ 0\\\\ 1\\end{bmatrix}$\n",
    "\n",
    "Choose $v_1 = x_2 = \\begin{bmatrix}0 \\\\ 0\\\\ 1\\end{bmatrix}$ and $\\sigma_1 = \\sqrt{\\lambda_2} = 3$, we have $u_1 = \\frac{Av_1}{\\sigma_1} = \\begin{bmatrix}0 \\\\ 1\\\\ 0\\end{bmatrix}$.\n",
    "\n",
    "Choose $v_2 = x_1 = \\begin{bmatrix}0 \\\\ 1\\\\ 0\\end{bmatrix}$ and $\\sigma_1 = \\sqrt{\\lambda_1} = 2$, we have $u_2 = \\frac{Av_2}{\\sigma_2} = \\begin{bmatrix}1 \\\\ 0\\\\ 0\\end{bmatrix}$.\n",
    "\n",
    "So we have right singular matrix: $V=\\begin{bmatrix}0 & 0 & 1\\\\ 0 & 1 & 0 \\\\ 1 & 0 &0 \\\\\\end{bmatrix}$, \n",
    "and left singular matrix: $U=\\begin{bmatrix}0 & 1 & 0\\\\ 1 & 0 & 0 \\\\ 0 & 0 &1 \\\\\\end{bmatrix}$\n",
    "note we picked the third singular vector to be perpendicular to other two singular vectors.\n",
    "\n",
    "And we have $\\Sigma=\\begin{bmatrix}3 & 0 & 0\\\\ 0 & 2 & 0 \\\\ 0 & 0 &0 \\\\\\end{bmatrix}$\n",
    "\n",
    "It can be shown that $A=U\\Sigma V^T$\n",
    "\n",
    "#### Problem I.8.9\n",
    "\n",
    "$L=\\frac{1}{2}x^TSx + \\lambda(x^Tx-1)$,  we have \n",
    "\n",
    "\\begin{align*}\n",
    "\\frac{\\partial{L}}{\\partial{x_i}} & = (Sx)_i + 2\\lambda (x)_i\\\\\n",
    "\\end{align*}\n",
    "\n",
    "for $i=1,2,\\dots,n$.\n",
    "\n",
    "So $\\frac{\\partial{L}}{\\partial{x}} = Sx + 2\\lambda x$, let this equal to 0, we see that $Sx = -2\\lambda x $, so $-2\\lambda$ is the eigenvalue of $S$, and $x$ is an eigenvector of $S$. \n",
    "\n",
    "So when $x$ is the eigenvector of $S$ with eigenvalue $\\lambda$. $R(x)=\\frac{x^TSx}{x^Tx} = \\frac{x^T\\lambda x}{x^Tx} = \\lambda$. This is maximum when $\\lambda = \\lambda_1$.\n",
    "\n",
    "#### Problem I.8.10\n",
    "\n",
    "Remove first the $N-n$ columns of $A$, the new matrix has $||C|| \\le ||A||$, this is because the Frobenius matrix norm is a $l^2$ norm of a $mn$ vector, the less the number of elements in the matrix, the less of its norm. \n",
    "\n",
    "Then transpose $C$: no change in norm. Finally remove $M-m$ columns of $C^T$ to product $B^T$ with no increase in norm. \n",
    "Altogether $||B|| = ||B^T|| \\le ||C^T|| = ||C|| \\le ||A||$.\n",
    "\n",
    "#### Problem I.8.11\n",
    "\n",
    "The trace of $S$ is $0$. By equation $(21)$, its eigenvalues are in pairs of $\\sigma_k$ and $-\\sigma_k$, so the sum of eigenvalues are also $0$. \n",
    "\n",
    "If $A$ is a square diagonal matrix with entries $1,2,\\dots,n$, then its eigenvalues are $1,2,\\dots,n$. Since its real, symmetric matrix, Both its right and left singular vectors are $x_i = \\begin{bmatrix}0 \\\\ \\dots \\\\ 0 \\\\ 1 \\\\ \\dots \\\\ 0\\end{bmatrix}$, where $1$ appears in the $i$th position for the $i$th eigenvalue. \n",
    "\n",
    "The $2n$ eigenvalues of $S$ are: $1,2,\\dots,n,-1,-2,\\dots,-n$. \n",
    "\n",
    "The $2n$ eigenvectors of $S$ are: $s_i = \\begin{bmatrix}0 \\\\ \\dots \\\\ 0 \\\\ 1 \\\\ \\dots \\\\ 0\\\\0 \\\\ \\dots \\\\ 0 \\\\ 1 \\\\ \\dots \\\\ 0\\end{bmatrix}$ and $s_j = \\begin{bmatrix}0 \\\\ \\dots \\\\ 0 \\\\ -1 \\\\ \\dots \\\\ 0\\\\0 \\\\ \\dots \\\\ 0 \\\\ 1 \\\\ \\dots \\\\ 0\\end{bmatrix}$\n",
    "\n",
    "Where $i,j=1,2,\\dots,n$\n",
    "\n",
    "#### Problem I.8.12\n",
    "\n",
    "$A^TA=\\begin{bmatrix}5 & 10 \\\\ 10 & 20\\end{bmatrix}$, it has eigenvalues of $\\lambda_1 = 0, \\lambda_2 = 25$. The corresponding eigenvectors (which are also right singular vectors) are $v_1 = \\frac{1}{\\sqrt{5}}\\begin{bmatrix}2 \\\\ -1\\end{bmatrix}$ and $v_2 = \\frac{1}{\\sqrt{5}}\\begin{bmatrix}1 \\\\ 2\\end{bmatrix}$. \n",
    "\n",
    "So $A^TA=Q\\Lambda Q^T = \\frac{1}{5}\\begin{bmatrix}2 & 1 \\\\ -1 & 2\\end{bmatrix}\\begin{bmatrix}0 & 0 \\\\ 0 & 25\\end{bmatrix}\\begin{bmatrix}2 & -1 \\\\ 1 & 2\\end{bmatrix} = \\begin{bmatrix}2 & 1 \\\\ -1 & 2\\end{bmatrix}\\begin{bmatrix}0 & 0 \\\\ 0 & 5\\end{bmatrix}\\begin{bmatrix}2 & -1 \\\\ 1 & 2\\end{bmatrix}$\n",
    "\n",
    "So we can compute the left singular vectors: $u_i = \\frac{Av_i}{\\sigma_i}$. \n",
    "Note we only need to compute where eigenvalue is larger than 0, i.e. $\\sigma_2 = 5$.\n",
    "$u_2 = \\frac{1}{\\sqrt{5}}\\begin{bmatrix}2 \\\\ 1\\end{bmatrix}$\n",
    "Select $u_1$ to be orthogonal to $u_2$, we have $u_1 = \\frac{1}{\\sqrt{5}}\\begin{bmatrix}-1 \\\\ 2\\end{bmatrix}$\n",
    "\n",
    "So we have $U=\\frac{1}{\\sqrt{5}}\\begin{bmatrix}2 & -1 \\\\ 1 & 2\\end{bmatrix}$ and $\\Sigma = \\begin{bmatrix}5 & 0 \\\\0 & 0\\end{bmatrix}$, $V=\\frac{1}{\\sqrt{5}}\\begin{bmatrix}1 & 2 \\\\ 2 & -1\\end{bmatrix}$, then\n",
    "\n",
    "$A=U\\Sigma V^T = \\frac{1}{5}\\begin{bmatrix}2 & -1 \\\\ 1 & 2\\end{bmatrix}\\begin{bmatrix}5 & 0 \\\\0 & 0\\end{bmatrix}\\begin{bmatrix}1 & 2 \\\\ 2 & -1\\end{bmatrix}$\n",
    "\n",
    "#### Problem I.8.13\n",
    "\n",
    "Step 3 multiplied Step 2 on the left by $U^T$ and on the right by $V$, Then the matrix $U^TAV$ commutes with the diagonal matrix $\\Lambda$ in step 3. \n",
    "\n",
    "The limitation on the proof: It needs the eigenvalues of $A^TA$ to be non repeated.\n",
    "\n",
    "#### Problem I.8.14\n",
    "\n",
    "When we move to $A=U\\Sigma V^T=2 \\text{by} 3$ with six entries. The number of $r$, i.e. the $\\sigma$'s are the rank of matrix $A$, which is the minimum of $m,n$. So there are 2 $\\sigma$'s for the 2 by 3 matrix. To recover $A$, that leaves 3 angles for the 3 by 3 orthogonal matrix $V$. \n",
    "\n",
    "The row space of $A$ is a plane in $R^3$. It takes 2 angles for the position of that plane. It takes 1 angle in the plane to find $v_1$ and $v_2$ since they are perpendicular to each other. A total of 3 angles for $V$.\n",
    "\n",
    "#### Problem I.8.15\n",
    "\n",
    "Every 3 by 3 matrix has 9 entries. So $U\\Sigma V^T$ must have 9 parameters. There are 3 parameters in $\\Sigma$. Each of $U$ and $V$ shall have 3 parameters. \n",
    "\n",
    "For 4 by 4 matrix, there are 4 parameters for $\\Sigma$, since $U$, $V$ have the same shape, they have $(16-4)\\div 2 = 6$ parameters each.\n",
    "\n",
    "There are 3 parameters to describe a rotation in a 4-dimensional space. (TODO)\n",
    "\n",
    "#### Problem I.8.16\n",
    "\n",
    "4 numbers will give the direction of a unit vector $v_1$ in $R^5$. Then the direction of an orthogonal unit vector $v_2$ takes 3 numbers. For $v_3$ it takes 2, and $v_4$ takes 1, and $v_5$ takes 0. Total: 10 numbers. \n",
    "\n",
    "#### Problem I.8.17\n",
    "\n",
    "If $v$ is an eigenvector of $A^TA$ with $\\lambda \\ne 0$, then $\\frac{Av}{\\sqrt{\\lambda}}$ is an eigenvector of $AA^T$.\n",
    "\n",
    "#### Problem I.8.18\n",
    "\n",
    "If $A=U\\Sigma V^T$ is square and invertible, then $A^{-1} = V\\Sigma^{-1}U^T$. $A^TA=V\\Sigma^2V^T$ Its singular values are squares of $\\Sigma$.\n",
    "\n",
    "#### Problem I.8.19\n",
    "\n",
    "If $S=S^T$ has orthogonal columns $u_1,u_2,u_3$ in $R^3$ of lengths 2,3,4.\n",
    "Then $S=\\begin{bmatrix}u_1 & u_2 & u_3 \\end{bmatrix}$. Then $U=\\begin{bmatrix}\\frac{u_1}{2} & \\frac{u_2}{3} & \\frac{u_3}{4} \\end{bmatrix}$ is an orthogonal matrix whose columns are orthognormal. We can easily see that \n",
    "$S=U\\begin{bmatrix}2 & 0 & 0 \\\\ 0 & 3 & 0 \\\\ 0 & 0 & 4\\end{bmatrix}I$, so $U$ is the left singular matrix and $I$ is the right singular matrix.\n",
    "\n",
    "#### Problem I.8.20\n",
    "\n",
    "$A=\\begin{bmatrix}-2 & -6 \\\\ 6 & 2 \\end{bmatrix}$, it has eigenvalues of $\\lambda_1 = 4\\sqrt{2}i, \\lambda_2 = -4\\sqrt{2}i$, which are complex numbers. The eigenvectors are $x_1 = \\begin{bmatrix}\\frac{2\\sqrt{2}i-1}{3} \\\\ 1 \\end{bmatrix}$ and $x_2 = \\begin{bmatrix}\\frac{-2\\sqrt{2}i-1}{3} \\\\ 1 \\end{bmatrix}$. \n",
    "We have $X=\\begin{bmatrix}\\frac{2\\sqrt{2}i-1}{3} & \\frac{-2\\sqrt{2}i-1}{3}\\\\ 1 & 1 \\end{bmatrix}$\n",
    "\n",
    "So $A^k =X\\Lambda^k X^{-1} = X\\begin{bmatrix}(4\\sqrt{2}i)^k & 0 \\\\0 & (-4\\sqrt{2}i)^k \\end{bmatrix} X^{-1}$.\n",
    "\n",
    "So $A^k$ will have complex singular values and singular vectors.\n",
    "\n",
    "$A^TA = \\begin{bmatrix}40 & 24 \\\\ 24 & 40\\end{bmatrix}$, this is a real symmetric matrix, it is also positive definite. So it has positive eigenvalues and real eigenvectors. Clearly, its singular values are real and positive, its singular vectors are real. This won't satisfy (a) (b) with $A^k$ which has complex values.\n",
    "\n",
    "\n",
    "\n",
    "#### Problem I.8.21\n",
    "\n",
    "$AA^TA = (U\\Sigma V^T)(U\\Sigma V^T)^T(U\\Sigma V^T) = (U\\Sigma V^T)(V\\Sigma U^T)(U\\Sigma V^T) = U\\Sigma^3V^T$, so the singular values are $\\sigma^3_1, \\dots, \\sigma^3_r$.\n",
    "\n",
    "#### Problem I.8.22\n",
    "\n",
    "$A=U_r\\Sigma_rV^T_r$, for a given $v_j$, we have\n",
    "\n",
    "$Av_j=U_r\\Sigma_rV^T_rv_j = U_r\\Sigma_r\\begin{bmatrix}0 \\\\ 0 \\\\ \\dots \\\\ 1 \\\\ \\dots \\\\ 0\\end{bmatrix} = U_r\\begin{bmatrix}0 & \\dots & 0 & \\dots & 0 \\\\ 0 & \\dots & \\sigma_j & \\dots & 0 \\\\ 0 & \\dots & 0 & \\dots & 0\\end{bmatrix} = \\sigma_j u_j$, which proves that $A$ satisfies equation (1). \n",
    "\n",
    "\n",
    "#### Problem I.8.23\n",
    " The $r$ orthonormal vectors $u_1$ to $u_r$ have $(m-1)+(m-2) + \\dots + (m-r) = mr - \\frac{r(r+1)}{2}$ parameters because it takes $m-1$ parameters to specify $u_1$ direction with length 1, and $m-2$ directions to specify $u_2$ direction which is perpendicular to $u_1$, ..., and $m-r$ parameters to specify $u_r$ direction which is orthogonal to all previous directions. It is also because there are $r$ constraints that the length of each $u_i$ need to be 1, and $r \\choose 2$ constraints that the inner product of $u_i$ and $u_j$ are zero. So in total we have $mr - r - \\frac{r(r-1)}{2} = mr - \\frac{r(r+1)}{2}$. And $v_1$ to $v_r$ have $(n-1)+(n-2)+\\dots + (n-r) = nr - \\frac{r(r+1)}{2}$ parameters , adding up with the $r$ parameters in $\\Sigma$, we have total $r(m+n-r)$ parameters.\n",
    " \n",
    " We can also consider $A=CR=(m\\times r)(r \\times n)$. The matrix $R$ contains an $r$ by $r$ identity matrix, removing $r^2$ parameters from $rm+rn$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.9.1\n",
    "\n",
    "The singular values of $A-A_k$ are: $\\lambda_{k+1}, \\dots, \\lambda_r$\n",
    "\n",
    "#### Problem I.9.2\n",
    "\n",
    "* $A=\\begin{bmatrix}3 & 0 & 0\\\\0 & 0 & 0 \\\\ 0 & 0 & 0\\end{bmatrix}$\n",
    "\n",
    "* The eigenvalues of $A^TA$ are $\\lambda_1 = 3, \\lambda_2=2$. We have $A=\\begin{bmatrix}0 & 3\\\\2 & 0 \\end{bmatrix} = U\\Sigma V^T = \\begin{bmatrix}1 & 0\\\\0 & 1\\end{bmatrix}\\begin{bmatrix}3 & 0\\\\0 & 2 \\end{bmatrix}\\begin{bmatrix}0 & 1\\\\1 & 0 \\end{bmatrix}$, so the rank-1 matrix approximation is: $3\\begin{bmatrix}1 \\\\0 \\end{bmatrix}\\begin{bmatrix}0 & 1\\end{bmatrix}=\\begin{bmatrix}0 & 3\\\\0 & 0\\end{bmatrix}$\n",
    "\n",
    "* The eigenvalues of $A^TA$ are $\\lambda_1 = 3, \\lambda_2=1$. We have $A=\\begin{bmatrix}2 & 1\\\\1 & 2 \\end{bmatrix} = U\\Sigma V^T = \\frac{1}{2}\\begin{bmatrix}1 & 1\\\\1 & -1 \\end{bmatrix}\\begin{bmatrix}3 & 0\\\\0 & 1 \\end{bmatrix}\\begin{bmatrix}1 & 1\\\\1 & -1 \\end{bmatrix}$, so the rank-1 matrix approximation is: $3\\frac{1}{2}\\begin{bmatrix}1 \\\\1 \\end{bmatrix}\\begin{bmatrix}1 & 1\\end{bmatrix}=\\frac{3}{2}\\begin{bmatrix}1 & 1\\\\1 & 1\\end{bmatrix}$\n",
    "\n",
    "#### Problem I.9.3\n",
    "Since $A$ is itself orthogonal, we have \n",
    "$A = \\begin{bmatrix}\\cos\\theta & -\\sin\\theta\\\\\\sin\\theta & \\cos\\theta \\end{bmatrix}=U\\Sigma V^T = AII$. All its signular values are 1, so the rank-1 approximation is $\\begin{bmatrix}\\cos\\theta \\\\ \\sin\\theta \\end{bmatrix}\\begin{bmatrix}1 & 0 \\end{bmatrix}= \\begin{bmatrix}\\cos\\theta &0 \\\\ \\sin\\theta &0\\end{bmatrix}$\n",
    "\n",
    "#### Problem I.9.4\n",
    "\n",
    "We have $A-A_1 = \\begin{bmatrix}\\frac{3}{2} & -\\frac{3}{2}\\\\ -\\frac{1}{2} & \\frac{1}{2} \\end{bmatrix}$, so $||A-A_1||_{\\infty} = max(3,1) = 3$.\n",
    "\n",
    "Let rank-1 matrix be $A_2 = \\begin{bmatrix}\\frac{3}{2} & \\frac{15}{11}\\\\ \\frac{9}{2} & \\frac{45}{11} \\end{bmatrix}$, we have $A-A_2 = \\begin{bmatrix}\\frac{3}{2} & -\\frac{15}{11}\\\\ -\\frac{1}{2} & \\frac{10}{11} \\end{bmatrix}$, $||A-A_2||_{\\infty} = max(\\frac{3}{2}+\\frac{15}{11},\\frac{1}{2}+\\frac{10}{11}) = \\frac{63}{22}$, which is closer to $A$ than $A_1$.\n",
    "\n",
    "#### Problem I.9.5\n",
    "\n",
    "We have $QA=\\begin{bmatrix}\\cos\\theta & -\\sin\\theta\\\\\\sin\\theta & \\cos\\theta \\end{bmatrix} \\begin{bmatrix}a & b\\\\c & d \\end{bmatrix} = \\begin{bmatrix}a\\cos\\theta - c\\sin\\theta & b\\cos\\theta - d\\sin\\theta\\\\a\\sin\\theta+c\\cos\\theta & b\\sin\\theta+d\\cos\\theta \\end{bmatrix}$\n",
    "\n",
    "Take $\\theta = \\frac{\\pi}{4}$, we have $QA=\\begin{bmatrix}a-c & b-d \\\\ a+c & b+d\\end{bmatrix}$, so\n",
    "\n",
    "$||QA||_{\\infty} = max(|a-c|+|b-d|, |a+c|+|b+d|)$ which doesn't equal to $||A||_{\\infty}$\n",
    "\n",
    "#### Problem I.9.6\n",
    "\n",
    "If $S=Q\\Lambda Q^T$ is a symmetric positive definite matrix. Then all of its eigenvalues are positive, so $S=Q\\Lambda Q^T$ is actually a SVD form and $\\Lambda$ is the singular value matrix, $Q$ is the singular vector matrix. So $q_1\\lambda_1q^T_1$ is the closest rank-1 approximation to $S$ in the $L^2$ matrix norm $||S||_2$ if $\\lambda_1$ is the largest eigenvalue.\n",
    "\n",
    "#### Problem I.9.7\n",
    "\n",
    "When $n=2$, the matrix $A$ has maximum rank of $k=2$, so it makes sense to discuss the case when $k=1$, otherwise if $k=2$, the best approximation of rank-2 is the $A$ matrix itself.\n",
    "\n",
    "So we have $CR=(m\\times 1)(1 \\times 2)$, so $D=C^TC$ is a 1 by 1 matrix, i.e. a number. \n",
    "From the second derivative, we have $A^TAR^T = R^TD$, so it's clear that $D$ is the eigenvalue of $A^TA$, and $R^T$ is the eigenvector. \n",
    "From the first derivative, we have $AR^T=C$, so $AA^TC = AR^TD = CD$, so $C$ is the eigenvector of $AA^T$.\n",
    "\n",
    "#### Problem I.9.8\n",
    "\n",
    "The rank-3 matrix $A = \\sigma_1u_1v^T_1 + \\sigma_2u_2v^T_2 + \\sigma_3u_3v^T_3$, so $A-A_1 = \\sigma_2u_2v^T_2 + \\sigma_3u_3v^T_3$ and $A-A_2 = \\sigma_3u_3v^T_3$. The $l^2$ norm of matrices is the largest singular value of the matrix. So $||A-A_1||_2 = \\sigma_2$ and $||A-A_2||_2 = \\sigma_3$.\n",
    "So $A$ has the same singular values $\\sigma_2 = \\sigma_3$.\n",
    "\n",
    "\n",
    "#### Problem I.9.9\n",
    "First remove a rectangle of 1's, touching the parabola where the slope = -1. This rectangle has a rank of 1. \n",
    "On the top, we have $N-\\frac{3}{4}N= \\frac{1}{4}N$ rows, they are independent, on the right we have $N-\\frac{1}{2}N=\\frac{1}{2}N$ columns, which are independent too. So the leading term in the rank is: $\\frac{1}{4}N + \\frac{1}{2}N = \\frac{3}{4}N$\n",
    "\n",
    "\n",
    "#### Problem I.9.10\n",
    "\n",
    "* $A^{-1} = V^{-T}\\Sigma^{-1}U^{-1} = V\\Sigma^{-1}U^T$, so its $l^2$ norm is the maximum signular value, i.e. $\\frac{1}{\\sigma_2}$.\n",
    "\n",
    "* Its Frobenius norm is $||A^{-1}||^2_{F} = \\frac{1}{\\sigma_1^2} + \\frac{1}{\\sigma_2^2}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.10.1\n",
    "\n",
    "* $S-\\lambda M = \\begin{bmatrix}5 - \\lambda & 4 \\\\ 4 & 5 - 4\\lambda\\end{bmatrix}$. Solving $det(S-\\lambda M)=0$, we find the eigenvalues: $\\lambda_1 = \\frac{25+\\sqrt{481}}{8}, \\lambda_2 =\\frac{25-\\sqrt{481}}{8}$.\n",
    "\n",
    "* $H=M^{-\\frac{1}{2}}SM^{-\\frac{1}{2}} = \\begin{bmatrix}5 & 2 \\\\ 2 & \\frac{5}{4} \\end{bmatrix}$, Solving for eigenvalues we have the same eigenvalues as above: $\\lambda_1 = \\frac{25+\\sqrt{481}}{8}, \\lambda_2 =\\frac{25-\\sqrt{481}}{8}$.\n",
    "\n",
    "* Solve for $(S-\\lambda M)x=0$, we find that $x_1 = \\begin{bmatrix}\\frac{15+\\sqrt{481}}{8}\\\\1\\end{bmatrix}$ and $x_2 = \\begin{bmatrix}\\frac{15-\\sqrt{481}}{8}\\\\1\\end{bmatrix}$. It's clear that $x^Tx \\ne 0$. But $x^T_1Mx_2 = \\begin{bmatrix}\\frac{15+\\sqrt{481}}{8}&1\\end{bmatrix}\\begin{bmatrix}1 & 0 \\\\ 0 & 4 \\end{bmatrix}\\begin{bmatrix}\\frac{15-\\sqrt{481}}{8}\\\\1\\end{bmatrix} = 0$\n",
    "\n",
    "* Solve for $(H-\\lambda I)y = 0$, we find that  $y_1 = \\begin{bmatrix}\\frac{15+\\sqrt{481}}{16}\\\\1\\end{bmatrix}$ and $y_2 = \\begin{bmatrix}\\frac{15-\\sqrt{481}}{16}\\\\1\\end{bmatrix}$. So $y^T_1y_2 = 0$.\n",
    "\n",
    "#### Problem I.10.2\n",
    "\n",
    "* (a) Let $x=(a,b)$ and $y=(c,d)$, we have $R^*(x) = \\frac{5a^2+8ab+5b^2}{a^2 + 4b^2}$ and $R(y) = \\frac{20c^2+16cd+5d^2}{4(c^2+d^2)}$\n",
    "\n",
    "* (b) Take the $c$ and $d$ derivatives of $R(y)$ to find its maximum and minimum, we have\n",
    "\n",
    "\\begin{align*}\n",
    "\\frac{\\partial{R(y)}}{\\partial{c}} &= \\frac{4(40c+16d)(c^2+d^2) - 8c(20c^2+16cd+5d^2)}{16(c^2+d^2)}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "\\begin{align*}\n",
    "\\frac{\\partial{R(y)}}{\\partial{d}} &= \\frac{4(16c+10d)(c^2+d^2) - 8d(20c^2+16cd+5d^2)}{16(c^2+d^2)}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "Let each derivative equal to 0, we have two equations: \n",
    "\n",
    "\\begin{align*}\n",
    "d(8d^2-8c^2+15cd) &= 0 \\\\\n",
    "c(8c^2 - 8d^2 - 15cd) &= 0\\\\\n",
    "\\end{align*}\n",
    "\n",
    "Let $d=1$ and solve for $c$ have see that the two roots are the same as $y_1$ and $y_2$. \n",
    "\n",
    "* (c) Take the $a$ and $b$ derivatives of $R^*(y)$ to find its maximum and minimum, we have\n",
    "\n",
    "\\begin{align*}\n",
    "\\frac{\\partial{R^*(y)}}{\\partial{a}} &= \\frac{(10a+8b)(a^2+4b^2) - 2a(5a^2+8ab+5b^2)}{a^2+4b^2}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "\\begin{align*}\n",
    "\\frac{\\partial{R^*(y)}}{\\partial{b}} &= \\frac{(10b+8a)(a^2+4b^2) - 8b(5a^2+8ab+5b^2)}{a^2+4b^2}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "Let each derivative equal to 0, we have two equations: \n",
    "\n",
    "\\begin{align*}\n",
    "b(32b^2+30ab-8a^2) &= 0 \\\\\n",
    "a(-32b^2 - 30ab + 8a^2) &= 0\\\\\n",
    "\\end{align*}\n",
    "\n",
    "Let $b=1$ and solve for $a$ have see that the two roots are the same as $x_1$ and $x_2$. \n",
    "\n",
    "#### Problem I.10.3 \n",
    "\n",
    "We have $x = M^{-\\frac{1}{2}}y = \\begin{bmatrix}1 & 0 \\\\ 0 & \\frac{1}{2} \\end{bmatrix} y$. It's easy to see that the $x_1,x_2$ and $y_1,y_2$ above satisfy this condition.\n",
    "\n",
    "#### Problem I.10.4\n",
    "\n",
    "$S-\\lambda M = \\begin{bmatrix}5 - \\lambda & 4 \\\\ 4 & 5 \\end{bmatrix}$, solve for $det(S-\\lambda M)=0$, we find $\\lambda_1 = \\frac{9}{5}$, the corresponding eigenvector is $x_1 = \\begin{bmatrix}5 \\\\ -4\\end{bmatrix}$.\n",
    "\n",
    "The other eigenvalue is infinite (why? TODO), so according to equation (10), we have $Mx=0$ when $\\lambda = \\infty$, solve for this we have: $x_2 = \\begin{bmatrix}0 \\\\ 1\\end{bmatrix}$.\n",
    "\n",
    "It's easy to see that $x_1$ and $x_2$ are $M-$orthogonal to each other, i.e. $x^T_1Mx_2=0$.\n",
    "\n",
    "#### Problem I.10.5\n",
    "\n",
    "When $D=\\Lambda^{-\\frac{1}{2}}$, we have $D^T\\Lambda D = \\Lambda^{-\\frac{1}{2}} \\Lambda \\Lambda^{-\\frac{1}{2}} = I$.\n",
    "\n",
    "By definition, $Q_2$ is the eigenvector matrix of the matrix $D^TQ^TMQD$, this matrix is symmetric, so we have $D^TQ^TMQD = Q_2\\Lambda_2Q^T_2$, and $Q^T_2D^TQ^TMQDQ_2 = \\Lambda_2$. \n",
    "\n",
    "We have $Z^TSZ = Q^T_2D^TQ^TSQDQ_2 = Q^T_2IQ_2 = I$, and $Z^TMZ = Q^T_2D^TQ^TMQDQ_2 = \\Lambda_2$. \n",
    "So $Z$ can diagonalize both congruences $Z^TSZ$ and $Z^TMZ$.\n",
    "\n",
    "#### Problem I.10.6\n",
    "\n",
    "* (a) Because the transpose of the congruence $Z^TSZ$ is itself. \n",
    "* (b) For a given $x\\ne 0$, we have $x^TZ^TSZx = (Zx)^TS(Zx)$, since $S$ is positive definite so let $y=Zx$, we have $x^TZ^TSZx =y^TSy$. If $Z$ is square and invertible, it means its rank equals to the number of columns. So the nullspace is empty. So when $x\\ne 0$, we have $Zx\\ne 0$. We now see that the congruence matrix is also positive definite. \n",
    "\n",
    "#### Problem I.10.7 TODO\n",
    "\n",
    "The matrix $Z^TZ$ is congruent to the identity matrix.\n",
    "\n",
    "#### Problem I.10.8\n",
    "\n",
    "$S=uu^T$, then $R(x) = \\frac{x^TSx}{x^TMx} = \\frac{x^Tuu^Tx}{x^TMx}= \\frac{(u^Tx)^T(u^Tx)}{x^TMx} = = \\frac{(u^Tx)^2}{x^TMx}$ since $u^Tx$ is a scalar. It's clear that when $M$ is positive definite, $R(x)$ achieves minimum value of 0 when $x$ is perpendicular to $u$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.11.1\n",
    "\n",
    "$|v|^2_2 = |v_1|^2 + \\dots + |v_n|^2 \\le |v_1||v_m| + \\dots + |v_n||v_m| = |v_m|(|v_1|+\\dots + |v_n|) = |v|_1|v|_{\\infty}$, where $|v_m| = \\max {|v_1|,\\dots,|v_n|}$\n",
    "\n",
    "#### Problem I.11.2\n",
    "\n",
    "The length squared of $v - \\frac{v^tw}{w^Tw}w$ is :\n",
    "\n",
    "\\begin{align*}\n",
    "(v - \\frac{v^Tw}{w^Tw}w)^T(v - \\frac{v^Tw}{w^Tw}w) &= v^Tv - 2\\frac{v^Twv^Tw}{w^Tw} + (\\frac{v^Tw}{w^Tw})^2w^Tw \\\\\n",
    "&= v^Tv - \\frac{|v^Tw|^2}{w^Tw}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "This is greater than or equal to zero, so we have $v^Tv - \\frac{|v^Tw|^2}{w^Tw} \\ge 0$, $|v|^2_2|w|^2_2 \\ge |v^Tw|^2$, i.e. $|v|_2|w|_2 \\ge |v^Tw|$\n",
    "\n",
    "#### Problem I.11.3\n",
    "\n",
    "$|v|_2 = \\sqrt{|v_1|^2 + \\dots + |v_n|^2} \\le \\sqrt{|v|_{\\infty}^2+\\dots + |v|_{\\infty}^2} = \\sqrt{n}|v|_{\\infty}$. \n",
    "\n",
    "Let $w=(sign(v_1),\\dots,sign(v_n))$, so we have $ |v|_1 = |v^Tw| \\le |v|_2|w|_2 = \\sqrt{n}|v|_2$.\n",
    "\n",
    "The inequality comes from Cachy-Schwarz inequality\n",
    "\n",
    "#### Problem I.11.4\n",
    "\n",
    "For $p=1$ and $q=\\infty$, Holder's inequality says: $|v^Tw|_1\\le |v|_1|w|_{\\infty}$, that says the $l^1$ norm of $v^Tw$ is less than or equal to the maximum component value of $w$ multiply $l^1$ norm of $v$ itself.\n",
    "\n",
    "#### Problem I.11.5\n",
    "\n",
    "The rules should be satisfied by any \"inner product\" of vectors $v$ and $w$ are:\n",
    "* $(v,v) \\ge 0$\n",
    "* $(v,w) = (w,v)$\n",
    "\n",
    "#### Problem I.11.6\n",
    "\n",
    "$|\\frac{v}{2}+\\frac{w}{2}| \\le |\\frac{v}{2}| + |\\frac{w}{2}| \\le 1$ where the triangle inequality is used in the second step.\n",
    "\n",
    "#### Problem I.11.7\n",
    "\n",
    "We know that $|(AB)_{ij}|^2 \\le |\\text{row i of }A|^2|\\text{column j of }B|^2$ from Cachy-Schwarz inequality. Add up both sides over all $i$ and $j$ we have\n",
    "\n",
    "\\begin{align*}\n",
    "\\sum_i\\sum_j |(AB)_{ij}|^2 &\\le \\sum_i\\sum_j|\\text{row i of }A|^2|\\text{column j of }B|^2 \\\\\n",
    "|AB|^2_{F} &= \\sum_i|\\text{row i of }A|^2 \\sum_j|\\text{column j of }B|^2\\\\\n",
    "&= \\sum_i|\\text{row i of }A|^2 |B|^2_{F}\\\\\n",
    "&= |A|^2_{F} |B|^2_{F}\\\\\n",
    "\\end{align*}\n",
    "\n",
    "#### Problem I.11.8\n",
    "\n",
    "* $A=B=I$, $AB=I$, $|A|_{F}=|B|_{F} = N$, and $|AB|_{F}=N$, so we have $|AB|_{F}\\le |A|_{F}|B|_{F}$.\n",
    "* $A=B$ are all ones matrix, then $AB$ is all $N$ matrix. We have $|A|_{F}=|B|_{F}=N^2$, $|AB|_{F}=N\\times N^2 = N^3$. so $|AB|_{F} = N^3 \\le |A|_{F}|B|_{F} = N^4$.\n",
    "\n",
    "#### Problem I.11.9 TODO\n",
    "\n",
    "#### Problem I.11.10\n",
    "\n",
    "Let $B=A^T$ and $C=A^TA$, so we have $c_{ii} = \\sum^n_{k=1} b_{ik}a_{ki} = \\sum^n_{k=1}a_{ki}a_{ki} = \\sum^n_{k=1}a^2_{ki}$\n",
    "$(A,A) = trace(A^T,A) = \\sum^n_{i=1}c_{ii} = \\sum^n_{i=1}\\sum^n_{k=1}a^2_{ki} = |A|^2_{F}$\n",
    "\n",
    "\n",
    "#### Problem I.11.11 TODO\n",
    "\n",
    "* Equation (21), it satisfies $|A|_{\\infty} > 0$, $|cA|_{\\infty} = |c||A|_{\\infty}$. \n",
    "Also, $|A+B|_{\\infty} \\le |A|_{\\infty} + |B|_{\\infty}$. \n",
    "\n",
    "For $|AB|_{\\infty} = \\text{largest L1 norm of the rows of }\\;AB$, we have \n",
    "\n",
    "$(AB)_{i,j} = \\sum_k a_{ik}b_{kj}$, so for the $l^1$ norm of row $i$, we have $|(AB)_{i,}| = \\sum_j|\\sum_k a_{ik}b_{kj}| \\le \\sum_j\\sum_k |a_{ik}b_{kj}| \\le \\sum_j\\sum_k |a_{ik}||b_{kj}| = \\sum_k |a_{ik}| \\sum_j |b_{kj}| = \\sum_k |a_{ik}| |B_{k,}| = |A_{i,}||B_{k,}| \\le |A|_{\\infty} |B|_{\\infty} $\n",
    "\n",
    "So $|AB|_{\\infty} = \\max {|(AB)_{i,}|} \\le \\max  |A|_{\\infty} |B|_{\\infty} =  |A|_{\\infty} |B|_{\\infty}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.11.12\n",
    "\n",
    "$(AB)_{ij} = \\sum_k a_{ik}b_{kj}$, so\n",
    "\n",
    "$|||AB|||_{\\infty} = max|(AB)_{ij}| = max |\\sum_k a_{ik}b_{kj}| \\le max \\sum_k |a_{ik}b_{kj}| \\le max \\sum_k |a_{ik}||b_{kj}| \\le max  \\sum_k |a_{ik}| \\le |||B|||_{\\infty} max \\sum_k |||A|||_{\\infty} = n|||A|||_{\\infty}|||B|||_{\\infty} $\n",
    "\n",
    "This is equivalent to $(\\sqrt{mp}|||AB|||_{\\infty})\\le (\\sqrt{mn}|||A|||_{\\infty})(\\sqrt{np}|||B|||_{\\infty})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.12.1\n",
    "\n",
    "Take derivative of the column norm w.r.t. $v_1$, we have \n",
    "\n",
    "$\\frac{d}{dv_1} = -2(a-v_1u_1)u_1 - 2(b-v_1u_2)u_2$, let it equal to 0, we have $(u^2_1 + u^2_2)v_1 = au_1 + bu_2$, which in vector notation we have $u^Tuv_1 = u^Ta_1$ where $a_1$ is the column 1 of $A$.\n",
    "\n",
    "#### Problem I.12.2\n",
    "\n",
    "The error vector $a_1  - v_1u$ is perpendicular to $u$. We can find the number $v_1$ that minimizes $||a_1 - v_1u||^2$. That is:\n",
    "\n",
    "$(a_1 - v_1u)^Tu = (a^T_1 - v_1 u^T)u = a^T_1u - v_1 u^Tu = 0 $ so we obtain the same formula as problem I.12.1.\n",
    "\n",
    "#### Problem I.12.3\n",
    "\n",
    "Similarly as problems above, the number $v_2$ that minimizes $||a_2 - v_2u||^2$ satisfies $u^Tuv_2 = u^Ta_2$.\n",
    "\n",
    "In vector form, the best $v$ solves $(u^Tu)v = u^TA$.\n",
    "\n",
    "#### Problem I.12.4\n",
    "\n",
    "With fixed $V$, we can do the same process but using  the rows of the matrix $A-UV$ since the Frobenius norm is not related to row or column order. The $u$ that minimize $||A-UV||^2_{F}$ is: $vv^Tu_1 = a^T_1v^T$, where $a^T_1$ is the first row of $A$.\n",
    "\n",
    "In vector form, the best $u$ solves $(vv^T)u=Av^T$.\n",
    "\n",
    "#### Problem I.12.5\n",
    "\n",
    "Reuse the example 1 from I.8, where $A=\\begin{bmatrix}3 & 0 \\\\ 4 & 5 \\end{bmatrix}$. Its closest rank 1 matrix $A_1 = \\sigma_1u_1v^T_1 = \\sqrt{45}\\frac{1}{\\sqrt{10}}\\begin{bmatrix}1 \\\\ 3 \\end{bmatrix}\\frac{1}{\\sqrt{2}}\\begin{bmatrix}1 & 1 \\end{bmatrix} = \\begin{bmatrix}\\frac{3}{2} & \\frac{3}{2} \\\\ \\frac{9}{2} & \\frac{9}{2} \\end{bmatrix}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_minimumV(A, U):\n",
    "    # We solve (u^Tu)v = u^TA, u is nx1, A: nxn\n",
    "    # The result V has shape 1xn\n",
    "    rhs = np.matmul(U.transpose(), A)\n",
    "    lhs = np.matmul(U.transpose(), U).flatten()\n",
    "    res = rhs/lhs\n",
    "    res = res.reshape(1, -1)\n",
    "    return res\n",
    "\n",
    "def find_minimumU(A, V):\n",
    "    # We solve (vv^T)vu= Av^T, V is 1xn, A: nxn\n",
    "    # The result U has shape nx1\n",
    "    rhs = np.matmul(A, V.transpose())\n",
    "    lhs = np.matmul(V, V.transpose()).flatten()\n",
    "    res = rhs/lhs\n",
    "    res = res.reshape(-1, 1)\n",
    "    return res\n",
    "\n",
    "def calc_forbenius_norm(M):\n",
    "    m, n = M.shape\n",
    "    F = 0\n",
    "    for i in np.arange(m):\n",
    "        for j in np.arange(n):\n",
    "            F += M[i,j]**2\n",
    "    return F\n",
    "    \n",
    "def find_minimum(A, max_it = 1000, tol = 1):\n",
    "    \"\"\"Minimize ||A-UV||^2_{F} using alterating minimization method. Where UV has rank 1\n",
    "    U has dimension nx1, and V has dimension 1xn\n",
    "    \"\"\"\n",
    "    \n",
    "    #Initial U\n",
    "    U = np.ones((A.shape[0], 1))\n",
    "    \n",
    "    for it in np.arange(max_it):\n",
    "        V=find_minimumV(A, U)\n",
    "        U=find_minimumU(A, V)\n",
    "        M = A - np.matmul(U, V)\n",
    "        norm = calc_forbenius_norm(M)\n",
    "        if norm < tol:\n",
    "            print('Stopped at iteration: ', it)\n",
    "            break\n",
    "    print('Final norm: ', norm)\n",
    "    approxA = np.matmul(U,V)\n",
    "    print('Final approx A: ', approxA)\n",
    "    return norm, approxA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Final norm:  5.0\n",
      "Final approx A:  [[1.5 1.5]\n",
      " [4.5 4.5]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(5.0, array([[1.5, 1.5],\n",
       "        [4.5, 4.5]]))"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.array([[3,0],[4,5]])\n",
    "find_minimum(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem I.12.6\n",
    "\n",
    "Given an $m$ by $n$ matrix $A$, we can check the number of independent columns in $A$, if there's only 1 column that is independent, then it has rank 1. We can do SVD decomposition, if the diagonal matrix has only one nonzero singular value, it has rank 1. \n",
    "\n",
    "#### Problem I.12.7\n",
    "\n",
    "The rank of a tensor $T$ is the smallest number of rank-1 tensors that add to $T$. The rank-1 tensors are outer products of three vectors. So if a tensor can be expressed as an outer product of 3 vectors, then it is rank-1.\n",
    "\n",
    "#### Problem I.12.8 \n",
    "\n",
    "Take $u=(1,1),v=(1,0),w=(0,1),p=(2,-1),q=(1,1)$, we can create a tensor \n",
    "\n",
    "$T=u\\times v \\times v + p \\times w \\times v + u \\times q \\times w = \\begin{bmatrix}1 & 1 & | & 1 & 1\\\\2 & 1 & | & -1 & 1\\end{bmatrix}$\n",
    "\n",
    "I am not sure it's rank-3 or not.\n",
    "\n",
    "#### Problem I.12.9\n",
    "\n",
    "* (a) For a matrix $A$, we should have $r_1 + \\dots + r_m = c_1 + \\dots + c_n$\n",
    "* (b) For an $m$ by $n$ by $p$ tensor, the sum of the $m$ slices, $n$ slices and $p$ slices should equal to each other. Because when you add the slices up, they are just the sum of all entries in the tensor.\n",
    "\n",
    "#### Problem I.12.10\n",
    "\n",
    "Let $\\gamma = (1,1), \\alpha =(1,1), \\beta=(1,1)$ and $r=(-1,0),p=(1,0),q=(1,0)$, we have\n",
    "\n",
    "$T_1 = \\gamma \\times \\alpha \\times \\beta = \\gamma \\times \\begin{bmatrix}1 & 1 \\\\ 1 & 1\\end{bmatrix} = \\begin{bmatrix}1 & 1 & | & 1 & 1\\\\1 & 1 & | & 1 & 1\\end{bmatrix}$\n",
    "\n",
    "$T_2 = r \\times p \\times q = r \\times \\begin{bmatrix}1 & 0 \\\\ 0 & 0\\end{bmatrix} = \\begin{bmatrix}-1 & 0 & | & 0 & 0\\\\0 & 0 & | & 0 & 0\\end{bmatrix}$\n",
    "\n",
    "So $T=T_1+T_2 = \\begin{bmatrix}0 & 1 & | & 1 & 1\\\\1 & 1 & | & 1 & 1\\end{bmatrix}$\n",
    "\n",
    "Note, to find such vectors, you can set the components of these vectors to variables, and solve for them using the condition that $T$ only has 1 zero entry. \n",
    "\n",
    "The closest rank-1 tensor to $T$ is the $T_1$.\n",
    "\n",
    "#### Problem I.12.11\n",
    "\n",
    "We can matricize the tensor $T$ into $4\\times 2$ matrix, then apply the matrix multiplication $Tv$ which will yield 4 by 1 matrix, Then we can unfold it into a 2 by 2 matrix $A$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}