ch_2_Matrix_Matrix_Multiplication_AB.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# HIGHLIGHTS of LINEAR ALGEBRA"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "ac24b8d8744b2e83"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## MATRIX-MATRIX MULTIPLICATION"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "c3caa534c0d99eee"
  },
  {
   "cell_type": "markdown",
   "source": [
    "\n",
    "**Inner Products** (=row times columns) produce each of the numbers in A * B = C\n",
    "\n",
    "$$\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    ". & . & . \\\\\n",
    "a_2_1 & a_2_2 & a_2_3 \\\\\n",
    ". & . & . \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    ". & . & b_1_3 \\\\\n",
    ". & . & b_2_3 \\\\\n",
    ". & . & b_3_3 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    ". & . & . \\\\\n",
    ". & . & c_2_3 \\\\\n",
    ". & . & . \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "$$\n",
    "\n",
    "**Row 2 of A and Column 3 of B give $c_2_3$ in C**"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "b410c8fd0bc0578a"
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "outputs": [
    {
     "data": {
      "text/plain": "array([[0, 0, 0],\n       [4, 5, 6],\n       [0, 0, 0]])"
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import torch\n",
    "import tensorflow as tf\n",
    "\n",
    "# defining matrix A\n",
    "A = np.array([[0,0,0],[4,5,6],[0,0,0]])\n",
    "\n",
    "A"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-25T03:13:04.585034900Z",
     "start_time": "2024-03-25T03:12:45.500035100Z"
    }
   },
   "id": "550d2ae183eec3d6"
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "outputs": [
    {
     "data": {
      "text/plain": "array([[0, 0, 1],\n       [0, 0, 2],\n       [0, 0, 3]])"
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#defining matrix B\n",
    "\n",
    "B = np.array([[0,0,1],[0,0,2],[0,0,3]])\n",
    "\n",
    "B"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-25T03:13:04.620791500Z",
     "start_time": "2024-03-25T03:13:04.586282300Z"
    }
   },
   "id": "c5a50a7ec82f604f"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# A * B does NOT give dot product. "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "9ed6e50a8f02d444"
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [
    {
     "data": {
      "text/plain": "array([[ 0,  0,  0],\n       [ 0,  0, 12],\n       [ 0,  0,  0]])"
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c_not = A * B\n",
    "\n",
    "c_not\n"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-25T03:13:04.642441Z",
     "start_time": "2024-03-25T03:13:04.609434100Z"
    }
   },
   "id": "6902bc98aa2249e2"
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [
    {
     "data": {
      "text/plain": "32"
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Calculating c_2_3 manually\n",
    "# c_2_3 = a_2_1 * b_1_3 + a_2_2 * b_2_3 + a_2_3 * b_3_3\n",
    "\n",
    "manuel_c_2_3 = 4*1 + 5*2 + 6*3\n",
    "manuel_c_2_3"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-25T03:13:04.682759100Z",
     "start_time": "2024-03-25T03:13:04.640392Z"
    }
   },
   "id": "7b789513d10bc7b2"
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "outputs": [
    {
     "data": {
      "text/plain": "array([[ 0,  0,  0],\n       [ 0,  0, 32],\n       [ 0,  0,  0]])"
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Calculating c_2_3 with numpy\n",
    "\n",
    "c_2_3 = np.dot(A,B)\n",
    "c_2_3"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-25T03:13:04.746492500Z",
     "start_time": "2024-03-25T03:13:04.673376700Z"
    }
   },
   "id": "813a57b7402eb545"
  },
  {
   "cell_type": "markdown",
   "source": [
    "That **Dot Product** $c_2_3$ = (row 2 of A) * (column 3 of B) is a sum of $a$'s times $b$'s:\n",
    "\n",
    "$$\n",
    "\n",
    "c_2_3= a_2_1*b_1_3 + a_2_2*b_2_3 + a_2_3*b_3_3 =>\n",
    "\n",
    "$$\n",
    "\n",
    "$$\n",
    "\n",
    "\\sum_{k=1}^{3} a_2_k b_k_3 = \n",
    "\n",
    "$$\n",
    "\n",
    "$$\n",
    "\n",
    "c_i_j= \\sum_{k=1}^{n} a_i_k*b_k_j\n",
    "\n",
    "$$\n",
    "\n",
    "This is how we usually compute each number AB = C.\n",
    "\n",
    "But there is another way."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "585c61bf8e5a422a"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The other way to multiply AB is **columns of A times rows of B**.\n",
    "\n",
    "We need to see this!\n",
    "\n",
    "I start with numbers to make two key points:\n",
    "\n",
    "*one column* $u$ time *one row* $v^T$ produces a *matrix*.\n",
    "\n",
    "Concentrate first on that piece of AB.\n",
    "\n",
    "This matrix $uv^T$ is especially simple:\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "75302cc154b0e41b"
  },
  {
   "cell_type": "markdown",
   "source": [
    " $$\n",
    "\n",
    "\n",
    "Outer Product / $uv^T$\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",
    "3 & 4 & 6  \\\\\n",
    "\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "6 & 8 & 12  \\\\\n",
    "6 & 8 & 12  \\\\\n",
    "3 & 4 & 6  \\\\\n",
    "\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "Rank One Matrix\n",
    "\n",
    "$$\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "7e179b312bfe7c3e"
  },
  {
   "cell_type": "markdown",
   "source": [
    "As m by 1 matrix (a column $u$) times a 1 by p matrix (a row of $v^T$ gives an m by p matrix.\n",
    "\n",
    "Notice that what is special about the rank one matrix $uv^T$.\n",
    "\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "21ff654cb098da76"
  },
  {
   "cell_type": "markdown",
   "source": [
    "All columns of $uv^T$ are multiplies of $u$ = $\\begin{bmatrix}\n",
    "\n",
    "2 \\\\\n",
    "2 \\\\\n",
    "1 \\\\\n",
    "\n",
    "\\end{bmatrix}$. \n",
    "\n",
    "All rows are multiplies of $v^T$ = $ \\begin{bmatrix}\n",
    "\n",
    "3 & 4 & 6  \\\\\n",
    "\n",
    "\n",
    "\\end{bmatrix}$."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "6839fd3b86a0eaaf"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The column space of $uv^T$ is one dimentional: *the line in the direction of **$u$***.\n",
    "\n",
    "The dimension of the column space (the number of independent columns) is the **rank of the matrix** - a key number. \n",
    "\n",
    "**All nonzero matrices $uv^T$ have rank one**.\n",
    "\n",
    "They are the perfect building blocks for every matrix.\n",
    "\n",
    "Notice also: **The row space of $uv^T$ is the line through $v$.**\n",
    "\n",
    "By definition, the row space of any matrix A is the column space C(A^T) of its transpose A^T.\n",
    "\n",
    "That way we stay with column vectors.\n",
    "\n",
    "In the example, we transpose $uv^T$ (**exchange rows with columns**) to get the matrix $vu^T$:\n",
    "\n",
    "$$\n",
    "\n",
    "(uv^T)^T\n",
    "\n",
    "=\n",
    "\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "6 & 8 & 12  \\\\\n",
    "6 & 8 & 12  \\\\\n",
    "3 & 4 & 6  \\\\\n",
    "\n",
    "\n",
    "\\end{bmatrix}^T\n",
    "\n",
    "\n",
    "=\n",
    "\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "6 & 6 & 3  \\\\\n",
    "8 & 8 & 4  \\\\\n",
    "12 & 12 & 6  \\\\\n",
    "\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "3  \\\\\n",
    "4  \\\\\n",
    "6  \\\\\n",
    "\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2 & 2 & 1  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "vu^T\n",
    "\n",
    "$$\n",
    "\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "b02d65ddfde978b2"
  },
  {
   "cell_type": "markdown",
   "source": [
    "We are seeing the clearest possible example of the first great theorem in linear algebra:\n",
    "\n",
    "$$\n",
    "\n",
    "ROW RANK = COLUMN RANK  \n",
    "\n",
    "$$\n",
    "\n",
    "$$\n",
    "\n",
    "r \\:independent\\:columns\\:<=>\\:r\\:independent\\:rows\n",
    "\n",
    "$$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "db3b1c50cfd06854"
  },
  {
   "cell_type": "markdown",
   "source": [
    "A nonzero matrix $uv^T$ has one independent column and one independent row.\n",
    "\n",
    "All columns are multiplies of $u$ and all rows are multiplies of $v^T$.\n",
    "\n",
    "The rank is $r = 1$ for this matrix."
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "71195e5f1048c1a6"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## $AB$ = SUM OF RANK ONE MATRICES"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "b88ee69b53a28b36"
  },
  {
   "cell_type": "markdown",
   "source": [
    "We turn to the full product $AB$, using columns of A times rows B.\n",
    "\n",
    "Let $a_1,a_2,...,a_n$ be the $n$ columns of A. Then B must have $n$ rows $b_1 ^*$, $b_2 ^*$, ..., $b_n ^*$. The matrix A can multiply the matrix B.\n",
    "\n",
    "**Their product $AB$ is the sum of columns $a_k$ times rows $b_k ^*$:\n",
    "\n",
    "$$\n",
    "Column-Row\\:Multiplication\\:of\\:Matrices\n",
    "$$\n",
    "\n",
    "$$\n",
    "\n",
    "AB\n",
    "\n",
    "=\n",
    "\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "| &  & |  \\\\\n",
    "a_1 & ... & a_n  \\\\\n",
    "| &  & |  \\\\\n",
    "\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\\begin{bmatrix}\n",
    "\n",
    "-- & b_1 ^* & --  \\\\\n",
    " & ... &   \\\\\n",
    "-- & b_n ^* & --  \\\\\n",
    "\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "a_1*b_1 ^* + a_2*b_2 ^* + ... + a_n*b_n ^*\n",
    "\n",
    "$$\n",
    "\n",
    "$$\n",
    "\n",
    "Sum\\:of\\:rank\\:1\\:matrices\n",
    "\n",
    "$$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "67b210fd4e84b9a5"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Please see 2 by 2 example to show the n=2 pieces (column times row) and their sum AB:"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "220e7540ea944240"
  },
  {
   "cell_type": "markdown",
   "source": [
    "\n",
    "$$\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "1 & 0 \\\\\n",
    "3 & 1 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2 & 4 \\\\\n",
    "0 & 5 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "1  \\\\\n",
    "3  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2 & 4 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "+\n",
    "\\begin{bmatrix}\n",
    "\n",
    "0  \\\\\n",
    "1  \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "*\n",
    "\\begin{bmatrix}\n",
    "\n",
    "0 & 5 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2 & 4 \\\\\n",
    "6 & 12 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "+\n",
    "\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "0 & 0 \\\\\n",
    "0 & 5 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\n",
    "\\begin{bmatrix}\n",
    "\n",
    "2 & 4 \\\\\n",
    "6 & 17 \\\\\n",
    "\n",
    "\\end{bmatrix}\n",
    "\n",
    "$$\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "9052a0230fe5aa1f"
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "outputs": [
    {
     "data": {
      "text/plain": "array([[1, 0],\n       [3, 1]])"
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_Sum = np.array([[1,0],[3,1]])\n",
    "A_Sum"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-25T03:13:04.971296200Z",
     "start_time": "2024-03-25T03:13:04.705357Z"
    }
   },
   "id": "a75014f71d673e20"
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "outputs": [
    {
     "data": {
      "text/plain": "array([[2, 4],\n       [0, 5]])"
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "B_Sum = np.array([[2,4],[0,5]])\n",
    "B_Sum"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-25T03:13:05.001241900Z",
     "start_time": "2024-03-25T03:13:04.724614Z"
    }
   },
   "id": "9dc182dde82e5c8c"
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "outputs": [
    {
     "data": {
      "text/plain": "array([[ 2,  4],\n       [ 6, 17]])"
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C_Sum= np.dot(A_Sum,B_Sum)\n",
    "C_Sum"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-25T03:13:05.021820200Z",
     "start_time": "2024-03-25T03:13:04.763954600Z"
    }
   },
   "id": "b471ea46b8bbfa17"
  },
  {
   "cell_type": "markdown",
   "source": [
    "We can count t he multiplications of number times number.\n",
    "\n",
    "Four multiplications to get 2,4,6,12. Four more to get 0,0,0,5.\n",
    "\n",
    "A total of 2^3 = 8 multiplications.\n",
    "\n",
    "Always there are n^3 multiplications when A and B are n by n.\n",
    "\n",
    "an $mnp$ multiplications when AB = (m by n) times (n by p): n rank one matrices, each of those matrices is m by p.\n",
    "\n",
    "$$\n",
    "\n",
    "rows\\:times\\:columns\\:\\: = \\:\\: mp \\: inner \\: products,\\:n\\:multiplications\\:each\\:\\:\\:=\\:mnp\n",
    "$$\n",
    "\n",
    "$$\n",
    "\n",
    "columns\\:times\\:rows\\:\\: = \\:\\: n \\: outer \\: products,\\:mp\\:multiplications\\:each\\:\\:\\:=\\:mnp\n",
    "\n",
    "$$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "f98a53fb693e5cd1"
  },
  {
   "cell_type": "markdown",
   "source": [
    "When you look closely, they are exactly the same multiplications $a_i _k$ $b_i _j$ in different order.\n",
    "\n",
    "Here is the algebra proof that each number $c_i _j$ in C = AB is the same be outer products as by inner products:\n",
    "\n",
    "The $i$,$j$ entry of a $a_k b_k ^*$ is $ a_i _k b_k _j$.\n",
    "\n",
    "\n",
    "Add to find $c_i _j$ = $\\sum^n_k_=_1 a_i _k b_k _j = row\\:i \\: * \\: column\\:j. $"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "bb9c32cb2370c850"
  },
  {
   "cell_type": "markdown",
   "source": [
    "## INSIGHTS FROM COLUMN TIMES ROW"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "c1550d2ad1507420"
  },
  {
   "cell_type": "markdown",
   "source": [
    "**Why is the outer product approach is essential in data science?**\n",
    "\n",
    "The short answer is :\n",
    "\n",
    "*We are looking for the important part of a matrix A*\n",
    "\n",
    "\n",
    "We do not usually want the biggest number in A (though that could be important).\n",
    "\n",
    "What we want more is the largest piece of A.\n",
    "\n",
    "**And those pieces are rank one matrices $uv^T$.**\n",
    "\n",
    "A dominant theme in applied linear algebra is:\n",
    "\n",
    "$$\n",
    "\n",
    "Factor\\:A\\:into\\:CR\\:and\\:look\\:at\\:the\\:pieces\\: c_k r_k ^*\\:of\\:A\\:=\\:CR.\n",
    "\n",
    "$$ \n",
    "\n",
    "Factoring A into CR is the reverse of multiplying CR = A.\n",
    "\n",
    "Factoring takes longer, especially if the pieces involve eigenvalues or singular values.\n",
    "\n",
    "But those numbers have inside information about the matrix A.\n",
    "\n",
    "That information is not visible until you factor.\n",
    "\n",
    "Here are five important factorizations, with the standard choice of letters (usually A) for the original product matrix and then for its factors.\n",
    "\n",
    "$$\n",
    "1-)\\:A\\: =\\: LU\n",
    "$$\n",
    " \n",
    "\n",
    "$$\n",
    "2-)\\:A\\: =\\: QR\n",
    "$$\n",
    "\n",
    "$$\n",
    "3-)\\:S\\: =\\: QΛQ^T\n",
    "$$\n",
    "\n",
    "$$\n",
    "\n",
    "4-)\\:A\\: =\\: XΛX^- ^1\n",
    "\n",
    "$$\n",
    "\n",
    "$$\n",
    "\n",
    "5-)\\:A\\: =\\: UΣV^T\n",
    "\n",
    "$$\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "a337182e70ebecda"
  },
  {
   "cell_type": "markdown",
   "source": [
    "At this point, we simply list key words and properties for each of these factorization.\n",
    "\n",
    "1-) A = LU comes from elimination.\n",
    "\n",
    "Combinations of rows take A to U and U back to A. The Matrix L is lower triangular and U is upper triangular.\n",
    "\n",
    "2-) A = QR comes from orthogonalizing the columns $a_1$ to $a_n$ as in \"Gram-Schmidt\".\n",
    "\n",
    "Q has orthonormal columns ($Q^TQ$=$I$) and R is upper triangular.\n",
    "\n",
    "3-) $S$ = $QΛQ^T$ comes from the eigenvalues $λ_1$,...,$λ_n$ of a symmetric matrix $S$ = $S^T$.\n",
    "\n",
    "Eigenvalues on the diagonal of Λ.\n",
    "\n",
    "Orthonormal eigenvectors in the columns of Q.\n",
    "\n",
    "4-) $A$ =  $QΛQ^- ^1$ is diagonalization when A is n by n with n independent eigenvectors.\n",
    "\n",
    "Eigenvalues of A on the diagonal of Λ.\n",
    "\n",
    "Eigenvectors of A in the columns of X.\n",
    "\n",
    "5-) $A$ = $UΣV^T$ is the Singular Value Decomposition of any matrix A (square or not).\n",
    "\n",
    "Singular values $σ_1$,...,$σ_r$ in Σ.\n",
    "\n",
    "Orthonormal singular vectors in U and V.\n",
    "\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "57d89b0e5c1b19c6"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Let me pick out a favorite (number 3) to illustrate the idea.\n",
    "\n",
    "This special factorization $QΛQ^T$ starts with a symmetric matirx S.\n",
    "\n",
    "That matrix has orthogonal unit eigenvectors $q_1$,...,$q_n$.\n",
    "\n",
    "Those perpendicular eigenvectors (dot products = 0) go into the columns of Q.\n",
    "\n",
    "S and Q are the kings and queens of linear algebra.\n",
    "\n",
    "$$\n",
    "\n",
    "Symmetric\\:matrix\\:$S$\\:\\:\\:\\:\\: $S^T$ = $S$\\:\\:\\:\\:\\:\\: All\\: s_i _j = s_j _i\n",
    "\n",
    "$$\n",
    "\n",
    "$$\n",
    "\n",
    "Orthogonal\\:matrix\\:$Q$\\:\\:\\:\\:\\: $Q^T$ = $Q^- ^1$\\:\\:\\:\\:\\:\\: All\\: q_i * q_j = \\{0\\: for\\: $i$ ≠ \\:$j$ \\:and\\: 1\\: for \\: $i$ = $j$ \\}\n",
    "\n",
    "$$\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "44af4edc190ab05d"
  },
  {
   "cell_type": "markdown",
   "source": [
    "The diagonal matrix $Λ$ contains real eigenvalues $λ_1$ to $λ_n$.\n",
    "\n",
    "Every real symmetric matrix $S$ has n orthonormal eigenvectors $q_1$ to $q_n$.\n",
    "\n",
    "When multiplied by S, the eigenvectors keep the same direction.\n",
    "\n",
    "They are just rescaled by the number $λ$:\n",
    "\n",
    "$$\n",
    "\n",
    "Eigenvector\\:$q$\\:and\\:eigenvalue\\:$λ$\\:\\:\\:\\:\\:\\:\\: $S_q$ = $λ_q$\n",
    "\n",
    "$$  \n",
    "\n",
    "Finding $λ$ and $q$ is not easy for a big matrix.\n",
    "\n",
    "But n pairs always exist when S is symmetric.\n",
    "\n",
    "Our purpose here is to see how $SQ$ = $QΛ$ comes column by column from $S_q$ = $λ_q$:\n",
    "\n",
    "\n",
    "$$\n",
    "\n",
    "SQ \n",
    "\n",
    "=\n",
    "\n",
    "S\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "&  &   \\\\\n",
    "&  &   \\\\\n",
    "&  &   \\\\\n",
    " &  &   \\\\\n",
    "q_1 & ... & q_n  \\\\\n",
    " &  &   \\\\\n",
    "&  &   \\\\\n",
    "&  &   \\\\\n",
    "&  &   \\\\\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "\\begin{bmatrix}\n",
    "&  &   \\\\\n",
    "&  &   \\\\\n",
    "&  &   \\\\\n",
    " &  &   \\\\\n",
    "λ_1q_1 & ... & λ_nq_n  \\\\\n",
    " &  &   \\\\\n",
    "&  &   \\\\\n",
    "&  &   \\\\\n",
    "&  &   \\\\\n",
    "\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\n",
    "=\n",
    "\\begin{bmatrix}\n",
    "&  &   \\\\\n",
    "&  &   \\\\\n",
    "&  &   \\\\\n",
    " &  &   \\\\\n",
    "q_1 & ... & q_n  \\\\\n",
    " &  &   \\\\\n",
    "&  &   \\\\\n",
    "&  &   \\\\\n",
    "&  &   \\\\\n",
    "\\end{bmatrix}\n",
    "\n",
    "*\n",
    "\n",
    "\\begin{bmatrix}\n",
    "λ_1&  &   \\\\\n",
    "& . &   \\\\\n",
    "& . &   \\\\\n",
    " & . &   \\\\\n",
    " & ... &   \\\\\n",
    " & . &   \\\\\n",
    "& . &   \\\\\n",
    "& . &   \\\\\n",
    "&  & λ_n  \\\\\n",
    "\\end{bmatrix}\n",
    "\n",
    "=\n",
    "\n",
    "QΛ\n",
    "\n",
    "\n",
    "$$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "aa86288b30907304"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Multiply $SQ$ = $QΛ$ are $Q^- ^1$ = $Q^T$ to get $S=QΛQ^T$ = a symmetric matrix.\n",
    "\n",
    "Each eigenvalue $λ_k$ and each eigenvector $q_k$ contribute a rank one piece $λ_k q_k q_k ^T$ to S.\n",
    "\n",
    "$$\n",
    "\n",
    "Rank\\:One\\:Pieces\\:\\:\\:\\: $S=(QΛ)Q^T$ =\\: $(λ_1 q_1) q_1 ^T$ + $(λ_2 q_2) q_2 ^T$ + ... +$(λ_n q_n) q_n ^T$ \n",
    "\n",
    "$$  \n",
    "\n",
    "$$\n",
    "\n",
    "All\\:\\:Symmetric\\:\\:\\:\\:\\:\\:\\: The\\: transpose \\:of \\:$q_i q_i ^T$ \\: is \\:$q_i q_i ^T$\n",
    "\n",
    "$$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "ab8e41da7ec66e33"
  },
  {
   "cell_type": "markdown",
   "source": [
    "Please notice that the columns of $QΛ$ are $(λ_1 q_1)$ to $(λ_n q_n)$.\n",
    "\n",
    "When you multiply a matrix on the right by the diagonal matrix $Λ$, you multiply its columns by the $λ$'s"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "4109e4a15d694818"
  },
  {
   "cell_type": "markdown",
   "source": [
    "We close with a comment on the proof of this **Spectral Theorem $S$ = $QΛQ^T$**:\n",
    "\n",
    "Every symmetric S has n real eigenvalues and n orthonormal eigenvectors.\n",
    "\n",
    "In eigenvalue and eigenvectors section, we will construct the eigenvalues as the roots of the nth degree polynomial $P_n (λ)$ = determinant of $S - λ I$.\n",
    "\n",
    "They are real numbers when $S$ = $S^T$.\n",
    "\n",
    "The delicate part of the proof comes when an eigenvalue $λ_i$ is repeated - it is a double root or an Mth root from a factor $(λ - λ_j)^M$.\n",
    "\n",
    "In this case, we need to produce M independent eigenvectors.\n",
    "\n",
    "The rank of $S - λ_jI$ must be n-M.\n",
    "\n",
    "This is true when $S = S^T$. But it requires a proof.\n",
    "\n",
    "Similarly, the Singular Value Decomposition $ A $ = $UΣV^T$ requires extra patience when a singular value σ is repeated M times in the diagonal matrix Σ.\n",
    "\n",
    "Again, there are M pairs of singular vectors $v$ and $u$ with $Av$ = $σu$. Again this true statement requires proof.\n",
    "\n",
    "**Notation for rows**:\n",
    "\n",
    "We introduced the symbols $b_1 ^*$, ... , $b_n ^*$ for the rows of the second matrix in AB.\n",
    "\n",
    "You might have expected $b_1 ^T$, ... , $b_n ^T$ and that was our original choice.\n",
    "\n",
    "But this notation is not entirely clear- it seems to mean the transposes of the columns of B.\n",
    "\n",
    "Since that right hand factor could be $U$ or $R$ or $Q^T$ or $X^- ^1$ or $V^T$, it is safer to say definitely:\n",
    "\n",
    "**We want the rows of that matrix**\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "2bb40de6624ba982"
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-03-25T03:13:05.022818600Z",
     "start_time": "2024-03-25T03:13:04.788566400Z"
    }
   },
   "id": "4d9c9e5d8d7da609"
  }
 ],
 "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
}