{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 09 In-Class Assignment: Determinants\n", "\n", "![Depiction of Cramer's Rule with two equations and two variables](https://i.imgur.com/3txKM4R.jpg \"Depiction of Cramer's Rule with two equations and two variables\")\n", " \n", "
Image from: http://www.mathnstuff.com/
\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "\n", "\n", "## 1. Review Pre-class Assignment\n", "\n", "* [09--Determinants_pre-class-assignment.ipynb](09--Determinants_pre-class-assignment.ipynb)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "\n", "## 2. Algorithm to calculate the determinant\n", "Consider the following recursive algorithm (algorithm that calls itself) to determine the determinate of a $n\\times n$ matrix $A$ (denoted $|A|$), which is the sum of the products of the elements of any row or column. i.e.:\n", "\n", "$$i^{th}\\text{ row expansion: } |A| = a_{i1}C_{i1} + a_{i2}C_{i2} + \\ldots + a_{in}C_{in} $$\n", "$$j^{th}\\text{ column expansion: } |A| = a_{1j}C_{1j} + a_{2j}C_{2j} + \\ldots + a_{nj}C_{nj} $$\n", "\n", "where $C_{ij}$ is the cofactor of $a_{ij}$ and is given by:\n", "\n", "$$ C_{ij} = (-1)^{i+j}|M_{ij}|$$\n", "\n", "and $M_{ij}$ is the matrix that remains after deleting row $i$ and column $j$ of $A$.\n", "\n", "Here is some code that tries to implement this algorithm. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "## Import our standard packages packages\n", "%matplotlib inline\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "import sympy as sym\n", "sym.init_printing(use_unicode=True)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import copy\n", "import random\n", "\n", "def makeM(A,i,j):\n", " ''' Deletes the ith row and jth column from A'''\n", " M = copy.deepcopy(A)\n", " del M[i]\n", " for k in range(len(M)):\n", " del M[k][j]\n", " return M\n", "\n", "def mydet(A):\n", " '''Calculate the determinant from list-of-lists matrix A'''\n", " if type(A) == np.matrix:\n", " A = A.tolist() \n", " n = len(A)\n", " if n == 2:\n", " det = (A[0][0]*A[1][1] - A[1][0]*A[0][1]) \n", " return det\n", " det = 0\n", " i = 0\n", " for j in range(n):\n", " M = makeM(A,i,j)\n", " \n", " #Calculate the determinant\n", " det += (A[i][j] * ((-1)**(i+j+2)) * mydet(M))\n", " return det" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The following code generates an $n \\times n$ matrix with random values from 0 to 10. \n", "Run the code multiple times to get different matrices:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#generate Random Matrix and calculate it's determinant using numpy\n", "n = 5\n", "s = 10\n", "A = [[round(random.random()*s) for i in range(n)] for j in range(n)]\n", "A = np.matrix(A)\n", "#print matrix\n", "sym.Matrix(A)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "✅ **DO THIS:** Use the randomly generated matrix ($A$) to test the above ```mydet``` function and compare your result to the ```numpy.linalg.det``` function." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Put your test code here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "✅ **QUESTION:** Are the answers to ```mydet``` and ```numpy.linalg.det``` exactly the same every time you generate a different random matrix? If not, explain why." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Put your answer here**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "✅ **QUESTION:** On line 26 of the above code, you can see that algorithm calls itself. Explain why this doesn't run forever." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Put your answer here**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Properties of Determinants\n", "\n", "✅ **QUESTION:** Compute $|B|$ and $|B^4|$ if\n", " $$B=\n", "\\begin{bmatrix}\n", " 1&0&1\\\\\n", " 1&1&2\\\\\n", " 1&2&1\n", "\\end{bmatrix}$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Put your answer here**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "✅ **QUESTION:** If $A$ is an $n\\times n$ matrix with the property $A^2=I$, where $I$ is the identity $n\\times n$ matrix, what are the possible values of $|A|$?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Put your answer here**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "✅ **QUESTION:** If $\\begin{vmatrix}\n", "a & b & c \\\\ \n", "d & e & f \\\\\n", "g & h & i\n", "\\end{vmatrix}=4$, what is $\\begin{vmatrix}\n", "a & b & c \\\\ \n", "d & e & f \\\\\n", "3g & 3h & 3i\n", "\\end{vmatrix}$ and $\\begin{vmatrix}\n", "a & b & c \\\\ \n", "d+3g & e+3h & f+3i \\\\\n", "g & h & i\n", "\\end{vmatrix}$ ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Put your answer here**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "\n", "\n", "## 4. Using Cramer's rule to solve $Ax=b$\n", "\n", "Let $Ax = b$ be a system of $n$ linear equations in $n$ variables such that $|A| \\neq 0$. The system has a unique solution given by:\n", "\n", "$$x_1 = \\frac{|A_1|}{|A|}, x_2 = \\frac{|A_2|}{|A|}, \\ldots, x_n = \\frac{|A_n|}{|A|}$$\n", "\n", "where $A_i$ is the matrix obtained by replacing column $i$ of $A$ with $b$. The following function generates $A_i$ by replacing the $i$th column of $A$ with $b$:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def makeAi(A,i,b):\n", " '''Replace the ith column in A with b'''\n", " if type(A) == np.matrix:\n", " A = A.tolist()\n", " if type(b) == np.matrix:\n", " b = b.tolist()\n", " Ai = copy.deepcopy(A)\n", " for j in range(len(Ai)):\n", " Ai[j][i] = b[j][0]\n", " return Ai" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "✅ **DO THIS:** Create a new function called ```cramersRule```, which takes $A$ and $b$ and returns $x$ using the Cramer's rule. **Note:** Use ```numpy``` and NOT ```mydet``` to find the required determinants. ```mydet``` is too slow. " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Stub code. Replace the np.linalg.solve code with your answer\n", "\n", "def cramersRule(A,b):\n", " detA = np.linalg.det(A)\n", " x = [] \n", " #####Start of your code here##### \n", " \n", "\n", " #####End of your code here##### \n", " \n", " return x" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "✅ **QUESTION:** Test your ```cramersRule``` function on the following system of linear equations:\n", "\n", "$$ x_1 + 2x_2 = 3$$\n", "$$3x_1 + x_2 = -1$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Put your answer to the above quesiton here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "✅ **QUESTION:** Verify the above answer by using the ```np.linalg.solve``` function:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Put your answer to the above quesiton here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "✅ **QUESTION:** Test your ```cramersRule``` function on the following system of linear equations and verify the answer by using the ```np.linalg.solve``` function: \n", "\n", "$$ x_1 + 2x_2 +x_3 = 9$$\n", "$$ x_1 + 3x_2 - x_3 = 4$$\n", "$$ x_1 + 4x_2 - x_3 = 7$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#Put your answer to the above quesiton here" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "✅ **QUESTION:** Cramer's rule is a $O(n!)$ algorithm and the Gauss-Jordan (or Gaussian) elimination is $O(n^3)$. What advantages does Cramer's rule have over elimination?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Put your answer here." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "----\n", "\n", "Written by Dr. Dirk Colbry, Michigan State University\n", "\"Creative
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License." ] } ], "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.12" } }, "nbformat": 4, "nbformat_minor": 4 }