{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Assignment 3 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MATH 7502  - Semsester 2, 2018\n",
    "## Mathematics for Data Science 1\n",
    "\n",
    "#### Created by Zhihao Qiao,  Maria Kleshnina and Yoni Nazarathy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 1\n",
    "Consider the following recurision, \n",
    "$$ x_{t+1} = A_1 x_t +A_2 x_{t-1},  \\quad , t=2,3,...$$\n",
    "where $x_t$ is n-vector and $A_1$ and $A_2$ are $n \\times n$ matrices.  Define $z_t = (x_t,x_{t-1})$. \n",
    "\n",
    "Show that $z_t$ satisfies the linear dynamical system equation $z_{t+1}=Bz_t$, for $t=2,3,...,$ where $B$ is a $(2n)\\times (2n)$ matrix. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 2 \n",
    "Consider the Fibonacci sequence $y_0,y_1,y_2,...$ with $y_0=0, y_1 = 1, y_2=1, y_3 =2,....$, and for $t = 2,3,...,$ $y_t$ is the sum of the previous two terms $y_{t-1}$ and $y_{t-2}$.  \n",
    "\n",
    "(a) Express the Fibonacci sequence as a time-invaraint dynamical system wit state $x_t = (y_t,y_{t-1})$ and output $y_t$ for $t=1,2,3....$  as\n",
    "\n",
    "$$ x_{t+1} = A x_t $$\n",
    "\n",
    "(b )For the matrix, A, compute the eigenvalues and describe the Fibonnaci sequence interms of eigevnalues and eigenvectors. How does the golden ratio play a role?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 3\n",
    "In the sepcial case $n=1$, the general least square problem reduces to finding a scalar $x$ that minimizes $\\|ax-b\\|^2$, where $a$ and $b$ are m-vectors. Assuming $a$ and $b$ are nonzero, show that $\\|a\\hat{x}-b\\|^2 = \\|b\\|^2\\sin^2(\\theta)$, where $\\theta = \\angle(a,b)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 4\n",
    "Consider a time-invaraint linear dynamical system with offset \n",
    "$$x_{t+1} = Ax_t+c$$\n",
    "where $x_t$ is the state n-vector. We say that a vector $z$ is an equilibrium point of the linear dynamical system if $x_1=z$ implies $x_2=z,x_3=z,...$\n",
    "\n",
    "(a) Find a matrix $F$ and a vector $g$ for which the set of linear equations $Fz = g$ characterizes equilibrium points. (This means: If $z$ is an equilibrium point, then $Fz = g$; conversely if\n",
    "$Fz= g$, then $z$ is an equilibrium point.)\n",
    "\n",
    "\n",
    " Express $F$ and $g$ interms of $A, c$ any standard matrices or vectors and matrix and vector operations. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 5\n",
    "Suppose that $m\\times n$ matrix $Q$ has orthonormal columns and $b$ is an m-vector. Show that $\\hat{x} = Q^T b$ is the vector that minimizes $\\|Qx-b\\|^2$. \n",
    "\n",
    "Comment on the complexity of finding $\\hat{x}$ given $Q$ and $b$ in this case.  Compare the complexity with the general leasure square problem where $Q$ is a coefficient matrix. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 6\n",
    "Suppose $m\\times n$ matrix $A$ has linearly independent columns, and $b$ is a m-vector. Let $\\hat{x} = A^{\\dagger} b$ denote the least squares approximate solution of $Ax=b$. \n",
    "\n",
    "(a) Show that for any n-vector $x$, $(Ax)^T b  = (Ax)^T (A\\hat{x})$. Hint: Use $(Ax)^T b  = x^T (A^T b)$, and $(A^T A)\\hat{x} = A^T b$. \n",
    "\n",
    "(b) Show that when $A\\hat{x}$ and $b$ are both nonzero, we have \n",
    "$$\\frac{(A\\hat{x})^T b}{\\|A\\hat{x}\\|\\|b\\|} = \\frac{\\|A\\hat{x}\\|}{\\|b\\|}$$.\n",
    "\n",
    "(c) The choice of $x=\\hat{x}$ minimizes the distance between $Ax$ and $b$, Show that $x=\\hat{x}$ also minimizes the angle between $Ax$ and $b$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 7\n",
    "Suppose $A$ is an $m\\times n $ matrix with linearly independent columns and $QR$ factorization $A=QR$, and $b$ is the m-vector. The vector $A\\hat{x}$ is the linear combination of the columns of $A$ that is closet to the vector $b$, i.e., it is the projection of $b$ onto the set of linear combinations of the columns of $A$. \n",
    "\n",
    "(a) Show that $A\\hat{x} = QQ^T b$.\n",
    "\n",
    "(b) Show that $\\|A\\hat{x}-b\\|^2 = \\|b\\|^2-\\|Q^T b\\|^2$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 8\n",
    "\n",
    "A generalization of the least squares problem adds an affine function to the least squares objective \n",
    "\n",
    "$$ \\text{minimize } \\qquad \\|Ax-b\\|^2+c^T x+d$$\n",
    "where $x$ is an n-vector as a variable to be chosen, and the data are the $m\\times n$ matrix $A$, the m-vector $b$, the n-vector $c$.  and the number $d$.  The columns of $A$ are linearly indeppendent. \n",
    "\n",
    "Show that that objective of the problem above can be expressed in the form \n",
    "$$ \\|Ax-b\\|^2 +c^T x +d = \\| Ax - b +f \\|^2+g$$,\n",
    "\n",
    "for some m-vector $f$ and some constant $g$. It follows that we can solve the generalized least squares problem by minimizing $\\|Ax-(b-f)\\|$, an ordinary least squares problem with solution $\\hat{x} = A^{\\dagger}(b-f)$.\n",
    "\n",
    "Hint: Express the norm squared term on the right-hand side as $\\|(Ax-b)+f\\|^2$ and expand it. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 9\n",
    "A very simple model of how the economic output changes over time is $a_{t+1}=Ba_t$, where $B$ is an $n\\times n$ matrix, $(a_t)_i$ is the economic output in sector $i$ in year $t$.   In this problem, we will consider the specific model with $n=4$ and \n",
    "\n",
    "$$ B = \\begin{bmatrix}  0.1&0.06&0.05&0.7\\\\\n",
    "0.48&0.44&0.10&0.04\\\\\n",
    "0.00&0.55&0.52&0.04\\\\\n",
    "0.04&0.01&0.42&0.51\n",
    "\\end{bmatrix}$$.\n",
    "\n",
    "(a) Breifly interpret $B_{23}$. \n",
    "\n",
    "(b) Suppose $a_1 = (0.6,0.9,1.3,0.05)$ plot four sector outputs and the total economic output versus $t$ for $t=1,...,20$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 10 \n",
    "Solve Question 12.13 from [VMLS], page 241."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 11\n",
    "You are given a channel impulse response, the n-vector $c$. Your job is to find an equalizer impulse response, the n-vector $h$ that minimizes $\\|h*c-e_1\\|^2$. You can assume $c_1 \\neq 0 $. \n",
    "\n",
    "(a) Explain how to find $h$, Apply your method to find the equalizer $h$ for the channel $c = (1.0,0.7,-0.3,-0.1,0.05).$\n",
    "\n",
    "(b) Plot $c$, $h$, and $h*c$. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question 12\n",
    "\n",
    "Consider the linear dynamical system,\n",
    "$$\n",
    "\\dot{x}_t = A x_t.\n",
    "$$\n",
    "with $x_0 = x_0$ and $A$ an $n \\times n$ matrix.\n",
    "\n",
    "Plot trajectories of such a system with $n=2$ and $x_0 = (1,1)'$ for the following numerical example cases:\n",
    " \n",
    "* Both eigenvalues of $A$ real and negative.\n",
    "* Both eigenvalues of $A$ real and positive.\n",
    "* One eigenvalue real positive and one real negative.\n",
    "* Both eigenvalues complex and negative.\n",
    "* Pure imaginary eigenvalues. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.6.2",
   "language": "julia",
   "name": "julia-0.6"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}