ch_5_Orthogonal_Matrices_and_SubSpaces.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# ORTHOGONAL MATRICES AND SUBSPACES"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "2a63c1bcd6ff2d21"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The word orthogonal appears everywhere in linear algebra.\n",
    "\n",
    "It means **perpendicular**.\n",
    "\n",
    "Its use extends far beyond the angle between two vectors.\n",
    "\n",
    "Here are important extensions of that key idea:\n",
    "\n",
    "**1-) Orthogonal Vectors $x$ and $y$:**\n",
    "\n",
    "The test is $x^T y$ = $x_1 y_1$ + ... + $x_n y_n$ = 0\n",
    "\n",
    "If $x$ and $y$ have complex components, change to $\\bar{x}^T y$ = $\\bar{x}_1 y_1$ + ... + $\\bar{x}_n y_n$ = 0 \n",
    "\n",
    "**2-) Orthogonal Basis for a Subspace:**\n",
    "\n",
    "Every pair of basis vectors has $v_1 ^T v_j$ = 0 \n",
    "\n",
    "**Orthonormal Basis:** Orthogonal basis of **unit vectors:** every $v_1 ^T v_j$ = 1 (length 1)\n",
    "\n",
    "From orthogonal to orthonormal, just divide every basis vector $v_i$ by its length $||v_i||$\n",
    "\n",
    "**3-) Orthogonal Subspaces R and N:**\n",
    "\n",
    "Every vector in the space $R$ is orthogonal to every vector in $N$.\n",
    "\n",
    "Notice Again! The row space and nullspace are orthogonal:\n",
    "\n",
    "$$\n",
    "\n",
    "\\\\\n",
    "\n",
    "Ax=0 \\:\\:means\\:each\\:row\\:x=0\n",
    "\n",
    "\\\\\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "Row\\:1\\:of\\:A \\\\\n",
    "...\\\\\n",
    "...\\\\\n",
    "Row\\:m\\:of\\:A\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    " \\\\\n",
    "x\\\\\n",
    "\\\\\n",
    "\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "0 \\\\\n",
    "...\\\\\n",
    "...\\\\\n",
    "0\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Every row (and every combination of rows) is orthogonal to all $x$ in the nullspace.\n",
    "\n",
    "**4-)Tall Thin Matrices $Q$ with Orthonormal Columns: $Q^T Q$ = $I$.**\n",
    "\n",
    "$$\n",
    "\n",
    "Q^T Q\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "--- & q^T _1 & --- \\\\\n",
    "&...&\\\\\n",
    "&...&\\\\\n",
    "--- & q^T _n & --- \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    " &  &  \\\\\n",
    "q_1&...&q_n\\\\\n",
    "&  &  \\\\\n",
    "&  & \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    " 1 & 0 & 0 \\\\\n",
    " 0 & 1 & 0 \\\\\n",
    " 0 & 0 & 1 \\\\\n",
    "\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "I\n",
    "\n",
    "$$\n",
    "\n",
    "If this $Q$ multiplies any vector $x$, the length of the vector does not change:\n",
    "\n",
    "$||Qx||$ = $||x||$ because $(Qx)^T$ * $(Qx)$ = $x^T$ $Q^T Q$ $x$ = $x^Tx$\n",
    "\n",
    "If m > n the $m$ rows cannot be orthogonal in $R^n$.\n",
    "\n",
    "Tall thin matrices have $Q Q^T$ =! $I$\n",
    "\n",
    "**5-)Orthogonal Matrices are square with orthonormal columns: $Q^T$ = $Q^-^1$**\n",
    "\n",
    "**For square matrices $Q^T Q=I$ leads to $QQ^T$= $I$**\n",
    "\n",
    "For square matrices $Q$, the left inverse $Q^T$ is also a right inverse of $Q$.\n",
    "\n",
    "The columns of this orthogonal $n$ by $n$ matrix are an orthonormal basis for $R^n$.\n",
    "\n",
    "The rows of $Q$ are a (probably different) orthonormal basis for $R^n$.\n",
    "\n",
    "The name orthogonal matrix should really be orthonormal matrix.\n",
    "\n",
    "We will now see examples of orthogonal **vectors**, **bases**, **subspaces** and **matrices**."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "6ea3e9bea5c26b2e"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## ORTHOGONAL VECTORS"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "98c63b9da70faaf"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The test $x^T y$ = 0 connects to right triangles by $c^z = a^z + b^z$:\n",
    "\n",
    "**Pythagoras Law for right triangles: $||x-y||^2$ = $||x||^2$ + $||y||^2$** \n",
    "\n",
    "The left side is $(x-y)^T$ * $(x-y)$.\n",
    "\n",
    "This expands to $x^T x$ + $y^T y$ - $x^T y$ - $y^T x$.\n",
    "\n",
    "When the last two terms are zero, we have equation $||x-y||^2$ = $||x||^2$ + $||y||^2$:\n",
    "\n",
    "$x$= (1,2,2) and $y$ = (2,1,-2) have $x^T y$=0\n",
    "\n",
    "The hypotenuse is $x-y$ = (-1,1,4).\n",
    "\n",
    "Then Pythagoras is 18 = 9 + 9.\n",
    "\n",
    "Dot products $x^T y$ and $y^T x$ always equal ||x||*||y|| cos$\\theta$, where $\\theta$ is the angle between x and y.\n",
    "\n",
    "So in all cases we have the Law of Cosines $c^2 = a^2 + b^2 - 2ab cosθ$ :\n",
    "\n",
    "**LAW OF COSINES : $||x-y||^2$ = $||x||^2$ + $||y||^2 - 2 ||x||*||y||* cosθ$** \n",
    "\n",
    "Orthogonal vectors have cosθ = 0 and that last term disappears."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "e8855fa80fc355c0"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## ORTHOGONAL BASIS"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "5ebffe58fcf5e7fd"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The standard basis is orthogonal (even orthonormal) in $R^n$:\n",
    "\n",
    "Standard basis $i,j,k$ in $R^3$:\n",
    "\n",
    "$$\n",
    "\n",
    "i \n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    " 1 \\\\\n",
    " 0  \\\\\n",
    " 0  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "j\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    " 0 \\\\\n",
    " 1  \\\\\n",
    " 0  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "k\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    " 0 \\\\\n",
    " 0  \\\\\n",
    " 1  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "$$\n",
    "\n",
    "Here are three Hadamard matrices $H_2$, $H_4$, $H_8$ containing orthogonal basis of $R^2$, $R^4$, $R^8$.\n",
    "\n",
    "$$\n",
    "\n",
    "Hadamard\\:Matrices \\\\\n",
    "\n",
    "Orthogonal\\:columns\\:sizes\\:2,\\:4,\\:8.\n",
    "\n",
    "\\\\\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    " 1 & 1 \\\\\n",
    " 1 & -1 \\\\\n",
    " \n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    " 1 & 1 &  1 & 1 \\\\\n",
    " 1 & -1 &  1 & -1 \\\\\n",
    " 1 & 1 &  -1 & -1 \\\\\n",
    " 1 & -1 &  -1 & 1 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    " H_4 & H_4 \\\\\n",
    " H_4 & -H_4 \\\\\n",
    " \n",
    "\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Are those orthogonal matrices?\n",
    "\n",
    "No.\n",
    "\n",
    "The columns have lengths $\\sqrt{2}$, $\\sqrt{4}$, $\\sqrt{8}$.\n",
    "\n",
    "If we divide by those lengths, we have the beginning of an infinite list: orthonormal bases in 2,4,8,16,32,... dimensions.\n",
    "\n",
    "The **Hadamard Conjecture** proposes that there is a ±1 matrix with orthogonal columns whenever 4 divides $n$.\n",
    "\n",
    "Wikipedia says that $n$ = 668 is the smallest of those sizes without a known Hadamard matrix.\n",
    "\n",
    "The construction for $n$= 16,32,... follows the pattern above.\n",
    "\n",
    "Here is the key fact:\n",
    "\n",
    "**Every subspace of $R^n$ has an orthogonal basis.**\n",
    "\n",
    "Think of a plane in three dimensional space $R^3$.\n",
    "\n",
    "The plane has two independent vectors $a$ and $b$.\n",
    "\n",
    "For an orthogonal basis, subtract away from b its component in the direction of $a$.\n",
    "\n",
    "$$\n",
    "\n",
    "Orthogonal\\:Basis\\:a\\:and\\:c: \\\\\n",
    "\n",
    "c\n",
    "\n",
    "= \n",
    "\n",
    "b\n",
    "\n",
    "-\n",
    "\n",
    "\\frac{a^T b}{a^T a}\n",
    "\n",
    "*\n",
    "\n",
    "a\n",
    "\n",
    "\n",
    "$$\n",
    "\n",
    "The inner product $a^T c$ is $a^T b$ - $a^T b$ ) 0/\n",
    "\n",
    "This idea of orthogonalizing applies to any number of basis vectors: *a basis becomes an orthogonal basis.**\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "127bd44604a25f39"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## ORTHOGONAL SUBSPACES"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "dfb63aa6a9196242"
  },
  {
   "cell_type": "markdown",
   "source": [
    "$$\n",
    "\n",
    "\\\\\n",
    "\n",
    "Ax=0 \\:\\:means\\:each\\:row\\:x=0\n",
    "\n",
    "\\\\\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "Row\\:1\\:of\\:A \\\\\n",
    "...\\\\\n",
    "...\\\\\n",
    "Row\\:m\\:of\\:A\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    " \\\\\n",
    "x\\\\\n",
    "\\\\\n",
    "\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "0 \\\\\n",
    "...\\\\\n",
    "...\\\\\n",
    "0\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "Above equation looked at $Ax==$.\n",
    "\n",
    "Every row of A is multiplying that nullspace vector $x$.\n",
    "\n",
    "So each row (and all combination of rows) will be orthogonal to $x$ in $N(A)$.\n",
    "\n",
    "**The row space of A is orthogonal to the nullspace of A.**\n",
    "\n",
    "$$\n",
    "Ax\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "Row\\:1\\:of\\:A \\\\\n",
    "...\\\\\n",
    "...\\\\\n",
    "Row\\:m\\:of\\:A\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    " \\\\\n",
    "x\\\\\n",
    "\\\\\n",
    "\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "0 \\\\\n",
    "...\\\\\n",
    "...\\\\\n",
    "0\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "\\\\\n",
    "\n",
    "A^T y\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "(Column\\:1)\\:^T \\\\\n",
    "...\\\\\n",
    "...\\\\\n",
    "(Column\\:n)\\:^T \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    " \\\\\n",
    "y\\\\\n",
    "\\\\\n",
    "\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "0 \\\\\n",
    "...\\\\\n",
    "...\\\\\n",
    "0\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "$$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "60197d94e60e109a"
  },
  {
   "cell_type": "markdown",
   "source": [
    "From $A^T y=0$, the columns of A are all orthogonal to $y$.\n",
    "\n",
    "Their combinations (the whole column space) will also be orthogonal to $y$.\n",
    "\n",
    "**The column space of A is orthogonal to the nullspace of $A^T$.**\n",
    "\n",
    "This produces the Big Picture of Linear Algebra.\n",
    "\n",
    "Notice the dimensions $r$ and $n-r$ adding to $n$.\n",
    "\n",
    "The whole space $R^n$ is accounted for.\n",
    "\n",
    "Every vector $v$ in $R^n$ has a row space component $v_r$ and a nullspace component $v_n$ with $v$ = $v_r$ + $v_n$.\n",
    "\n",
    "A row space basis (r vectors) together w\n",
    "th a nullspace basis (n-r vectors) produces a basis for all of $R^n$ (n vectors). "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "2149d2e77106c91"
  },
  {
   "cell_type": "markdown",
   "source": [
    "![fig_1_6](./fig_1_6.png)"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "59795b56f0836af2"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Above shows two pairs of orthogonal subspaces.\n",
    "\n",
    "The dimensions add to n and add to m.\n",
    "\n",
    "This is the Big Picture -- two subspaces in $R^n$ and two subspaces in $R^m$."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "decc880b365b7ced"
  },
  {
   "cell_type": "markdown",
   "source": [
    "I will mention a big improvement.\n",
    "\n",
    "It comes from the Singular Value Decomposition.\n",
    "\n",
    "The SVD is the most important theorem in data science.\n",
    "\n",
    "It finds orthonormal bases $v_1$,...,$v_r$ for the row space of A and $u_1$,..., $u_r$ for the column space of A.\n",
    "\n",
    "Gram-Schmidt can do that.\n",
    "\n",
    "The special bases from the SVD have the extra property that each pair ($v$ and $u$) is connected by A:\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "acb99db2a9f3058d"
  },
  {
   "cell_type": "markdown",
   "source": [
    "------------------------------------\n",
    "\n",
    "Singular Vectors:\n",
    "\n",
    "$$\n",
    "\n",
    "Av_1\n",
    "\n",
    "=\n",
    "\n",
    "\\sigma{_1}u_1\n",
    "\n",
    "\\:\\:\\:\\:\\:\n",
    "Av_2\n",
    "\n",
    "=\n",
    "\n",
    "\\sigma{_2}u_2\n",
    "\\:\\:\\:\\:\\:\n",
    "...\n",
    "\\:\\:\\:\\:\\:\n",
    "Av_r\n",
    "\n",
    "=\n",
    "\n",
    "\\sigma{_r}u_r\n",
    "\n",
    "\n",
    "$$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "7182887bfadba7e5"
  },
  {
   "cell_type": "markdown",
   "source": [
    "In above figure, imagine the $v$'s on the left and the $u$'s on the right.\n",
    "\n",
    "For the bases from the SVD, multiplying by A takes an orthogonal basis of $v$'s to an orthogonal basis of $u$'s."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "7ed27fc873abe5fb"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## TALL THIN $Q$ with ORTHONORMAL COLUMNS: $Q^T Q = I$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "94b4ff63308e6880"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Here are three possible $Q$'s, growing from (3 by 1) to (3 by 2) to an orthogonal matrix $Q_3$.\n",
    "\n",
    "$$\n",
    "\n",
    "Q_1\n",
    "\n",
    "=\n",
    "\n",
    "\\frac{1}{3}\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2  \\\\\n",
    "2  \\\\\n",
    "-1 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "\\:\\:\\:\\:\\:\\:\\:\\:\n",
    "\n",
    "Q_2\n",
    "\n",
    "=\n",
    "\n",
    "\\frac{1}{3}\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2 & 2 \\\\\n",
    "2 & -1 \\\\\n",
    "-1 & 2\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "\\:\\:\\:\\:\\:\\:\\:\\:\n",
    "\n",
    "Q_3\n",
    "\n",
    "=\n",
    "\n",
    "\\frac{1}{3}\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2 & 2 & -1\\\\\n",
    "2 & -1 & 2\\\\\n",
    "-1 & 2 & 2\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "$$\n",
    "\n",
    "Each one of those matrices has $Q^T Q= I$.\n",
    "\n",
    "So $Q^T$ is a left inverse of $Q$. Only the last matrix has $Q_3 Q^T_3= I$.\n",
    "\n",
    "Then $Q^T_3$ is also right inverse. $Q_3$ happens to be symmetric as well as orthogonal.\n",
    "\n",
    "It is a king and also a queen, truly a royal matrix.\n",
    "\n",
    "**Notice that all the matrices $P=Q Q^T$ have $P^2 = P$.**\n",
    "\n",
    "$$\n",
    "\n",
    "P^2\n",
    "\n",
    "=\n",
    "\n",
    "(Q Q^T)\n",
    "\n",
    "*\n",
    "\n",
    "(Q Q^T)\n",
    "\n",
    "=\n",
    "\n",
    "Q\n",
    "\n",
    "*\n",
    "\n",
    "(Q^T Q)\n",
    "\n",
    "*\n",
    "\n",
    "Q^T\n",
    "\n",
    "=\n",
    "\n",
    "Q\n",
    "\n",
    "*\n",
    "\n",
    "Q^T\n",
    "\n",
    "=\n",
    "\n",
    "P\n",
    "\n",
    "$$\n",
    "\n",
    "In the middle we removed $Q^T Q= I$.\n",
    "\n",
    "The equation $P^2 = P$ signals a **projection matrix.**\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "84781b845ceca573"
  },
  {
   "cell_type": "markdown",
   "source": [
    "------------------------------------------\n",
    "\n",
    "**If $P^2$ = $P$ = $P^T$ then $P b$ is the orthogonal projection of b onto the column space of P.**\n",
    "\n",
    "--------------------------------------------"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "12e212f29726a358"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## EXAMPLE-1\n",
    "\n",
    "To project $b = (3,3,3)$ on the $Q_1$ line, multiply by $P_1 = Q_1 Q^T _1$.\n",
    "\n",
    "\n",
    "$$\n",
    "\n",
    "P_1 b\n",
    "\n",
    "=\n",
    "\n",
    "\\frac{1}{9}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2  \\\\\n",
    "2  \\\\\n",
    "-1 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2 & 2 & -1  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "3  \\\\\n",
    "3  \\\\\n",
    "3 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\\frac{1}{9}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2  \\\\\n",
    "2  \\\\\n",
    "-1 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "9\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2  \\\\\n",
    "2  \\\\\n",
    "-1 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "projection\\:on\\:a\\:line\n",
    "\n",
    "$$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "9495468005da01e0"
  },
  {
   "cell_type": "markdown",
   "source": [
    "That matrix splits $b$ in two perpendicular parts: projection $P_1 b$ and error $e$ = $(I - P_1) b$.\n",
    "\n",
    "Below is the projection of $b$ onto a line by $P_1 = Q_1 Q^T_1$ and onto a plane by $P_2 = Q_2 Q^T_2$."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "2f23de625464d87a"
  },
  {
   "cell_type": "markdown",
   "source": [
    "![fig_1_7](./fig_1_7.png)"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "cb891c404a12d999"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Now project the same $b = (3,3,3)$ on the column space of $Q_2$ (a plane).\n",
    "\n",
    "The error vector $b - P_2 b$ is shorter than $b - P_1b$ because the plane contains the line.\n",
    "\n",
    "$$\n",
    "\n",
    "\n",
    "\n",
    "P_2 b\n",
    "\n",
    "=\n",
    "\n",
    "\\frac{1}{9}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2  & 2\\\\\n",
    "2  & -1\\\\\n",
    "-1 & 2\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2 & 2 & -1  \\\\\n",
    "2 & -1 & 2  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "3  \\\\\n",
    "3  \\\\\n",
    "3 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\\frac{1}{9}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2  & 2\\\\\n",
    "2  & -1\\\\\n",
    "-1 & 2\\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\\begin{bmatrix}\n",
    "\n",
    "9 \\\\\n",
    "9 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "4  \\\\\n",
    "1  \\\\\n",
    "1  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "\n",
    "$$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "3d025f700ce61dba"
  },
  {
   "cell_type": "markdown",
   "source": [
    "### QUESTION:\n",
    "\n",
    "What is $P_3 b$ = $Q_3 Q^T_3 b$?\n",
    "\n",
    "Now you are projecting $b$ onto the whole space $R^3$.\n",
    "\n",
    "Answer: \n",
    "\n",
    "$P_3 b = b$.\n",
    "\n",
    "In fact $P_3 = Q_3 Q^T_3 = $ identity matrix!!!\n",
    "\n",
    "**The error $e$ is now zero.\n",
    "\n",
    "Projections lie at the heart of \"least squares\"."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "328b11cd38d9e3e2"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 5-) ORTHOGONAL MATRICES"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "a429cf36c3541831"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Now $Q$ is square: $Q^T Q$ = $I$ and $QQ^T$ = $I$.\n",
    "\n",
    "So $Q^- ^1$ = $Q^T$.\n",
    "\n",
    "These Q's are truly important.\n",
    "\n",
    "For 2 by 2, they are rotations of the plane or reflections.\n",
    "\n",
    "When the whole plane rotates around (0,0), lengths do not change.\n",
    "\n",
    "Angles between vectors do not change.\n",
    "\n",
    "The columns of $Q$ are orthogonal unit vectors, with $cos^2 θ$ + $sin^2 θ$ = 1:\n",
    "\n",
    "$$\n",
    "\n",
    "Q_r _o _t _a _t _e \n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "cosθ & -sinθ \\\\\n",
    "sinθ & cosθ  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "rotation\\:through\\:an\\:angle\\:θ.\n",
    "\n",
    "\n",
    "$$\n",
    "\n",
    "And if I multiply a column by -1, the two columns are still orthogonal of length 1.\n",
    "\n",
    "$$\n",
    "\n",
    "Q_r _e _f _l _e _c _t \n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "cosθ & sinθ \\\\\n",
    "sinθ & -cosθ  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "reflection\\:across\\:the\\:\\frac{θ}{2}\\:line.\n",
    "\n",
    "\n",
    "$$\n",
    "\n",
    "Now $Q$ reflects every vector in a mirror.\n",
    "\n",
    "It is a reflection with determinant -1 instead of a rotation with determinant +1.\n",
    "\n",
    "The $x-y$ plane rotates or the $x-y$ plane flips over.\n",
    "\n",
    "It is important that multiplying orthogonal matrices produces an orthogonal matrix.\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "45199ab6ce8b55fa"
  },
  {
   "cell_type": "markdown",
   "source": [
    "-----------------------------------------------\n",
    "\n",
    "**$Q_1 Q_2$ is orthogonal :**\n",
    "\n",
    "$(Q_1 Q_2)^T(Q_1 Q_2)$ = $Q^T_2 Q^T_1 Q_1 Q_2$ = $Q^T_2 Q_2$ = $I$ \n",
    "\n",
    "\n",
    "--------------------------------------------"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "f560fbb4ea1defd3"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Rotation times Rotation = Rotation\n",
    "\n",
    "Reflection times Reflection = Rotation\n",
    "\n",
    "Rotation times Reflection = Reflection\n",
    "\n",
    "All still true in $R^n$.\n",
    "\n",
    "Below rotate the whole plane by θ. Reflect every vector across the line at angle $\\frac{θ}{2}.$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "7210340722513faf"
  },
  {
   "cell_type": "markdown",
   "source": [
    "![fig_1_8](./fig_1_8.png)"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "c73cc8a8a3a1812d"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The figure shows how the columns of $Q$ come from  $Q$ $\\begin{bmatrix}\n",
    "\n",
    "1 \\\\\n",
    "0  \\\\\n",
    "\n",
    "\\end{bmatrix}$ and $Q$ $\\begin{bmatrix}\n",
    "\n",
    "0 \\\\\n",
    "1  \\\\\n",
    "\n",
    "\\end{bmatrix}$\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "b09073e3bdf4c24c"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## ORTHOGONAL BASIS = ORTHOGONAL AXES IN $R^n$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "77cdfa790638e2cd"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Suppose the $n$ by $n$ orthogonal matrix $Q$ has columns $q_1$,...,$q_n$.\n",
    "\n",
    "Those unit vectors are a basis for n-dimentional space $R^n$.\n",
    "\n",
    "Every vector $v$ can be written as a combination of the basis vectors (the $q$'s):\n",
    "\n",
    "$$\n",
    "\n",
    "v \n",
    "\n",
    "=\n",
    "\n",
    "c_1 q_1\n",
    "\n",
    "+\n",
    "\n",
    "...\n",
    "\n",
    "+\n",
    "\n",
    "c_n q_n\n",
    "\n",
    "$$\n",
    "\n",
    "Those $c_1 q_1$ and $c_2 q_2$ and $c_n q_n$ are the components of $v$ along the axes.\n",
    "\n",
    "They are the projections of $v$ onto the axes!!\n",
    "\n",
    "There is a simple formula for each number $c_1$ to $c_n$:\n",
    "\n",
    "**Coefficients in an Orthonormal Basis**\n",
    "\n",
    "--------------------------------------\n",
    "\n",
    "$c_1$ = $q^T_1 v$ \\\n",
    "$c_2$ = $q^T_2 v$ \\\n",
    "$c_n$ = $q^T_n v$ \n",
    "\n",
    "-------------------------------------\n",
    " \n",
    "I will give a vector proof and a matrix proof.\n",
    "\n",
    "Take dot products with $q_1$ in equation:\n",
    "\n",
    "$q^T_1 v$ = $c_1 q^T_1 q_1$ + ... + $c_n q^T_1 q_n$ = $c_1$\n",
    "\n",
    "\n",
    "All terms are zero except $c_1 q^T_1q_1$ = $c_1$.\n",
    "\n",
    "So $q^T_1 v$ = $c_1$ and every $q^T_k v$ = $c_k$.\n",
    "\n",
    "If we write $\n",
    "\n",
    "v \n",
    "\n",
    "=\n",
    "\n",
    "c_1 q_1\n",
    "\n",
    "+\n",
    "\n",
    "...\n",
    "\n",
    "+\n",
    "\n",
    "c_n q_n\n",
    "\n",
    "$ as a matrix equation $v= Qc$, multiply by $Q^T$ to see coefficients in an orthonormal:\n",
    " \n",
    "$Q^T v$ = $Q^T Q c$ = $c$ gives all the coefficients $c_k$ = $q^T_k v$ at once.\n",
    "\n",
    "This is the key application of orthogonal bases (for example the basis for Fourier Series).\n",
    "\n",
    "When basis vectors are orthonormal, each coefficient $c_1$ to $c_n$ can be found separately! "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "f0daa9df94962cd9"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## HouseHolder Reflections"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "4d7f92e5c79909ba"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Here are neat examples of **reflection matrices** $Q$ = $H_n$.\n",
    "\n",
    "Start with the identity matrix.\n",
    "\n",
    "Choose a unit vector $u$.\n",
    "\n",
    "Subtract the rank one symmetric matrix $2 u u^T$.\n",
    "\n",
    "Then $I - 2 u u^T$ is a Householder matrix.\n",
    "\n",
    "For example choose $u$ = $\\frac {(1,1,...,1)}{\\sqrt{n}}$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "2c175199e9b0577c"
  },
  {
   "cell_type": "markdown",
   "source": [
    "---------------------------------------------\n",
    "\n",
    "$H_n$ = $I - 2 u u^T$ = $ I$ - $\\frac{2}{n}$ **ones** (n,n)\n",
    "\n",
    "------------------------------------------"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "bf49de2aa6e4a1b1"
  },
  {
   "cell_type": "markdown",
   "source": [
    "With $u u^T$, $H_n$ is surely symmetric.\n",
    "\n",
    "Two reflections give $H^2$= $I$ because $u^T u$ = 1:\n",
    "\n",
    "$$\n",
    "\n",
    "H^T H = H^2 = (I - 2 u u^T)(I - 2 u u^T) = I - 4 u u^T + 4 u u^T u u^T = I\n",
    "\n",
    "\n",
    "$$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "52e56b3eba8a25f2"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The 3 by 3 and 4 by 4 examples are easy to remember and $H_4$ is like a Hadamard matrix:\n",
    "\n",
    "$$\n",
    "\n",
    "H_3 \n",
    "\n",
    "=\n",
    "\n",
    "I - \\frac{2}{3}ones\n",
    "\n",
    "=\n",
    "\n",
    "\\frac{1}{3}\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "1 & -2 & -2 \\\\\n",
    "-2 & 1 & -2 \\\\\n",
    "-2 & -2 & 1 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "\\\\\n",
    "\n",
    "H_4 \n",
    "\n",
    "=\n",
    "\n",
    "I - \\frac{2}{4}ones\n",
    "\n",
    "=\n",
    "\n",
    "\\frac{1}{2}\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "1 & -1 & -1 & -1 \\\\\n",
    "-1 & 1 & -1 & -1 \\\\\n",
    "-1 & -1 & 1 & -1 \\\\\n",
    "-1 & -1 & -1 & 1 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "$$ "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "607750c34c395f3d"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Householder's n by n reflection matrix has $H_n u$ = $(I - 2 u u^T) u$ = $u - 2u = -u$.\n",
    "\n",
    "and $H_n w$ = $+w$ whenever $w$ is perpendicular to $u$.\n",
    "\n",
    "The eigenvalues of H are -1 (once) and +1 (n-1 times).\n",
    "\n",
    "All reflection matrices have eigenvalues -1 and +1."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "6fb26466bdf89043"
  }
 ],
 "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
}