{ "cells": [ { "cell_type": "markdown", "id": "870d26af-9609-4765-a812-50e7d7833390", "metadata": {}, "source": [ "**Author:** Florent Schaffhauser, Uni-Heidelberg, Summer Semester 2023" ] }, { "cell_type": "markdown", "id": "d136116e-dcde-4d60-8b01-04e84a4d2b22", "metadata": { "tags": [] }, "source": [ "# Bases" ] }, { "cell_type": "markdown", "id": "99a5ed3f-ff21-44eb-a1bf-ecfc0b3996e3", "metadata": {}, "source": [ "## Kernel and range" ] }, { "cell_type": "markdown", "id": "1102e510-a492-4a6f-aab2-b272672304b0", "metadata": { "tags": [] }, "source": [ "### Solving linear systems" ] }, { "cell_type": "markdown", "id": "6b5a7a6f-4c4a-487f-9833-99e7f04c058e", "metadata": {}, "source": [ "Let us consider the following linear system of two equations and four variables:\n", "$$ \n", "\\left\\{\n", "\\begin{array}{rcl}\n", "x + y - z + 5t & = & 2 \\\\\n", "-y + 3z & = & -1 \n", "\\end{array}\n", "\\right.\n", "$$" ] }, { "cell_type": "markdown", "id": "5338eebc-1686-43bd-8f14-0f8fec283778", "metadata": {}, "source": [ "We can ask *Sage* to solve it for us. Note that we must declare the variables *and* specify what variables to solve for. Note also that *Sage* will introduce parameters automatically if they are needed. If you want more information, you can type `solve?` in a code cell and run it. As usual, the `show` command is optional." ] }, { "cell_type": "code", "execution_count": 1, "id": "88f8a54a-f678-4d55-b82e-0a8a15e05240", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left[\\left[x = -5 \\, r_{1} - 2 \\, r_{2} + 1, y = 3 \\, r_{2} + 1, z = r_{2}, t = r_{1}\\right]\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[\\left[x = -5 \\, r_{1} - 2 \\, r_{2} + 1, y = 3 \\, r_{2} + 1, z = r_{2}, t = r_{1}\\right]\\right]$" ], "text/plain": [ "[[x == -5*r1 - 2*r2 + 1, y == 3*r2 + 1, z == r2, t == r1]]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "x, y, z, t = var( \"x, y, z, t\" )\n", "show( solve( [ x + y - z + 5*t == 2, y-3*z == 1 ], [ x,y,z,t ]) )" ] }, { "cell_type": "markdown", "id": "91cc5a47-d0b6-432b-b87b-821e4a0cf2a1", "metadata": { "tags": [] }, "source": [ "In this example, *Sage* has introduced two parameters. This means that the system of equations that we were considering has a solution and that this solution is non-unique. Without more information, we can hardly say more. For instance, it is unclear if the parameters are to be taken as rational, real or complex numbers. In fact, the `solve` command is not related to linear systems and could be used to solve other types of equations." ] }, { "cell_type": "code", "execution_count": 2, "id": "ce6aafcb-9300-4791-963f-f931dcde0a53", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "[x == 1/2*pi]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solve( cos(x) == 0, x )" ] }, { "cell_type": "markdown", "id": "3c0c48e5-bb83-4b13-9717-30d994de1813", "metadata": {}, "source": [ "Let us write the previous linear system in matrix form:\n", "$$\n", "\\begin{pmatrix}\n", "1 & 1 & -1 & 5 \\\\\n", "0 & -1 & 3 & 0\n", "\\end{pmatrix}\n", "\\begin{pmatrix}\n", "x \\\\\n", "y \\\\\n", "z \\\\\n", "t\n", "\\end{pmatrix}\n", "=\n", "\\begin{pmatrix}\n", "2 \\\\\n", "-1\n", "\\end{pmatrix}\n", "$$\n", "We can declare the matrix in *Sage* and apply Gaussian reduction to it." ] }, { "cell_type": "code", "execution_count": 3, "id": "dbf1ed36-796e-441a-8607-28b97be149a0", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 0 & 2 & 5 \\\\\n", "0 & 1 & -3 & 0\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 0 & 2 & 5 \\\\\n", "0 & 1 & -3 & 0\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 0 2 5]\n", "[ 0 1 -3 0]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "A = matrix( QQ, [ [ 1, 1, -1, 5 ], [ 0, -1, 3, 0 ] ])\n", "show( A.echelon_form() )" ] }, { "cell_type": "markdown", "id": "68a7f804-2a17-42b3-8f59-13f3c27ef182", "metadata": { "tags": [] }, "source": [ "As we can see, the reduced row-echelon form of $ A $ has two columns without a pivot (the third column and the fourth column). This means that the variables corresponding to these columns (in this case, the third and fourth variables, i.e. $ z $ and $ t $) are *free variables* and that they will be used as parameters. Mathematically, this tells us that $$ \\dim \\ker A = 2 $$ i.e. that $ \\ker A $ **is a $2$-dimensional subspace of** $ \\mathbb{Q}^4 $.\n", "\n", "This is something that *Sage* is able to tell us, but in a slightly different terminology." ] }, { "cell_type": "code", "execution_count": 4, "id": "b6a94cc2-853f-4fae-a1f4-2ebea5983cd6", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "Vector space of degree 4 and dimension 2 over Rational Field\n", "Basis matrix:\n", "[ 1 0 0 -1/5]\n", "[ 0 1 1/3 -2/15]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.right_kernel()" ] }, { "cell_type": "markdown", "id": "eb093041-8ab8-4b06-8ea3-7d922c28f007", "metadata": {}, "source": [ "There are several remarks to be made:\n", "1. To *Sage*, the expression \"Vector space of degree 4 and dimension 2 over Rational field\" means \"$2$-dimensional subspace of $ \\mathbb{ Q }^4 $\".\n", "1. The function `right_kernel()` applied to matrix $ A $ means the space of *column* vectors $ X $ such that $ A X = 0 $, which in mathematics we just call *kernel*. If we use the function `kernel()`, it is interpreted by *Sage* as `left_kernel()`, which means the space of *row* vectors $ X $ such that $ X A = 0 $ (which, as a vector space, is isomorphic to $ \\ker \\,^t A $).\n", "1. *Sage* also returns automatically a basis of $ \\ker A $, which is presented as a family of row vectors. However, we should think of them as column vectors." ] }, { "cell_type": "code", "execution_count": 5, "id": "44d0c0d8-b2ac-4416-9432-38de69fd7296", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The following function returns the dimension of the kernel\n", "A.right_nullity()" ] }, { "cell_type": "code", "execution_count": 6, "id": "8c7a17c5-d564-44e8-bfe3-61b763b1c410", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{RowSpan}_{\\Bold{Q}}\\left(\\begin{array}{rrrr}\n", "1 & 0 & 0 & -\\frac{1}{5} \\\\\n", "0 & 1 & \\frac{1}{3} & -\\frac{2}{15}\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\newcommand{\\Bold}[1]{\\mathbf{#1}}\\mathrm{RowSpan}_{\\Bold{Q}}\\left(\\begin{array}{rrrr}\n", "1 & 0 & 0 & -\\frac{1}{5} \\\\\n", "0 & 1 & \\frac{1}{3} & -\\frac{2}{15}\n", "\\end{array}\\right)$" ], "text/plain": [ "Vector space of degree 4 and dimension 2 over Rational Field\n", "Basis matrix:\n", "[ 1 0 0 -1/5]\n", "[ 0 1 1/3 -2/15]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# We get a slightly different presentation of the kernek of A if we use show()\n", "show( A.right_kernel() )" ] }, { "cell_type": "code", "execution_count": 7, "id": "fc0b3139-7471-43fc-a330-9b8a1c2c86d9", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{r}\n", "1 \\\\\n", "0 \\\\\n", "0 \\\\\n", "-\\frac{1}{5}\n", "\\end{array}\\right) \\left(\\begin{array}{r}\n", "0 \\\\\n", "1 \\\\\n", "\\frac{1}{3} \\\\\n", "-\\frac{2}{15}\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{r}\n", "1 \\\\\n", "0 \\\\\n", "0 \\\\\n", "-\\frac{1}{5}\n", "\\end{array}\\right) \\left(\\begin{array}{r}\n", "0 \\\\\n", "1 \\\\\n", "\\frac{1}{3} \\\\\n", "-\\frac{2}{15}\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1]\n", "[ 0]\n", "[ 0]\n", "[-1/5] [ 0]\n", "[ 1]\n", "[ 1/3]\n", "[-2/15]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# We can transform the row vectors of the basis of ker A into column vectors\n", "B = A.right_kernel().basis()\n", "v1 = column_matrix( B[0] )\n", "v2 = column_matrix( B[1] )\n", "show( v1, v2 )" ] }, { "cell_type": "code", "execution_count": 8, "id": "6c77b660-60ea-4574-a9d3-35177b1b336b", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "(True, True)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We can also check that the vectors v1, v2 lie in ker A\n", "A * v1 == 0, A * v2 == 0" ] }, { "cell_type": "markdown", "id": "d381bab6-6962-4b2a-a8a2-fd9aee276362", "metadata": { "tags": [] }, "source": [ "Note that the system that we wanted to solve in the first place was not a homogeneous system:\n", "$$\n", "\\begin{pmatrix}\n", "1 & 1 & -1 & 5 \\\\\n", "0 & -1 & 3 & 0\n", "\\end{pmatrix}\n", "\\begin{pmatrix}\n", "x \\\\\n", "y \\\\\n", "z \\\\\n", "t\n", "\\end{pmatrix}\n", "=\n", "\\begin{pmatrix}\n", "2 \\\\\n", "-1\n", "\\end{pmatrix}\n", "$$\n", "So we should form the augmented matrix and apply Gaussian reduction to the latter." ] }, { "cell_type": "code", "execution_count": 9, "id": "b91f96a9-bad6-4346-bea6-b9069b5237fb", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrr|r}\n", "1 & 1 & -1 & 5 & 2 \\\\\n", "0 & -1 & 3 & 0 & -1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrr|r}\n", "1 & 1 & -1 & 5 & 2 \\\\\n", "0 & -1 & 3 & 0 & -1\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 1 -1 5| 2]\n", "[ 0 -1 3 0|-1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "y = vector( QQ, [ 2, -1 ] )\n", "M = A.augment( y, subdivide = True )\n", "show( M )" ] }, { "cell_type": "code", "execution_count": 10, "id": "80c55386-3901-43f0-ae61-264814c6a009", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrr|r}\n", "1 & 0 & 2 & 5 & 1 \\\\\n", "0 & 1 & -3 & 0 & 1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrr|r}\n", "1 & 0 & 2 & 5 & 1 \\\\\n", "0 & 1 & -3 & 0 & 1\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 0 2 5| 1]\n", "[ 0 1 -3 0| 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "show( M.echelon_form() )" ] }, { "cell_type": "markdown", "id": "189ae1ce-4efa-4910-b5a7-bdcb060e8dc8", "metadata": {}, "source": [ "The reduced row-echelon form of $ M $ shows that the system \n", "$ A X = \n", "\\begin{pmatrix} \n", "2 \\\\ \n", "-1 \n", "\\end{pmatrix}\n", "$ admits solutions (no inconsistent equation of the form $ 0x + 0y + 0z + 0t = 1 $). In what follows, we shall denote by $ Y $ the vector $ Y = \\begin{pmatrix} \n", "2 \\\\ \n", "-1 \n", "\\end{pmatrix} $." ] }, { "cell_type": "markdown", "id": "a065c816-bd1d-4b21-b52e-ff4207d84198", "metadata": {}, "source": [ "The general theory of linear systems then tells us that the set of solutions of the non-homogeneous system $ A X = Y $ is the affine subspace $$ X_0 + \\ker A = \\{ X_0 + H : H \\in \\ker A \\} $$\n", "where $ X_0 $ is an arbitrary solution of $ A X = Y $. This affine space has the same dimension as the vector space $ \\ker A $." ] }, { "cell_type": "markdown", "id": "e50a6e30-abfc-430a-9508-6d14688afcee", "metadata": {}, "source": [ "**Proof.** \n", "\n", "Let $ X_0 \\in \\mathbb{Q}^4$ satisfy $ A X_0 = Y $.\n", "\n", "Then for all $ H \\in \\ker A $, we have \n", "$$ A( X_0 + H )= A X_0 + A H = Y + 0 = Y $$ \n", "so the vector $ X_0 + H $ is indeed a solution of the equation $ A X = Y $. \n", "\n", "Conversely, if $ X_1 \\in \\mathbb{Q}^4$ satisfies $ A X_1 = Y $ then \n", "$$ A ( X_1 - X_0 ) = A X_1 - A X_0 = Y - Y = 0 $$\n", "so the vector $ H := X_1 -X_0 \\in \\ker A $ and we have indeed $ X_1 = X_0 + H $." ] }, { "cell_type": "markdown", "id": "a70de46b-2546-4916-bfc6-c8d12725453e", "metadata": {}, "source": [ "Since we already know a basis of $ \\ker A $, in order to completely solve the system $ A X = Y $, it suffices to find a vector $ X_0 $ such that $ A X_0 = Y $. This can also be done using *Sage*." ] }, { "cell_type": "code", "execution_count": 11, "id": "384faa31-6f84-4ff7-8fc4-9ccc9a9ec187", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "((1, 1, 0, 0), True)" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We ask Sage for one solution of the system AX = Y\n", "x0 = A.solve_right(y)\n", "x0, A*x0 == y " ] }, { "cell_type": "markdown", "id": "88776be6-5587-4c22-b1be-bdc3b97ed40b", "metadata": {}, "source": [ "We have thus found a parameterisation of the space of solutions of the system $ A X = Y $, namely $ X \\in \\mathbb{ Q }^4 $ satisfies $ A X = Y $ if and only if there are rational numbers $ a_1, a_2 \\in \\mathbb{ Q } $ such that \n", "$$ X = X_0 + a_1 v_1 + a_2 v_2 $$\n", "where $ ( v_1, v_2 ) $ is the basis of $ \\ker A $ determined earlier using *Sage*." ] }, { "cell_type": "code", "execution_count": 12, "id": "f1ec683f-aba3-4702-95e7-9601b32f7312", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{r}\n", "1 \\\\\n", "1 \\\\\n", "0 \\\\\n", "0\n", "\\end{array}\\right) \\left(\\begin{array}{r}\n", "2 \\\\\n", "-1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{r}\n", "1 \\\\\n", "1 \\\\\n", "0 \\\\\n", "0\n", "\\end{array}\\right) \\left(\\begin{array}{r}\n", "2 \\\\\n", "-1\n", "\\end{array}\\right)$" ], "text/plain": [ "[1]\n", "[1]\n", "[0]\n", "[0] [ 2]\n", "[-1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# We construct column vectors, for convenience later on\n", "X0 = column_matrix( x0 )\n", "Y = column_matrix( y )\n", "show( X0, Y )" ] }, { "cell_type": "code", "execution_count": 13, "id": "55e7e646-9ea1-4efb-bcdc-ab63367a253e", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Note that the following verification is performed symbolically\n", "a1, a2 = var( \" a1 a2 \" )\n", "X = X0 + a1 * v1 + a2 * v2\n", "A*X == Y" ] }, { "cell_type": "code", "execution_count": 14, "id": "b18c357a-eb3d-4a91-9d8f-155f16dca926", "metadata": { "tags": [] }, "outputs": [], "source": [ "# We can display the vector X nicely by using a few tricks\n", "from IPython.display import Latex as tex" ] }, { "cell_type": "code", "execution_count": 15, "id": "9197b692-2253-4abe-a695-3b57a97fd03b", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/latex": [ " $$ X = X_0 + a_1 v_1 + a_2 v_2 = \\left(\\begin{array}{r}\n", "1 \\\\\n", "1 \\\\\n", "0 \\\\\n", "0\n", "\\end{array}\\right) + a_1 \\left(\\begin{array}{r}\n", "1 \\\\\n", "0 \\\\\n", "0 \\\\\n", "-\\frac{1}{5}\n", "\\end{array}\\right) + a_2 \\left(\\begin{array}{r}\n", "0 \\\\\n", "1 \\\\\n", "\\frac{1}{3} \\\\\n", "-\\frac{2}{15}\n", "\\end{array}\\right) = \\left(\\begin{array}{r}\n", "a_{1} + 1 \\\\\n", "a_{2} + 1 \\\\\n", "\\frac{1}{3} \\, a_{2} \\\\\n", "-\\frac{1}{5} \\, a_{1} - \\frac{2}{15} \\, a_{2}\n", "\\end{array}\\right) $$ " ], "text/plain": [ "" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "tex( f\" $$ X = X_0 + a_1 v_1 + a_2 v_2 = {latex(X0)} + a_1 {latex(v1)} + a_2 {latex(v2)} = {latex(X)} $$ \" )" ] }, { "cell_type": "markdown", "id": "ce56a5e7-6e92-4343-bc6a-6a7953364186", "metadata": { "tags": [] }, "source": [ "### The span of a family of vectors" ] }, { "cell_type": "markdown", "id": "38a986f4-613b-4d76-a663-2279f66b3070", "metadata": {}, "source": [ "A basic problem in linear algebra is to compute the dimension of a subspace $ F $ of a given finite-dimensional vector space $ E $. \n", "\n", "We illustrated this in the previous section with the example of $ \\ker A $, where $ A $ is an $ m \\times n $ matrix. In that case, if $ A $ has entries in $ \\mathbb{Q} $, say, then $ \\ker A $ is a subspace of $ \\mathbb{Q}^n $. But we can also study the subspace $ \\mathrm{Im} \\, A \\subset \\mathbb{ Q }^m $, which is generated by the columns of $ A $ (which is why $ \\mathrm{Im} \\, A $ is also called the *column space* of $ A $). \n", "\n", "A natural question is how to *extract a basis for the column space* from the family of all columns of $ A $. This can be achieved using the reduced row-echelon form of $ A $ and of course it gives us a byproduct the dimension of $ \\mathrm{Im} \\, A $, also called the *rank* of $ A $." ] }, { "cell_type": "code", "execution_count": 16, "id": "73f6fdcf-254f-4ffa-91f6-0d39962634b7", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 1 & -1 & 5 \\\\\n", "0 & -1 & 3 & 0\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 1 & -1 & 5 \\\\\n", "0 & -1 & 3 & 0\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 1 -1 5]\n", "[ 0 -1 3 0]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Let us retake the previous matrix A\n", "show(A)" ] }, { "cell_type": "code", "execution_count": 17, "id": "a78f3559-a467-4980-9373-7e39a6e95b73", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We have seen that dim ker A = 2, so the rank of $ A is 4 - 2 = 2.\n", "A.rank()" ] }, { "cell_type": "code", "execution_count": 18, "id": "6a9fd7bb-6d98-4cba-b762-b7e644488b23", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 0 & 2 & 5 \\\\\n", "0 & 1 & -3 & 0\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 0 & 2 & 5 \\\\\n", "0 & 1 & -3 & 0\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 0 2 5]\n", "[ 0 1 -3 0]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# This is reflected in the reduced row-echelon form of A\n", "# The rank of A is equal to the number of the number of pivots in A1\n", "A1 = A.echelon_form()\n", "show(A1)" ] }, { "cell_type": "code", "execution_count": 19, "id": "b2ee1ec4-35d9-404a-b55f-15984e473f70", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "(0, 1)" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The following function returns the indices of columns of A1 containing pivots\n", "A1.pivots()" ] }, { "cell_type": "code", "execution_count": 20, "id": "6a8c3d72-df32-438b-8709-b59a2dda21a4", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "[(1, 0), (1, -1), (-1, 3), (5, 0)]" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We can list the colums of A as vectors using the following function\n", "A.columns()" ] }, { "cell_type": "markdown", "id": "6a4e6b3a-9690-44a2-bb9b-3e8fe0e524d0", "metadata": {}, "source": [ "So the *first and second columns* of $ A $ form a basis of the column space of $ A $. And the third column of $ A $ is equal to twice the first one minus three times the second, while the fourth one is equal to five times the first. Can you read this information on the reduced row-echelon form of $ A $ ?" ] }, { "cell_type": "code", "execution_count": 21, "id": "ef7015e7-69c9-4382-b75d-8ea20161e514", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We check that the subspace generated by the first two columns of A is equal\n", "# to the whole column space\n", "span( [ vector( A[:,i] ) for i in A1.pivots() ] ) == span( [ v for v in A.columns() ] )" ] }, { "cell_type": "code", "execution_count": 22, "id": "a0c0b317-61ad-4ff6-846a-6673ac1651f9", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Here is an indication of how we can express the third and fourth columns of A\n", "# as a linear combination of the basis that we have just found\n", "A[:,2] == A1[0,2] * A[:,0] + A1[1,2] * A[:,1]\n", "# Can you do something similar for A[:,3]?" ] }, { "cell_type": "markdown", "id": "e95785c6-3a12-44e2-ad9c-b5c1f5e47041", "metadata": {}, "source": [ "We have therefore extracted, from the family of colums of $ A $, a sub-family which is a basis of the column space of $ A $. In the example above, this column space is all of $ \\mathbb{ Q }^2 $, so we cannot complete that basis to a basis of the ambient space.\n", "\n", "Let us consider instead the transpose of $ A $ and the subspace $ \\mathrm{ Im } \\, \\,^t A \\subset \\mathbb{ Q }^4 $." ] }, { "cell_type": "code", "execution_count": 23, "id": "9cd3c606-a42c-4426-a42a-377aaa42d298", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "Vector space of degree 4 and dimension 2 over Rational Field\n", "Basis matrix:\n", "[ 1 0 2 5]\n", "[ 0 1 -3 0]" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "C = A.transpose()\n", "F = span( [ v for v in C.columns() ] )\n", "# Note that Sage computes a basis of F that is *not* a subset of the set of columns \n", "# (also, Sage writes this basis as rows)\n", "F" ] }, { "cell_type": "code", "execution_count": 24, "id": "ac0505e8-3683-4554-8654-a0b0fed391c7", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# But in fact, the two columns of C are linearly independent\n", "C.rank()" ] }, { "cell_type": "code", "execution_count": 25, "id": "f21826c8-f3d7-4d32-abeb-55dd12985541", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "[(1, 1, -1, 5), (0, -1, 3, 0)]" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# So we can just take these two columns as a basis of the space they generate\n", "C.columns()" ] }, { "cell_type": "markdown", "id": "20924bc5-e740-4fda-9be1-80302ccbcd74", "metadata": {}, "source": [ "In order to complete this basis of the column space of $ C $ to a basis of $ \\mathbb{ Q }^4 $, we can add to it the vectors of the canonical basis of $ \\mathbb{ Q }^4 $ and extract from this overly large family (six vectors in a four-dimensional space) a basis of the space that they generate (which is all of $ \\mathbb{ Q }^4 $) by using the same method as earlier." ] }, { "cell_type": "code", "execution_count": 26, "id": "7c552aa7-77ad-4ad1-b0c8-4585eb71fb8d", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrr}\n", "1 & 0 & 1 & 0 & 0 & 0 \\\\\n", "1 & -1 & 0 & 1 & 0 & 0 \\\\\n", "-1 & 3 & 0 & 0 & 1 & 0 \\\\\n", "5 & 0 & 0 & 0 & 0 & 1\n", "\\end{array}\\right) \\left(\\begin{array}{rrrrrr}\n", "1 & 0 & 0 & 0 & 0 & \\frac{1}{5} \\\\\n", "0 & 1 & 0 & 0 & \\frac{1}{3} & \\frac{1}{15} \\\\\n", "0 & 0 & 1 & 0 & 0 & -\\frac{1}{5} \\\\\n", "0 & 0 & 0 & 1 & \\frac{1}{3} & -\\frac{2}{15}\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrr}\n", "1 & 0 & 1 & 0 & 0 & 0 \\\\\n", "1 & -1 & 0 & 1 & 0 & 0 \\\\\n", "-1 & 3 & 0 & 0 & 1 & 0 \\\\\n", "5 & 0 & 0 & 0 & 0 & 1\n", "\\end{array}\\right) \\left(\\begin{array}{rrrrrr}\n", "1 & 0 & 0 & 0 & 0 & \\frac{1}{5} \\\\\n", "0 & 1 & 0 & 0 & \\frac{1}{3} & \\frac{1}{15} \\\\\n", "0 & 0 & 1 & 0 & 0 & -\\frac{1}{5} \\\\\n", "0 & 0 & 0 & 1 & \\frac{1}{3} & -\\frac{2}{15}\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 0 1 0 0 0]\n", "[ 1 -1 0 1 0 0]\n", "[-1 3 0 0 1 0]\n", "[ 5 0 0 0 0 1] [ 1 0 0 0 0 1/5]\n", "[ 0 1 0 0 1/3 1/15]\n", "[ 0 0 1 0 0 -1/5]\n", "[ 0 0 0 1 1/3 -2/15]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "D = column_matrix(C.augment(identity_matrix(4)).columns())\n", "D1 = D.echelon_form()\n", "show( D, D1 )" ] }, { "cell_type": "code", "execution_count": 27, "id": "b64740fb-260a-43d3-93a8-210deffbcf1d", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 0 & 1 & 0 \\\\\n", "1 & -1 & 0 & 1 \\\\\n", "-1 & 3 & 0 & 0 \\\\\n", "5 & 0 & 0 & 0\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrr}\n", "1 & 0 & 1 & 0 \\\\\n", "1 & -1 & 0 & 1 \\\\\n", "-1 & 3 & 0 & 0 \\\\\n", "5 & 0 & 0 & 0\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 0 1 0]\n", "[ 1 -1 0 1]\n", "[-1 3 0 0]\n", "[ 5 0 0 0]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# We can represent the completed basis as the columns of a matrix\n", "E = D.matrix_from_columns( [ i for i in D1.pivots() ] )\n", "show( E )" ] }, { "cell_type": "code", "execution_count": 28, "id": "8dde01a4-9462-43d5-86d0-9153e947c326", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The columns of E indeed form a basis of QQ^4\n", "E.rank()" ] }, { "cell_type": "code", "execution_count": 29, "id": "e4f66542-99b5-46e0-a14f-c056af1a2e9b", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "[(1, 1, -1, 5), (0, -1, 3, 0), (1, 0, 0, 0), (0, 1, 0, 0)]" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Or we can just list the vectors in the completed basis\n", "[ D.column(i) for i in D1.pivots() ]" ] }, { "cell_type": "markdown", "id": "9ed3c57c-a6b8-4dad-9f0f-9dcfc9294e47", "metadata": { "tags": [] }, "source": [ "### Exercises" ] }, { "cell_type": "markdown", "id": "d0854b26-6df7-468c-a1ec-0717edc15790", "metadata": {}, "source": [ "**Exercise 1.** Find a basis of the kernel of the matrix\n", "$$ B = \n", "\\left(\\begin{array}{rrrrrr}\n", "1 & 3 & -2 & 0 & 2 & 0 \\\\\n", "2 & 6 & -5 & -2 & 4 & -3 \\\\\n", "0 & 0 & 5 & 10 & 0 & 15 \\\\\n", "2 & 6 & 0 & 8 & 4 & 18\n", "\\end{array}\\right)\n", "\\in \\mathrm{Mat}( 4 \\times 6; \\mathbb{Q} )\n", "$$ \n", "and find a parameterisation of the space of solutions of the system \n", "$$ B X =\n", "\\left(\n", "\\begin{array}{r}\n", "-1 \\\\\n", "-3 \\\\\n", "5 \\\\\n", "2 \n", "\\end{array}\n", "\\right)\n", ".$$\n" ] }, { "cell_type": "code", "execution_count": 30, "id": "8d85e579-1c2d-4736-9d0b-f096e6722b1c", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrrrrr}\n", "1 & 3 & -2 & 0 & 2 & 0 \\\\\n", "2 & 6 & -5 & -2 & 4 & -3 \\\\\n", "0 & 0 & 5 & 10 & 0 & 15 \\\\\n", "2 & 6 & 0 & 8 & 4 & 18\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrrrrr}\n", "1 & 3 & -2 & 0 & 2 & 0 \\\\\n", "2 & 6 & -5 & -2 & 4 & -3 \\\\\n", "0 & 0 & 5 & 10 & 0 & 15 \\\\\n", "2 & 6 & 0 & 8 & 4 & 18\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 3 -2 0 2 0]\n", "[ 2 6 -5 -2 4 -3]\n", "[ 0 0 5 10 0 15]\n", "[ 2 6 0 8 4 18]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# For convenience, I input B here\n", "B = matrix( QQ, [ [ 1 , 3 , -2 , 0 , 2 , 0], \n", " [ 2 , 6 , -5 , -2 , 4 , -3],\n", " [ 0 , 0 , 5 , 10 , 0 , 15 ],\n", " [ 2 , 6 , 0 , 8 , 4 , 18] ] )\n", "show( B )" ] }, { "cell_type": "markdown", "id": "a205c312-c67d-410e-a1fb-c55ed413b111", "metadata": { "tags": [] }, "source": [ "**Exercise 2.** Extract from the family defined by the columns of $B$ a basis of the column space of $ B $ and express the remaining columns of $ B $ as a linear combination of the columns in that basis." ] }, { "cell_type": "markdown", "id": "37057d6f-56d2-41f6-89fa-c02bec0709fa", "metadata": {}, "source": [ "**Exercise 3.** Explore the commands `row_space()` and `column_space()` and figure out how they work. How is the basis of the row space obtained? And the basis of the column space?" ] }, { "cell_type": "markdown", "id": "28283f4e-acfa-4474-a386-30b537cc3ddd", "metadata": {}, "source": [ "## Diagonalisation" ] }, { "cell_type": "markdown", "id": "c7a23aca-7f6e-4280-bba8-19eeb265c771", "metadata": { "tags": [] }, "source": [ "### Eigenvalues and eigenvectors" ] }, { "cell_type": "markdown", "id": "48d7936e-b755-4129-b49e-c2a6822c6b89", "metadata": { "tags": [] }, "source": [ "We can define diagonalisability of a square matrix as follows.\n", "\n", "**Definition.** Let $ \\mathbb{ k } $ be a field and let $ n > 0 $ be an integer. A matrix $ A \\in \\mathrm{Mat}( n \\times n; \\mathbb{ k } )$ is called **diagonalisable over** $ \\mathbb{ k } $ if there exists a pair of matrices $ ( D, P ) $ in $ \\mathrm{Mat}( n \\times n; \\mathbb{ k } ) $ such that:\n", "1. $ D $ is diagonal.\n", "1. $ P $ is invertible.\n", "1. $ A P = P D $.\n", "\n", "The last equality means that, for all $ j \\in \\{ 1; \\ldots ; n \\} $, the $ j $-th column of $ P $ is an eigenvector for $ A $, associated to the $ j $-th diagonal coefficient $ d_j $ of $ D $: \n", "$$ \\forall \\ j \\in \\{ 1; \\ldots ; n \\}, A C_j( P ) = d_j C_j( P ) $$\n", "where \n", "$$ D = \n", "\\left( \n", "\\begin{array}{rrr}\n", "d_1 & & \\\\\n", "& \\ddots & \\\\\n", "& & d_n\n", "\\end{array}\n", "\\right)\n", "$$\n", "and $$ P = \\left[ C_1(P), \\ldots , C_n(P) \\right] .$$" ] }, { "cell_type": "markdown", "id": "765d9335-502a-4d0c-b83d-07bfb75062cf", "metadata": { "tags": [] }, "source": [ "We then have the following criterion of diagonalisability.\n", "\n", "**Theorem.** A matrix $ A \\in \\mathrm{Mat}( n \\times n; \\mathbb{k} ) $ is diagonalisable over $ \\mathbb{ k } $ if and only if its characteristic polynomial \n", "$$ f_A( t ) := \\det( t I_n - A ) $$\n", "splits into a product of linear factors\n", "$$ f_A( t ) = ( t - a_1 )^{ m_1} \\ldots ( t - a_r )^{ m_r }, \\ a_j \\in \\mathbb{ k } $$\n", "and\n", "$$ \\forall \\ j \\in \\{ 1; \\ldots ; r \\}, \\ \\dim \\ker( A - a_j I_n ) = m_j .$$ \n", "\n", "In other words, $ A $ is diagonalisable over $ \\mathbb{ k } $ if and only if its characteristic polynomial $ f_A( t ) $ splits over $ \\mathbb{ k } $ and *the geometric multiplicity of of $ a_j $ as an eigenvalue of $ A $ is equal to its algebraic multiplicity as a root of $ f_A( t ) $*.\n", "\n", "We will now see how to apply this theorem using `Sage`. Note that sometimes the characteristic polynomial of $ A $ is defined as $ \\det( A - t I_n ) $, which is equal to $ ( -1 )^n \\times f_A( t ) $ with $ f_A( t ) $ as above. We have chosen to follow Sage's convention here." ] }, { "cell_type": "code", "execution_count": 31, "id": "e82824af-2c3f-4150-861d-45ddb188f77c", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle t^{3} - 3 t^{2} + 2 t\\)" ], "text/latex": [ "$\\displaystyle t^{3} - 3 t^{2} + 2 t$" ], "text/plain": [ "t^3 - 3*t^2 + 2*t" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Example 1\n", "A = matrix(QQ, [[2,0,4],[3,-4,12],[1,-2,5]])\n", "f_A = A.charpoly(\"t\")\n", "show( f_A )" ] }, { "cell_type": "code", "execution_count": 32, "id": "4a608a87-d2ca-4d1a-a75a-321b90e26e7a", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle (t - 2) \\cdot (t - 1) \\cdot t\\)" ], "text/latex": [ "$\\displaystyle (t - 2) \\cdot (t - 1) \\cdot t$" ], "text/plain": [ "(t - 2) * (t - 1) * t" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# We can factorise f_A\n", "show( f_A.factor() )" ] }, { "cell_type": "code", "execution_count": 33, "id": "b30f5ce5-17b0-4d61-ad97-0bf941c8ce5a", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left[2, 1, 0\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[2, 1, 0\\right]$" ], "text/plain": [ "[2, 1, 0]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# And its roots are indeed the eigenvalues of A\n", "ev_A = A.eigenvalues()\n", "show( ev_A )" ] }, { "cell_type": "code", "execution_count": 34, "id": "b7aefb9b-72ac-4a35-8fd5-046753b0f82d", "metadata": { "tags": [] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[\n", "(1, 1/2, 0)\n", "]\n", "[\n", "(1, 0, -1/4)\n", "]\n", "[\n", "(1, -3/4, -1/2)\n", "]\n" ] } ], "source": [ "# If we want to find eigenvectors, we need to compute ker( A - a I_3 ) for all eigenvalue a\n", "I = identity_matrix(3)\n", "for a in ev_A:\n", " print((A - a*I).right_kernel().basis())" ] }, { "cell_type": "code", "execution_count": 35, "id": "7a0581ca-63e3-4703-9fde-fe782fda55e8", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "1 & 1 & 1 \\\\\n", "\\frac{1}{2} & 0 & -\\frac{3}{4} \\\\\n", "0 & -\\frac{1}{4} & -\\frac{1}{2}\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "1 & 1 & 1 \\\\\n", "\\frac{1}{2} & 0 & -\\frac{3}{4} \\\\\n", "0 & -\\frac{1}{4} & -\\frac{1}{2}\n", "\\end{array}\\right)$" ], "text/plain": [ "[ 1 1 1]\n", "[ 1/2 0 -3/4]\n", "[ 0 -1/4 -1/2]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Each eigenspace is 1-dimensional here, and we can construct the matrix P easily\n", "P = matrix( QQ, 3, 3)\n", "i = 0\n", "for a in ev_A:\n", " vec_a = (A - a*I).right_kernel().basis()[0]\n", " P[:,i] = column_matrix( vec_a )\n", " i = i + 1\n", "show( P )" ] }, { "cell_type": "code", "execution_count": 36, "id": "a0be6797-88f3-4c62-a3a1-ee0955de9b27", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 0 & 0 \\\\\n", "0 & 1 & 0 \\\\\n", "0 & 0 & 0\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 0 & 0 \\\\\n", "0 & 1 & 0 \\\\\n", "0 & 0 & 0\n", "\\end{array}\\right)$" ], "text/plain": [ "[2 0 0]\n", "[0 1 0]\n", "[0 0 0]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Likewise, we can easily construct the matrix D in this case\n", "D = matrix( QQ, 3, 3 )\n", "i=0\n", "for a in ev_A:\n", " D[i,i] = a\n", " i = i + 1\n", "show( D )" ] }, { "cell_type": "code", "execution_count": 37, "id": "614ade63-7827-4ddf-8907-29576e9a13df", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We check that A is indeed diagonalisable\n", "A*P == P*D" ] }, { "cell_type": "code", "execution_count": 38, "id": "12af0d09-a5c0-4eb0-b2c0-66d97ce5d6d0", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 0 & 0 \\\\\n", "0 & 1 & 0 \\\\\n", "0 & 0 & 0\n", "\\end{array}\\right) \\left(\\begin{array}{rrr}\n", "1 & 1 & 1 \\\\\n", "\\frac{1}{2} & 0 & -\\frac{3}{4} \\\\\n", "0 & -\\frac{1}{4} & -\\frac{1}{2}\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "2 & 0 & 0 \\\\\n", "0 & 1 & 0 \\\\\n", "0 & 0 & 0\n", "\\end{array}\\right) \\left(\\begin{array}{rrr}\n", "1 & 1 & 1 \\\\\n", "\\frac{1}{2} & 0 & -\\frac{3}{4} \\\\\n", "0 & -\\frac{1}{4} & -\\frac{1}{2}\n", "\\end{array}\\right)$" ], "text/plain": [ "[2 0 0]\n", "[0 1 0]\n", "[0 0 0] [ 1 1 1]\n", "[ 1/2 0 -3/4]\n", "[ 0 -1/4 -1/2]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# In fact, Sage can do all of this for us\n", "D1, P1 = A.eigenmatrix_right()\n", "show( D1, P1 )" ] }, { "cell_type": "code", "execution_count": 39, "id": "75338064-d8a7-45d1-a765-46132a5a51b7", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left[\\left(2, \\left[\\left(1,\\,\\frac{1}{2},\\,0\\right)\\right], 1\\right), \\left(1, \\left[\\left(1,\\,0,\\,-\\frac{1}{4}\\right)\\right], 1\\right), \\left(0, \\left[\\left(1,\\,-\\frac{3}{4},\\,-\\frac{1}{2}\\right)\\right], 1\\right)\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[\\left(2, \\left[\\left(1,\\,\\frac{1}{2},\\,0\\right)\\right], 1\\right), \\left(1, \\left[\\left(1,\\,0,\\,-\\frac{1}{4}\\right)\\right], 1\\right), \\left(0, \\left[\\left(1,\\,-\\frac{3}{4},\\,-\\frac{1}{2}\\right)\\right], 1\\right)\\right]$" ], "text/plain": [ "[(2,\n", " [\n", " (1, 1/2, 0)\n", " ],\n", " 1),\n", " (1,\n", " [\n", " (1, 0, -1/4)\n", " ],\n", " 1),\n", " (0,\n", " [\n", " (1, -3/4, -1/2)\n", " ],\n", " 1)]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Another way to get information on the eigenspaces of A is as follows\n", "show( A.eigenvectors_right() )" ] }, { "cell_type": "markdown", "id": "284662fa-eebf-4bf5-9b19-21845a7912b6", "metadata": {}, "source": [ "The first term in the triple above means that $ 2 $ is an eigenvalue of $ A $, that the vector $ \\left( 1, \\frac{1}{2}, 0 \\right) $ is a basis for the eigenspace $ \\ker( A - 2 I_3 ) $, and that $ 2 $ has algebraic multiplicity $ 1 $. And similarly for the other two terms." ] }, { "cell_type": "code", "execution_count": 40, "id": "5d829e22-7966-4726-9739-77cbb508878d", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle t \\cdot (t - 1)^{2}\\)" ], "text/latex": [ "$\\displaystyle t \\cdot (t - 1)^{2}$" ], "text/plain": [ "t * (t - 1)^2" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Example 2, with multiple eigenvalues\n", "A = matrix(QQ, [[2,-3,1],[1,-2,1],[1,-3,2]])\n", "f_A = A.charpoly(\"t\")\n", "show( f_A.factor() )" ] }, { "cell_type": "code", "execution_count": 41, "id": "f48e268e-bce9-4c86-9e26-2215e03616b3", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left[0, 1, 1\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[0, 1, 1\\right]$" ], "text/plain": [ "[0, 1, 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Sage can show us the eigenvalues of A, counted with\n", "# their respective (algebraic) mutiplicities\n", "show( A.eigenvalues() )" ] }, { "cell_type": "code", "execution_count": 42, "id": "028e0bcd-717a-409a-90a1-39b54c0379d0", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left[\\left(0, \\left[\\left(1,\\,1,\\,1\\right)\\right], 1\\right), \\left(1, \\left[\\left(1,\\,0,\\,-1\\right), \\left(0,\\,1,\\,3\\right)\\right], 2\\right)\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[\\left(0, \\left[\\left(1,\\,1,\\,1\\right)\\right], 1\\right), \\left(1, \\left[\\left(1,\\,0,\\,-1\\right), \\left(0,\\,1,\\,3\\right)\\right], 2\\right)\\right]$" ], "text/plain": [ "[(0,\n", " [\n", " (1, 1, 1)\n", " ],\n", " 1),\n", " (1,\n", " [\n", " (1, 0, -1),\n", " (0, 1, 3)\n", " ],\n", " 2)]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Similarly, it can show us eigenvectors for A\n", "show( A.eigenvectors_right() )" ] }, { "cell_type": "markdown", "id": "0d35ced7-475f-43f3-9358-a774c3d53f00", "metadata": {}, "source": [ "The second term in the pair above means that $ 1 $ is an eigenvalue of $ A $ and that the family \n", "$$ \\left( \n", "\\left(\n", "\\begin{array}{r}\n", "1 \\\\ \n", "0 \\\\\n", "-1 \n", "\\end{array}\n", "\\right)\\left(\n", "\\begin{array}{r}\n", "0 \\\\ \n", "1 \\\\\n", "3 \n", "\\end{array}\n", "\\right)\n", "\\right)\n", "$$\n", "is a basis for the eigenspace $ \\ker( A - I_3 ) $, which therefore has dimension $ 2 $, the same as the algebraic multiplicity of the eigenvalue $ 1 $ for $ A $." ] }, { "cell_type": "code", "execution_count": 43, "id": "313c154f-771d-477a-bc5b-04d948ab2331", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "0 & 0 & 0 \\\\\n", "0 & 1 & 0 \\\\\n", "0 & 0 & 1\n", "\\end{array}\\right) \\left(\\begin{array}{rrr}\n", "1 & 1 & 0 \\\\\n", "1 & 0 & 1 \\\\\n", "1 & -1 & 3\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "0 & 0 & 0 \\\\\n", "0 & 1 & 0 \\\\\n", "0 & 0 & 1\n", "\\end{array}\\right) \\left(\\begin{array}{rrr}\n", "1 & 1 & 0 \\\\\n", "1 & 0 & 1 \\\\\n", "1 & -1 & 3\n", "\\end{array}\\right)$" ], "text/plain": [ "[0 0 0]\n", "[0 1 0]\n", "[0 0 1] [ 1 1 0]\n", "[ 1 0 1]\n", "[ 1 -1 3]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "D, P = A.eigenmatrix_right()\n", "show( D, P )" ] }, { "cell_type": "code", "execution_count": 44, "id": "8a096822-d9c8-4b1b-817b-429038402ee8", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle (t + 2) \\cdot (t - 1)^{2}\\)" ], "text/latex": [ "$\\displaystyle (t + 2) \\cdot (t - 1)^{2}$" ], "text/plain": [ "(t + 2) * (t - 1)^2" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Example 3: a matrix whose characteristic polynomial splits but which is not diagonalisable over QQ\n", "A = matrix( QQ, 3, 3, [ -4, 0, -2, 0, 1, 0, 5, 1, 3 ] )\n", "show( A.charpoly(t).factor() )" ] }, { "cell_type": "code", "execution_count": 45, "id": "f2733746-1810-4f95-9d18-6fb90d647a8d", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left[\\left(-2, \\left[\\left(1,\\,0,\\,-1\\right)\\right], 1\\right), \\left(1, \\left[\\left(1,\\,0,\\,-\\frac{5}{2}\\right)\\right], 2\\right)\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[\\left(-2, \\left[\\left(1,\\,0,\\,-1\\right)\\right], 1\\right), \\left(1, \\left[\\left(1,\\,0,\\,-\\frac{5}{2}\\right)\\right], 2\\right)\\right]$" ], "text/plain": [ "[(-2,\n", " [\n", " (1, 0, -1)\n", " ],\n", " 1),\n", " (1,\n", " [\n", " (1, 0, -5/2)\n", " ],\n", " 2)]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# 1 is an eigenvalue of geometric multiplicity 1 but algebraic multiplicity 2\n", "show(A.eigenvectors_right())\n" ] }, { "cell_type": "code", "execution_count": 46, "id": "a47c69ec-b40b-4295-8f9d-3d1588d1d5c5", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\left(\\begin{array}{rrr}\n", "-2 & 0 & 0 \\\\\n", "0 & 1 & 0 \\\\\n", "0 & 0 & 1\n", "\\end{array}\\right), \\left(\\begin{array}{rrr}\n", "1 & 1 & 0 \\\\\n", "0 & 0 & 0 \\\\\n", "-1 & -\\frac{5}{2} & 0\n", "\\end{array}\\right)\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\left(\\begin{array}{rrr}\n", "-2 & 0 & 0 \\\\\n", "0 & 1 & 0 \\\\\n", "0 & 0 & 1\n", "\\end{array}\\right), \\left(\\begin{array}{rrr}\n", "1 & 1 & 0 \\\\\n", "0 & 0 & 0 \\\\\n", "-1 & -\\frac{5}{2} & 0\n", "\\end{array}\\right)\\right)$" ], "text/plain": [ "(\n", "[-2 0 0] [ 1 1 0]\n", "[ 0 1 0] [ 0 0 0]\n", "[ 0 0 1], [ -1 -5/2 0]\n", ")" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Do not get fooled by the information that the command A.eigenmatrix_right() returns!\n", "show( A.eigenmatrix_right() )\n", "# The third column of the right matrix is 0, so that matrix is not invertible..." ] }, { "cell_type": "markdown", "id": "48dad4e8-3dbe-4ffa-bf1d-1c4c56f1f297", "metadata": { "tags": [] }, "source": [ "### Extension of the base field" ] }, { "cell_type": "markdown", "id": "d2b1b2e9-7359-4725-960b-abd0394fbc07", "metadata": {}, "source": [ "Sometimes, a matrix which is not diagonalisable over a given field ($ \\mathbb{ R } $ for instance) can become diagonalisable if it is seen as a matrix with entries in a larger field (for instance $ \\mathbb{ C } $)." ] }, { "cell_type": "code", "execution_count": 47, "id": "9186fad2-c31f-45f9-bbfc-17a783c4a607", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle t \\cdot (t^{2} + 3 t + 3)\\)" ], "text/latex": [ "$\\displaystyle t \\cdot (t^{2} + 3 t + 3)$" ], "text/plain": [ "t * (t^2 + 3*t + 3)" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Example 4: A matrix which is not diagonalisable over QQ but yes over QQbar\n", "A = matrix(QQ, [ [ -1, 1, 0 ], [ 0, -1, 1 ], [ 1, 0, -1 ] ] )\n", "f_A = A.charpoly(\"t\")\n", "show( f_A.factor() )" ] }, { "cell_type": "code", "execution_count": 48, "id": "1ce92110-509c-48d2-b669-6ca380ad9538", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "[(0, 1)]" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The roots() command shows the roots of f_A that lie in the same field as the coefficients\n", "f_A.roots()" ] }, { "cell_type": "markdown", "id": "d9a789fc-b0fd-4a09-a1b0-1c6dd7424ba0", "metadata": {}, "source": [ "The above means that $ 0 $ is a root of multiplicity $ 1 $ of $ f_A( t ) $, and it is the only rational root of that polynomial." ] }, { "cell_type": "code", "execution_count": 49, "id": "7db2002e-da3a-4a0a-a793-b6330b2b3f12", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "[(0, 1),\n", " (-1.500000000000000? - 0.866025403784439?*I, 1),\n", " (-1.500000000000000? + 0.866025403784439?*I, 1)]" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We can ask Sage to look for roots in the usual algebraic closure of QQ\n", "f_A.roots(QQbar)" ] }, { "cell_type": "markdown", "id": "605aa87f-cc3f-4121-a073-8271948a4d21", "metadata": {}, "source": [ "We have obtained two more roots, each one of multiplicity $ 1 $. This is not very convenient for us, though, because the roots are presented as complex numbers $ a + i b $, with $ a, b \\in \\mathbb{ R } $, but in `Sage` real numbers are of type `float` and this is not appropriate for *symbolic computation*. Fortunately, we can ask `Sage` to work in look for roots of $ f_A $ in the **Symbolic Ring**." ] }, { "cell_type": "code", "execution_count": 50, "id": "e21c21ef-73d8-41f0-ae11-2564f919e335", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left[\\left(-\\frac{1}{2} i \\, \\sqrt{3} - \\frac{3}{2}, 1\\right), \\left(\\frac{1}{2} i \\, \\sqrt{3} - \\frac{3}{2}, 1\\right), \\left(0, 1\\right)\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[\\left(-\\frac{1}{2} i \\, \\sqrt{3} - \\frac{3}{2}, 1\\right), \\left(\\frac{1}{2} i \\, \\sqrt{3} - \\frac{3}{2}, 1\\right), \\left(0, 1\\right)\\right]$" ], "text/plain": [ "[(-1/2*I*sqrt(3) - 3/2, 1), (1/2*I*sqrt(3) - 3/2, 1), (0, 1)]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Now we can see the roots of f_A in an appropriate way\n", "show( f_A.roots( SR ) )" ] }, { "cell_type": "code", "execution_count": 51, "id": "8ab2b66e-fece-4f8d-a292-0e1e80109a6a", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left[\\left(-\\frac{1}{2} i \\, \\sqrt{3} - \\frac{3}{2}, 1\\right), \\left(\\frac{1}{2} i \\, \\sqrt{3} - \\frac{3}{2}, 1\\right), \\left(0, 1\\right)\\right]\\)" ], "text/latex": [ "$\\displaystyle \\left[\\left(-\\frac{1}{2} i \\, \\sqrt{3} - \\frac{3}{2}, 1\\right), \\left(\\frac{1}{2} i \\, \\sqrt{3} - \\frac{3}{2}, 1\\right), \\left(0, 1\\right)\\right]$" ], "text/plain": [ "[(-1/2*I*sqrt(3) - 3/2, 1), (1/2*I*sqrt(3) - 3/2, 1), (0, 1)]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Another method to do so:\n", "P_A = f_A.change_ring(SR)\n", "show( P_A.roots() )" ] }, { "cell_type": "code", "execution_count": 52, "id": "de858b74-61db-4df4-a409-d9718af3f665", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/html": [ "\\(\\displaystyle \\left(\\begin{array}{rrr}\n", "-\\frac{1}{2} i \\, \\sqrt{3} - \\frac{3}{2} & 0 & 0 \\\\\n", "0 & \\frac{1}{2} i \\, \\sqrt{3} - \\frac{3}{2} & 0 \\\\\n", "0 & 0 & 0\n", "\\end{array}\\right) \\left(\\begin{array}{rrr}\n", "1 & 1 & 1 \\\\\n", "-\\frac{1}{2} i \\, \\sqrt{3} - \\frac{1}{2} & \\frac{1}{2} i \\, \\sqrt{3} - \\frac{1}{2} & 1 \\\\\n", "\\frac{1}{2} i \\, \\sqrt{3} - \\frac{1}{2} & -\\frac{1}{2} i \\, \\sqrt{3} - \\frac{1}{2} & 1\n", "\\end{array}\\right)\\)" ], "text/latex": [ "$\\displaystyle \\left(\\begin{array}{rrr}\n", "-\\frac{1}{2} i \\, \\sqrt{3} - \\frac{3}{2} & 0 & 0 \\\\\n", "0 & \\frac{1}{2} i \\, \\sqrt{3} - \\frac{3}{2} & 0 \\\\\n", "0 & 0 & 0\n", "\\end{array}\\right) \\left(\\begin{array}{rrr}\n", "1 & 1 & 1 \\\\\n", "-\\frac{1}{2} i \\, \\sqrt{3} - \\frac{1}{2} & \\frac{1}{2} i \\, \\sqrt{3} - \\frac{1}{2} & 1 \\\\\n", "\\frac{1}{2} i \\, \\sqrt{3} - \\frac{1}{2} & -\\frac{1}{2} i \\, \\sqrt{3} - \\frac{1}{2} & 1\n", "\\end{array}\\right)$" ], "text/plain": [ "[-1/2*I*sqrt(3) - 3/2 0 0]\n", "[ 0 1/2*I*sqrt(3) - 3/2 0]\n", "[ 0 0 0] [ 1 1 1]\n", "[-1/2*I*sqrt(3) - 1/2 1/2*I*sqrt(3) - 1/2 1]\n", "[ 1/2*I*sqrt(3) - 1/2 -1/2*I*sqrt(3) - 1/2 1]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# In fact, we can change the base rinf of A and use the same methods as earlier\n", "B = A.change_ring(SR)\n", "D, P = B.eigenmatrix_right() \n", "show( D, P )" ] }, { "cell_type": "code", "execution_count": 53, "id": "3a5201ca-aa91-43e2-b50f-3f6c86a1b317", "metadata": { "tags": [] }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We check that B is indeed diagonalisable over QQbar \n", "# (or over SR, according to Sage)\n", "B*P == P*D" ] }, { "cell_type": "markdown", "id": "e518c021-1a6e-41ad-9d18-5d0298c1de40", "metadata": { "tags": [] }, "source": [ "### Exercises" ] }, { "cell_type": "markdown", "id": "885149da-93ad-4045-82fe-4de6a3694418", "metadata": {}, "source": [ "**Exercise 1.** Using the matrix \n", "$$ A = \\left(\\begin{array}{rrr}\n", "2 & -3 & 1 \\\\\n", "1 & -2 & 1 \\\\\n", "1 & -3 & 2\n", "\\end{array}\\right)\n", "$$ \n", "as an example, write a piece of `Sage` code that constructs, from the list of eigenvalues of $ A $, a basis of each eigenspace. \n", "\n", "*Indication:* Compare this to what was done for Example 1 in the paragraph about Diagonalisation. The difficulty is that now we have an eigenvalue of algebraic multiplicity equal to $ 2 $." ] }, { "cell_type": "markdown", "id": "0c98d606-6b72-4af1-bdaf-05a0755228ca", "metadata": { "tags": [] }, "source": [ "**Exercise 2.** Give an example of a $ 2 \\times 2 $ matrix with rational entries and that is diagonalisable over $ \\mathbb{ R } $ but not over $ \\mathbb{ Q } $." ] }, { "cell_type": "markdown", "id": "c395b31f-ad90-48d8-bebd-1b72434c5f5b", "metadata": {}, "source": [ "## Projects" ] }, { "cell_type": "markdown", "id": "35598489-fa7b-4d46-8fe4-d81e3d0235d6", "metadata": { "tags": [] }, "source": [ "### Complement of a subspace and adapted bases" ] }, { "cell_type": "markdown", "id": "b8a13665-3bbe-4a42-ade7-33b8d3a5f15c", "metadata": {}, "source": [ "In this project, you are asked to write a `Sage` or `Python` program that:\n", "1. Asks the user to input an integer $ n $ and family of vectors in the vector space $ E = \\mathbb{Q}^n $.\n", "1. Extracts from this family a basis of the subspace $ F $ generated by these vectors.\n", "1. Complete this basis to a basis of $ \\mathbb{ Q }^n $ and extract from it a basis of an explicit complement of $ F $ in $ \\mathbb{ Q }^n $." ] }, { "cell_type": "markdown", "id": "b4b7cd12-36c3-4a5e-95dd-172b78a3d35e", "metadata": { "tags": [] }, "source": [ "### Diagonalisability" ] }, { "cell_type": "markdown", "id": "0c3cb947-f882-4a54-99d3-559f2b5188bb", "metadata": {}, "source": [ "In this project, you are asked to build on Exercise 1 of the Section about Matrices of linear transformations and write a program that:\n", "1. Asks the user to input a square matrix $ A $.\n", "1. Returns a small explanatory paragraph saying what the eigenvalues of $ A $ are, with their respective algebraic and geometric multiplicities, and saying whether $ A $ is diagonalisable (by applyting the theorem recalled in these notes)\n", "1. In case $ A $ is diagonalisable, returns matrices $ D $ and $ P $ such that $ A P = P D $.\n", "1. In case $ A $ is not diagonalisable, lets the user know if $ A $ is diagonalisable over an extension of the base field." ] } ], "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 }, "nbformat": 4, "nbformat_minor": 5 }