2-Vector spaces.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Vector space and subspace\n",
    "Vector spaces are denoted by $\\mathbb{R}^{1},\\mathbb{R}^{2},\\mathbb{R}^{3},\\ldots,\\mathbb{R}^{n}$. The space $\\mathbb{R}^{n}$ consists of *all column vectors with n components, i.e. n-dimensions*. $\\mathbb{R}^{1}$ is a **line**, $\\mathbb{R}^{2}$ is a **x-y plane**, $\\mathbb{R}^{3}$ is a **3-D space**. For a vector in $\\mathbb{R}^{1}$ we just need the seven components, even if the geometry is hard to visualize.\n",
    "\n",
    "We can add any two vectors, and we can multiply all vectors by scalars. In other words, we can take **linear combinations** ($x + y$, $cx$).\n",
    "\n",
    "A real **vector space** is a set of vectors together with rules for vector addition and multiplication by real numbers.  **All combinations stay in the same space**. E.g. 1/4 x-y plant is not a vector space since it is not closed.\n",
    "\n",
    "A **subspace** of a vector space is a nonempty subset that satisfies the requirements for a vector space: *Linear combinations stay in the subspace*. **Any subspace include the origin**.\n",
    "\n",
    "1. If we add any vectors x and y in the subspace, x+ y is in the subspace.\n",
    "2. If we multiply any vector x in the subspace by any scalar c, cx is in the subspace. The zero vector (c = 0, zero-dimension, the smallest possible vector space) will belong to every subspace. \n",
    "\n",
    "E.g. sub-space of $\\mathbb{R}^{2}$: 1. all of $\\mathbb{R}^{2}$, 2. lines through origin, 3. origin (0,0). Sub-space of $\\mathbb{R}^{3}$: 1. all of $\\mathbb{R}^{3}$, 2. plane through origin, 3. lines through origin, 4. origin (0,0).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Column space -- C(A)\n",
    "The column space contains all linear combinations of the columns of A (m rows by n cols matrix). It is a subspace of $\\mathbb{R}^{m}$.\n",
    "\n",
    "The system $Ax = b$ is **solvable if and only if** the vector *b* can be expressed as a combination of the columns of *A*. That is: ***b* is in the column space**. \n",
    "\n",
    "E.g. $$\\begin{bmatrix}1 & 0\\\\\n",
    "5 & 4\\\\\n",
    "2 & 4\n",
    "\\end{bmatrix}\\begin{bmatrix}u\\\\\n",
    "v\n",
    "\\end{bmatrix}=\\begin{bmatrix}b_{1}\\\\\n",
    "b_{2}\\\\\n",
    "b_{3}\n",
    "\\end{bmatrix}=u\\begin{bmatrix}1\\\\\n",
    "5\\\\\n",
    "2\n",
    "\\end{bmatrix}+v\\begin{bmatrix}0\\\\\n",
    "4\\\\\n",
    "4\n",
    "\\end{bmatrix}$$\n",
    "\n",
    "When m > n we have more equations than unknowns (and usually there will be no solution). In this example, we have 3 equations and 2 unknowns. **$Ax = b$ can be solved if and only if b lies in the plane that is spanned by the two column vectors**. The column space is a plane defined by the two column vectors. $Ax$ is actually combinations of column vectors, which will stay in the plant. Therefore, vector *b* needs also from this plane to satisfy the equality. For vectors from outside of this plane, no solutions can make the equality. \n",
    "\n",
    "But if $m = n$, i.e. same number of equations and unknowns, and A is nonsingular, then the column space is the whole $\\mathbb{R}^{m}$ and every b is in C(A) thus there will be solutions.\n",
    "\n",
    "### The nullspace of A -- N(A)\n",
    "The solutions to $Ax = 0$ form a vector space—the nullspace of A (m rows by n cols matrix). It is a subspace of $\\mathbb{R}^{n}$.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solving $Ax = 0$ and $Ax = b$\n",
    "We want to be able, for any system $Ax = b$, to find C(A) and N(A): all attainable right-hand sides b and all solutions to $Ax = 0$.\n",
    "\n",
    "For an invertible matrix, the nullspace contains only $x = 0$ (multiply $Ax = 0$ by $A^{−1}$). The column space is the whole space ($Ax = b$ has a solution for every b). The **new questions** appear when the nullspace contains *more than the zero vector* and/or the column space contains *less than all vectors*:\n",
    "\n",
    "1. Any vector $x_n$ in the nullspace can be added to a particular solution $x_p$. The solutions to all linear equations have this form, $x = x_p + x_n$: **Complete solution $Ax_p = b$ and $Ax_n = 0$ produce $A(x_p + x_n) = b$**.\n",
    "2. When the column space doesn’t contain every b in $\\mathbb{R}^{m}$, we need the conditions on b that make $Ax = b$ solvable.\n",
    "\n",
    "Example: $0x = b$: it has no solutions unless b = 0 since the column space contains only 0; $0x = 0$ has infinitely many solutions as the null space contains all x. Here a particular solution is $x_p = 0$, ans the complete solution is $x = x_p + x_n = 0 + (any\\ x)$\n",
    "\n",
    "**Echelon matrix U**: upper triangular, but its pivots are not on the main diagonal. With a rectangular matrix, we expect trouble when do elimination (zeros in the pivots position and no row exchange can fix it), we need to *go on to the next column*. We can always reach this echelon form U (staircase pattern), with zeros below the pivots:\n",
    "\n",
    "1. The pivots are the first nonzero entries in their rows.\n",
    "2. Below each pivot is a column of zeros, obtained by elimination.\n",
    "3. Each pivot lies to the right of the pivot in the row above. This produces the staircase pattern, and zero rows come last.\n",
    "\n",
    "**For any m by n matrix A there is a permutation P, a lower triangular L with unit diagonal, and an m by n echelon matrix U, such that PA = LU**.\n",
    "\n",
    "**From U to R** to make the matrix even simpler: all pivots are 1, and zeros above and below pivots. **reduced row echelon form R**.\n",
    "\n",
    "To find complete solutions to $Ax = b$:\n",
    "\n",
    "1. Find $x_{particular}$: set all free variables (columns without pivot) in A to zero, then solve $Ax = b$.\n",
    "2. Find $x_{nullspace}$.\n",
    "3. $x_{complete} = x_{particular} + x_{nullspace}$\n",
    "\n",
    "Suppose elimination reduces $Ax = b$ to $Ux = c$ and $Rx = d$, with r pivot rows and r pivot columns. The rank of those matrices is r. The last $m − r$ rows of U and R are zero, so there is a solution only if the last $m − r$ entries of c and d are also zero."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "m rows by n columns matrix A with rank r ($r \\leq m,r \\leq n$). The rank r tells you almost everything about the solutions of $Ax = b$. *The rank counts the number of genuinely independent rows in the matrix A.*\n",
    "\n",
    "$r = m = n$ | $r = n < m$ | $r = m <n$ | $r < m,\\ r < n$\n",
    ":------:|:------:|:------:|:------:\n",
    "R = rref(A) = $I$  |$R=\\begin{bmatrix}I\\\\0\\end{bmatrix}$ |$R=\\begin{bmatrix}I & F\\end{bmatrix}$  | $R=\\begin{bmatrix}I & F\\\\0 & 0\\end{bmatrix}$ \n",
    "full rank, square invertible matrix | no free variables, N(A) = 0 | n - m free variables, can solve every b | normal case\n",
    "1 solution to $Ax=b$ | 0 or 1 solution | infinite solutions | 0 or infinite solutions\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $c_1v_1 + ··· + c_kv_k = 0$ only happens when $c_1 = ··· = c_k = 0$. Then the vectors $v_1,..., v_k$ are **linearly independent**. If any c’s are nonzero, the v’s are linearly dependent. One vector is a combination of the others.\n",
    "\n",
    "The columns of A are independent exactly when N(A) = {zero vector}.\n",
    "It is the columns with pivots that are guaranteed to be independent. \n",
    "\n",
    "Linear dependence is easy to visualize in three-dimensional space, when all vectors go out from the origin. Two vectors are dependent if they lie on the same line. Three vectors are dependent if they lie in the same plane. \n",
    "\n",
    "Vectors v1, v2, ..., vl **span** a space means: the space consists of all combinations of these vectors.\n",
    "\n",
    "**Basis** for a space ois a sequence of vectors with two properties: 1. they are independent; 2. they span the space. E.g in 3-d space, x, y, z unit axis form one basis. Space can have more than one basis. N vectors give basis of the n by n matrix with those columns is invertible. Every basis for the space have the same number of vectors: the dimension of the space.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Four Fundamental Subspaces\n",
    "\n",
    "1. Column space C(A)\n",
    "2. Null space N(A)\n",
    "3. Row space: all combinations of rows = all combinations of columns of $A^T$ = C($A^T$)\n",
    "4. Null space of $A^T$: N($A^T$) = left null space of A.\n",
    "\n",
    "If A has m rows and n columns, with rank = r\n",
    "\n",
    "|                  |      $C(A)$      |      $C(A^T)$     |                $N(A)$               |     $N(A^T)$     |\n",
    "|:----------------:|:----------------:|:-----------------:|:-----------------------------------:|:----------------:|\n",
    "|       Basis      |   Pivot columns  | First r rows of R | Special solutions of free variables |                  |\n",
    "|    Dimension    |      $r$      |       $r$     |                $n-r$                |       $m-r$      |\n",
    "| Within space of: | $\\mathbb{R}^{m}$ |  $\\mathbb{R}^{n}$ |           $\\mathbb{R}^{n}$          | $\\mathbb{R}^{m}$ |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### invertiblitity of sqaure matrix\n",
    "Each of these conditions is a necessary and sufficient test. Every conditions is equivalent to every other and ensure that A is invertible.\n",
    "\n",
    "1. The columns span $\\mathbb{R}^{n}$ , so $Ax = b$ has at least one solution for every $b$.\n",
    "2. The columns are independent, so $Ax = 0$ has only the solution $x = 0$.\n",
    "3. The rows of A span $\\mathbb{R}^{n}$.\n",
    "4. The rows are linearly independent.\n",
    "5. Elimination can be completed: PA = LDU, with all n pivots.\n",
    "6. The determinant of A is not zero.\n",
    "7. Zero is not an eigenvalue of A.\n",
    "8. $A^TA$ is positive definite."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### linear transformation\n",
    "90 degree rotations Q, projections P (onto the x-axis), reflections H (through the 45 degree line)\n",
    "\n",
    "$Q=\\begin{bmatrix}0 & -1\\\\\n",
    "1 & 0\n",
    "\\end{bmatrix}$\n",
    "\n",
    "$P=\\begin{bmatrix}1 & 0\\\\\n",
    "0 & 0\n",
    "\\end{bmatrix}$\n",
    "\n",
    "$H=\\begin{bmatrix}0 & 1\\\\\n",
    "1 & 0\n",
    "\\end{bmatrix}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}