{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Singular matrices: A first look\n",
    "\n",
    "If we encounter a zero pivot (or even just a small pivot, on a computer) during Gaussian elimination, we normally swap rows to bring a nonzero pivot up from a subsequent row.  However, what if there are *no* nonzero values below the pivot in that column?  This is called a [singular matrix](https://en.wikipedia.org/wiki/Invertible_matrix): we can still proceed with Gaussian elimination, but **we can't get rid of the zero pivot**.\n",
    "\n",
    "If you have $Ax=b$ where $A$ is singular, then there will typically (for most right-hand sides $b$) be **no solutions**, but there will occasionally (for very special $b$) be **infinitely many solutions**.  (For $2 \\times 2$ matrices, solving $Ax=b$ corresponds to finding the intersection of two lines, and a singular case corresponds to two parallel lines — either there are no intersections, or they intersect everywhere.)\n",
    "\n",
    "For example, consider the following $4 \\times 4$ matrix $A=LU$:\n",
    "\n",
    "$$\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "             2 & -1 & 0 &  3 \\\\\n",
    "             4 & -1 & 1 &  8 \\\\\n",
    "             6 &  1 & 4 & 15 \\\\\n",
    "             2 & -1 & 0 &  0 \\\\\n",
    "            \\end{pmatrix}}_A =\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "                1 & 0 & 0 & 0 \\\\\n",
    "                2 & 1 & 0 & 0 \\\\\n",
    "                3 & 4 & 1 & 0 \\\\\n",
    "                1 & 0 & 2 & 1 \\\\\n",
    "            \\end{pmatrix}}_L\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "                \\color{blue}{2} & -1 &  0 &  3 \\\\\n",
    "                0 &  \\color{blue}{1} &  1 &  2 \\\\\n",
    "                0 &  0 &  \\color{red}{0} & \\color{blue}{-2} \\\\\n",
    "                0 &  0 &  0 &  1 \\\\\n",
    "            \\end{pmatrix}}_U\n",
    "$$\n",
    "\n",
    "In the **third column, we got zeros** where we were hoping for a pivot.  So, we **only have three pivots (blue)** in this case.   Now, suppose we want to solve $Ax=b$.  We first solve $Lc=b$ to apply the elimination steps to $b$.  This is no problem since $L$ has 1's along the diagonal. Suppose we get $c = (c_1, c_2, c_3, c_4)$.  Then we proceed by backsubstitution to solve $Ux = c$, starting with the last row of $U$:\n",
    "\n",
    "$$\n",
    "1 \\times x_4 = c_4 \\implies x_4 = c_4 \\\\\n",
    "\\color{red}{0 \\times x_3} - 2 \\times x_4 = c_3 \\implies \\mbox{no solution unless } -2 x_4 = -2 c_4 = c_3\n",
    "$$\n",
    "For very special right-hand sides, where $c_3 = 2c_4$, we can plug in *any* $x_3$ and get a solution (infinitely many solutions).  Otherwise, we get *no* solutions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4×4 Matrix{Int64}:\n",
       " 2  -1  0   3\n",
       " 4  -1  1   8\n",
       " 6   1  4  15\n",
       " 2  -1  0   0"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[1 0 0 0\n",
    " 2 1 0 0\n",
    " 3 4 1 0\n",
    " 1 0 2 1 ] *\n",
    "[2 -1  0  3\n",
    " 0  1  1  2\n",
    " 0  0  0 -2\n",
    " 0  0  0  1 ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may think that singular cases are not very interesting.  In reality, **exactly singular square matrices never occur by accident**.  There is always some *deep structure of the underlying problem* that causes the singularity, and understanding this structure is *always* interesting.\n",
    "\n",
    "On the other hand, **nearly singular** matrices (where the pivots are nonzero but very small) *can* occur by accident, and dealing with them is often a delicate problem because they are very sensitive to roundoff errors.  (We call these matrices [ill-conditioned](https://en.wikipedia.org/wiki/Condition_number).)  But that's mostly not a topic for 18.06.\n",
    "\n",
    "Singular **non-square** systems, where you have **more equations than unknowns** are *very* common and important, and lead to *fitting* problems where one *minimizes the error* in the solution.  We will talk more about this soon in 18.06."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some matrices are **more singular than others**.  For example, they can have **two pivots**:\n",
    "\n",
    "$$\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "             2 & -1 & 0 &  3 \\\\\n",
    "             4 & -2 & 1 &  8 \\\\\n",
    "             6 &  3 & 4 & 17 \\\\\n",
    "             2 & -1 & 0 &  3 \\\\\n",
    "            \\end{pmatrix}}_A =\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "                1 & 0 & 0 & 0 \\\\\n",
    "                2 & 1 & 0 & 0 \\\\\n",
    "                3 & 4 & 1 & 0 \\\\\n",
    "                1 & 0 & 2 & 1 \\\\\n",
    "            \\end{pmatrix}}_L\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "                \\color{blue}{2} & -1 &  0 &  3 \\\\\n",
    "                0 &  0 &  \\color{blue}{1} &  2 \\\\\n",
    "                0 &  0 &  \\color{red}{0} & \\color{red}{0} \\\\\n",
    "                0 &  0 &  0 &  \\color{red}{0} \\\\\n",
    "            \\end{pmatrix}}_U\n",
    "$$\n",
    "\n",
    "or **one pivot**:\n",
    "\n",
    "$$\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "             2 & -1 & 0 &  3 \\\\\n",
    "             4 & -2 & 0 &  6 \\\\\n",
    "             6 &  3 & 0 &  9 \\\\\n",
    "             2 & -1 & 0 &  3 \\\\\n",
    "            \\end{pmatrix}}_A =\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "                1 & 0 & 0 & 0 \\\\\n",
    "                2 & 1 & 0 & 0 \\\\\n",
    "                3 & 4 & 1 & 0 \\\\\n",
    "                1 & 0 & 2 & 1 \\\\\n",
    "            \\end{pmatrix}}_L\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "                \\color{blue}{2} & -1 &  0 &  3 \\\\\n",
    "                0 &  0 &  0 &  0 \\\\\n",
    "                0 &  0 &  0 & 0 \\\\\n",
    "                0 &  0 &  0 &  0 \\\\\n",
    "            \\end{pmatrix}}_U\n",
    "$$\n",
    "\n",
    "or **zero pivots**:\n",
    "\n",
    "$$\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "                0 &  0 &  0 & 0 \\\\\n",
    "                0 &  0 &  0 &  0 \\\\\n",
    "                0 &  0 &  0 & 0 \\\\\n",
    "                0 &  0 &  0 &  0 \\\\\n",
    "            \\end{pmatrix}}_A =\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "                1 & 0 & 0 & 0 \\\\\n",
    "                2 & 1 & 0 & 0 \\\\\n",
    "                3 & 4 & 1 & 0 \\\\\n",
    "                1 & 0 & 2 & 1 \\\\\n",
    "            \\end{pmatrix}}_L\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "                0 &  0 &  0 & 0 \\\\\n",
    "                0 &  0 &  0 &  0 \\\\\n",
    "                0 &  0 &  0 & 0 \\\\\n",
    "                0 &  0 &  0 &  0 \\\\\n",
    "            \\end{pmatrix}}_U\n",
    "$$\n",
    "\n",
    "If $A$ is the zero matrix, then $Ax=b$ only has solutions when $b=0$, and then *any* $x$ is a solution!\n",
    "\n",
    "Intuitively, having fewer pivots seems \"more singular\", and requires \"more coincidences\" in the right-hand side to have a solution, and has a \"bigger infinity\" of solutions when there *is* a solution.   We will quantify intuitions in 18.06, starting with the notion of the [rank](https://en.wikipedia.org/wiki/Rank_(linear_algebra) of a matrix.\n",
    "\n",
    "* The **rank = r** of the matrix is the **number of (nonzero) pivots** obtained by elimination (with row swaps if needed) for an $m \\times n$ matrix $A$. \n",
    "\n",
    "* $r \\le m$ and $r \\le n$ because you can't have more pivots than you have rows or columns.\n",
    "\n",
    "The smaller the rank is compared to the size of the matrix, the \"more singular\" it is.  Pretty soon we will understand this better."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4×4 Matrix{Int64}:\n",
       " 2  -1  0   3\n",
       " 4  -2  1   8\n",
       " 6  -3  4  17\n",
       " 2  -1  0   3"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[1 0 0 0\n",
    " 2 1 0 0\n",
    " 3 4 1 0\n",
    " 1 0 2 1 ] *\n",
    "[2 -1  0  3\n",
    " 0  0  1  2\n",
    " 0  0  0  0\n",
    " 0  0  0  0 ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4×4 Matrix{Int64}:\n",
       " 2  -1  0  3\n",
       " 4  -2  0  6\n",
       " 6  -3  0  9\n",
       " 2  -1  0  3"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[1 0 0 0\n",
    " 2 1 0 0\n",
    " 3 4 1 0\n",
    " 1 0 2 1 ] *\n",
    "[2 -1  0  3\n",
    " 0  0  0  0\n",
    " 0  0  0  0\n",
    " 0  0  0  0 ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that if we encounter zeros in a column where we were hoping for a pivot, and we can't get a nonzero element by swapping rows, we skip to the next column.  The following example is **rank 2**, not rank 0:\n",
    "\n",
    "$$\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "             0 & -1 & 0 &  3 \\\\\n",
    "             0 & -2 & 0 &  8 \\\\\n",
    "             0 &  3 & 0 & 17 \\\\\n",
    "             0 & -1 & 0 &  3 \\\\\n",
    "            \\end{pmatrix}}_A =\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "                1 & 0 & 0 & 0 \\\\\n",
    "                2 & 1 & 0 & 0 \\\\\n",
    "                3 & 4 & 1 & 0 \\\\\n",
    "                1 & 0 & 2 & 1 \\\\\n",
    "            \\end{pmatrix}}_L\n",
    "\\underbrace{\\begin{pmatrix} \n",
    "                0 & \\color{blue}{-1} &  0 &  3 \\\\\n",
    "                0 &  0 &  0 &  \\color{blue}{2} \\\\\n",
    "                0 &  0 &  0 & 0 \\\\\n",
    "                0 &  0 &  0 &  0 \\\\\n",
    "            \\end{pmatrix}}_U\n",
    "$$\n",
    "\n",
    "That is, if we encounter *all zeros* in a column where we were hoping for a pivot, we skip to the next column for our pivot and continue eliminating below the pivots."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4×4 Matrix{Int64}:\n",
       " 0  -1  0   3\n",
       " 0  -2  0   8\n",
       " 0  -3  0  17\n",
       " 0  -1  0   3"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[1 0 0 0\n",
    " 2 1 0 0\n",
    " 3 4 1 0\n",
    " 1 0 2 1 ] *\n",
    "[0 -1  0  3\n",
    " 0  0  0  2\n",
    " 0  0  0  0\n",
    " 0  0  0  0 ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# More to come\n",
    "\n",
    "Much of the material in the second part of 18.06 (somewhat in exam 1, but especially in exam 2) will be focused on how we understand **singular and non-square** systems of equations.\n",
    "\n",
    "It turns out that there are lots of interesting things to say and do about systems of equations that may not have solutions.  We don't just give up!"
   ]
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "kernelspec": {
   "display_name": "Julia 1.7.1",
   "language": "julia",
   "name": "julia-1.7"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}