{ "cells": [ { "cell_type": "markdown", "id": "0e214b73-ba5e-4d2d-ba32-2042e4c7b5ff", "metadata": {}, "source": [ "**Authors:** Judith Ludwig and Florent Schaffhauser, Uni-Heidelberg, Summer Semester 2024" ] }, { "cell_type": "markdown", "id": "f11bf9b7-9cd9-4437-bc03-5fb478aa3bf7", "metadata": { "tags": [] }, "source": [ "## Matrices in Sage" ] }, { "cell_type": "markdown", "id": "ae32a5ea-62a7-4892-81f1-2031449096fe", "metadata": { "tags": [] }, "source": [ "### Basic operations" ] }, { "cell_type": "markdown", "id": "fc320ea2-33d2-403f-8ee0-6e9702a12c98", "metadata": {}, "source": [ "When we define a matrix in *Sage*, we can specify the ring or field in which we take the entries. \n", "\n", "Let us for instance consider the matrix\n", "\n", "$$\n", "\\begin{pmatrix}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & 2 \n", "\\end{pmatrix}\n", "$$\n", "\n", "and declare it first as a matrix $A$ with entries in $\\mathbb{Q}$, then as a matrix $B$ with entries the field with seven elements $\\mathbb{F}_7$." ] }, { "cell_type": "code", "execution_count": 1, "id": "787d81ec-d354-409b-bf5e-19bdadec3756", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & 2\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & 2\n", "\\end{array}\\right)$" ], "text/plain": [ "[2 4 6]\n", "[4 5 6]\n", "[3 1 2]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "A = matrix( QQ, [[2,4,6],[4,5,6],[3,1,2]] )\n", "show(A)" ] }, { "cell_type": "code", "execution_count": 2, "id": "0a91fba0-f2bc-4423-b33d-6216f920ba8d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The command 'type()' shows what kind of object the argument is\n", "type(A)" ] }, { "cell_type": "code", "execution_count": 3, "id": "b5a04df4-1244-4303-84d1-f5621b551d55", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & 2\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & 2\n", "\\end{array}\\right)$" ], "text/plain": [ "[2 4 6]\n", "[4 5 6]\n", "[3 1 2]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "B = matrix( GF(7), [[2,4,6],[4,5,6],[3,1,2]])\n", "show(B)" ] }, { "cell_type": "code", "execution_count": 4, "id": "5b89d645-2c67-40c0-be06-42b6abf8d477", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Matrices with entries in a finite field are of the \"mod n\" class\n", "type(B)" ] }, { "cell_type": "markdown", "id": "bc0a9a42-c370-4245-b48b-8e8e8119be01", "metadata": {}, "source": [ "If we declare our matrix as a matrix with entries in the field with $3$ elements, *Sage* will automatically reduce the entries modulo $3$:" ] }, { "cell_type": "code", "execution_count": 5, "id": "79179029-5233-4371-b3a1-09e2e9be9b0b", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 1 & 0 \\\\\n", "1 & 2 & 0 \\\\\n", "0 & 1 & 2\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 1 & 0 \\\\\n", "1 & 2 & 0 \\\\\n", "0 & 1 & 2\n", "\\end{array}\\right)$" ], "text/plain": [ "[2 1 0]\n", "[1 2 0]\n", "[0 1 2]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "C = matrix( GF(3), [[2,4,6],[4,5,6],[3,1,2]])\n", "show(C)" ] }, { "cell_type": "code", "execution_count": 6, "id": "04abad66-527a-45f2-9019-75f7c7fc41ae", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The type of C in this case is the same as the type of B \n", "type(C)" ] }, { "cell_type": "markdown", "id": "e31e8b52-6421-4379-9448-15ce4fafde06", "metadata": {}, "source": [ "As we know, depending on the ring in which the entries are taken to lie, the properties of a \"same\" matrix may be quite different. For instance, here, $B$ is invertible in $\\mathrm{Mat}( 3 \\times 3; \\mathbb{F}_7 )$, but $C$ is not invertible in $\\mathrm{Mat}( 3 \\times 3; \\mathbb{F}_3)$." ] }, { "cell_type": "code", "execution_count": 7, "id": "54090782-2ff0-4195-818f-54ba9691f4ae", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "-18" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The determinant function computes the determinant of square matrix...\n", "A.determinant()" ] }, { "cell_type": "code", "execution_count": 8, "id": "63823ee5-71c7-46aa-8949-34a36e97ac19", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Recall that -18 mod 7 is 3\n", "B.determinant()" ] }, { "cell_type": "code", "execution_count": 9, "id": "94de143b-1bfe-4a45-aaa6-7ff2406bfcc7", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# And -18 mod 3 is 0\n", "C.determinant()" ] }, { "cell_type": "markdown", "id": "36b26e71-c783-4810-a754-4bd41143398b", "metadata": {}, "source": [ "Also, the inverse of $A$ in $\\mathrm{Mat}( 3 \\times 3; \\mathbb{Q} )$ looks very different from the inverse of $B$ in $\\mathrm{Mat}( 3 \\times 3; \\mathbb{F}_7 )$." ] }, { "cell_type": "code", "execution_count": 10, "id": "e907e348-1b7d-425f-9240-be7cf9718de0", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "-\\frac{2}{9} & \\frac{1}{9} & \\frac{1}{3} \\\\\n", "-\\frac{5}{9} & \\frac{7}{9} & -\\frac{2}{3} \\\\\n", "\\frac{11}{18} & -\\frac{5}{9} & \\frac{1}{3}\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "-\\frac{2}{9} & \\frac{1}{9} & \\frac{1}{3} \\\\\n", "-\\frac{5}{9} & \\frac{7}{9} & -\\frac{2}{3} \\\\\n", "\\frac{11}{18} & -\\frac{5}{9} & \\frac{1}{3}\n", "\\end{array}\\right)$" ], "text/plain": [ "[ -2/9 1/9 1/3]\n", "[ -5/9 7/9 -2/3]\n", "[11/18 -5/9 1/3]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(A.inverse())" ] }, { "cell_type": "code", "execution_count": 11, "id": "1f6a45ac-5914-44ea-8fa6-b5db37192ae4", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "6 & 4 & 5 \\\\\n", "1 & 0 & 4 \\\\\n", "1 & 1 & 5\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "6 & 4 & 5 \\\\\n", "1 & 0 & 4 \\\\\n", "1 & 1 & 5\n", "\\end{array}\\right)$" ], "text/plain": [ "[6 4 5]\n", "[1 0 4]\n", "[1 1 5]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(B.inverse())" ] }, { "cell_type": "markdown", "id": "8470eac2-36c1-4856-8023-9dc8ae84f92a", "metadata": {}, "source": [ "In *Sage*, we can perform usual matrix operations in a fairly intuitive manner:" ] }, { "cell_type": "code", "execution_count": 27, "id": "ebfb90df-9b8c-4e2f-9ede-8c216741a1af", "metadata": { "scrolled": true, "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "\\frac{284}{9} & \\frac{200}{9} & \\frac{92}{3} \\\\\n", "\\frac{296}{9} & \\frac{302}{9} & \\frac{140}{3} \\\\\n", "\\frac{74}{9} & \\frac{134}{9} & \\frac{68}{3}\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "\\frac{284}{9} & \\frac{200}{9} & \\frac{92}{3} \\\\\n", "\\frac{296}{9} & \\frac{302}{9} & \\frac{140}{3} \\\\\n", "\\frac{74}{9} & \\frac{134}{9} & \\frac{68}{3}\n", "\\end{array}\\right)$" ], "text/plain": [ "[284/9 200/9 92/3]\n", "[296/9 302/9 140/3]\n", "[ 74/9 134/9 68/3]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(2*A^(-1)+A^2-3*A)" ] }, { "cell_type": "code", "execution_count": 28, "id": "0b29e224-7f60-4a3f-849c-c6c2571bd3d3", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 2 & 5 \\\\\n", "1 & 4 & 0 \\\\\n", "2 & 4 & 4\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 2 & 5 \\\\\n", "1 & 4 & 0 \\\\\n", "2 & 4 & 4\n", "\\end{array}\\right)$" ], "text/plain": [ "[2 2 5]\n", "[1 4 0]\n", "[2 4 4]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(2*B^(-1)+B^2-3*B)" ] }, { "cell_type": "markdown", "id": "6711a2ac-953e-4b33-9828-14320f812590", "metadata": {}, "source": [ "Note that the command \"A^(-1)\" returns the inverse of $A$." ] }, { "cell_type": "code", "execution_count": 29, "id": "a938c1d0-5222-4a38-9fda-db845b349646", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We can test in the following way whether an assertion is True or False\n", "A^(-1) == A.inverse()" ] }, { "cell_type": "code", "execution_count": 30, "id": "f428c440-f4c6-4523-bc23-f63592b5e44b", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "3*B == B^2" ] }, { "cell_type": "markdown", "id": "1508b78c-3b8f-497b-90f6-883642355212", "metadata": { "tags": [] }, "source": [ "### Reduced row-echelon form" ] }, { "cell_type": "markdown", "id": "642b3293-a422-4d19-936c-8f50a443752d", "metadata": {}, "source": [ "In order to solve homogeneous linear systems $AX=0$, one reduces $A$ to its *reduced row-echelon form* (or RREF), which *Sage* can do." ] }, { "cell_type": "code", "execution_count": 31, "id": "b19c4ac4-06e2-4f48-ab08-b6a06da77b78", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & 2\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & 2\n", "\\end{array}\\right)$" ], "text/plain": [ "[2 4 6]\n", "[4 5 6]\n", "[3 1 2]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Recall our matrix A (with rational entries)\n", "show(A)" ] }, { "cell_type": "code", "execution_count": 32, "id": "df8fb27d-ac6f-468d-865f-f13850fd27c2", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "1 & 0 & 0 \\\\\n", "0 & 1 & 0 \\\\\n", "0 & 0 & 1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "1 & 0 & 0 \\\\\n", "0 & 1 & 0 \\\\\n", "0 & 0 & 1\n", "\\end{array}\\right)$" ], "text/plain": [ "[1 0 0]\n", "[0 1 0]\n", "[0 0 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# The function echelon_form() returns the RREF of a matrix\n", "show(A.echelon_form())" ] }, { "cell_type": "markdown", "id": "691d2cc4-f8c8-4fdd-9af5-67a85c770e43", "metadata": {}, "source": [ "In this case, the reduced row-echelon form of $A$ is the identity, which shows that $\\ker A=\\{0\\}$. Note that the computation we have done has not affected the variable $A$." ] }, { "cell_type": "code", "execution_count": 33, "id": "b0740502-614e-445e-a75a-ba41c753b430", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & 2\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & 2\n", "\\end{array}\\right)$" ], "text/plain": [ "[2 4 6]\n", "[4 5 6]\n", "[3 1 2]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(A)" ] }, { "cell_type": "markdown", "id": "76ecf1be-636c-4596-9622-15d72d467478", "metadata": {}, "source": [ "In order to solve general linear systems $AX=Y$, we can perform Gaussian elimination on the *augmented matrix* $(A|Y)$. \n", "\n", "For instance, if we consider the linear system \n", "$$\n", "\\begin{pmatrix}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & 2 \n", "\\end{pmatrix}\n", "\\begin{pmatrix}\n", "x \\\\\n", "y \\\\\n", "z \n", "\\end{pmatrix}\n", "=\n", "\\begin{pmatrix}\n", "18 \\\\\n", "24 \\\\\n", "4 \n", "\\end{pmatrix}\n", ",\n", "$$ we can proceed as follows." ] }, { "cell_type": "code", "execution_count": 34, "id": "a72bf994-433d-4401-8b15-2c6043e43829", "metadata": { "tags": [] }, "outputs": [], "source": [ "# The function A.augment(Y) is used to define the augmented matrix M = (A|Y)\n", "# We can put a vertical bar to separate A from Y in the resulting matrix M\n", "A = matrix( QQ, [ [2,4,6], [4,5,6], [3,1,2] ] )\n", "# Y = matrix( QQ, [ [18], [24], [4] ] )\n", "Y = column_matrix( QQ, [[ 18, 24, 4 ]])\n", "M = A.augment(Y, subdivide = \"True\")" ] }, { "cell_type": "code", "execution_count": 35, "id": "edff9df1-452f-472c-b28a-543f5b0c9d36", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr|r}\n", "2 & 4 & 6 & 18 \\\\\n", "4 & 5 & 6 & 24 \\\\\n", "3 & 1 & 2 & 4\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr|r}\n", "2 & 4 & 6 & 18 \\\\\n", "4 & 5 & 6 & 24 \\\\\n", "3 & 1 & 2 & 4\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 2 4 6|18]\n", "[ 4 5 6|24]\n", "[ 3 1 2| 4]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# We display the augmented matrix (A|Y)\n", "# Note the vertical bar separating A from Y\n", "show(M)" ] }, { "cell_type": "code", "execution_count": 36, "id": "91a2fc0b-c3af-4acc-97ee-7cda4eedf66d", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr|r}\n", "1 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 6 \\\\\n", "0 & 0 & 1 & -1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr|r}\n", "1 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 6 \\\\\n", "0 & 0 & 1 & -1\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 0 0| 0]\n", "[ 0 1 0| 6]\n", "[ 0 0 1|-1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# The RREF is computed in the exact same way as before\n", "show(M.echelon_form())" ] }, { "cell_type": "markdown", "id": "9d7ca856-6be7-4578-a27d-eb68d872e1bc", "metadata": {}, "source": [ "The rightmost column of the matrix thus obtained is the solution of the system $AX=Y$, as we now check." ] }, { "cell_type": "code", "execution_count": 37, "id": "f0593932-3f2f-4d7a-b4c2-d9289e60e487", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{r}\n", "0 \\\\\n", "6 \\\\\n", "-1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{r}\n", "0 \\\\\n", "6 \\\\\n", "-1\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 0]\n", "[ 6]\n", "[-1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# We first store the reduced row-echelon form of M in a variable N\n", "N = M.echelon_form()\n", "# Then we extract the entries contained in Rows 0,1 and 2 and Column 3\n", "# Note that Row 0 is the first row (in maths, we usually call it Row 1)\n", "X = N.matrix_from_rows_and_columns([ 0, 1, 2 ], [3])\n", "show(X)" ] }, { "cell_type": "code", "execution_count": 38, "id": "6c2940b2-0e66-446f-b098-70cd39ca4f88", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We check that the expected equality indeed holds\n", "A*X == Y" ] }, { "cell_type": "code", "execution_count": 39, "id": "74e5bab6-9405-4e94-afa6-825d2b7d445b", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(0,\\,6,\\,-1\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(0,\\,6,\\,-1\\right)$" ], "text/plain": [ "(0, 6, -1)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Note that the following also works and displays the solution as a vector\n", "X1 = N.column(3)\n", "show(X1)" ] }, { "cell_type": "code", "execution_count": 40, "id": "7c877a60-a24c-4c5d-8128-3fbdb6fe5d65", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(X1)" ] }, { "cell_type": "code", "execution_count": 41, "id": "40c55f31-116f-40b2-9ba4-e1b0bce0ca56", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Since Y was declared as a column matrix, we must make it a vector in order to compare it to A*X1\n", "A*X1 == Y.column(0)" ] }, { "cell_type": "markdown", "id": "6c0d59ee-43c5-4e23-b1c0-f4b3f91364c5", "metadata": { "tags": [] }, "source": [ "### Exercises" ] }, { "cell_type": "markdown", "id": "75ce9c3e-4004-4662-8dc0-c87194ca35b4", "metadata": {}, "source": [ "**Exercise 1.** Why does it not work if we try to compute $B+C$ with $B$ and $C$ as above?" ] }, { "cell_type": "markdown", "id": "c3fdc8eb-428b-4f27-9cec-4ebddec6ea21", "metadata": {}, "source": [ "**Exercise 2.** Declare a $2 \\times 2$ matrix $A$ with entries in $\\mathbb{C}$ and compute its determinant and its square $A^2$. Check the computations manually." ] }, { "cell_type": "markdown", "id": "72e6dbde-ff5b-4b9e-b78b-cc8c8ecaf9b9", "metadata": {}, "source": [ "**Exercise 3.** Use *Sage* to reduce the following linear system to its reduced row-echelon form and solve manually the equivalent system thus obtained. \n", "\n", "$$\n", "\\left\\{\n", "\\begin{array}{rcl}\n", "2x + 4y + 6z & = & 18 \\\\\n", "4x + 5y + 6z & = & 24 \\\\\n", "2x + 7y + 12z & = & 30\n", "\\end{array}\n", "\\right.\n", "$$" ] }, { "cell_type": "markdown", "id": "1a9af174-7a80-4cbf-a8ca-6cf70d3e1585", "metadata": { "tags": [] }, "source": [ "## Invertible matrices" ] }, { "cell_type": "markdown", "id": "1524171c-6265-47bb-9c35-571f00c7f813", "metadata": { "tags": [] }, "source": [ "### Computing the inverse" ] }, { "cell_type": "markdown", "id": "9b5ac7e2-a691-4b9a-a4e8-ffcf178d1a9c", "metadata": {}, "source": [ "Given a square matrix $A$ with entries in a ring $R$, we can check whether it is invertible by computing its determinant: if $\\det(A)$ is invertible in $R$, then $A$ is invertible." ] }, { "cell_type": "code", "execution_count": 42, "id": "72dfc3be-184b-4a6b-8b96-68250710736e", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "Ring of integers modulo 36" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Zmod(36)" ] }, { "cell_type": "code", "execution_count": 43, "id": "48d06feb-f978-4277-b2d6-9b3f83630b02", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "8" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Zmod(24).unit_group_order()" ] }, { "cell_type": "code", "execution_count": 44, "id": "340db9d2-aed0-42db-9fe0-c39aa2dd094b", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rr}\n", "1 & 35 \\\\\n", "1 & 6\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rr}\n", "1 & 35 \\\\\n", "1 & 6\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 35]\n", "[ 1 6]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "A = matrix( Zmod(36), [ [1,-1], [1,42] ])\n", "show(A)" ] }, { "cell_type": "code", "execution_count": 45, "id": "bab4a4cf-0eaa-424c-b206-5109fe97ea10", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle 7\\)" ], "text/latex": [ "$\\displaystyle 7$" ], "text/plain": [ "7" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(det(A))" ] }, { "cell_type": "code", "execution_count": 46, "id": "37a0a869-a2c9-4c1b-9795-e5c20974b323", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Check whether a determinant is invertible in a given ring (here Z/6Z)\n", "det(A).is_unit()" ] }, { "cell_type": "code", "execution_count": 47, "id": "3dd991c3-c202-46ac-b6c9-c68437611dca", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "31" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# If det(A) is invertible, one can compute its multiplicative inverse easily\n", "det(A)^(-1)" ] }, { "cell_type": "markdown", "id": "952a724d-205e-4ad4-a244-7a32dcbfc8ea", "metadata": {}, "source": [ "If the matrix $A$ is invertible, we can compute its inverse directly, using the inverse() function." ] }, { "cell_type": "code", "execution_count": 48, "id": "102268ef-b9c4-49cc-aee3-8d353226f520", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rr}\n", "6 & 31 \\\\\n", "5 & 31\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rr}\n", "6 & 31 \\\\\n", "5 & 31\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 6 31]\n", "[ 5 31]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show(A.inverse())" ] }, { "cell_type": "markdown", "id": "1bd53f3c-f5ff-4fcb-8330-6cf53403ac09", "metadata": {}, "source": [ "However, if the entries of $A$ are taken to lie *in a field*, then there is another method, based on the reduction to the RREF of $A$, which tells us if $A$ is invertible and, if so, what $A^{-1}$ is.\n", "\n", "If $A$ is of size $n \\times n$, we simply reduce the augmented matrix $(A|I_n)$ to its RREF $(H|B)$. Then $A$ is invertible if and only if $H=I_n$ and, in this case $A^{-1}=B$.\n", "\n", "*Observation:* **We need the entries of $A$ to lie in a field in order to apply Gaussian elimination.** Note that $H$ is the RREF of $A$ in the computation above." ] }, { "cell_type": "code", "execution_count": 49, "id": "eb5a1b07-ec7d-49c8-831b-1920bb649e37", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rr}\n", "1 & 1 \\\\\n", "1 & 0\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rr}\n", "1 & 1 \\\\\n", "1 & 0\n", "\\end{array}\\right)$" ], "text/plain": [ "[1 1]\n", "[1 0]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Let us work in the field with 2^4 = 32 elements\n", "# You can also declare the field GF(2^4) as GF(32) or GF(2,4)\n", "# Whatever you choose, you should use the same convention consistenly throughout the file\n", "A = matrix( GF(2^4), [ [1,-1], [1,42] ])\n", "show(A)" ] }, { "cell_type": "code", "execution_count": 50, "id": "b95c00f9-313a-4818-8b58-b5e3d9c6f4cc", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 1 & 1 & 0 \\\\\n", "1 & 0 & 0 & 1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 1 & 1 & 0 \\\\\n", "1 & 0 & 0 & 1\n", "\\end{array}\\right)$" ], "text/plain": [ "[1 1 1 0]\n", "[1 0 0 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# We construct the identity matrix I and the augmented matrix (A|I)\n", "# For some reason, we cannot use \"subdivide\" when working with matrices with entries in GF(2^4)\n", "I2 = matrix.identity(GF(2^4),2)\n", "M = A.augment(I2)\n", "show(M)" ] }, { "cell_type": "code", "execution_count": 51, "id": "ffb1183c-9312-4995-9fb1-2cea10fc2a66", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 0 & 0 & 1 \\\\\n", "0 & 1 & 1 & 1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 0 & 0 & 1 \\\\\n", "0 & 1 & 1 & 1\n", "\\end{array}\\right)$" ], "text/plain": [ "[1 0 0 1]\n", "[0 1 1 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# We reduce M to its RREF\n", "# The left 2x2 matrix is the identity, so M is invertible\n", "show(M.echelon_form())" ] }, { "cell_type": "code", "execution_count": 52, "id": "cb81e601-7a82-43e0-998f-33a3830007e6", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rr}\n", "0 & 1 \\\\\n", "1 & 1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rr}\n", "0 & 1 \\\\\n", "1 & 1\n", "\\end{array}\\right)$" ], "text/plain": [ "[0 1]\n", "[1 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# The rightmost 2x2 matrix is the inverse of M and we extract it (directly from M.echelon_form())\n", "B = (M.echelon_form()).matrix_from_rows_and_columns([0,1], [2,3])\n", "show(B)" ] }, { "cell_type": "code", "execution_count": 53, "id": "a1c3ef90-df8e-4eba-a074-cb43188a7c7b", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We check that B is indeed the inverse of A\n", "B == A.inverse()" ] }, { "cell_type": "markdown", "id": "e876989a-6d3c-4d8e-97d1-5dce7e873a59", "metadata": { "tags": [] }, "source": [ "### Row operations and elementary matrices" ] }, { "cell_type": "markdown", "id": "d101433d-6ba2-47a1-8c2d-39527efde84a", "metadata": {}, "source": [ "In *Sage*, it is easy to manipulate matrices and perform operations on them, for instance on rows." ] }, { "cell_type": "code", "execution_count": 54, "id": "df1ece05-9ff3-4b1b-a1f8-ea1facd39f8a", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & -2\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & -2\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 2 4 6]\n", "[ 4 5 6]\n", "[ 3 1 -2]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# We declare a 3x3 matrix (in an alternate way) and perform row operations on it\n", "A = matrix(QQ, 3, 3, [2, 4, 6, 4, 5, 6, 3, 1, -2])\n", "show(A)" ] }, { "cell_type": "code", "execution_count": 55, "id": "49eb642a-71e8-4e9c-b6fa-5a3d49eb4b17", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "0 & 3 & -2\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "0 & 3 & -2\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 2 4 6]\n", "[ 4 5 6]\n", "[ 0 3 -2]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Here is how to modify a coefficient of A (storing A in a new variable first)\n", "B = copy(A)\n", "B[2,0] = 0\n", "B[2,1] = 3 * B[2,1]\n", "show(B)" ] }, { "cell_type": "code", "execution_count": 56, "id": "804482f6-15e3-47d8-b419-1819ad9baeb0", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "1 & 2 & 3 \\\\\n", "0 & -3 & -6 \\\\\n", "0 & -5 & -11\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "1 & 2 & 3 \\\\\n", "0 & -3 & -6 \\\\\n", "0 & -5 & -11\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 2 3]\n", "[ 0 -3 -6]\n", "[ 0 -5 -11]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Let us start the reduction to row-echelon form of A (storing it in a new variable first)\n", "# We proceed as in Gauß's algorithm\n", "N = copy(A)\n", "# The first operation replaces the first row of N with 1/2 times that row\n", "N[0,:] = 1/2 * N[0,:]\n", "# This replaces the second row with the second row minus 4 times the first row\n", "N[1,:] = N[1,:] - 4 * N[0,:]\n", "# What do you think this does?\n", "N[2,:] = N[2,:] - 3 * N[0,:]\n", "show(N)" ] }, { "cell_type": "code", "execution_count": 57, "id": "82301402-899f-4b6e-b0b6-84555e3508f0", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "1 & 2 & 3 \\\\\n", "0 & 1 & 2 \\\\\n", "0 & 0 & 1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "1 & 2 & 3 \\\\\n", "0 & 1 & 2 \\\\\n", "0 & 0 & 1\n", "\\end{array}\\right)$" ], "text/plain": [ "[1 2 3]\n", "[0 1 2]\n", "[0 0 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# We go on like this\n", "N[1,:] = -1/3 * N[1,:]\n", "N[2,:] = N[2,:] + 5*N[1,:]\n", "N[2:] = -N[2:]\n", "show(N)" ] }, { "cell_type": "markdown", "id": "244a9236-2eec-4821-88f6-a607ee8ab761", "metadata": {}, "source": [ "As we know, performing row operations on a $m \\times n$ matrix is the same as multiplying to the left by an appropriate invertible $m \\times m$ matrix. Likewise, performing column operations on a matrix is the same as multiplying to the right by an appropriate invertible $n \\times n$ matrix.\n", "\n", "In *Sage*, there is a command to define the elementary matrix corresponding to an elementary operation (e.g. swapping two rows or multiplying a column by a scalar). Unfortunately, the syntax is not very clear, due to *Sage* numbering method." ] }, { "cell_type": "code", "execution_count": 58, "id": "9ed3baf0-4458-4241-a40b-00b316cf3e05", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 0 \\\\\n", "0 & 0 & 1 & 0 \\\\\n", "-1 & 0 & 0 & 1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 0 & 0 & 0 \\\\\n", "0 & 1 & 0 & 0 \\\\\n", "0 & 0 & 1 & 0 \\\\\n", "-1 & 0 & 0 & 1\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 0 0 0]\n", "[ 0 1 0 0]\n", "[ 0 0 1 0]\n", "[-1 0 0 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# The 4x4 elementary matrix which multiplies row 1 by -1 and adds it to row 4 of a 4xn matrix \n", "E = elementary_matrix( QQ, 4, row1 = 3, row2 = 0, scale= -1 )\n", "show(E)" ] }, { "cell_type": "code", "execution_count": 59, "id": "1a342b45-bf18-463a-b546-06ac11186f81", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "0 & 1 & 0 \\\\\n", "1 & 0 & 0 \\\\\n", "0 & 0 & 1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "0 & 1 & 0 \\\\\n", "1 & 0 & 0 \\\\\n", "0 & 0 & 1\n", "\\end{array}\\right)$" ], "text/plain": [ "[0 1 0]\n", "[1 0 0]\n", "[0 0 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Swapping columns 1 and 2 of an mx3 matrix\n", "S = elementary_matrix( QQ, 3, col1 = 0, col2 = 1 )\n", "show(S)" ] }, { "cell_type": "code", "execution_count": 60, "id": "f1ef3337-ba91-4105-bd8d-5001681c81cb", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "1 & 0 & 0 \\\\\n", "0 & 42 & 0 \\\\\n", "0 & 0 & 1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "1 & 0 & 0 \\\\\n", "0 & 42 & 0 \\\\\n", "0 & 0 & 1\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 0 0]\n", "[ 0 42 0]\n", "[ 0 0 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Scaling the second row of a 3xn matrix\n", "M = elementary_matrix(QQ, 3, row1 = 1, scale = 42)\n", "show(M)\n", "# How would you scale the third column of an mx4 matrix by a factor of -33?" ] }, { "cell_type": "markdown", "id": "8c9845c7-7e50-4791-8f5a-fc83fada83b4", "metadata": { "tags": [] }, "source": [ "### Exercises" ] }, { "cell_type": "markdown", "id": "26c869d1-604a-4d55-81fa-218942c36b11", "metadata": {}, "source": [ "**Exercise 1.** Retake the matrix $N$ above and put it in RREF by writing down the row operations in *Sage*. Compare your result with A.echelon_form()." ] }, { "cell_type": "markdown", "id": "76de8809-1f32-4043-b9e3-da57383bee1f", "metadata": {}, "source": [ "**Exercise 2.** How would you write down elementary operations on the *columns* of a matrix $A$?" ] }, { "cell_type": "markdown", "id": "2595822e-8fe8-4fcf-a90f-962903ba8db9", "metadata": { "tags": [] }, "source": [ "**Exercise 3.** Consider the matrix \n", "$$ \n", "A = \n", "\\begin{pmatrix}\n", "2 & 4 & 6 \\\\\n", "4 & 5 & 6 \\\\\n", "3 & 1 & -2\n", "\\end{pmatrix}\n", "\\in \\mathrm{Mat}(3\\times 3; \\mathbb{Q})$$\n", "Define an augmented matrix $M=(A|I_3)$ and reduce it to its RREF, extract the rightmost $3 \\times 3$ matrix and check that it is an inverse for $A$." ] }, { "cell_type": "markdown", "id": "d3ccf5e1-370b-48db-b0f8-fd3b752f70f4", "metadata": { "tags": [] }, "source": [ "## Projects" ] }, { "cell_type": "markdown", "id": "119377f8-a893-4e67-85a7-9002a4670d93", "metadata": {}, "source": [ "Choose one the projects below and start working on it. Depending on your degree of proficiency with *Sage* or *Python*, you might need to read the documentation to make progress. You may also ask me for guidance and suggestions.\n", "\n", "The goal is to present your findings in a short oral presentation later on in the seminar." ] }, { "cell_type": "markdown", "id": "85822e5d-68b0-4cc7-8269-7d5df1e2ca15", "metadata": { "jp-MarkdownHeadingCollapsed": true, "tags": [] }, "source": [ "### Elementary matrices" ] }, { "cell_type": "markdown", "id": "f414515d-39d4-42c3-b1c0-43b3103109e7", "metadata": {}, "source": [ "In this project, you are asked to write a short program that lets you:\n", "1. Input a matrix $A$.\n", "1. Ask the user which row operation they want to apply to that matrix: this row operation should be encoded under the form $\\lambda R_i + R_j \\rightarrow R_j$ or $R_i \\leftrightarrow R_j$ or $\\lambda R_i \\rightarrow R_i$.\n", "1. Output the elementary matrix corresponding to the row operation entered by the user and the resulting new matrix $A$." ] }, { "cell_type": "markdown", "id": "833f20e7-eef7-4ccf-8d06-300f7b3c341b", "metadata": { "jp-MarkdownHeadingCollapsed": true, "tags": [] }, "source": [ "### PLU Decomposition" ] }, { "cell_type": "markdown", "id": "7e837242-efc8-4967-9065-f32962ea9c1b", "metadata": {}, "source": [ "In this project, you are asked to write a program that lets you:\n", "1. Input a matrix $A$.\n", "2. Determine whether $A$ is invertible and, if so, compute its inverse and write it down as a product of elementary matrices.\n", "\n", "This entails:\n", "1. Recalling why the inverse of an invertible matrix can be expressed as a product of elementary matrices.\n", "2. Looking into LU and PLU decompositions in *Sage*." ] }, { "cell_type": "markdown", "id": "5088e720-9855-4df6-b124-ae9a1afa0852", "metadata": { "jp-MarkdownHeadingCollapsed": true, "tags": [] }, "source": [ "### Cramer's rule" ] }, { "cell_type": "markdown", "id": "f6ac0571-4b76-4d9a-af49-2b5eaa2797f5", "metadata": {}, "source": [ "In this project, you are asked to write a program that lets you:\n", "1. Input a matrix $A$.\n", "1. Input a vector $Y$ such that the equality $AX=Y$ makes sense.\n", "1. Determine whether $A$ is invertible and, if so, compute the solution $X$ of the system $AX=Y$ using *Cramer's rule*.\n", "\n", "This entails:\n", "1. Recalling the mathematical proof of Cramer's rule.\n", "1. In the program, substitute a given column of $A$ with $Y$ and compute the determinant of the matrix thus obtained." ] }, { "cell_type": "markdown", "id": "0bc00f61-1118-4379-be6f-c13becd09b33", "metadata": { "jp-MarkdownHeadingCollapsed": true, "tags": [] }, "source": [ "### Gauß's algorithm\n" ] }, { "cell_type": "markdown", "id": "520c16d0-4975-4df4-8f5f-b6bbd31c6bba", "metadata": {}, "source": [ "This is the most programmation-oriented project. You are asked to write a program that lets you:\n", "1. Input a matrix.\n", "2. Put it in reduced row-echelon form.\n", "3. (If possible) Indicate the list of elementary operations that has been performed, along with the corresponding elementary matrices." ] }, { "cell_type": "markdown", "id": "3269178a-d8b0-4921-8487-a5cdb7b2df15", "metadata": {}, "source": [ "---" ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.8", "language": "sage", "name": "sagemath-9.8" }, "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.11.1" }, "toc-autonumbering": false, "toc-showcode": false, "toc-showmarkdowntxt": false, "toc-showtags": false }, "nbformat": 4, "nbformat_minor": 5 }