1. Linear Algebra 1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "# Scalars\n",
    "x = 2\n",
    "print x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tensors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **vector** is a collection of scalars.  \n",
    "For instance, two coordinates $(x, y)$ to represent a point on a plane.\n",
    "\n",
    "In general, we say that a vector is $n$-dimensional, i.e. in $\\mathbb{R}^n$.  \n",
    "In particular, the following example is in $\\mathbb{R}^3$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 2 1]\n",
      "(3,)\n"
     ]
    }
   ],
   "source": [
    "# Vectors\n",
    "x = np.array( [1, 2, 1] )\n",
    "print x\n",
    "print x.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **matrix** instead is said to be in $R^{m \\times n}$.  \n",
    "In particular, the following example belongs to $R^{2 \\times 3}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1 2 1]\n",
      " [2 1 2]]\n",
      "(2, 3)\n"
     ]
    }
   ],
   "source": [
    "# Matrices\n",
    "x = np.array([[1, 2, 1],\n",
    "              [2, 1, 2]])\n",
    "print x\n",
    "print x.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Tensors** generalize the concept of matrices to higher orders.  \n",
    "An $N^{th}$ order tensor belongs to the set $R^{n_1 \\times n_2 \\times \\dots \\times n_N}$.  \n",
    "In particular, the following example is in $R^{4 \\times 2 \\times 3}$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[[1 2 1]\n",
      "  [2 1 2]]\n",
      "\n",
      " [[1 2 1]\n",
      "  [2 1 2]]\n",
      "\n",
      " [[1 2 1]\n",
      "  [2 1 2]]\n",
      "\n",
      " [[1 2 1]\n",
      "  [2 1 2]]]\n",
      "(4, 2, 3)\n"
     ]
    }
   ],
   "source": [
    "x = np.array([[[1, 2, 1], [2, 1, 2]],\n",
    "              [[1, 2, 1], [2, 1, 2]],\n",
    "              [[1, 2, 1], [2, 1, 2]],\n",
    "              [[1, 2, 1], [2, 1, 2]]])\n",
    "print x\n",
    "print x.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that matices of size $m \\times n$ can be flattened out to form a vector of size $mn$.  \n",
    "Similarly, tensors can be flattened out to form vectors of size $n_1 n_2 \\dots n_N$.  \n",
    "\n",
    "We say that the two spaces are **isomorphic**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Vector Space\n",
    "\n",
    "$\\mathbb{R}^3$ over $\\mathbb{R}$ gives us the coordinate system for 3 dimensional geometry.  \n",
    "A **vector space** $V$ over $F$ is a generalization of this notion."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we have an operator $+$:\n",
    "1. $x, y \\in V \\implies x + y \\in V$\n",
    "2. $x + y = y + x$, i.e. $+$ is **commutative**\n",
    "3. $x + (y + z) = (x + y) + z$, i.e. $+$ is **associative**\n",
    "4. There is a **zero** such that $x + 0 = 0 + x = x$\n",
    "4. There is an **additive inverse** such that $x + (-x) = (-x) + x = 0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also have an operator $\\cdot$, for scalar multiplication:\n",
    "1. $x \\in V, \\alpha \\in R \\implies \\alpha \\cdot x \\in V$\n",
    "2. $\\alpha \\cdot (x + y) = \\alpha \\cdot x + \\alpha \\cdot y$\n",
    "3. $(\\alpha + \\beta) \\cdot x = \\alpha \\cdot x + \\beta \\cdot x$\n",
    "4. $(\\alpha \\beta) \\cdot x = \\alpha \\cdot (\\beta \\cdot x)$\n",
    "5. There is a **one** such taht $1 \\cdot x = x$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's take a moment to go back to vectors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "x1 = np.array([1, -2, 1])\n",
    "x2 = np.array([0, 1, 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can measure the standard Euclidean distance between these vectors:  \n",
    "$$\\lVert x_1 - x_2\\rVert_2 = \\sqrt{\\sum_{i=0}^2 ((x_1)_i - (x_2)_i)^2}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.74165738677\n"
     ]
    }
   ],
   "source": [
    "distance = 0\n",
    "\n",
    "for i in range(3):\n",
    "    distance += (x1[i] - x2[i]) ** 2\n",
    "\n",
    "distance = distance ** 0.5\n",
    "print distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The quantity $\\lVert x \\lVert_2$ is called the **Euclidean norm** or **$L_2$ norm**.  \n",
    "Here's a handy helper method that allows us to compute the distance:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.74165738677\n",
      "[ 1 -3 -2]\n"
     ]
    }
   ],
   "source": [
    "print np.linalg.norm(x1 - x2)\n",
    "print x1-x2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are a number of other useful norms:\n",
    "1. **$L_2$ norm:** $$\\lVert x \\rVert_1 = \\sum_{i} \\left| x_i \\right|$$\n",
    "2. **$L_1$ norm:** $$\\lVert x \\rVert_2 = \\sqrt{\\sum_{i} x_i^2}$$\n",
    "3. **Infinity norm:** $$\\lVert x \\rVert_\\infty = \\arg\\max_{i} \\left| x_i \\right|$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1 -3 -2]\n",
      "6.0\n",
      "3.74165738677\n",
      "3.0\n"
     ]
    }
   ],
   "source": [
    "print x1 - x2\n",
    "print np.linalg.norm(x1 - x2, ord=1)\n",
    "print np.linalg.norm(x1 - x2, ord=2)\n",
    "print np.linalg.norm(x1 - x2, ord=np.inf)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Inner Product Space and Distance Metrics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$(\\mathbb{R}^3, \\lVert \\cdot \\rVert_2)$ forms the basis for Euclidean 3 dimensional geometry.  \n",
    "We can generalize this to the notion of a **inner product space** of $(V, d)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In particular, we say that $d$ is a distance if it satisfies:  \n",
    "1. Non-negativity: $d(x,y) \\ge 0$ and $d(x, y) = 0 \\iff x = y$\n",
    "2. Symmetric: $d(x,y) = d(y,x)$\n",
    "3. Triangle inequality: $d(x,z) \\le d(x,y) + d(y,z)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Try it!**  \n",
    "Check that $\\lVert \\cdot \\rVert_1$ and $\\lVert \\cdot \\rVert_\\infty$ are valid distance metrics."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear Independence and Basis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A set of vectors $x_1, x_2, \\dots x_n$ is said to be **linearly independent** if there is no way to write one as a linear combination of the others, i.e.:\n",
    "\n",
    "$$x_i \\neq \\sum_{j \\ne i} \\alpha_j x_j$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 0 0] \n",
      "[0 1 0] \n",
      "[0 0 1]\n"
     ]
    }
   ],
   "source": [
    "x1 = np.array([1, 0, 0])\n",
    "x2 = np.array([0, 1, 0])\n",
    "x3 = np.array([0, 0, 1])\n",
    "\n",
    "print x1, \"\\n\", x2, \"\\n\", x3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's easy to see that you cannot express $(1, 0, 0)$ as a sum of $(0, 1, 0)$ and $(0, 0, 1)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A **basis** is a set of linearly independent vectors that make up the whole space.  \n",
    "It is easy to see that $x_1$, $x_2$, $x_3$ as defined above make up the whole of $\\mathbb{R}^3$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[444 178 250]\n",
      "[444 178 250]\n"
     ]
    }
   ],
   "source": [
    "x = np.random.randint(1, 1000, size=(3,))\n",
    "print x\n",
    "print x[0] * x1 + x[1] * x2 + x[2] * x3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Result:** Any linearly independent set of cardinality $N$ is a basis of $\\mathbb{R}^N$ (why?)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}