linear-algebra/linear-algebra-concepts.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vector Definitions\n",
    "\n",
    "- \"Physics definition\"\n",
    "  - a pointed segment in space\n",
    "- \"Computer science deffinition\"\n",
    "  - a list of obecjts (usually numbers)\n",
    "  - dimensions = length\n",
    "- Math Definition\n",
    "  - encompasses both and allow even more abstraction $\\vec{v}$\n",
    "  - vectors can be added and multiplied (by numbers and by other vectors)\n",
    "  - similar to how we define a field\n",
    "- another perspective\n",
    "  - transformations\n",
    "  - actually, things can be more complicated (tensors)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vector Components\n",
    "\n",
    "- the distance to all coordinate axes: $v_x, v_y$\n",
    "- equivalent to:  $[\\frac{v_x}{v_y}]$\n",
    "  - polar coordinates: $ v = |\\vec{v}|, \\theta$\n",
    "- finding components\n",
    "  - Pythagoras: $ v_x = vcos(\\theta), v_y = vsin(\\theta)$\n",
    "- finding the polar form (magnitude, direction):\n",
    "  - $v = \\sqrt{v_x^2 + v_y^2}, \\theta = tan^{-1}(\\frac{v_y}{v_x})$\n",
    "- all this operations generalize to more than 2 dimensions\n",
    "**note** - we usually denote vectors by $\\vec{v}$ or with bold **$v$**  \n",
    "![Vector Components](vector-components.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vector Operations\n",
    "\n",
    "- addition\n",
    "  - result:   \n",
    "  **length** = distance from start to end,   \n",
    "  **direction**: start $\\rightarrow$ end\n",
    "  - in component form: sum all components for every direction\n",
    "  ![Vector addition](vector-addition.png)\n",
    "- multiplication by a number (scalar)\n",
    "  - result:   \n",
    "  **length** = scaled length,   \n",
    "  **direction**: same (if scalar $\\geq$ 0, opposite otherwise)\n",
    "  - in component form: multiply each component by the number\n",
    "  ![Vector scalar](vector-scalar.png)\n",
    "- scalar product of two vectors\n",
    "  - also called **dot product** or **inner product**\n",
    "  - result: scalar\n",
    "  - definition: $\\vec{a} . \\vec{b} = |\\vec{a}||\\vec{b}|cos(\\theta)$\n",
    "  - using the vectors components: $ \\vec{a} x \\vec{b} = \\sum\\limits_{i=1}^n {a_i b_i}$ \n",
    "  ![Dot/inner product](dot-product.png)\n",
    "- vector product of two vectors\n",
    "  - also called **cross product**\n",
    "  - result: vector, perpendiculant to both initial vectors\n",
    "  - definition: $\\vec{a} x \\vec{b} = |\\vec{a}||\\vec{b}|sin(\\theta)\\vec{n}$\n",
    "    - $\\vec{n}$ - normal vector\n",
    "    - magnitude: $|\\vec{a}||\\vec{b}|sin(\\theta)$ - volume of parallelogram between $\\vec{a}$ and $\\vec{b}$\n",
    "    - direction: coincides with the direction of $\\vec{n}$\n",
    "    ![Cross product](cross-product.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vector Space\n",
    "\n",
    "- a field (usually $\\mathbb{R}$ or $\\mathbb{C}$): F\n",
    "- a set of elements (vectors): $V$\n",
    "- operations\n",
    "  - additions of two vectors: $w = u + v$\n",
    "  - multiplication by element of the field: $w = \\lambda u$\n",
    "- a check list of [eight axioms of vector space](http://mathworld.wolfram.com/VectorSpace.html)\n",
    "- we read this as \"vector space (or linear space) V over the field F\"\n",
    "- **examples** of vectors spaces:\n",
    "  - coordinate space, e.g. real coordinate space $\\mathbb{R}^n$\n",
    "    - $n$ dimensional vectors\n",
    "  - infinite coordinate space $\\mathbb{R}^\\infty$\n",
    "    - vectors with infinitely many components\n",
    "  - polynomial space\n",
    "    - all polynomials of variable $x$ with real coefficients $\\mathbb{R}[x]$\n",
    "  - function space"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Combinations\n",
    "\n",
    "- Vectors: $v_1, v_2, ... , v_n$\n",
    "- Numbers (scalars): $\\lambda_1, \\lambda_2, ... , \\lambda_n$\n",
    "- Linear Combinations\n",
    "  - the sum of each vector multiplied by a scalar coefficient  \n",
    "  $\\lambda_1 v_1 + \\lambda_2 v_2 + ... \\lambda_n v_n = \\sum{\\lambda_i v_i}$\n",
    "  - **why linear?** - no fancy functions, no vector multiplications\n",
    "- span (linear hull) of vectors: the set of all their linear combinations\n",
    "- Linear (in)dipendence\n",
    "  - the vectors $v_1, v_2, ... , v_n$ are **lineary independent** if the only solution of the equation $\\lambda_1 v_1 + \\lambda_2 v_2 + ... \\lambda_n v_n = \\vec{0}$ **is** $\\lambda_1 = 0, \\lambda_2 = 0 ... \\lambda_n = 0$\n",
    "  - conversely, they are **linery dependent** if there is a non-trivial linear combination which is equal to zero\n",
    "  - example:  \n",
    "  $u = (2, -1, 1), v = (3, -4, -2), w = (5, -10, -8)$  \n",
    "  $w = -2u + 3v \\Rightarrow 2u - 3v + 1w = 0$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic Vectors\n",
    "\n",
    "![Basic Vectors](basic-vectors.png)\n",
    "- consider: i = (1, 0), j = (0, 1)\n",
    "- now consider the vector a = (-2, 1)\n",
    "- we can see that we can express **a** as the linear combination $ a = -2\\hat{i} + 1\\hat{j}$\n",
    "- **linearly independent**\n",
    "- every other vector in the space can be represented as their linear combination\n",
    "  - this linear combination is unique\n",
    "- **each vector space has a basis**\n",
    "- each pair of two linear vectors forms a basis in 2D coordinate space\n",
    "  - more generally, each sets of n linear vectors forms a basis in n-dimensional vector space "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Matrix\n",
    "\n",
    "- a rectangular table of numbers\n",
    "- dimensions: rows x columns\n",
    "  - may also be infinite\n",
    "- examples:  \n",
    "$ A = \\begin{bmatrix} \n",
    "1 & 3 & 5\\\\\n",
    "2 & -4.2 & 8 \n",
    "\\end{bmatrix}\n",
    "$\n",
    "$ B = \\begin{bmatrix} \n",
    "2 & -1 & 1\\\\\n",
    "4 & 7 & 12 \\\\\n",
    "0 & 5 & -3\n",
    "\\end{bmatrix}\n",
    "$\n",
    "$ E = \\begin{bmatrix} \n",
    "1 & 0 & 0\\\\\n",
    "0 & 1 & 0 \\\\\n",
    "0 & 0 & 1\n",
    "\\end{bmatrix}\n",
    "$\n",
    "$ R = \\begin{bmatrix} \n",
    "2 & 4 & 3\n",
    "\\end{bmatrix}\n",
    "$\n",
    "$ C = \\begin{bmatrix} \n",
    "3\\\\\n",
    "2\\\\\n",
    "-5\n",
    "\\end{bmatrix}\n",
    "$\n",
    "    - R - row vector, C - column vector\n",
    "- Elements $ a = {a_{ij}}$\n",
    "- some thoughts about dimensions\n",
    "  - scalars has no dimensions: 2; 3; 18, -42; 0,5\n",
    "  - vectors has one dimension: $v = \\{v_i\\}$\n",
    "  - matrices have two dimensions: $A = \\{ v_{ij} \\}$\n",
    "  - a generalizations of this pattern for many dimensions is called a **tensor**\n",
    "    - a tensors are quite more complicated than this, but for almost all purposes it's OK to think about the as multidimensional matrices. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Matrix Operations\n",
    "\n",
    "- additions (the dimensions must be the same)  \n",
    "$ A = \\begin{bmatrix} \n",
    "2 & 3 & 7\\\\\n",
    "8 & 9 & 1 \n",
    "\\end{bmatrix}\n",
    "$,\n",
    "$ B = \\begin{bmatrix} \n",
    "1 & -3 & 0\\\\\n",
    "2 & -4 & 1\n",
    "\\end{bmatrix}\n",
    "\\Rightarrow A + B = \n",
    "\\begin{bmatrix} \n",
    "2+1 & 3-3 & 7+0\\\\\n",
    "8+2 & 9-4 & 1+1\n",
    "\\end{bmatrix} = \n",
    "\\begin{bmatrix} \n",
    "3 & 0 & 7\\\\\n",
    "10 & 5 & 2\n",
    "\\end{bmatrix}\n",
    "$\n",
    "- multiplication by a scalar  \n",
    "$\\lambda = 2, A = \n",
    "\\begin{bmatrix} \n",
    "2 & 3 & 7\\\\\n",
    "8 & 9 & 1 \n",
    "\\end{bmatrix}\n",
    "\\Rightarrow \\lambda A = \n",
    "\\begin{bmatrix} \n",
    "2.2 & 2.3 & 2.7\\\\\n",
    "2.8 & 2.9 & 2.1 \n",
    "\\end{bmatrix} = \n",
    "\\begin{bmatrix} \n",
    "4 & 6 & 14\\\\\n",
    "16 & 18 & 2 \n",
    "\\end{bmatrix}\n",
    "$\n",
    "- transponition: turning rows into columns and vice versa\n",
    "  - the transpose of a matrix is doneted by an upper index T  \n",
    "  $A^T = (a_{ij})_{mxn}^T = (a_{ij})_{nxm}$\n",
    "  - example:  \n",
    "$ A = \\begin{bmatrix} \n",
    "1 & 2 & 0 & 1\\\\\n",
    "-3 & -4 & 1 & 3\\\\\n",
    "2 & 0 & 1 & 1\n",
    "\\end{bmatrix}\n",
    "\\Rightarrow A^T = \n",
    "\\begin{bmatrix} \n",
    "1 & -3 & 2\\\\\n",
    "2 & -4 & 0\\\\\n",
    "0 & 1 & 1 \\\\\n",
    "1 & 3 & 1\n",
    "\\end{bmatrix}\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "source": [
    "## Matrix Multiplication\n",
    "\n",
    "- the dimensions must match: $A_{mxp}B_{pxn} = C_{mxn}$\n",
    "  - \"inner dimensions\" are the same, result has \"outher dimensions\"\n",
    "- definition: $ c_{ij} = \\sum\\limits_{k=1}^p = a_{ik}b_{kk}$\n",
    "- example: \n",
    "\n",
    "$ A = \\begin{bmatrix} \n",
    "2 & 3 & 7\\\\\n",
    "8 & 9 & 1 \n",
    "\\end{bmatrix}\n",
    "$,\n",
    "$ B = \n",
    "\\begin{bmatrix} \n",
    "1 & 2 & 0 & 1\\\\\n",
    "-3 & -4 & 1 & 3 \\\\\n",
    "2 & 0 & 1 & 1\n",
    "\\end{bmatrix}\n",
    "$  \n",
    "\n",
    "$ AB = \\begin{bmatrix} \n",
    "2.1 + 3.(-3) + 7.2 & 2.2 + 3.(-4) + 7.0 & 2.0 + 3.1 + 7.1 & 2.1 + 3.3 + 7.1\\\\\n",
    "8.1 + 9.(-3) + 1.2 & 8.2 + 9.(-4) + 1.0 & 8.0 + 9.1 + 1.1 & 8.1 + 9.3 + 1.1\n",
    "\\end{bmatrix}\n",
    "$    \n",
    "\n",
    "$AB = \\begin{bmatrix} \n",
    "7 & -8 & 10 & 18\\\\\n",
    "-17 & -20  & 10 & 36 \n",
    "\\end{bmatrix}\n",
    "$\n",
    "- note that $AB \\neq BA$\n",
    "  - in some cases, we can't even multiply BA (like above)\n",
    "  - we say that matrix multiplication is not commutative\n",
    "    - compare with multiplication of numbers: $3.5 = 5.3 \\Rightarrow$ commutative\n",
    "![Matrix multiplication](matrix-multiplication.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Matrix Operations in Numpy\n",
    "\n",
    "- in numpy we can use **dot()** for matrix multiplication and dot products\n",
    "- **note** whenever possible, use numpy arrays instead of Python lists\n",
    "  - the perform much faster\n",
    "  - they make the code a lot cleaner\n",
    "```python\n",
    "    A = np.array([\n",
    "      [2, 3, 7],\n",
    "      [8, 9, 1]\n",
    "    ])\n",
    "    B = np.array([\n",
    "      [1, -3, 0],\n",
    "      [2, -4, 1]\n",
    "    ])\n",
    "\n",
    "    print(A+B)\n",
    "    print(2*A)\n",
    "    print(A*B) #Element wise multiplication\n",
    "    print(A.dot(B)) #Error: incompatible dimensions\n",
    "    print(A.dot(B.T)) #Matrix Multiplication\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Transformations\n",
    "\n",
    "- Transformation\n",
    "  - a mapping (function) between two vector spaces $V \\rightarrow W$\n",
    "  - special case: mapping a space onto itself: $V \\rightarrow V$\n",
    "    - this is called linear operator\n",
    "  - each vector of $V$ gets mapped to a vector in $W$\n",
    "    - intuition: think about vectors as points\n",
    "- Linear\n",
    "  - only linear combinations are allowed\n",
    "  - the origin remains fixed\n",
    "  - all lines remain lines (not curves)\n",
    "  - all lines remain evenly spaced (equidistant)\n",
    "- each space has a basis\n",
    "  - all other vectors can be expressed as linear combination of the basis vectors\n",
    "  - **if we know how basis vectors are transformed, we can transfer every other vector**\n",
    "- consider the transformation:  \n",
    "$\n",
    "\\hat{i}’ = \\begin{bmatrix} 1\\\\-1 \\end{bmatrix}, \\hat{j}’ = \\begin{bmatrix} 2\\\\1 \\end{bmatrix} \\Rightarrow \\begin{bmatrix} 1\\\\0 \\end{bmatrix} = \\begin{bmatrix} 1\\\\-1 \\end{bmatrix}, \\begin{bmatrix} 0\\\\1 \\end{bmatrix} = \\begin{bmatrix} 2\\\\1 \\end{bmatrix}\n",
    "$\n",
    "\n",
    "![Linear Transformation](linear-transformation.png)\n",
    "\n",
    "- this operations is called applying the **linear transformation**\n",
    "  - note how applying linear transformation and change of a basis are the same\n",
    "  \n",
    "Useful site for visualization: https://shadanan.github.io/MatVis/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "source": [
    "## Transformation Matrices\n",
    "\n",
    "- consider the same transformation\n",
    "  - $\\hat{i}’ = \\begin{bmatrix} 1\\\\-1 \\end{bmatrix}, \\hat{j}’ = \\begin{bmatrix} 2\\\\1 \\end{bmatrix}$\n",
    "- we applied linear transformation by taking dot products\n",
    "  - therefore we can describe it in another way - using a matrix\n",
    "  - this is called **matrix of the linear transformation**\n",
    "  - it's columns denotes where basis vectors go  \n",
    "  $T = \\begin{bmatrix}1 & 2\\\\-1 & 1 \\end{bmatrix}$\n",
    "- applying the transformation to a vector is the same as multiplying the matrix times the original vector (in that order)  \n",
    "  $v’ = Tv$\n",
    "- example:  \n",
    "  $ T = \\begin{bmatrix}3 & 2\\\\-2 & 1 \\end{bmatrix}, v = \\begin{bmatrix}5\\\\7\\end{bmatrix}$   \n",
    "  \n",
    "  $v’ = \\begin{bmatrix}3 & 2\\\\-2 & 1 \\end{bmatrix} \\begin{bmatrix}5\\\\7\\end{bmatrix} = \\begin{bmatrix}29\\\\-3\\end{bmatrix}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "is_executing": false
    }
   },
   "source": [
    "## Multiple Transformations \n",
    "\n",
    "- we can apply many transformations, one right after the other\n",
    "  - result: composite transformation\n",
    "  - we do this by multiplying **one the left** by the matrix of each transformation \n",
    "  - so, matrix multiplications $\\equiv$ applying many transformations\n",
    "- intuition\n",
    "  - apply each transformation in order\n",
    "  - after the last one, record where the basis vectors land\n",
    "  - the new matrix is matrix of composite transformation\n",
    "- we can either apply all transofrmations one by one or just the resulting transformation\n",
    "  - note that second is much, much faster and gives the same result\n",
    "- this is especially useful in computer graphics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Determinant\n",
    "\n",
    "- a linear transformation streches space\n",
    "  - since lines remain parallel and equidistant, space is streched equally, no matter where we look\n",
    "  - a characteristic of the space is \"the unit area\" - a 1x1 square\n",
    "  - the transformation will change that area\n",
    "- **Determinant** - a measure of how much the unit area changes\n",
    "  - scalar value\n",
    "  - defined only for square matrices\n",
    "  - for more that two dimensions, square -> value\n",
    "- determinant of matrix $A$ is denoted $det(A)$\n",
    "  - writen with straight lines\n",
    "  - there are \"easy\" computation rules for 2D and 3D matrices\n",
    "  - generally, the determinant is given by a formula"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear system in Matrix form\n",
    "\n",
    "- consider the linear system  \n",
    "    $ \\begin{cases}\n",
    "    2x - 5y + 3z = - 3\\\\\n",
    "    4x + 0y + 8z = 0\\\\\n",
    "    1x + 3y + 0z = 2\n",
    "    \\end{cases} $\n",
    "- unknown variables - x, y, z\n",
    "- we can represent this as a matrix equation  \n",
    "$\\begin{bmatrix}2 & -5 & 3\\\\4 & 0 & 8\\\\1 & 3 & 0\\end{bmatrix} \\begin{bmatrix}x\\\\y\\\\z\\end{bmatrix} = \\begin{bmatrix}-3\\\\0\\\\2\\end{bmatrix}$\n",
    "  - or more generally, $Ax = b$\n",
    "- transformation perspective\n",
    "  - the matrix $A$ specifies a transoformation\n",
    "  - this transoformation was applied to ${\\begin{bmatrix}x & y &z\\end{bmatrix}}^T $ to get ${\\begin{bmatrix}-3 & 0 & 2\\end{bmatrix}}^T $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Inverse Matrix\n",
    "\n",
    "- consider a general, good transformation\n",
    "  - the inverse transformation will \"bring back\" the basis vectors\n",
    "  - e.g. 90 $^{\\circ}$ clockwise rotation $\\Rightarrow$ 90 $^{\\circ}$ countclockwise rotation\n",
    "- the inverse transformation has it's own matrix: $T^{-1}$\n",
    "- if we apply the transformation and the reverse, we'll get our initial result\n",
    "  - this mean nothing will change\n",
    "  - in math terms $T^{-1}T = E$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## \"Bad\" Matrices\n",
    "\n",
    "- if the determinant of the matrix is zero, every element is mapped into a lower dimensional space\n",
    "  - 2D case: $det(A) = 0 \\Rightarrow $ every possible point in the 2D space is mapped onto a single vector\n",
    "    - we can use visualization to confirm this\n",
    "    - we can use our intuition: where is the area equal to zero\n",
    "  - another viewpoint: $det(A) = 0 \\Rightarrow $ linear depentant rows\n",
    "- consequantly, there are many points mapped on the same point\n",
    "  - consider projection as an example\n",
    "- no \"reversible\" function maps many inputs to one output\n",
    "  - the matrix therefore is non-invertible\n",
    "  - $A^{-1}$ does not exist\n",
    "- however solutions to the matrix can sometimes exist\n",
    "\n"
   ]
  }
 ],
 "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"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "metadata": {
     "collapsed": false
    },
    "source": []
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}