{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Algorithme de réduction des matrices\n", "\n", "## Algorithmes de Gauss et de Smith" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 1-Matrices en Sage" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En Sage, on définit des matrices comme suit:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "A = matrix(QQ, 2,3, [1,2,3,4,5,6])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "ou comme suit:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "B = matrix(ZZ, [[1,2,3],[4,5,6]])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ou encore:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 0 1/8]\n", "[ 1/13 3/56]\n", "[ 2/49 5/152]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A=matrix(QQ,3,[i/(2*i^2+6) for i in range(18) if i%3==0]); A" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "A = matrix(QQ, 2,3, [1,2,3,4,5,6])" ] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On obtient la taille d'une matrice comme suit:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(2, 3)" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ " A.nrows(),A.ncols()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le test d'égalité marche..." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A==B" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Définir quelques matrices spéciales:" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1 0 0 0 0]\n", "[0 1 0 0 0]\n", "[0 0 1 0 0]\n", "[0 0 0 1 0]\n", "[0 0 0 0 1]" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "identity_matrix(5)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0 0 0]\n", "[0 0 0]\n", "[0 0 0]\n", "[0 0 0]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "matrix(QQ,4,3,0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Par blocs..." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1 2 3|0 0 0]\n", "[4 5 6|0 0 0]\n", "[-----+-----]\n", "[0 0 0|1 2 3]\n", "[0 0 0|4 5 6]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E = block_matrix([[A,0],[0,B]]); E" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "C=matrix(QQ,0,0,0)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1 2 3|0 0 0]\n", "[4 5 6|0 0 0]\n", "[-----+-----]\n", "[0 0 0|1 2 3]\n", "[0 0 0|4 5 6]" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "block_matrix([[A,0],[0,B]])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour extraire des sous-matrices:" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[3]\n", "[6]" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.matrix_from_rows_and_columns([0,1],[2])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 2-Pivot de Gauss" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour échelonner une matrice (en lignes), Sage a une fonction déjà codée:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "C=A.echelon_form()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Attention: le résultat que l'on obtient est une matrice immuable: on ne peut pas changer ses valeurs." ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "ename": "ValueError", "evalue": "matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M).", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mValueError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mC\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mInteger\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mInteger\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mInteger\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;32m/ext/sage/sage-8.4_1804/local/lib/python2.7/site-packages/sage/matrix/matrix0.pyx\u001b[0m in \u001b[0;36msage.matrix.matrix0.Matrix.__setitem__ (build/cythonized/sage/matrix/matrix0.c:8401)\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1372\u001b[0m \u001b[0;31m# If the matrix is immutable, check_mutability will raise an\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1373\u001b[0m \u001b[0;31m# exception.\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1374\u001b[0;31m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcheck_mutability\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 1375\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1376\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mtype\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mkey\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0mtuple\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m/ext/sage/sage-8.4_1804/local/lib/python2.7/site-packages/sage/matrix/matrix0.pyx\u001b[0m in \u001b[0;36msage.matrix.matrix0.Matrix.check_mutability (build/cythonized/sage/matrix/matrix0.c:5331)\u001b[0;34m()\u001b[0m\n\u001b[1;32m 382\u001b[0m \"\"\"\n\u001b[1;32m 383\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_is_immutable\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 384\u001b[0;31m \u001b[0;32mraise\u001b[0m \u001b[0mValueError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M).\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 385\u001b[0m \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 386\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_cache\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mValueError\u001b[0m: matrix is immutable; please change a copy instead (i.e., use copy(M) to change a copy of M)." ] } ], "source": [ "C[1,1]=3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Si l'on veut l'éditer, il faut en créer une copie:" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "C=copy(A.echelon_form())" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1 0 -1]\n", "[ 0 3 2]" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "C[1,1]=3; C" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On a déjà des fonctions codées pour les opérations sur les lignes et les colonnes:" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(\n", "[ 5 2 3] [13 17 21]\n", "[14 5 6], [ 4 5 6]\n", ")" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.with_added_multiple_of_column(0,1,2), B.with_added_multiple_of_row(0,1,3)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1 3 2]\n", "[4 6 5]" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.with_swapped_columns(1,2)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(\n", "[ 1 2 6] [ 1 2 3]\n", "[ 4 5 12], [12 15 18]\n", ")" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.with_rescaled_col(2,2),B.with_rescaled_row(1,3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction _echelon_form_ de Sage ne donne pas la matrice de passage... " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Soit $A\\in \\mathrm{M}_n(\\mathbf Q)$ une matrice. On a vu en cours qu'il est très utile de disposer de matrices inversibles $P$ et $Q$ telles que $PAQ$ soit \"diagonale\".\n", "Il y a une fonction prédéfinie dans Sage qui réduit selon les lignes et selon les colonnes et renvoie les matrices de passage: c'est la fonction _smith_form()_." ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(\n", " [ 1 -2 1]\n", "[1 0 0] [ 1 0] [ 0 1 -2]\n", "[0 1 0], [ 4/3 -1/3], [ 0 0 1]\n", ")" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.smith_form()\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Dans un premier temps, vous pouvez utiliser cette fonction. Vous pourrez la coder vous-même à la fin de la séance." ] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice 1**: Soient $u,v,w,z$ les vecteurs de $\\mathbf Q^{10}$ ci-dessous. \n", "\n", "a)Donner un système d'équations pour le sous-e.v. de $\\mathbf Q^{10}$ engendré par ces vecteurs" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [], "source": [ "u=vector(QQ, [1/i for i in primes_first_n(10)]); \n", "v=vector(QQ, [integer_floor(exp(2*i)) for i in range(10)])\n", "w=vector(QQ, [i for i in range(10)])\n", "z=vector(QQ, [1,0,4,12/5, 0,0,0,0,0,1/3])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " Pour trouver un système d'équations vérifiées par ces 4 vecteurs, on utilise la méthode présentée en td: on les met dans une matrice, on calcule le forme de Gauss et on lit le résultat dans la matrice de passage..." ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1/2 1 0 1]\n", "[ 1/3 7 1 0]\n", "[ 1/5 54 2 4]\n", "[ 1/7 403 3 12/5]\n", "[ 1/11 2980 4 0]\n", "[ 1/13 22026 5 0]\n", "[ 1/17 162754 6 0]\n", "[ 1/19 1202604 7 0]\n", "[ 1/23 8886110 8 0]\n", "[ 1/29 65659969 9 1/3]" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A=matrix (QQ,4,[u,v,w,z]); A=A.transpose(); A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " Pour une matrice à coefficients rationnels, la fonction Smith_form() calcule la forme de Gauss avec les matrices de passage." ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1 0 0 0]\n", "[0 1 0 0]\n", "[0 0 1 0]\n", "[0 0 0 1]\n", "[0 0 0 0]\n", "[0 0 0 0]\n", "[0 0 0 0]\n", "[0 0 0 0]\n", "[0 0 0 0]\n", "[0 0 0 0]" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "D,P,Q=A.smith_form(); D" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " On lit que $A$ est de rang 4: il faut donc trouver 10-4=6 équations. Les coefficients de ces équations sont dans les 6 dernières lignes de $P$." ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ -14540732/2489861 1853076/226351 16173065/2489861 -20896470/2489861 1 0 0 0 0 0]\n", "[ -165476498/2942563 470788065/5885126 11716730/226351 -369827885/5885126 0 1 0 0 0 0]\n", "[ -1663854324/3847967 2368317918/3847967 1490407875/3847967 -1790740490/3847967 0 0 1 0 0 0]\n", "[ -13829929270/4300669 39368345559/8601338 12333896350/4300669 -29588046775/8601338 0 0 0 1 0 0]\n", "[ -123831141352/5206073 176245761021/5206073 110358778765/5206073 -132334989045/5206073 0 0 0 0 1 0]\n", "[-3461625677987/19692537 3284549679853/13128358 2056450143305/13128358 -7397568121685/39385074 0 0 0 0 0 1]" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E=P.matrix_from_rows(range(4,10));E" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [], "source": [ "R = PolynomialRing(QQ,10,\"x\") # On définit un anneau où peut vivre l'équation; ici un anneau de polynômes à 10 indéterminées." ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [], "source": [ "v=vector(R.gens())\n" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(-14540732/2489861*x0 + 1853076/226351*x1 + 16173065/2489861*x2 - 20896470/2489861*x3 + x4, -165476498/2942563*x0 + 470788065/5885126*x1 + 11716730/226351*x2 - 369827885/5885126*x3 + x5, -1663854324/3847967*x0 + 2368317918/3847967*x1 + 1490407875/3847967*x2 - 1790740490/3847967*x3 + x6, -13829929270/4300669*x0 + 39368345559/8601338*x1 + 12333896350/4300669*x2 - 29588046775/8601338*x3 + x7, -123831141352/5206073*x0 + 176245761021/5206073*x1 + 110358778765/5206073*x2 - 132334989045/5206073*x3 + x8, -3461625677987/19692537*x0 + 3284549679853/13128358*x1 + 2056450143305/13128358*x2 - 7397568121685/39385074*x3 + x9)" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E*v" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " On vérifie notre résultat:" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0 0 0 0]\n", "[0 0 0 0]\n", "[0 0 0 0]\n", "[0 0 0 0]\n", "[0 0 0 0]\n", "[0 0 0 0]" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E*A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "b) Donner une base de l'intersection de l'ev précédent avec l'hyperplan $\\sum_{i=0}^{10}x_i=0$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " On rajoute cette équation aux précédentes (celles de E) dans une matrice $E_1$" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1 1 1 1 1 1 1 1 1 1]" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "W=matrix(QQ,1,10,[1 for i in range(10)]); W" ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ -14540732/2489861 1853076/226351 16173065/2489861 -20896470/2489861 1 0 0 0 0 0]\n", "[ -165476498/2942563 470788065/5885126 11716730/226351 -369827885/5885126 0 1 0 0 0 0]\n", "[ -1663854324/3847967 2368317918/3847967 1490407875/3847967 -1790740490/3847967 0 0 1 0 0 0]\n", "[ -13829929270/4300669 39368345559/8601338 12333896350/4300669 -29588046775/8601338 0 0 0 1 0 0]\n", "[ -123831141352/5206073 176245761021/5206073 110358778765/5206073 -132334989045/5206073 0 0 0 0 1 0]\n", "[-3461625677987/19692537 3284549679853/13128358 2056450143305/13128358 -7397568121685/39385074 0 0 0 0 0 1]\n", "[-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------]\n", "[ 1 1 1 1 1 1 1 1 1 1]" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E1=block_matrix([[E],[W]]); E1" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1 0 0 0 0 0 0 0 0 0]\n", "[0 1 0 0 0 0 0 0 0 0]\n", "[0 0 1 0 0 0 0 0 0 0]\n", "[0 0 0 1 0 0 0 0 0 0]\n", "[0 0 0 0 1 0 0 0 0 0]\n", "[0 0 0 0 0 1 0 0 0 0]\n", "[0 0 0 0 0 0 1 0 0 0]" ] }, "execution_count": 53, "metadata": {}, "output_type": "execute_result" } ], "source": [ "D1,P1,Q1=E1.smith_form(); D1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " $E_1$ est de rang 7, donc l'équation rajoutée n'est pas combinaison linéaire des précédentes (ce n'est pas très surprenant: les vecteurs de départ ne vérifiaient pas cette équation!).\n", "On cherche une base du noyau de $E_1$ qui est donc de dim 3. D'après le td, on lit cette base dans les colonnes de $Q1$." ] }, { "cell_type": "code", "execution_count": 58, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 10774990831690184602/201553337623442969 -10709682305025391055/201553337623442969 1286012357552269839/201553337623442969]\n", "[ 10691286913739471132/201553337623442969 -20926126695497667015/403106675246885938 1284222222123060220/201553337623442969]\n", "[-81476944788163596754/1007766688117214845 77532260430425031699/1007766688117214845 -10107236505151251636/1007766688117214845]\n", "[-47165328240597998566/1007766688117214845 90179913424679745997/2015533376234429690 -5893910286899785824/1007766688117214845]\n", "[ 2078600530538451510/201553337623442969 -1924575236886685238/201553337623442969 234069520990108440/201553337623442969]\n", "[ 1396739956223422789/201553337623442969 -1226677828047530487/201553337623442969 147869494256759352/201553337623442969]\n", "[ 585283035937346062/201553337623442969 -401998048467983621/201553337623442969 46502425864566672/201553337623442969]\n", "[ 1 0 0]\n", "[ 0 1 0]\n", "[ 0 0 1]" ] }, "execution_count": 58, "metadata": {}, "output_type": "execute_result" } ], "source": [ "B=Q1.matrix_from_columns(range(7,10)); B" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ces 3 colonnes forment une base du noyau de $E_1$. Vérifions le:" ] }, { "cell_type": "code", "execution_count": 59, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0 0 0]\n", "[0 0 0]\n", "[0 0 0]\n", "[0 0 0]\n", "[0 0 0]\n", "[0 0 0]\n", "[-----]\n", "[0 0 0]" ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "E1*B" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3-Réduction des matrices entières" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice 2:** Soit $A$ la matrice entière suivante. " ] }, { "cell_type": "code", "execution_count": 96, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[2 4 0]\n", "[0 3 6]\n", "[6 0 5]" ] }, "execution_count": 96, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A=matrix(ZZ,[[2,4,0],[0,3,6],[6,0,5]]); A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**a)** Appliquez lui pas à pas, en utilisant les fonctions prédéfinies, les suites d'opérations élémentaires comme dans l'algorithme présenté en cours." ] }, { "cell_type": "code", "execution_count": 97, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 2 1 -6]\n", "[ 0 3 6]\n", "[ 6 0 5]" ] }, "execution_count": 97, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.add_multiple_of_row(0,1,-1); A" ] }, { "cell_type": "code", "execution_count": 98, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1 2 -6]\n", "[ 3 0 6]\n", "[ 0 6 5]" ] }, "execution_count": 98, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.swap_columns(0,1);A" ] }, { "cell_type": "code", "execution_count": 99, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1 0 -6]\n", "[ 3 -6 6]\n", "[ 0 6 5]" ] }, "execution_count": 99, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.add_multiple_of_column(1,0,-2); A" ] }, { "cell_type": "code", "execution_count": 100, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1 0 0]\n", "[ 3 -6 24]\n", "[ 0 6 5]" ] }, "execution_count": 100, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.add_multiple_of_column(2,0,6); A" ] }, { "cell_type": "code", "execution_count": 101, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1 0 0]\n", "[ 0 -6 24]\n", "[ 0 6 5]" ] }, "execution_count": 101, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.add_multiple_of_row(1,0,-3); A" ] }, { "cell_type": "code", "execution_count": 102, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1 0 0]\n", "[ 0 -36 -1]\n", "[ 0 6 5]" ] }, "execution_count": 102, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.add_multiple_of_row(1,2,-5);A" ] }, { "cell_type": "code", "execution_count": 103, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1 0 0]\n", "[ 0 -1 -36]\n", "[ 0 5 6]" ] }, "execution_count": 103, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.swap_columns(2,1); A" ] }, { "cell_type": "code", "execution_count": 104, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1 0 0]\n", "[ 0 -1 0]\n", "[ 0 5 -174]" ] }, "execution_count": 104, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.add_multiple_of_column(2,1,-36); A" ] }, { "cell_type": "code", "execution_count": 105, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1 0 0]\n", "[ 0 -1 0]\n", "[ 0 0 -174]" ] }, "execution_count": 105, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A.add_multiple_of_row(2,1,5); A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " C'est bon: A est sous la forme d'une matrice diagonale. On vérifie que Sage est d'accord avec nous..." ] }, { "cell_type": "code", "execution_count": 116, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(\n", "[ 1 0 0] [ 0 0 1] [ 1 0 5]\n", "[ 0 1 0] [ 1 -1 -10] [ 2 1 -46]\n", "[ 0 0 174], [ 3 -4 -30], [ -1 0 -6]\n", ")" ] }, "execution_count": 116, "metadata": {}, "output_type": "execute_result" } ], "source": [ "matrix(ZZ,[[2,4,0],[0,3,6],[6,0,5]]).smith_form()\n" ] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**N.B.** En sage, l'algorithme présenté en cours est aussi codé dans la fonction _smith_form_ lorsqu'on l'utilise sur une matrice à coefficients entiers." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**b)** A quelle conditions sur les entiers $a,b,c$ existe-t-il des entiers $x,y,z$ tels que l'on ait \n", "$A \\begin{bmatrix} x\\cr y\\cr z \\end{bmatrix}= \\begin{bmatrix} a \\cr b\\cr c \\end{bmatrix} $?\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " On cherche les \"équations\" de l'image. On les trouve toujours grâce à la matrice de passage \"P\" dans la forme de Smith. Plutôt que d'utiliser celle que me fournit Smith_form(), je récupère la \"mienne\" en faisant sur la matrice identité les mêmes opérations sur les lignes." ] }, { "cell_type": "code", "execution_count": 117, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1 -1 0]\n", "[ -3 4 -5]\n", "[-15 20 -24]" ] }, "execution_count": 117, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P=identity_matrix(3); P.add_multiple_of_row(0,1,-1);P.add_multiple_of_row(1,0,-3);P.add_multiple_of_row(1,2,-5); P.add_multiple_of_row(2,1,5);P" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On trouve l'équation $$ -15x+20y-24z \\equiv 0 [174].$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " **N.B.:** En utilisant la matrice de Sage, on touverait plutôt l'équation $$3x-4y-30z \\equiv 0[174] .$$ Qui a tort, qui a raison? Les deux, bien entendu: en multipliant cette de Sage par -5 (qui est inversible dans $ \\mathbf Z/174 \\mathbf Z$) on trouve la mienne ($5\\times 30=150 \\equiv-24[174]$)." ] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice 3** a)Exhiber une matrice $P$ inversible dans $\\mathrm{M}_n(\\mathbb{Z})$ vérifiant \n", "$\\left(\\begin{array}{rrrr} 24 & 18 & 12 & 15 \\end{array}\\right)P=\\left(\\begin{array}{rrrr} d & 0 & 0 & 0 \\end{array}\\right)$ pour un entier $d$ convenable." ] }, { "cell_type": "code", "execution_count": 122, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(\n", " [-2 -5 -2 -3]\n", " [ 2 5 2 4]\n", " [ 0 0 1 0]\n", "[3 0 0 0], [ 1 2 0 0]\n", ")" ] }, "execution_count": 122, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A=matrix(ZZ,1,[24,18,12,15]); D,Q,P=A.smith_form(); D,P" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " Donc $d=3$, et $P$ est la matrice ci-dessus." ] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "b)En déduire une $\\mathbf Z$-base du noyau de l'application $\\mathbf Z^4 \\to \\mathbf Z$, $(x,y,z,t) \\mapsto 24x +18y+12z+15t$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " Elles se lit dans les colonnes de $P$. Ce sont les 3 dernières colonnes de cette matrice." ] }, { "cell_type": "code", "execution_count": 141, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[-5 -2 -3]\n", "[ 5 2 4]\n", "[ 0 1 0]\n", "[ 2 0 0]" ] }, "execution_count": 141, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P1=P.matrix_from_columns(range(1,4)); P1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "c)Puis un repère affine des solutions entières de l'équation $24x +18y+12z+15t=9$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " Les solutions s'obtiennent en ajoutant une solution particulière à la solution générale de l'équation homogène trouvée à la question précédente. On trouve une solution particulière à partir d'une solution particulière de $3x+0y+0z+0t=9$, à savoir (3,0,0,0)." ] }, { "cell_type": "code", "execution_count": 132, "metadata": {}, "outputs": [], "source": [ "a=vector([3,0,0,0])" ] }, { "cell_type": "code", "execution_count": 137, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 8 6 4 5]\n", "[-4 -3 -2 -2]\n", "[ 0 0 1 0]\n", "[ 1 1 0 0]" ] }, "execution_count": 137, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.inverse()" ] }, { "cell_type": "code", "execution_count": 138, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(-6, 6, 0, 3)" ] }, "execution_count": 138, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a0=P*a; a0" ] }, { "cell_type": "code", "execution_count": 139, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "9" ] }, "execution_count": 139, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a0*vector([24,18,12,15])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La solution générale est donc de la forme:" ] }, { "cell_type": "code", "execution_count": 142, "metadata": {}, "outputs": [], "source": [ "R.=PolynomialRing(QQ)" ] }, { "cell_type": "code", "execution_count": 143, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(-5*u - 2*v - 3*w - 6, 5*u + 2*v + 4*w + 6, v, 2*u + 3)" ] }, "execution_count": 143, "metadata": {}, "output_type": "execute_result" } ], "source": [ "vector(a0)+P1*vector([u,v,w])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice 4** (examen 2017) Donner une base du groupe abélien formé des éléments de $\\mathbf{Z}^5$\n", " qui sont combinaisons linéaires à *coefficients rationnels* des deux vecteurs $(1,2,3,4,5)$ et $(6,7,8,9,10)$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " Comme d'habitude, on résout cette question en se ramenant au cas d'une matrice diagonale en utilisant Smith." ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "([1, 2, 3, 4, 5], [6, 7, 8, 9, 10])" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "u=range(1,6); v=range(6,11); u,v\n" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ 1 6]\n", "[ 2 7]\n", "[ 3 8]\n", "[ 4 9]\n", "[ 5 10]" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A=matrix(ZZ,2,[u,v]); A=A.transpose(); A" ] }, { "cell_type": "code", "execution_count": 0, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(\n", "[1 0] [ 0 0 0 4 -3] \n", "[0 5] [ 0 0 0 -5 4] \n", "[0 0] [ 1 0 0 -4 3] \n", "[0 0] [ 0 1 0 -3 2] [ 1 6]\n", "[0 0], [ 0 0 1 -2 1], [ 0 -1]\n", ")" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "d,p,q=A.smith_form(); d,p,q" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " Pour la matrice d, une base de l'image entière est $e_1$ et $5e_2$) (où $e_i$ est le ième vecteur de la base canonique).\n", "Les cominaisons rationnelles qui restent entières sont les combinaisons linéaires entières de $e_1$ et $e_2$.\n", "Comme $\\mathrm{Im}\\ A=P^{-1} \\mathrm{Im}\\ d$, on en déduit qu'une base entière est formée des 2 premières colonnes de $P^{-1}$." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1 0]\n", "[2 1]\n", "[3 2]\n", "[4 3]\n", "[5 4]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(p.inverse()).matrix_from_columns([0,1])\n" ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 8.9", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.15" } }, "nbformat": 4, "nbformat_minor": 1 }