ch_3_Four_Fundamental_Subspace.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# THE FOUR FUNDAMENTAL SUBSPACE\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "920af631c2bab3e6"
  },
  {
   "cell_type": "markdown",
   "source": [
    "This section will explain the \"big picture\" of linear algebra.\n",
    "\n",
    "**That picture shows how every m by n matrix A leads to four subspaces -- two subspaces of $R^m$ and two more of $R^n$.**\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "d2e40c6fc207204a"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The first example will be a rank one matrix $uv^T$, where the column space is the line through $u$ and the row space is the line through $v$.\n",
    "\n",
    "The second example moves to 2 by 3.\n",
    "\n",
    "The third example (a 5 by 4 matrix A) will be the incidence matrix of a graph.\n",
    "\n",
    "Graphs have become the most important models in the discrete mathematics.\n",
    "\n",
    "All four subspaces have meaning on the graph. "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "dc068272e39b5b2b"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## EXAMPLE 1\n",
    "\n",
    "$$\n",
    "\n",
    "A\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "1 & 2 \\\\\n",
    "3 & 6 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "uv^T\n",
    "\n",
    "\\:\\:has\\:m=2\\:and\\:n=2\\:.\n",
    "$$\n",
    "$$\n",
    "\\:We\\:have\\:subspaces\\:of\\:R^2.\n",
    "\n",
    "\n",
    "$$\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "aed5224e7a46bfbf"
  },
  {
   "cell_type": "markdown",
   "source": [
    "1-) The column space C(A) is the line through $u$ = $ \\begin{bmatrix}\n",
    "\n",
    "1  \\\\\n",
    "3  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "$. Column 2 is on that line."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "62dc4f9b76e6adc0"
  },
  {
   "cell_type": "markdown",
   "source": [
    "2-) The row space $C(A^T)$ is the line through $v$ = $ \\begin{bmatrix}\n",
    "\n",
    "1  \\\\\n",
    "2  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "$. Row 2 of A is on that line."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "155c63b2a992b4c6"
  },
  {
   "cell_type": "markdown",
   "source": [
    "3-) The  nullspace $N(A)$ is the line through $x$ = $ \\begin{bmatrix}\n",
    "\n",
    "2  \\\\\n",
    "-1  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "$. Then $Ax$=0."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "32ce9f32d3fb6714"
  },
  {
   "cell_type": "markdown",
   "source": [
    "4-) The  left nullspace $N(A^T)$ is the line through $x$ = $ \\begin{bmatrix}\n",
    "\n",
    "3  \\\\\n",
    "-1  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "$. Then $A^T y$=0."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "fec2cdddf35862d7"
  },
  {
   "cell_type": "markdown",
   "source": [
    "---------------------------------\n",
    "The column space $C(A)$ contains all combinations of the columns of A.\n",
    "\n",
    "The row space $C(A^T)$ contains all combinations of the columns of $A^T$.\n",
    "\n",
    "The nullspace $N(A)$ contains all solutions x to $Ax$=0\n",
    "\n",
    "The left nullspace $N(A^T)$ contains all solutions $y$ to $A^T y$=0 \n",
    "\n",
    "------------------------------"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "6bc34ec7635091fc"
  },
  {
   "cell_type": "markdown",
   "source": [
    "![fig_1_1](./fig_1_1.png)"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "6a5946a3e0fa817d"
  },
  {
   "cell_type": "markdown",
   "source": [
    "That example had exactly one $u$ and $v$ and $x$ and $y$.\n",
    "\n",
    "All four subspaces were 1 dimensional(just lines).\n",
    "\n",
    "**Always the $u$'s and $v$'s and $x$'s and $y$'s will be independent vectors-they give a \"basis\" for each of the subspace.**\n",
    "\n",
    "A larger matrix will need more than one basis vector per subspace.\n",
    "\n",
    "The choice of basis vectors is a crucial step in computing."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "5d6e1bb133780945"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## EXAMPLE 2"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "bcb2964979e08e6b"
  },
  {
   "cell_type": "markdown",
   "source": [
    "$$\n",
    "\n",
    "B\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "1 & -2 & -2 \\\\\n",
    "3 & -6 & -6 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "$$ \n",
    "\n",
    "has $m$ =2 and $n$=3. Subspaces in $R^3$ and $R^2$."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "43909d19597cfed6"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Going from A to B, two subspaces change and two subspaces do not change.\n",
    "\n",
    "The column space of B is still in $R^2$. It has the same basis vector.\n",
    "\n",
    "But now, there are $n$=3 numbers in the rows of B and left half of below figure is in $R^3$.\n",
    "\n",
    "There is still only one $v$ in the row space!\n",
    "\n",
    "The rank is still $r$=1 because both rows of this B go in the same direction.\n",
    "\n",
    "**With $n$=3 unknowns and only $r$=1 independent equation, $Bx$=0 will have 3-1=2 independent solutions $x_1$ and $x_2$.**\n",
    "\n",
    "All solutions go into the nullspace.\n",
    "\n",
    "$$\n",
    "\n",
    "Bx\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "1 & -2 & -2 \\\\\n",
    "3 & -6 & -6 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "a \\\\\n",
    "b \\\\\n",
    "c \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "0 \\\\\n",
    "0 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "$$\n",
    "\n",
    "has solutions\n",
    "\n",
    "$$\n",
    "\n",
    "\n",
    "\n",
    "x_1\n",
    "\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2 \\\\\n",
    "1 \\\\\n",
    "0 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "\\: and\\:\n",
    "\n",
    "x_2\n",
    "\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2 \\\\\n",
    "0 \\\\\n",
    "1 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "\n",
    "$$\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "3c05749cbaaa46ba"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Those vectors $x_1$ and $x_2$ are called special solutions.\n",
    "\n",
    "They come from the steps of elimination--and you quickly see that $Bx_1$ = 0 and $Bx_2$=0."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "a57a96dbdab11f14"
  },
  {
   "cell_type": "markdown",
   "source": [
    "But those are not perfect choices in the nullspace of B because the vectors $x_1$ and $x_2$ are not perpendicular.(Dikey)\n",
    "\n",
    "We will give strong preference to perpendicular basis vectors.\n",
    "\n",
    "Our nullspace $N(B)$ is a plane in $R^3$.\n",
    "\n",
    "We can see an orthonormal basis $v_2$ and $v_3$ in that plane.\n",
    "\n",
    "The $v_2$ and $v_3$ axes make a 90 degree angle with each other and with $v_1$."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "a9d69d728aa97602"
  },
  {
   "cell_type": "markdown",
   "source": [
    "![fig_1_2](./fig_1_2.png)"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "c11990cafec12bb0"
  },
  {
   "cell_type": "markdown",
   "source": [
    "------------------------------------------------\n",
    "**COUNTING LAW:**\n",
    "\n",
    "**$r$ independent equations $Ax$=0 have $n$-$r$ independent solutions! \n",
    "\n",
    "\n",
    "-----------------------------------------------"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "98c64027b21209a7"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## EXAMPLE-3:\n",
    "\n",
    "Here is an example that has five equations (one for every edge in the graph).\n",
    "\n",
    "The equations hav four unknowns (one for every node in the graph).\n",
    "\n",
    "The matrix in $Ax$=b is the 5 by 4 incidence matrix of the graph.\n",
    "\n",
    "A has 1 and -1 on every row to show the end node and the start node for each edge.\n",
    "\n",
    "\n",
    "$$\n",
    "\n",
    "-x_1 + x_2 = b_1\n",
    "\\\\\n",
    "-x_1 + x_3 = b_2\n",
    "\\\\\n",
    "-x_2 + x_3 = b_3\n",
    "\\\\\n",
    "-x_2 + x_4 = b_4\n",
    "\\\\\n",
    "-x_3 + x_4 = b_5\n",
    "\\\\\n",
    "\n",
    "\n",
    "$$\n",
    "\n",
    "Differences $Ax$=b across edges 1,2,3,4,5 between nodes 1,2,3,4.\n",
    "\n",
    "In other words 5 by 4 matrix indicates 5 edges to 4 nodes.\n",
    "\n",
    "$$\n",
    "\n",
    "A\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "-1 & 1 & 0 & 0 \\\\\n",
    "-1 & 0 & 1 & 0 \\\\\n",
    "0 & -1 & 1 & 0 \\\\\n",
    "0 & -1 & 0 & 1 \\\\\n",
    "0 & 0 & -1 & 1 \\\\\n",
    "\\end{bmatrix}\n",
    "\n",
    " \n",
    "\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "1  \\\\\n",
    "2  \\\\\n",
    "3  \\\\\n",
    "4  \\\\\n",
    "5 \\\\\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "edges\n",
    "$$\n",
    "$$\n",
    "nodes\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "1 & 2 & 3 & 4 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "\n",
    "$$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "4254221ff9d051f0"
  },
  {
   "cell_type": "markdown",
   "source": [
    "![fig_1_2_2](./fig_1_2_2.png)"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "6ffc920f7acad67b"
  },
  {
   "cell_type": "markdown",
   "source": [
    "This graph has 5 edges and 4 nodes. A is its 5 by 4 incidence matrix.\n",
    "\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "5aa0d3c44b2e7a32"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Finding Nullspace N(A)\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "5517c624da01fd08"
  },
  {
   "cell_type": "markdown",
   "source": [
    "To find the nullspace we set b = 0 in the 5 equations above.\n",
    "\n",
    "Then the first equation says $x_1$ = $x_2$.\n",
    "\n",
    "The second equation is $x_3$ = $x_1$.\n",
    "\n",
    "Equation 4 is $x_2$ = $x_4$.\n",
    "\n",
    "All four unknowns $x_1$, $x_2$, $x_3$, $x_4$ have the same value $c$.\n",
    "\n",
    "**The vector $x$ = (1,1,1,1) and all vectors $x$ = (c, c, c,c) are the solutions to $Ax$ =0.**\n",
    "\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "59a800bbe91cb1b0"
  },
  {
   "cell_type": "markdown",
   "source": [
    "That null space is a line in $R^4$.\n",
    "\n",
    "The special solution $x$=(1,1,1,1) is a basis for $N(A)$.\n",
    "\n",
    "The dimension on $N(A)$ is 1 (One vector in the basis, a line has dimension 1).\n",
    "\n",
    "The rank of A must be 3, since n-r = 4-3=1.\n",
    "\n",
    "From rank r=3, we now know the dimensions of all four subspaces.\n",
    "\n",
    "- Dimension of Row Space = $r$= 3\n",
    "- Dimension of Column Space = $r$=3\n",
    "- Dimension of Nullspace= $n$-$r$=1\n",
    "- Dimension of Nullspace of $A^T$ = $m$-$r$=2 "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "ded6d572475293e8"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### The Column Space C(A)"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "d6104f44182e140a"
  },
  {
   "cell_type": "markdown",
   "source": [
    "There must be $r$ = 4-1 = 3 independent columns.\n",
    "\n",
    "The fast way is to look at the first 3 columns.\n",
    "\n",
    "They give a basis for the column space.\n",
    "$$\n",
    "\\\\\n",
    "-1 \\:\\:\\:\\:\\:\\:\\:\\:\\:\\: 1 \\:\\:\\:\\:\\:\\:\\:\\:\\:\\:  0 \\:\\:\\:\\:\\:\\:\\:\\:\\\\\n",
    "-1 \\:\\:\\:\\:\\:\\:\\:\\:\\:\\: 0 \\:\\:\\:\\:\\:\\:\\:\\:\\:\\:  1 \\:\\:\\:\\:\\:\\:\\:\\:\\\\\n",
    "0 \\:\\:\\:\\:\\:\\:\\:\\:\\:\\: -1 \\:\\:\\:\\:\\:\\:\\:\\:\\:\\:  1 \\:\\:\\:\\:\\:\\:\\:\\:\\\\\n",
    "0 \\:\\:\\:\\:\\:\\:\\:\\:\\:\\: -1 \\:\\:\\:\\:\\:\\:\\:\\:\\:\\:  0 \\:\\:\\:\\:\\:\\:\\:\\:\\\\\n",
    "0 \\:\\:\\:\\:\\:\\:\\:\\:\\:\\: 0 \\:\\:\\:\\:\\:\\:\\:\\: \\:\\: -1 \\:\\:\\:\\:\\:\\:\\:\\:\\\\\n",
    "\n",
    "\\\\\n",
    "$$\n",
    "\n",
    "**Columns 1,2,3 of this A are independent**\n",
    "\n",
    "**Column 4 is a combination of those three basic columns**\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "263959637e4ff710"
  },
  {
   "cell_type": "markdown",
   "source": [
    "*Independent* means that the only solution to $Ax$ = 0 is ($x_1$,$x_2$,$x_3$) = (0,0,0)\n",
    "\n",
    "We know that $x_3$ =0 from the fifth equation 0$x_1$ + 0$x_2$ - $x_3$ = 0\n",
    "\n",
    "We know $x_2$=0 from the forth equation 0$x_1$-$x_2$+0$x_3$=0.\n",
    "\n",
    "Then we know $x_1$ = 0 from the first equation.\n",
    "\n",
    "Column 4 of the incidence matrix A is the sum of those three columns, times -1."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "69901a09acdd0a2e"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### The Row Space $C(A^T)$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "18a4aee32e107cc6"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The dimension must again be $r$=3, the same as for columns.\n",
    "\n",
    "But the first 3 rows of A are not independent: row 3 = row2 - row1.\n",
    "\n",
    "The first three independent rows are rows 1,2,4.\n",
    "\n",
    "Those rows are a basis(one possible basis) for the row space.\n",
    "\n",
    "\n",
    "$$\n",
    "A\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "-1 & 1 & 0 & 0 \\\\\n",
    "-1 & 0 & 1 & 0 \\\\\n",
    "0 & -1 & 1 & 0 \\\\\n",
    "0 & -1 & 0 & 1 \\\\\n",
    "0 & 0 & -1 & 1 \\\\\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "\n",
    "- Edges 1,2,3 form a loop in the graph: Dependent rows 1,2,3.\n",
    "\n",
    "- Edges 1,2,4 form a tree in the graph: Independent rows 1,2,4.\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "9e4eeeca55127140"
  },
  {
   "cell_type": "markdown",
   "source": [
    "![fig_1_2_3](./fig_1_2_3.png)"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "89ec35840d05fe7c"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### The Left NullSpace $N(A^T)$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "2937463551b1c278"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Now we solve $A^T$$y$ = 0\n",
    "\n",
    "Combinations of the rows give zero.\n",
    "\n",
    "We already noticed that row 3 = row 2 - row 1, so one solution is $y$= (1,-1,1,0,0).\n",
    "\n",
    "I would say this $y$ comes from the following upper loop in the graph: forward on edges 1 and 3 and backward on edge 2.\n",
    "\n",
    "Another $y$ comes from going around the lower loop in the graph: forward on 4, back on 5 and 3.\n",
    "\n",
    "This $y$= (0,0,-1,1,-1) is an independent solution of $A^T$$y$ = 0.\n",
    "\n",
    "The dimensions of the left nullspace $N(A^T)$ is $m$-$r$= 5 - 3 = 2.\n",
    "\n",
    "So those two $y$'s are a basis for the left nullspace.\n",
    "\n",
    "\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "e5a15025fe675434"
  },
  {
   "cell_type": "markdown",
   "source": [
    "You may ask how \"loops\" and \"trees\" got into this problem.\n",
    "\n",
    "That did not have to happen.\n",
    "\n",
    "We could have used elimination to solve $A^T y$ = 0\n",
    "\n",
    "The 4 by 5 matrix $A^T$ would have three pivots.\n",
    "\n",
    "The nullspace of $A^T$ has dimension two: $m$ - $r$ = 5 - 3 = 2\n",
    "\n",
    "But loops and trees identify dependent rows and independent rows in a beautiful way.\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "bc55bc19556118fa"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The equation $A^T y$ = 0 give currents ($y_1$, $y_2$, $y_3$, $y_4$, $y_5$) on the five edges of the graph.\n",
    "\n",
    "Flows around loops obey **Kirchhoff's Current Law: In = Out**.\n",
    "\n",
    "Graphs are the most important model in discrete applied mathematics.\n",
    "\n",
    "You see graphs everywhere: roads, pipelines, blood flows...\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "84b38c9ca46a5c50"
  },
  {
   "cell_type": "markdown",
   "source": [
    "--------------------------------------\n",
    "\n",
    "**Four subspaces for connected graph with $m$ edges and $n$ nodes: Incidence Matrix A:**\n",
    "\n",
    "$N(A)$ =  The constant vectors ($c$,$c$,...,$c$) make up the 1 dimensional nullspace of A.\n",
    "\n",
    "$C(A^T)$ = The $r$ edges of a tree give $r$ independent rows of A: rank = r = n-1\n",
    "\n",
    "$C(A)$ = **Voltage Law:** The components of $Ax$ add to zero around all loops.\n",
    "\n",
    "$N(A^T)$ = **Current Law:** $A^T y$ = flow in - flow out = 0 is solved by loop currents.\n",
    "\n",
    "\\:\\:\\:\\:**There are $m$-$r$ = $m$ - $n$ + 1 independent small loops in the graph**\n",
    "\n",
    "\n",
    "\n",
    "----------------------------------------"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "5d93e87f1b0df60d"
  },
  {
   "cell_type": "markdown",
   "source": [
    "![fig_1_3](./fig_1_3.png)"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "49b4c485f02989f6"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## THE RANKS OF $AB$ and $A$ + $B$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "439c4ce3602afa5b"
  },
  {
   "cell_type": "markdown",
   "source": [
    "This page establishes key facts about ranks:\n",
    "\n",
    "**When we multiply matrices, the rank cannot increase.**\n",
    "\n",
    "You will see this by looking at column spaces and row spaces.\n",
    "\n",
    "And there is one special situation when the rank cannot decrease.\n",
    "\n",
    "Then you know the rank of $AB$.\n",
    "\n",
    "Statement 4 will be important when data science factors a matrix into $UV$ or $CR$.\n",
    "\n",
    "Here are the 5 key facts in one place: inequalities and equalities of rank."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "eb3e7b5c08f077c2"
  },
  {
   "cell_type": "markdown",
   "source": [
    "-----------------------------------------------\n",
    "1-) Rank of $AB$ <= Rank of $A$ \n",
    "2-) Rank of $AB$ <= Rank of $B$\n",
    "3-) Rank of $A$ + $B$ <= (Rank of $A$) + (Rank of $B$)\n",
    "4-) Rank of $A^T A$ = Rank of $A^T A$ = Rank of $A$ = Rank of $A^T$  \n",
    "5-) If $A$ is $m$ by $r$ and $B$ is $r$ by $n$ -- both with rank $r$ --- then $AB$ also has rank $r$.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "---------------------------------"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "1d2692eba024d6d0"
  },
  {
   "cell_type": "markdown",
   "source": [
    "**Statement 1 and 2** involves the column space and row space of AB:\n",
    "\n",
    "$C(AB)$ ins contained in $C(A)$ \n",
    "\n",
    "$C((AB)^T)$ is contained in $C(B^T)$\n",
    "\n",
    "*Every column of AB is a combination of the columns of A (matrix multiplication)*\n",
    "\n",
    "*Every row of AB is a combination of the rows of B (matrix multiplication)*\n",
    "\n",
    "Remember from first section that **ROW RANK = COLUMN RANK**.\n",
    "\n",
    "We can use rows or columns.\n",
    "\n",
    "The rank cannot grow when we multiply AB."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "d988aeaad052b11c"
  },
  {
   "cell_type": "markdown",
   "source": [
    "**Statement 3** \n",
    "\n",
    "Each column of A + B is the sum of (column of A) + (column of B)\n",
    "\n",
    "rank(A + B) <= rank(A) + rank(B) is always true. It combines bases for $C(A)$ and $C(B)$\n",
    "\n",
    "rank(A+ B) = rank(A) + rank(B) is **not** always true. It is certainly falce if A = B = I.\n",
    "\n",
    " \n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "2df8de073e60044c"
  },
  {
   "cell_type": "markdown",
   "source": [
    "**Statement 4**\n",
    "\n",
    "$A$ and $A^T$$A$ both have n columns.\n",
    "\n",
    "**They also have the same nullspace.**\n",
    "\n",
    "So $n$-$r$ is the same for both and the rank $r$ is the same for both.\n",
    "\n",
    "Then rank($A^T$)<= rank($A^T$$A$) = rank($A$)\n",
    "\n",
    "Exchange A and $A^T$ to show their equal ranks."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "cb556156866b177a"
  },
  {
   "cell_type": "markdown",
   "source": [
    "**Statement 5**\n",
    "\n",
    "We are told that A and B have rank $r$.\n",
    "\n",
    "By statement 4, $A^TA$ and $BB^T$ have rank $r$.\n",
    "\n",
    "Those are $r$ by $r$ matrices so they are invertible.\n",
    "\n",
    "So their product $A^TABB^T$.\n",
    "\n",
    "Then r = rank of ($A^TABB^T$) <= rank of ($AB$) by statement 1: $A^T$, $B^T$ cannot increase rank.\n",
    "\n",
    "We also know rank (AB) <= rank A = $r$.\n",
    "\n",
    "So we have proved that AB has rank exactly $r$.\n",
    "\n",
    "Note:\n",
    "\n",
    "This does not mean that every product of rank $r$ matrices will have rank $r$.\n",
    "\n",
    "Statement 5 assumes that A has exactly $r$, columns and B has $r$ rows. BA can easily fail.\n",
    "\n",
    "$$\n",
    "\n",
    "A\n",
    "\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "\n",
    "1 \\\\\n",
    "1 \\\\\n",
    "1 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\\:\\:\\:\n",
    "B\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "1 & 2 & -3 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\\:\\:\\:\\:\\:\\:\n",
    "\n",
    "AB\\:has\\:rank\\:1.\n",
    "\n",
    "\\:\\:\\:\\:\\:\\:\n",
    "\n",
    "But\\:BA\\:is\\:zero\\:!!.\\:\n",
    "\n",
    "$$\n",
    "\n",
    "\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "1a567ab4081d312d"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false
   },
   "id": "a5351772d13b74af"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}