rowEchelon.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import dependency\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# List comprehensions\n",
    "A list comprehension is used in the **rowMod0* function and thus we will have a look at it shortly.\n",
    "\n",
    "From the Doc:\n",
    ">List comprehensions provide a concise way to create lists. Common applications are to make new lists where each element is the result of some operations applied to each member of another sequence or iterable, or to create a subsequence of those elements that satisfy a certain condition.\n",
    "\n",
    "For example let's say you would like to calculate the square of all numbers from 1 to 10. You could use a for loop like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the array to store the squares \n",
    "squares = []\n",
    "for x in range(10):\n",
    "    # appends adds an element to an array\n",
    "    squares.append(x**2)\n",
    "squares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or we can use **list comprehension**, then it would look like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# in other words we apply a function for every x in range(10)\n",
    "# here the function is calculating the square of each iterator\n",
    "squares = [x**2 for x in range(10)]\n",
    "squares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, the results are identical. The function **rowMod0** also uses the **zip** function which we are going to see for ourselves next."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# zip function explained\n",
    "From the Doc:\n",
    ">zip(*iterables)\n",
    "Make an iterator that aggregates elements from each of the iterables.\n",
    "Returns an iterator of tuples, where the i-th tuple contains the i-th element from each of the argument sequences or iterables.\n",
    "\n",
    "Which begs the question what is an iterator? W3schools offers a definition which is actually human readable\n",
    ">An iterator is an object that can be iterated upon, meaning that you can traverse through all the values.\n",
    "\n",
    "Thus, iterators in python are **Lists, tuples, dictionaries, strings* and sets.**\n",
    "\n",
    "_\\*strings in python are lists of chars_  \n",
    "\n",
    "We will use the zip function which string lists to start:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# borrowed from W3schools \n",
    "# we define two iterables, here two arrays that contain names.\n",
    "a = (\"John\", \"Kurt\", \"Chandler\")\n",
    "b = (\"Yoko\", \"Courtney\", \"Monica\")\n",
    "\n",
    "couples = zip(a, b)\n",
    "\n",
    "#use the tuple() function to display a readable version of the result:\n",
    "print(tuple(couples))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see **zip()** did aggreate both elements from both lists. Now let's take a simple example where the iterators for the zip functions are simple integer arrays. These integer arrays could represent the row of a matrix for example. We will simply add the ith / jth element of each iterator together:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define the iterators\n",
    "a = [1,2,3]\n",
    "b = [3,2,1]\n",
    "# define the empty array storing the result\n",
    "res = []\n",
    "# here i or j are the current value of a[iterator] and respective b[iterator]\n",
    "for a, b in zip(a,b):\n",
    "    res.append(a + b)\n",
    "    print(\"a is currently {} and b is currenbtly {} and res is currently {}\".format(a,b,res))\n",
    "res\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course we could also do the same with **list comprehension** like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define the iterators again\n",
    "a = [1,2,3]\n",
    "b = [3,2,1]\n",
    "# a much more concise way\n",
    "res = [a + b for a, b in zip(a, b)]\n",
    "res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we are armed to take a look at **rowMod0()**. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# rowMod0\n",
    "This one liner accomplishes that you can add a row multiplied by a constant to another row. This is the same as operation III, which was described on the lecture slide SW02 number 12.\n",
    "\n",
    "Let's take a brief look at the args that the function expects:\n",
    "**M** is the matrix that you want to perform that row operation on.  \n",
    "**i** is the row of the matrix that you will add the other matrix to that has been multiplied by a constant. The matrix, where you want to eliminate the Leitkoeffizient.\n",
    "**j** is the row of the matrix that you **multiply with a constant** and then add to row i  \n",
    "**x** the constant with which you will multiply j in order to eliminate one variable.\n",
    "\n",
    "So let's finally have a look at the function!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rowMod0 (M,i,j,x):\n",
    "    # the result will be stored in M[i] which is the row which we want to eliminate a variable in\n",
    "    # we use zip and iterate over each element of both rows and apply the function\n",
    "    # a + x*b to each element\n",
    "    # and that's rowMod0()\n",
    "    M[i] = [a+x*b for a, b in zip(M[i],M[j])]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Time for an example. Let's create a simple matrix **\\begin{bmatrix}\n",
    "1 & 1 & 1\\\\\n",
    "3 & 4 & 4\n",
    "\\end{bmatrix}**\n",
    "\n",
    "from that matrix we want to change the 3 in the second row to a zero in order to get the row echelon form. So we want it to look like that afterwards. For that we will use **rowMod0()**.\n",
    "\n",
    "**\\begin{bmatrix}\n",
    "1 & 1 & 1\\\\\n",
    "0 & 1 & 1\n",
    "\\end{bmatrix}**\n",
    "\n",
    "In order to get the second matrix as a result we need to add -3 * III to II. Thus our constant x will be -3. We want the second row to be transformed, therefore i is 1 (arrays start at zero). We will use the first row to multiply it by a constant and add it to the second column, hence j=0. \n",
    "Now let's use the function with the defined args!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define the matrix a\n",
    "a = np.array([[1,1,1],[3,4,4]])\n",
    "print(\"The matrix as defined previously is \\n{}\".format(a))\n",
    "a_row_echelon_form = rowMod0(a,1,0,-3)\n",
    "print(\"The matrix after using rowMod0() is \\n{}\".format(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For illustration purpose let's look at an implementation of **rowMod0()** that uses a for loop instead of list comprehensions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rowMod0ForLoop (M,i,j,x):\n",
    "    # the result will be stored in M[i] which is the row which we want to eliminate a variable in\n",
    "    # we use zip and iterate over each element of both rows \n",
    "    # initialize the M_new which where we will store the results of the loop\n",
    "    M_new = []\n",
    "    for a, b in zip(M[i],M[j]):\n",
    "        M_new.append(a + b * x)\n",
    "    # assign the value of M_new to M[i]\n",
    "    M[i] = M_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define the matrix a\n",
    "a = np.array([[1,1,1],[3,4,4]])\n",
    "print(\"The matrix as defined previously is \\n{}\".format(a))\n",
    "a_row_echelon_form = rowMod0ForLoop(a,1,0,-3)\n",
    "print(\"The matrix after using rowMod0() is \\n{}\".format(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected we received the same result. Now let's tackle the elephant in the room **rowEchelon0()**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# understanding rowEchelon0()\n",
    "I first thought about drawing a flowchart or using pseudo code but that would get messy very quickly. So instead I will simply explain what specific snippets do and then you will understand the big picture hopefully.\n",
    "## snippet 1                   \n",
    "    while row < rows and col < cols:\n",
    "        # Versuche Pivotelement zu finden\n",
    "        if M[row][col] == 0:\n",
    "            # die Zeilen unter row durchgehen\n",
    "            for r in range(row + 1, rows):\n",
    "                if M[r][col] != 0:\n",
    "                    # iterate through rows to find one that has a Leitkoeffizienten and add it to the first row\n",
    "                    rowMod0(M,row,r,1)\n",
    "                    break\n",
    "                    \n",
    "\n",
    "This snippet does nothing else than:\n",
    "1. check if element at current row, column is not zero\n",
    "2. if not loop through rows at that column until you find one row that is not zero\n",
    "3. then add the non-zero row to your inital row where you started.\n",
    "4. then you leave the loop.\n",
    "\n",
    "This accomplishes that you get a pivot instead of a zero in your current row.\n",
    "## snippet 2\n",
    "    # if all rows at M[r][col] are zero then there is simply not a Leitkoeffizienten at that column so increase column by one\n",
    "        if M[row][col] == 0:\n",
    "            col += 1\n",
    "            continue\n",
    "\n",
    "\n",
    "This snippet is quite simple and does the following:\n",
    "1. check that if even after iterating through all rows at a column that the element is still zero (this means the whole column is filled with zeros).\n",
    "2. as the whole column is filled with zero there won't be a Leitkoeffizienten or a Pivot in this column, hence we increase the column.\n",
    "3. then we start again at the first code snippet because there is nothing we could do in that row. So back to snippet 1 with the next column.  \n",
    "\n",
    "## snippet 3\n",
    "    pivot = M[row][col]\n",
    "\n",
    "This snippet is only reached when M[row][col] is no longer zero and thus we have a pivot point. It is a pivot and not just a Leitkoeffizient as there are two scenarios:\n",
    "1. This is our first column of the matrix and therefore if there is a non zero number at that column we have a Leitkoeffizient by definition.\n",
    "2. This is not our first column but all the other columns are filled with zeros (result of snippet 1 and 2, thus we have a Leitkoeffizient by definition.\n",
    "3. From here on I refer to this current row as pivot row. This will help explain the next snippet.\n",
    "\n",
    "## snippet 4\n",
    "    for r in range(row + 1, rows):\n",
    "                # die Zeilen unter row durchgehen\n",
    "                if M[r][col] != 0:\n",
    "                    # r is the row below that will be transformed\n",
    "                    # row is the row where we found the pivot\n",
    "                    # M[r][col] is the Leitkoeffizient at the row below \n",
    "                    # the term -M[r][col]/pivot is the constant by dividing M[r][col] / pivot \n",
    "                    # we get -M[r][col]/pivot*pivot = -M[r][col] \n",
    "                    # and adding this to M[r][col] wil eliminate that Leitkoeffizient\n",
    "                    rowMod0(M,r,row, -M[r][col]/pivot)\n",
    "\n",
    "This is the longest snippet that we will have a look at. It does the following:\n",
    "1. We reached this because our pivot row element is non-zero. This follows from snippet 1-4.\n",
    "2. We loop through all rows below our pivot row. \n",
    "3. If a row below is non-zero we eliminate it by adding our pivot row multiplied by -1 * Leitkoeffizient of the current row / pivot\n",
    "4. The constant multiplied by our pivot value results in the following:  \n",
    "$$\\frac{-1 * Leitkoeffizient * pivot}{pivot} = -Leitkoeffizient$$ \n",
    "5. and because we will add this to our current non-zero row, the value of that row at that column turns zero.\n",
    "6. This brings us a step closer to our row echelon form, because we will simply loop over all rows below our pivot and set them zero with the steps 3,4.\n",
    "\n",
    "## snippet 5\n",
    "    row += 1\n",
    "    col += 1\n",
    "This short snippet marks the end of that lengthy explanation. It does the following:\n",
    "1. Because of snippet 4 we have a pivot at our column and all rows below it are now zeros.\n",
    "2. The only thing that remains is to increase the column and the vector so we can apply snippet 1-4 to the rest of the matrix.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rowEchelon0 (M):\n",
    "    # Auf Deutsch: Zeilenstufenform\n",
    "    row, col = 0,0\n",
    "    rows, cols = len(M), len(M[0])\n",
    "    while row < rows and col < cols:\n",
    "        # Versuche Pivotelement zu finden\n",
    "        if M[row][col] == 0:\n",
    "            # die Zeilen unter row durchgehen\n",
    "            for r in range(row + 1, rows):\n",
    "                if M[r][col] != 0:\n",
    "                    # iterate through rows to find one that has a Leitkoeffizienten and add it to the row from where this for loop started\n",
    "                    rowMod0(M,row,r,1)\n",
    "                    break\n",
    "        # if all rows at M[r][col] are zero then there is simply not a Leitkoeffizienten at that column so increase column by one (all elements are zero in this column)\n",
    "        if M[row][col] == 0:\n",
    "            col += 1\n",
    "            continue\n",
    "        # else we have a pivot point!\n",
    "        pivot = M[row][col]\n",
    "        # next we simply set all elements in the current column below our pivot zero\n",
    "        for r in range(row + 1, rows):\n",
    "            # die Zeilen unter row durchgehen\n",
    "            if M[r][col] != 0:\n",
    "                # r is the row below that will be transformed\n",
    "                # row is the row where we found the pivot\n",
    "                # M[r][col] is the Leitkoeffizient at the row below, the one we want to set zero at that element\n",
    "                # the term -M[r][col]/pivot is the constant with which we will multiply our pivt row\n",
    "                rowMod0(M,r,row, -M[r][col]/pivot)\n",
    "        # now the column is properly setup so we can increase the column and row to work through the rest of the matrix\n",
    "        row += 1\n",
    "        col += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I hope all of this explains it well enough. To finish let's see the infamous rowEchelon0() in action with our familiar matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define the matrix a\n",
    "a = np.array([[1,1,1],[3,4,4]])\n",
    "print(\"The matrix as defined previously is \\n{}\".format(a))\n",
    "a_row_echelon_form = rowEchelon0(a)\n",
    "print(\"The matrix after using rowMod0() is \\n{}\".format(a))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected it does the same as rowMod0 but without the need to specify args."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}