Linear Algebra Background.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear Algebra Background\n",
    "\n",
    "In this course, we will need to use material from linear algebra and calculus. This section serves as a review of the essential topics from those subjects that will be needed for this course.\n",
    "\n",
    "## Vectors and Matrices\n",
    "\n",
    "We will denote a vector $x \\in \\mathbb{R}^{n}$, and usually we will denote its components by $x_{i}$. (Sometimes we'll also write a series of vectors as $y_{i} \\in \\mathbb{R}^{n}$ for $i = 1, \\ldots, m$ where here the subscript simply denotes vector $i$ in the set.) The components of this column vector $x \\in \\mathbb{R}^{n}$ can be written as follows\n",
    "\\begin{equation*}\n",
    "    x = \\begin{bmatrix}\n",
    "        x_{1} \\\\ x_{2} \\\\ x_{3} \\\\ \\vdots \\\\ x_{n} \\\\\n",
    "    \\end{bmatrix}.\n",
    "\\end{equation*}\n",
    "We'll often need to write inequalities. Generally $x \\ge 0$ will denote that $x_{i} \\ge 0$ for $i = 1, \\ldots, n$.\n",
    "\n",
    "\n",
    "### Dot products and norms\n",
    "Dot products with two vectors $x, y \\in \\mathbb{R}^{n}$ can be written as follows:\n",
    "\\begin{equation*}\n",
    "    x^{T} y = \\sum_{i=1}^{n} x_{i} y_{i}.\n",
    "\\end{equation*}\n",
    "\n",
    "The norm of a vector is a measure of its length. We'll see a couple different norms. The $\\ell_{2}$ norm is related to the dot product such that\n",
    "\n",
    "\\begin{equation*}\n",
    "    ||x||_{2} = \\left(\\sum_{i=1}^{n} x_{i}^{2} \\right) = \\sqrt{ x^{T} x}.\n",
    "\\end{equation*}\n",
    "\n",
    "The $\\ell_{1}$ norm is a sum of the absolute values of all the components of the vector\n",
    "\\begin{equation*}\n",
    "    ||x||_{1} = \\sum_{i=1}^{n} |x_{i}|.\n",
    "\\end{equation*}\n",
    "\n",
    "The $\\ell_{\\infty}$ norm is the maximum absolute value of a vector\n",
    "\\begin{equation*}\n",
    "    ||x||_{\\infty} = \\max_{i} | x_{i} |.\n",
    "\\end{equation*}\n",
    "\n",
    "### Matrices\n",
    "\n",
    "We will also work a lot with both square and rectangular real matrices which we will write as $A \\in \\mathbb{R}^{m \\times n}$, which denotes a matrix with $m$ rows and $n$ columns. The components of this matrix can be written as\n",
    "\n",
    "\\begin{equation*}\n",
    "    A = \\begin{bmatrix}\n",
    "        A_{11} & A_{12} & \\ldots & A_{1n} \\\\\n",
    "        A_{21} & A_{22} & \\ldots & A_{2n} \\\\\n",
    "        \\vdots & \\vdots &        & \\\\\n",
    "        A_{m1} & A_{m2} & \\ldots & A_{mn} \\\\\n",
    "    \\end{bmatrix}\n",
    "\\end{equation*}\n",
    "\n",
    "### Eigenvalues and Eigenvectors\n",
    "\n",
    "In this course it is *very* important to understand eigenvalues and eigenvectors. In this course, we will work entirely with eigenvalues of real, square matrices. In other words $A \\in \\mathbb{R}^{n \\times n}$, with $A = A^{T}$. This space of matrices is sometimes written as $A \\in \\mathbb{S}^{n}$.\n",
    "\n",
    "The eigenvalue problem can be written as\n",
    "\\begin{equation*}\n",
    "    A q = \\lambda q,\n",
    "\\end{equation*}\n",
    "where $\\lambda \\in \\mathbb{R}$ is a real scalar and $q \\in \\mathbb{R}^{n}$ is a vector. There are $n$ eigenvalues and eigenvector pairs. The eigenvectors are linearly independent and span $\\mathbb{R}^{n}$. Note that if you scale the eigenvector by a constant, $\\alpha \\in \\mathbb{R}$, then $\\alpha q$ is also an eigenvector. As a result, it is common to normalize the eigenvectors such that $||q||_{2} = 1$. Other normalizations are possible, such as $||q||_{\\infty} = 1$, so be careful if you're computing the eigenvalues using a library.\n",
    "\n",
    "The eigenvalues can be arranged into a diagonal matrix $\\Lambda \\in \\mathbb{R}^{n \\times n}$ where\n",
    "\\begin{equation*}\n",
    "    \\Lambda = \\text{diag}\\{\\lambda_{1}, \\lambda_{2}, \\ldots, \\lambda_{n}\\},\n",
    "\\end{equation*}\n",
    "where $\\lambda_{i}$ denote the eigenvalues of the matrix $A$. The eigenvectors, $q_{i} \\in \\mathbb{R}^{n}$, can be arranged column-wise in a matrix $Q \\in \\mathbb{R}^{n \\times n}$\n",
    "\\begin{equation*}\n",
    "    Q = \\begin{bmatrix} q_{1} & q_{2} & \\ldots & q_{n} \\end{bmatrix}.\n",
    "\\end{equation*}\n",
    "\n",
    "With these definitions, all the eigenvalues satisfy the identity\n",
    "\\begin{equation*}\n",
    "    A Q = Q \\Lambda.\n",
    "\\end{equation*}\n",
    "\n",
    "If the eigenvectors are normalized with respect to the $\\ell_{2}$ norm, then $q_{i}^{T} q_{i} = 1$. In addition, the eigenvectors are *orthogonal* such that $q_{i}^{T} q_{j} = 0$ when $i \\ne j$. Using these relationships you can find that\n",
    "\\begin{equation*}\n",
    "    Q^{T} Q = I,\n",
    "\\end{equation*}\n",
    "where $I$ is the identity matrix. *Verify this identity for yourself.*\n",
    "\n",
    "There are several important facts about eigenvalues of real symmetric matrices that it is important to know. These can be found in any textbook on linear algebra.\n",
    "\n",
    "1. The eigenvalues of $A = A^{T}$ are real (not complex)\n",
    "2. A is diagonalizable such that $A = Q \\Lambda Q^{T}$ or $\\Lambda = Q^{T} A Q$. The first form of this equation can also be written as\n",
    "\\begin{equation*}\n",
    "    A = \\sum_{i=1}^{n} \\lambda_{i} q_{i} q_{i}^{T}\n",
    "\\end{equation*}\n",
    "3. If any eigenvalue of a matrix is zero ($\\lambda_{i} = 0$ for some $i$), then the matrix is singular\n",
    "\n",
    "#### Definitions\n",
    "\n",
    "A real symmetric matrix is often classified according to its eigenvalues.\n",
    "\n",
    "1. If the eigenvalues of $A$ are all strictly positive $\\lambda_{i} > 0$, then the matrix $A$ is called *positive definite*. This is also equivalent to demonstrating that $x^{T} A x \\ge \\alpha x^{T} x$ for some $\\alpha > 0$.\n",
    "2. If the eigenvalues of $A$ are non-negative such that $\\lambda_{i} \\ge 0$, then the matrix $A$ is called *positive semi-definite*. Note that since we possibly have $\\lambda_{i} = 0$, $A$ may be singular when $A$ is only positive semi-definite. \n",
    "3. If the eigenvalues of $A$ are both positive and negative, then $A$ is called *indefinite*.\n",
    "4. If $\\lambda_{i} < 0$ then $A$ is *negative definite*.\n",
    "5. If $\\lambda_{i} \\le 0$ then $A$ is *negative semi-definite*.\n",
    "\n",
    "\n",
    "## Examples\n",
    "\n",
    "It's important to get used to computing the eigenvalues and eigenvectors of small matrices and to understand how they're computed numerically. To get a handle on this we'll consider a few simple cases.\n",
    "\n",
    "In all computational examples, we'll use the eigh function from python package numpy.linalg. The documentation for this package can be found here: \n",
    "\n",
    "https://docs.scipy.org/doc/numpy-1.15.0/reference/generated/numpy.linalg.eigh.html\n",
    "\n",
    "1. First consider the simple diagonal matrix\n",
    "\\begin{equation*}\n",
    "    A = \\begin{bmatrix}\n",
    "    1 & 0 \\\\\n",
    "    0 & 2 \\\\\n",
    "    \\end{bmatrix}\n",
    "\\end{equation*}\n",
    "You can immediately see that it is already diagonal, so that $A = \\Lambda$ in this case with $Q = I$. In other words, the eigenvalues are $\\lambda_{1} = 1$ and $\\lambda_{2} = 2$, and the eigenvectors are $q_{1} = (1, 0)$ and $q_{2} = (0,1 )$. Don't waste time trying to compute the eigenvalues and eigenvectors of a diagonal matrix. This matrix is positive definite.\n",
    "\n",
    "2. A more complicated case is the matrix\n",
    "\\begin{equation*}\n",
    "    A = \\begin{bmatrix}\n",
    "        2 & 1 \\\\\n",
    "        1 & 2 \\\\\n",
    "    \\end{bmatrix}\n",
    "\\end{equation*}\n",
    "Note that in this case, when multiplying $A$ by the vector $v = (1, 1)$ gives $Av = (3, 3) = 3 v$. In other words $\\lambda_{1} = 3$ and $q_{1} = (1, 1)/\\sqrt{2}$. The second eigenvector must be orthogonal to $v$ so it has to be along the direction $v = (1, -1)$ (so that $v^{T}q_{1} = 0$. Note that $Av = (1, -1) = v$ so the second eigenvalue is $\\lambda_{2} = 1$, and $q_{2} = (1, -1)/\\sqrt{2}$. This matrix is positive definite.\n",
    "\n",
    "3. Another more complex case is\n",
    "\\begin{equation*}\n",
    "    A = \\begin{bmatrix}\n",
    "        1 & -1 \\\\\n",
    "        -1 & 1 \\\\\n",
    "    \\end{bmatrix}\n",
    "\\end{equation*}\n",
    "Note that in this case $v = (1, 1)$ satisfies $Av = 0$, so $\\lambda_{1} = 0$, $q_{1} = (1, 1)/\\sqrt{2}$ is the first eigen pair. This eigenvector is in the *null space* of the matrix $A$, such that $Av = 0$. The other eigenvector must be orthogonal to this vector so that $v = (1, -1)$. Note that $A v = (2, -2) = 2 v$ so that $\\lambda_{2} = 2$ and $q_{2} = (1, -1)/\\sqrt{2}$. This matrix is positive semi-definite and singular (its inverse does not exist).\n",
    "\n",
    "4. Randomly generated matrix. This example computes the eigenvalues of a randomly generated matrix $A = A^{T} \\in \\mathbb{R}^{10 \\times 10}$. Note the eigenvalues are returned by numpy in sorted in increasing order.\n",
    "\n",
    "5. Construct a matrix with known eigenvalues. In this example, we construct a matrix with known eigenvalues (eigenspectra) by first computing an orthonormal matrix using QR decomposition. Details of the QR decomposition can be found here: https://docs.scipy.org/doc/numpy-1.10.1/reference/generated/numpy.linalg.qr.html.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lam =  [1. 2.]\n",
      "Q =  [[1. 0.]\n",
      " [0. 1.]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "A = np.array([[1, 0], [0, 2]])\n",
    "lam, Q = np.linalg.eigh(A)\n",
    "print('lam = ', lam)\n",
    "print('Q = ', Q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lam =  [1. 3.]\n",
      "Q =  [[-0.70710678  0.70710678]\n",
      " [ 0.70710678  0.70710678]]\n"
     ]
    }
   ],
   "source": [
    "A = np.array([[2, 1], [1, 2]])\n",
    "lam, Q = np.linalg.eigh(A)\n",
    "print('lam = ', lam)\n",
    "print('Q = ', Q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lam =  [0. 2.]\n",
      "Q =  [[-0.70710678 -0.70710678]\n",
      " [-0.70710678  0.70710678]]\n"
     ]
    }
   ],
   "source": [
    "A = np.array([[1, -1], [-1, 1]])\n",
    "lam, Q = np.linalg.eigh(A)\n",
    "print('lam = ', lam)\n",
    "print('Q = ', Q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lam =  [-2.28878484 -1.38557068 -1.10697969 -0.27015127 -0.10155179  0.32096373\n",
      "  0.74241123  1.44807113  2.12179769  9.59556492]\n"
     ]
    }
   ],
   "source": [
    "B = np.random.uniform(size=(10, 10)) # Create a random matrix of size (10 times 10)\n",
    "A = B + B.T # Make the matrix symmetric\n",
    "lam, Q = np.linalg.eigh(A)\n",
    "print('lam = ', lam)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lam2 =  [ 1.  2.  3.  4.  5.  6.  7.  8.  9. 10. 11. 12. 13. 14. 15.]\n"
     ]
    }
   ],
   "source": [
    "n = 15 # Dimension of the matrix that will be generated\n",
    "B = -1.0 + 2*np.random.uniform(size=(n, n)) # Randomly generated matrix that will be used to generate the eigenvectors\n",
    "Q, r = np.linalg.qr(B, mode='complete') # Construct Q\n",
    "lam = np.linspace(1, n, n) # Create a uniform set of eigenvalues\n",
    "A = np.dot(Q, np.dot(np.diag(lam), Q.T)) # Compute A = Q*Lambda*Q^{T}\n",
    "lam2, Q2 = np.linalg.eigh(A)\n",
    "print('lam2 = ', lam2)"
   ]
  },
  {
   "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}