Ch6_Det_&_Inv_Matrix_Ex6.4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "418ddb4c",
   "metadata": {},
   "source": [
    "<b>Question 1</b> \n",
    "\n",
    "Solve the following linear system $Ax = b$ by using LU factorization for: \n",
    "\n",
    "(a) $A = \\begin{pmatrix}\n",
    "1&2&2\\\\\n",
    "3&-3&-2\\\\\n",
    "4&-1&-5\\\\\n",
    "\\end{pmatrix}, b = \\begin{pmatrix}\n",
    "5\\\\\n",
    "0\\\\\n",
    "-10\\\\\n",
    "\\end{pmatrix}\\qquad$(b) $A = \\begin{pmatrix}\n",
    "1&5&6\\\\\n",
    "2&11&19\\\\\n",
    "3&19&47\\\\\n",
    "\\end{pmatrix}, b = \\begin{pmatrix}\n",
    "1\\\\\n",
    "-4\\\\\n",
    "-22\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "(c) $A = \\begin{pmatrix}\n",
    "2&1&3\\\\\n",
    "4&-1&0\\\\\n",
    "10&12&34\\\\\n",
    "\\end{pmatrix}, b = \\begin{pmatrix}\n",
    "5\\\\\n",
    "-11\\\\\n",
    "84\\\\\n",
    "\\end{pmatrix}\\qquad$(d) $A = \\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "3&-9&-12\\\\\n",
    "-1&8&18\\\\\n",
    "\\end{pmatrix}, b = \\begin{pmatrix}\n",
    "-5\\\\\n",
    "9\\\\\n",
    "-4\\\\\n",
    "\\end{pmatrix}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9638fa9a",
   "metadata": {},
   "source": [
    "<b> Solution</b>\n",
    "\n",
    "<b>LU Factorization Procedure</b>\n",
    "\n",
    "Given a matrix $A$, we can form an upper triangular matrix $U$ by using two row operations:<br>\n",
    "- Multiplying a row by a non-zero constant\n",
    "- Adding a multiple of one row to another\n",
    "\n",
    "Swapping rows is <i>not allowed</i> \n",
    "\n",
    "<b>Solution (a)</b>\n",
    "\n",
    "$A = \\begin{pmatrix}\n",
    "1&2&2\\\\\n",
    "3&-3&-2\\\\\n",
    "4&-1&-5\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Now, to get $U$ - upper triangular matrix\n",
    "\n",
    "Step 1: $R_2 = R_{2} - 3R_{1}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&2\\\\\n",
    "0&-9&-8\\\\\n",
    "4&-1&-5\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 2: $R_3 = R_{3} - 4R_{1}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&2\\\\\n",
    "0&-9&-8\\\\\n",
    "0&-9&-13\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 3: $R_3 = R_{3} - R_{2}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&2\\\\\n",
    "0&-9&-8\\\\\n",
    "0&0&-5\\\\\n",
    "\\end{pmatrix} = U$ This is the upper triangular matrix, $U$\n",
    "\n",
    "Now, using negative multipliers from the step1 , step2, and step3, and with $I$ $3 \\times 3$ matrix<br>\n",
    "We get, <br>\n",
    "$L = \\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "3&1&0\\\\\n",
    "4&1&1\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Next, we can solve <b>$Ly = b$</b> to get y:\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "3&1&0\\\\\n",
    "4&1&1\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "y_{1}\\\\\n",
    "y_{2}\\\\\n",
    "y_{3}\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "5\\\\\n",
    "0\\\\\n",
    "-10\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Here, $y_{1} = 5$<br>\n",
    "$\\Rightarrow 3y_{1} + y_{2} =0$<br>\n",
    "$\\Rightarrow y_{2} = -3y_{1} = -15$<br>\n",
    "\n",
    "$\\Rightarrow y_{3} = 4(5) + (-15) + y_{3} = 0$<br>\n",
    "$\\Rightarrow y_{3} = -15$<br>\n",
    "\n",
    "Next, we need to solve $Ux = y$ to get our solution<br>\n",
    "We have now, <br>\n",
    "$\\begin{pmatrix}\n",
    "1&2&2\\\\\n",
    "0&-9&-8\\\\\n",
    "0&0&-5\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "x_{1}\\\\\n",
    "x_{2}\\\\\n",
    "x_{3}\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "5\\\\\n",
    "-15\\\\\n",
    "-15\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Here, $-5x_{3} = -15$<br>\n",
    "$\\Rightarrow x_{3} = 3$\n",
    "\n",
    "Next, <br>\n",
    "$-9x_{2} -8x_{3} = -15$<br>\n",
    "$\\Rightarrow -9x_{2} -8(3) = -15$<br>\n",
    "$\\Rightarrow -9x_{2} = -15 + 24$<br>\n",
    "$\\Rightarrow x_{2} = -1$<br>\n",
    "\n",
    "Next, <br>\n",
    "$x_{1} +2x_{2} + 2x_{3} = 5$<br>\n",
    "$\\Rightarrow x_{1} +2(-1) +2(3) = 5$<br>\n",
    "$\\Rightarrow x_{1} -2 + 6 = 5$<br>\n",
    "$\\Rightarrow x_{1} = 1$<br>\n",
    "\n",
    "Hence, <b>$x_{1} =1, x_{2} = -1$ and $x_{3} = 3$</b>\n",
    "\n",
    "<b>Solution(b)</b>\n",
    "\n",
    "$A = \\begin{pmatrix}\n",
    "1&5&6\\\\\n",
    "2&11&19\\\\\n",
    "3&19&47\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Now, to get $U$ - upper triangular matrix\n",
    "\n",
    "Step 1: $R_2 = R_{2} - 2R_{1}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&5&6\\\\\n",
    "0&1&7\\\\\n",
    "3&19&47\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 2: $R_3 = R_{3} - 3R_{1}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&5&6\\\\\n",
    "0&1&7\\\\\n",
    "0&4&29\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 3: $R_3 = R_{3} - 4R_{2}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&5&6\\\\\n",
    "0&1&7\\\\\n",
    "0&0&3\\\\\n",
    "\\end{pmatrix} = U$ This is the upper triangular matrix, $U$\n",
    "\n",
    "Now, using negative multipliers from the step1 , step2, and step3, and with $3 \\times 3$ matrix $I$<br>\n",
    "We get, <br>\n",
    "$L = \\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "2&1&0\\\\\n",
    "3&4&1\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Next, we can solve <b>$Ly = b$</b> to get y:\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "2&1&0\\\\\n",
    "3&4&1\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "y_{1}\\\\\n",
    "y_{2}\\\\\n",
    "y_{3}\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "1\\\\\n",
    "-4\\\\\n",
    "-22\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "$\\Rightarrow y_{1} = 1$<br>\n",
    "Then, <br>\n",
    "$2y_{1} + y_{2} = -4 \\qquad \\Rightarrow y_{2} = -4 -2 = -6$<br>\n",
    "\n",
    "and, $3y_{1} + 4y_{2} + y_{3} = -22$<br>\n",
    "$\\Rightarrow 3(1) +4(-6) + y_{3} = -22$<br>\n",
    "$\\Rightarrow 3 - 24 + y_{3} = -22$<br>\n",
    "\n",
    "$\\Rightarrow y_{3} = -22 + 21 = -1$\n",
    "\n",
    "Next, we need to solve $Ux = y$ to get our solution<br>\n",
    "We have now, <br>\n",
    "$\\begin{pmatrix}\n",
    "1&5&6\\\\\n",
    "0&1&7\\\\\n",
    "0&0&3\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "x_{1}\\\\\n",
    "x_{2}\\\\\n",
    "x_{3}\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "1\\\\\n",
    "-6\\\\\n",
    "-1\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "$\\Rightarrow x_{3} = -1$\n",
    "Then,<br>\n",
    "$x_{2} + 7x_{3} = -6$<br>\n",
    "$\\Rightarrow x_{2} =-6 -(-7) = 1$<br>\n",
    "and, <br>\n",
    "$x_{1} + 5(1) + 6(-1) = 1$<br>\n",
    "$\\Rightarrow x_{1} + 5 - 6 = 1$<br>\n",
    "$\\Rightarrow x_{1} = 2$\n",
    "\n",
    "Hence, $x_{1} = 2, x_{2} = 1$ and $x_{1} = -1$ is our solution\n",
    "\n",
    "\n",
    "<b>Solution(c)</b>\n",
    "\n",
    "$A = \\begin{pmatrix}\n",
    "2&1&3\\\\\n",
    "4&-1&0\\\\\n",
    "10&12&34\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Now, to get $U$ - upper triangular matrix\n",
    "\n",
    "Step 1: $R_2 = R_{2} - 2R_{1}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "2&1&3\\\\\n",
    "0&-3&-6\\\\\n",
    "10&12&34\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 2: $R_3 = R_{3} - 5R_{1}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "2&1&3\\\\\n",
    "0&-3&-6\\\\\n",
    "0&7&19\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 3: $R_2 = R_{2} - \\frac{1}{-3}R_{2}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "2&1&3\\\\\n",
    "0&1&2\\\\\n",
    "0&7&19\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 4: $R_{3} = R_{3} - 7R_{2}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "2&1&3\\\\\n",
    "0&1&2\\\\\n",
    "0&0&5\\\\\n",
    "\\end{pmatrix}= U$ This is the upper triangular matrix, $U$\n",
    "\n",
    "Now, using negative multipliers from the step1 , step2, step3, and step4, and with $3 \\times 3$ matrix $I$<br>\n",
    "We get, <br>\n",
    "$L = \\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "2&-3&0\\\\\n",
    "5&7&1\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Next, we can solve <b>$Ly = b$</b> to get y:\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "2&-3&0\\\\\n",
    "5&7&1\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "y_{1}\\\\\n",
    "y_{2}\\\\\n",
    "y_{3}\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "5\\\\\n",
    "-11\\\\\n",
    "84\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "$\\Rightarrow y_{1} = 5$<br>\n",
    "Next,<br>\n",
    "$2y_{1} -3y_{2} = -11$<br>\n",
    "$-3y_{2} = -11 - 10$<br>\n",
    "$\\Rightarrow y_{2} = 7$\n",
    "\n",
    "$5y_{1} + 7y_{2} + y_{3} = 84$<br>\n",
    "$5(5) + 7(7) + y_{3} = 84$<br>\n",
    "$\\Rightarrow y_{3} = 84 - 74 = 10$\n",
    "\n",
    "Next, we have to solve $Ux = y$ to get our solution\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "2&1&3\\\\\n",
    "0&1&2\\\\\n",
    "0&0&5\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "x_{1}\\\\\n",
    "x_{2}\\\\\n",
    "x_{3}\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "5\\\\\n",
    "7\\\\\n",
    "10\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Solving this, we get $x_{1} = -2,, x_{2} = 3$, and $x_{3} = 2$\n",
    "\n",
    "\n",
    "<b>Solution(d)</b>\n",
    "\n",
    "$A = \\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "3&-9&-12\\\\\n",
    "-1&8&18\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Now, to get $U$ - upper triangular matrix\n",
    "\n",
    "Step 1: $R_2 = R_{2} - 3R_{1}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "0&-15&-21\\\\\n",
    "-1&8&18\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 2: $R_3 = R_{3} + R_{1}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "0&-15&-21\\\\\n",
    "0&10&21\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 3: $R_2 = R_{2} - \\frac{1}{-3}R_{2}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "0&5&7\\\\\n",
    "0&10&21\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 4: $R_{3} = R_{3} - 2R_{2}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "0&5&7\\\\\n",
    "0&0&75\\\\\n",
    "\\end{pmatrix}= U$ This is the upper triangular matrix, $U$\n",
    "\n",
    "Now, using negative multipliers from the step1 , step2, step3, and step4, and with $3 \\times 3$ matrix $I$<br>\n",
    "We get, <br>\n",
    "$L = \\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "3&-3&0\\\\\n",
    "-1&2&1\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Next, we can solve <b>$Ly = b$</b> to get y:\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "3&-3&0\\\\\n",
    "-1&2&1\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "y_{1}\\\\\n",
    "y_{2}\\\\\n",
    "y_{3}\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "-5\\\\\n",
    "9\\\\\n",
    "-4\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "$\\Rightarrow y_{1} = -5$<br>\n",
    "Next,<br>\n",
    "$3y_{1} -3y_{2} = 9$<br>\n",
    "$\\Rightarrow 3(-5) -3y_{2} =9$<br>\n",
    "$\\Rightarrow -3y_{2} = 9 + 14$<br>\n",
    "$\\Rightarrow y_{2} = -8$\n",
    "\n",
    "Then, <br>\n",
    "$-y_{1} + 2y_{2} + y_{3} = -4$<br>\n",
    "$-(-5) +2(-8) + y_{3} = -4$<br>\n",
    "$\\Rightarrow 5 - 16 = -4$<br>\n",
    "$\\Rightarrow y_{3} = -4 + 11 = 7$<br>\n",
    "\n",
    "Next, solving $Ux = y$ to get our solution\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "0&5&7\\\\\n",
    "0&0&7\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "x_{1}\\\\\n",
    "x_{2}\\\\\n",
    "x_{3}\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "-5\\\\\n",
    "-8\\\\\n",
    "7\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Solving this, we get $x_{1} = -2, x_{2} = -3$ and $x_{3} = 1$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f191622d",
   "metadata": {},
   "source": [
    "-----------------------------------------------------------------"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4466e3bf",
   "metadata": {},
   "source": [
    "<b>Question 2</b>\n",
    "\n",
    "Solve the following system $Ax = b$ by using LU factorization:\n",
    "\n",
    "$A = \\begin{pmatrix}\n",
    "1&2&3&4\\\\\n",
    "17&22&27&8\\\\\n",
    "77&44&47&-494\\\\\n",
    "-10&1&7&63\\\\\n",
    "\\end{pmatrix}, b = \\begin{pmatrix}\n",
    "-10\\\\\n",
    "22\\\\\n",
    "2106\\\\\n",
    "-243\\\\\n",
    "\\end{pmatrix}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a7a96f3",
   "metadata": {},
   "source": [
    "<b>Solution</b>\n",
    "\n",
    "Step 1 : $R_{2} = R_{2} - 17R_{1}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3&4\\\\\n",
    "0&-12&-24&60\\\\\n",
    "77&44&47&-494\\\\\n",
    "-10&1&7&63\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 2: $R_{2} = \\frac{1}{-12}R_{2}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3&4\\\\\n",
    "0&1&2&5\\\\\n",
    "77&44&47&-494\\\\\n",
    "-10&1&7&63\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 3: $R_{3} = R_{3} - 77R_{1}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3&4\\\\\n",
    "0&1&2&5\\\\\n",
    "0&-110&-184&-802\\\\\n",
    "-10&1&7&63\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 4: $R_{3} = R_{3} + 110R_{2}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3&4\\\\\n",
    "0&1&2&5\\\\\n",
    "0&0&36&-252\\\\\n",
    "-10&1&7&63\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 5: $R_{4} = R_{4} + 10R_{1}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3&4\\\\\n",
    "0&1&2&5\\\\\n",
    "0&0&36&-252\\\\\n",
    "0&21&37&103\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 6: $R_{4} = R_{4} - 21R_{2}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3&4\\\\\n",
    "0&1&2&5\\\\\n",
    "0&0&36&-252\\\\\n",
    "0&0&-5&-2\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 7: $R_{3} = \\frac{1}{36}R_{3}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3&4\\\\\n",
    "0&1&2&5\\\\\n",
    "0&0&1&-7\\\\\n",
    "0&0&-5&-2\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 8: $R_{4} = R_{4} - 5R_{3}$\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3&4\\\\\n",
    "0&1&2&5\\\\\n",
    "0&0&1&-7\\\\\n",
    "0&0&0&-37\\\\\n",
    "\\end{pmatrix} = U$\n",
    "\n",
    "Collecting negative multipliers from $step1, \\dots step8$ we can get Lower triangular matrix, $L$ as: \n",
    "\n",
    "$L = \\begin{pmatrix}\n",
    "1&0&0&0\\\\\n",
    "17&-12&0&0\\\\\n",
    "77&-110&36&0\\\\\n",
    "-10&21&-5&1\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Next, solving $Ly = b$ to get y<br>\n",
    "$\\begin{pmatrix}\n",
    "1&0&0&0\\\\\n",
    "17&-12&0&0\\\\\n",
    "77&-110&36&0\\\\\n",
    "-10&21&-5&1\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "y_1\\\\\n",
    "y_2\\\\\n",
    "y_3\\\\\n",
    "y_4\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "-10\\\\\n",
    "22\\\\\n",
    "2106\\\\\n",
    "-243\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "$\\Rightarrow y_{1} = -10$\n",
    "\n",
    "Next,<br>\n",
    "$17y_{1} - 12y_{2} = 22$<br>\n",
    "$\\Rightarrow 17(-10) - 12y_{2} = 22$<br>\n",
    "$\\Rightarrow -170 - 12y_{2} = 22$\n",
    "\n",
    "$\\Rightarrow y_{2} = \\frac{192}{-12} = -16$\n",
    "\n",
    "Then<br>\n",
    "$77y_{1} -110y_{2} + 36y_{3} = 2106$<br>\n",
    "$\\Rightarrow 77(-10) -110(-16) + 36y_{3} = 2106$<br>\n",
    "$\\Rightarrow -770 + 1760 + 36y_{3} = 2106$<br>\n",
    "$\\Rightarrow 36y_{3} = 2106 - 990$\n",
    "\n",
    "$\\Rightarrow y_{3} = \\frac{1116}{36} = 31$\n",
    "\n",
    "Then, <br>\n",
    "$-10y_{1} + 21y_{2} - 5y_{3} + y_{4} = -243$<br>\n",
    "$-10(-10) + 21(-16) -5(31) + y_{4} = -243$<br>\n",
    "$\\Rightarrow 100 -336 - 155 + y_{4} = -243$\n",
    "\n",
    "$\\Rightarrow y_{4} = -243 + 391 = 148$\n",
    "\n",
    "\n",
    "Now, solving $Ux = y$ to get the solution\n",
    "\n",
    "$\\begin{pmatrix}\n",
    "1&2&3&4\\\\\n",
    "0&1&2&5\\\\\n",
    "0&0&1&-7\\\\\n",
    "0&0&0&-37\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "x_{1}\\\\\n",
    "x_{2}\\\\\n",
    "x_{3}\\\\\n",
    "x_{4}\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "-10\\\\\n",
    "-16\\\\\n",
    "31\\\\\n",
    "148\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Solving this, we get <b>our solution as $x_{1} = 1, x_{2} = -2, x_{3} = 3$ and $x_{4} = -4$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48828a2e",
   "metadata": {},
   "source": [
    "------------------------------------------------------------"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b5f6f777",
   "metadata": {},
   "source": [
    "<b> Question 3</b>\n",
    "\n",
    "Find the determinant of the matrix $A$ given in question 2."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6e47ab6",
   "metadata": {},
   "source": [
    "<b> Solution</b> \n",
    "\n",
    "We can write given matrix A as $A = LU$ representing :\n",
    "\n",
    "$A =  \\begin{pmatrix}\n",
    "1&0&0&0\\\\\n",
    "17&-12&0&0\\\\\n",
    "77&-110&36&0\\\\\n",
    "-10&21&-5&1\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "1&2&3&4\\\\\n",
    "0&1&2&5\\\\\n",
    "0&0&1&-7\\\\\n",
    "0&0&0&-37\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Then, $det(A)$ is given by $det(A) = det(LU)$\n",
    "\n",
    "$\\Rightarrow det(A) = det(L) \\times det(U)$\n",
    "\n",
    "$det(A) = \\left[1 \\times (-12) \\times 36 \\times1)\\right] \\times \\left[1 \\times 1 \\times 1 \\times - 37 \\right]$\n",
    "\n",
    "$det(A) = 15984$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad9594c8",
   "metadata": {},
   "source": [
    "-------------------------------------------"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f54926f",
   "metadata": {},
   "source": [
    "<b> Question 4</b> <br>\n",
    "Decompose the matrix $A = \\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "0&4&5\\\\\n",
    "0&0&6\\\\\n",
    "\\end{pmatrix}$ into LU"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ade3c0ee",
   "metadata": {},
   "source": [
    "<b> Solution </b> \n",
    "\n",
    "Given matrix is already an upper triangular matrix, therefore we need only identity matrix $I$ as lower triangular matrix.\n",
    "\n",
    "Therefore, <br>\n",
    "$ A = \\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "0&1&0\\\\\n",
    "0&0&1\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "0&4&5\\\\\n",
    "0&0&6\\\\\n",
    "\\end{pmatrix}$  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b71bc4c9",
   "metadata": {},
   "source": [
    "----------------------------------"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48ed2274",
   "metadata": {},
   "source": [
    "<b>Question 5</b>\n",
    "\n",
    "Let $A = \\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "3&7&14\\\\\n",
    "4&13&38\\\\\n",
    "\\end{pmatrix}$<br>\n",
    "(a) Convert the matrix $A$ into LU form<br>\n",
    "(b) Find $A^{-1}$<br>\n",
    "9(c) Solve $Ax = b$ for $\\quad (i)b = \\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "\\end{pmatrix}^T \\quad (ii)b = \\begin{pmatrix}\n",
    "-1&3&1\\\\\n",
    "\\end{pmatrix}^T$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6a7132e",
   "metadata": {},
   "source": [
    "<b>Solution (a)</b>\n",
    "\n",
    "Here, $A = \\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "3&7&14\\\\\n",
    "4&13&38\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 1: $R_{2} = R_{2} - 3R_{1}$ and step 2: $R_3 = R_{3} - 4R_{1}$, we have<br>\n",
    "$\\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "0&1&5\\\\\n",
    "0&5&26\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Step 3: $R_{3} = R_{3} - 5R_{2}$<br>\n",
    "$\\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "0&1&5\\\\\n",
    "0&0&1\\\\\n",
    "\\end{pmatrix} = U$\n",
    "\n",
    "Then, collecting negative multipliers from the step 1, step 2 and step 3, we have $L$ as:<br>\n",
    "$L = \\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "3&1&0\\\\\n",
    "4&5&1\\\\\n",
    "\\end{pmatrix}\n",
    "$\n",
    "\n",
    "Therefore, A can be written as:\n",
    "\n",
    "$A = \\begin{pmatrix}\n",
    "1&2&3\\\\\n",
    "0&1&5\\\\\n",
    "0&0&1\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "3&1&0\\\\\n",
    "4&5&1\\\\\n",
    "\\end{pmatrix}\n",
    "$\n",
    "\n",
    "<b>Solution (b)</b>\n",
    "\n",
    "We know that, $A = LU$<br>\n",
    "Therefore, <br>\n",
    "$A^{-1} = (LU)^{-1}$\n",
    "\n",
    "And, as if $A$ and $B$ is invertible, then $(AB)^{-1} = B^{-1}A^{-1}$.\n",
    "\n",
    "Therefore, $A^{-1} = U^{-1}L^{-1}$\n",
    "\n",
    "So, $U^{-1} = (U | I)$ <br>\n",
    "$\\qquad = \\left(\\begin{array}{ccc|ccc}\n",
    "1&2&3&1&0&0\\\\\n",
    "0&1&5&0&1&0\\\\\n",
    "0&0&1&0&0&1\\\\\n",
    "\\end{array}\n",
    "\\right)$\n",
    "\n",
    "Step 1: $R_{1} = R_{1} - 2R_{2}$\n",
    "\n",
    "$= \\left(\\begin{array}{ccc|ccc}\n",
    "1&0&-7&1&-2&0\\\\\n",
    "0&1&5&0&1&0\\\\\n",
    "0&0&1&0&0&1\\\\\n",
    "\\end{array}\n",
    "\\right)$\n",
    "\n",
    "Step 2: $R_{1} =  R_{1} +7R_{3}$ and $R_{2} = R_{2} - 5R_{3}$\n",
    "\n",
    "$= \\left(\\begin{array}{ccc|ccc}\n",
    "1&0&0&1&-2&7\\\\\n",
    "0&1&0&0&1&-5\\\\\n",
    "0&0&1&0&0&1\\\\\n",
    "\\end{array}\n",
    "\\right)$\n",
    "\n",
    "Therefore, $U^{-1} = \\begin{pmatrix}\n",
    "1&-2&7\\\\\n",
    "0&1&-5\\\\\n",
    "0&0&1\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "Similarly, \n",
    "\n",
    "$L^{-1} = (L | I)$\n",
    "\n",
    "$\\qquad = \\left(\\begin{array}{ccc|ccc}\n",
    "1&0&0&1&0&0\\\\\n",
    "3&1&0&0&1&0\\\\\n",
    "4&5&1&0&0&1\\\\\n",
    "\\end{array}\n",
    "\\right)$\n",
    "\n",
    "Step 1: $R_{2} = R_{2} - 3R_{1}$ and $R_{3} = R_{3} - 4R_{1}$\n",
    "\n",
    "$\\qquad = \\left(\\begin{array}{ccc|ccc}\n",
    "1&0&0&1&0&0\\\\\n",
    "0&1&0&-3&1&0\\\\\n",
    "0&5&1&-4&0&1\\\\\n",
    "\\end{array}\n",
    "\\right)$\n",
    "\n",
    "Step 2: $R_{3} = R_{3} - 5R_{2}$\n",
    "\n",
    "$\\qquad = \\left(\\begin{array}{ccc|ccc}\n",
    "1&0&0&1&0&0\\\\\n",
    "0&1&0&-3&1&0\\\\\n",
    "0&0&1&11&-5&1\\\\\n",
    "\\end{array}\n",
    "\\right)$\n",
    "\n",
    "$L^{-1} = \\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "-3&1&0\\\\\n",
    "11&-5&1\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "$A^{-1} = U^{-1}L^{-1} = \\begin{pmatrix}\n",
    "1&-2&7\\\\\n",
    "0&1&-5\\\\\n",
    "0&0&1\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "1&0&0\\\\\n",
    "-3&1&0\\\\\n",
    "11&-5&1\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "$\\Rightarrow A^{-1} = \\begin{pmatrix}\n",
    "84&-37&7\\\\\n",
    "-58&26&-5\\\\\n",
    "11&-5&1\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "<b>Solution(c) (i)</b>\n",
    "\n",
    "We have, $b = \\begin{pmatrix}\n",
    "1\\\\\n",
    "2\\\\\n",
    "3\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "To get $x$ for $Ax = b$, we can compute as:\n",
    "\n",
    "$x = A^{-1}b = \\begin{pmatrix}\n",
    "84&-37&7\\\\\n",
    "-58&26&-5\\\\\n",
    "11&-5&1\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "1\\\\\n",
    "2\\\\\n",
    "3\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "84(1) - 37(2) +7(3)\\\\\n",
    "-58(1) + 26(2) -5(3)\\\\\n",
    "11(1) -5(2) +1(3)\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "31\\\\\n",
    "-21\\\\\n",
    "4\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "\n",
    "\n",
    "Solution(c) (i)</b>\n",
    "\n",
    "We have, $b = \\begin{pmatrix}\n",
    "-1\\\\\n",
    "3\\\\\n",
    "1\\\\\n",
    "\\end{pmatrix}$\n",
    "\n",
    "To get $x$ for $Ax = b$, we can compute as:\n",
    "\n",
    "$x = A^{-1}b = \\begin{pmatrix}\n",
    "84&-37&7\\\\\n",
    "-58&26&-5\\\\\n",
    "11&-5&1\\\\\n",
    "\\end{pmatrix} \\cdot \\begin{pmatrix}\n",
    "-1\\\\\n",
    "3\\\\\n",
    "1\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "84(-1) - 37(3) +7(1)\\\\\n",
    "-58(-1) + 26(3) -5(1)\\\\\n",
    "11(-1) -5(3) +1(1)\\\\\n",
    "\\end{pmatrix} = \\begin{pmatrix}\n",
    "-188\\\\\n",
    "131\\\\\n",
    "-25\\\\\n",
    "\\end{pmatrix}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9313c5d0",
   "metadata": {},
   "source": [
    "-------------------------------------"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45d0325d",
   "metadata": {},
   "source": [
    "<b>Question 6</b>\n",
    "\n",
    "Explain why we cannot convert the following $\\begin{pmatrix}\n",
    "0&1\\\\\n",
    "2&3\\\\\n",
    "\\end{pmatrix}$ into LU factorization"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "599a96c2",
   "metadata": {},
   "source": [
    "<b>Solution</b>\n",
    "\n",
    "Switching rows in LU Factorization is not allowed, therefore, without it given matrix cannot be converted into $A = LU$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52316c60",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}