{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Math599 2021S"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LA-exam\n",
    "You may find the `ipynb` file of this exam at  \n",
    "http://www.math.nsysu.edu.tw/~chlin/2021SMath599/LinearA-exam.ipynb   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name:  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Student ID #:  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Please read the instructions carefully:\n",
    "1. Write your **name** and **Student ID #** first.\n",
    "2. You are allowed to use the internet, but you are **NOT allowed to communicate** with others in any form.\n",
    "3. **Do NOT use your cell phone**, use the computer instead.\n",
    "4. Different problems might use same variable names.  Make sure you use the right one to answer the problem.\n",
    "5. If the answer is too long, write **two digits after the decimal point**.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Problem 1 [2pt]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let  \n",
    "```python\n",
    "grid = np.meshgrid(np.linspace(0,10,101),np.linspace(0,10,101))\n",
    "xs = grid[0].ravel()\n",
    "ys = grid[1].ravel()\n",
    "vs = np.vstack([xs,ys])\n",
    "```\n",
    "The columns of `vs` contain 10201 points $(x_i,y_i)$.  \n",
    "How many of these points satisfy $2x + 3y > 12.01$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Your answer:_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8940"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = np.meshgrid(np.linspace(0,10,101),np.linspace(0,10,101))\n",
    "xs = grid[0].ravel()\n",
    "ys = grid[1].ravel()\n",
    "vs = np.vstack([xs,ys])\n",
    "\n",
    "r = np.array([2,3])\n",
    "np.sum(r.dot(vs) > 12.01)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Problem 2 [2pt]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let  \n",
    "```python\n",
    "x = np.linspace(0,10,101)\n",
    "y = 2.1*x + 1.1 + 0.5*np.sin(x)\n",
    "```\n",
    "The variable `x` stores 101 values $x_i$'s.  \n",
    "The variable `y` stores 101 values $y_i$'s.  \n",
    "Let $f(x) = 2x + 1$.  \n",
    "Find the mean square error between $y$ and $f(x)$, which is defined as    \n",
    "$$\\frac{1}{101}\\sum_{i=0}^{100}(f(x_i) - y_i)^2.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Your answer:_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6563453624224954"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = np.linspace(0,10,101)\n",
    "y = 2.1*x + 1.1 + 0.5*np.sin(x)\n",
    "\n",
    "diff = y - 2*x - 1\n",
    "np.mean(diff**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Problem 3 [2pt]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let  \n",
    "```python\n",
    "grid = np.meshgrid(np.linspace(-5,5,101),np.linspace(-5,5,101))\n",
    "c0 = grid[0].ravel()\n",
    "c1 = grid[1].ravel()\n",
    "cs = np.vstack([c0,c1])\n",
    "A = np.array([[1,1], \n",
    "              [-1,1], \n",
    "              [0,-2]])\n",
    "pts = A.dot(cs)\n",
    "```\n",
    "Let ${\\bf b} = (1,1,2)^\\top$ and ${\\bf p}_i$'s the columns of `pts` .  \n",
    "Find  \n",
    "$$\\min_{i}\\|{\\bf b} - {\\bf p}_i\\|.$$\n",
    "That is, the shortest distance between ${\\bf b}$ and a point ${\\bf p}_i$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Your answer:_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.3108440016582685"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grid = np.meshgrid(np.linspace(-5,5,101),np.linspace(-5,5,101))\n",
    "c0 = grid[0].ravel()\n",
    "c1 = grid[1].ravel()\n",
    "cs = np.vstack([c0,c1])\n",
    "A = np.array([[1,1], \n",
    "              [-1,1], \n",
    "              [0,-2]])\n",
    "pts = A.dot(cs)\n",
    "\n",
    "b = np.array([1,1,2])\n",
    "\n",
    "diff = b[:,np.newaxis] - pts\n",
    "dist = np.linalg.norm(diff, axis=0)\n",
    "dist.min()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Problem 4 [2pt]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let  \n",
    "$$A = \\begin{bmatrix} 1 & 1 \\\\ -1 & 1 \\\\ 0 & -2 \\end{bmatrix} \\text{ and } {\\bf b} = \\begin{bmatrix} 1 \\\\ 1 \\\\ 2 \\end{bmatrix}.$$  \n",
    "Solve $A{\\bf x} = {\\bf b}$.  \n",
    "If there is no solution for ${\\bf x}$, then find ${\\bf x}$ that minimizes $\\|A{\\bf x } - {\\bf b}\\|$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Your answer:_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x = [ 0.         -0.33333333]\n",
      "Ax = [-0.33333333 -0.33333333  0.66666667]\n",
      "dist = 2.3094010767585034\n"
     ]
    }
   ],
   "source": [
    "A = np.array([[1,1], \n",
    "              [-1,1], \n",
    "              [0,-2]])\n",
    "b = np.array([1,1,2])\n",
    "\n",
    "ATAinv = np.linalg.inv(A.T.dot(A))\n",
    "x = ATAinv.dot(A.T).dot(b)\n",
    "print('x =', x)\n",
    "print('Ax =', A.dot(x))\n",
    "print('dist =', np.linalg.norm(A.dot(x) - b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Problem 5 [2pt]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let  \n",
    "```python\n",
    "A = np.arange(1,5)[:,np.newaxis] ** np.arange(3)\n",
    "b = np.array([3,2,3,2])\n",
    "```\n",
    "Find the projection of `b` onto the column space of `A` ."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Your answer:_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([2.8, 2.6, 2.4, 2.2])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.arange(1,5)[:,np.newaxis] ** np.arange(3)\n",
    "b = np.array([3,2,3,2])\n",
    "\n",
    "ATAinv = np.linalg.inv(A.T.dot(A))\n",
    "proj = A.dot(ATAinv).dot(A.T).dot(b)\n",
    "proj"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Problem 6 [2pt]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Download the file  \n",
    "http://www.math.nsysu.edu.tw/~chlin/2021SMath599/LinearA-text.csv  \n",
    "Let  \n",
    "```python\n",
    "arr = np.genfromtxt('LinearA-text.csv', delimiter=',')\n",
    "vals,vecs = np.linalg.eigh(arr)\n",
    "```  \n",
    "Let $\\lambda_i$'s be the values in `vals` and ${\\bf u}_i$'s the columns of `vecs` .  \n",
    "Compute  \n",
    "$$ B = \\sum_{\\lambda_i < 300}\\lambda_i{\\bf u}_i{\\bf u}_i^\\top$$\n",
    "and use `plt.imshow(..., cmap='Greys_r)` to visualize the matrix $B$.  \n",
    "What text do you see there?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Your answer:_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "arr = np.genfromtxt('LinearA-text.csv', delimiter=',')\n",
    "vals,vecs = np.linalg.eigh(arr)\n",
    "\n",
    "new_vals = vals.copy()\n",
    "mask = (vals > 300)\n",
    "new_vals[mask] = 0\n",
    "D = np.diag(new_vals)\n",
    "Q = vecs\n",
    "new_arr = Q.dot(D).dot(Q.T)\n",
    "plt.imshow(new_arr, cmap='Greys_r')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The answer is \"BOOK\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Problem 7 [2pt]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let  \n",
    "```python\n",
    "Q = np.array([[1,1,1], \n",
    "              [-1,1,1], \n",
    "              [0,-2,1]])\n",
    "Q = Q / np.linalg.norm(Q, axis=0)\n",
    "```\n",
    "Let ${\\bf u}_0, {\\bf u}_1, {\\bf u}_2$ be the columns of `Q` .  \n",
    "Let ${\\bf v} = (2,1,1)^\\top$.  \n",
    "Find $c_0,c_1,c_2$ such that ${\\bf v} = c_0{\\bf u}_0 + c_1{\\bf u}_1 + c_2{\\bf u}_2$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Your answer:_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.70710678, 0.40824829, 2.30940108])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Q = np.array([[1,1,1], \n",
    "              [-1,1,1], \n",
    "              [0,-2,1]])\n",
    "Q = Q / np.linalg.norm(Q, axis=0)\n",
    "\n",
    "v = np.array([2,1,1])\n",
    "Q.T.dot(v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Problem 8 [2pt]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let  \n",
    "```python\n",
    "Q = np.array([[1,1,1], \n",
    "              [-1,1,1], \n",
    "              [0,-2,1]])\n",
    "Q = Q / np.linalg.norm(Q, axis=0)\n",
    "```\n",
    "Let ${\\bf u}_0, {\\bf u}_1, {\\bf u}_2$ be the columns of `Q` .  \n",
    "Find a matrix $A$ such that  \n",
    "$A{\\bf u}_0 = {\\bf u}_0$    \n",
    "$A{\\bf u}_1 = {\\bf u}_1$  \n",
    "$A{\\bf u}_2 = {\\bf 0}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Your answer:_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0.66666667, -0.33333333, -0.33333333],\n",
       "       [-0.33333333,  0.66666667, -0.33333333],\n",
       "       [-0.33333333, -0.33333333,  0.66666667]])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Q = np.array([[1,1,1], \n",
    "              [-1,1,1], \n",
    "              [0,-2,1]])\n",
    "Q = Q / np.linalg.norm(Q, axis=0)\n",
    "\n",
    "D = np.diag([1,1,0])\n",
    "\n",
    "A = Q.dot(D).dot(Q.T)\n",
    "A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Problem 9 [2pt]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let  \n",
    "```python\n",
    "k = 3\n",
    "J = np.ones((k,k))\n",
    "v = np.ones(k)\n",
    "```\n",
    "Is `v` an eigenvector of `J` ?  \n",
    "If yes, what is the corresponding eigenvalue?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Your answer:_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1. 1. 1.]\n",
      "[3. 3. 3.]\n",
      "[3. 3. 3.]\n"
     ]
    }
   ],
   "source": [
    "k = 3\n",
    "J = np.ones((k,k))\n",
    "v = np.ones(k)\n",
    "print(v)\n",
    "print(J.dot(v))\n",
    "print(J.dot(v) / v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The asnwer is 3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Problem 10 [2pt]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let  \n",
    "$$A = \\begin{bmatrix} -2 & -2 \\\\ -1 & -1 \\\\ 0 & 0 \\\\ 1 & 1 \\\\ 2 & 2 \\end{bmatrix}.$$\n",
    "Find a vector ${\\bf x}$ of length $1$ that maximizes ${\\bf x}^\\top A^\\top A{\\bf x}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Your answer:_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0.70710678, 0.70710678])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = np.array([[-2,-2], \n",
    "              [-1,-1], \n",
    "              [0,0], \n",
    "              [1,1], \n",
    "              [2,2]])\n",
    "vals,vecs = np.linalg.eigh(A.T.dot(A))\n",
    "vecs[:,-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Problem 11 [extra 2pt]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Download the file  \n",
    "http://www.math.nsysu.edu.tw/~chlin/2021SMath599/LinearA_T.py  \n",
    "Run  \n",
    "```python\n",
    "from LinearA_T import f\n",
    "```\n",
    "Thus, `f` is a function taking an array of shape `(3,)` and return another.  \n",
    "For example, you may run.  \n",
    "```python\n",
    "v = np.array([1,2,3])\n",
    "f(v)\n",
    "```\n",
    "Suppose that $f=$ `f` is a linear function from $\\mathbb{R}^3$ to $\\mathbb{R}^3$.  \n",
    "Find a matrix $A$ such that $A{\\bf v} = f({\\bf v})$ for all ${\\bf v}\\in\\mathbb{R}^3$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Your answer:_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1., 1., 1.],\n",
       "       [0., 1., 1.],\n",
       "       [0., 0., 1.]])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from LinearA_T import f\n",
    "\n",
    "e0,e1,e2 = np.eye(3)\n",
    "A = np.vstack([f(e0), f(e1), f(e2)]).T\n",
    "A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---  \n",
    "Exam ends here.  \n",
    "Total point = 20 (+2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your score:"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (system-wide)",
   "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}