{
"cells": [
{
"cell_type": "markdown",
"id": "82993029",
"metadata": {},
"source": [
"# Algèbre linéaire avec SageMath"
]
},
{
"cell_type": "markdown",
"id": "3363318b",
"metadata": {},
"source": [
"**Consigne :** lire le sujet dans l'ordre et **exécuter chaque cellule de code pré-remplie** pour observer le résultat avant de continuer."
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "cf1a0f05-428d-4b18-ba84-414a7cc45895",
"metadata": {},
"outputs": [],
"source": [
"%display latex # mise en forme plus lisible"
]
},
{
"cell_type": "markdown",
"id": "9386b979",
"metadata": {},
"source": [
"## 1. Construire des matrices et des vecteurs"
]
},
{
"cell_type": "markdown",
"id": "9cc54f07-84db-4092-9014-ee6f1466584d",
"metadata": {},
"source": [
"Dans SageMath, la construction d'une matrice se fait avec la commande `matrix`, à partir d'une liste de listes et en indiquant le corps (ou anneau) des coefficients, et les dimensions (nombre de lignes puis de colonnes). Par exemple :"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "ae668afc",
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\\(\\displaystyle \\left(\\begin{array}{rrrr}\n",
"1 & 2 & 3 & 4 \\\\\n",
"5 & 6 & 7 & 8 \\\\\n",
"9 & 10 & 11 & 12\n",
"\\end{array}\\right)\\)"
],
"text/latex": [
"$\\displaystyle \\left(\\begin{array}{rrrr}\n",
"1 & 2 & 3 & 4 \\\\\n",
"5 & 6 & 7 & 8 \\\\\n",
"9 & 10 & 11 & 12\n",
"\\end{array}\\right)$"
],
"text/plain": [
"[ 1 2 3 4]\n",
"[ 5 6 7 8]\n",
"[ 9 10 11 12]"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"M = matrix(QQ, 3, 4, [[1,2,3,4],[5,6,7,8],[9,10,11,12]])\n",
"M"
]
},
{
"cell_type": "markdown",
"id": "8a2b3ab8",
"metadata": {},
"source": [
"On peut également *oublier* certains arguments et laisser SageMath compléter :\n",
"- si on n'indique pas le type des coefficients, il va essayer de l'inférer (par exemple `ZZ` si tous les coefficients sont entiers) ;\n",
"- si on donne les dimensions, on peut fournir une liste plutôt qu'une liste de liste, et SageMath remplit la matrice ligne par ligne ;\n",
"- inversement, on peut ne pas donner les dimensions si on fournit une liste de listes."
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "dbd4813a",
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\\(\\displaystyle \\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\mathrm{True}, \\Bold{Z}, \\Bold{Q}\\right)\\)"
],
"text/latex": [
"$\\displaystyle \\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\mathrm{True}, \\Bold{Z}, \\Bold{Q}\\right)$"
],
"text/plain": [
"(True, Integer Ring, Rational Field)"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"M1 = matrix(QQ, 3, 4, [1,2,3,4,5,6,7,8,9,10,11,12])\n",
"M2 = matrix(QQ, [[1,2,3,4],[5,6,7,8],[9,10,11,12]])\n",
"M3 = matrix([[1,2,3,4],[5,6,7,8],[9,10,11,12]])\n",
"M1 == M2 == M, M3.base_ring(), M.base_ring() # base_ring renvoie l'anneau de base"
]
},
{
"cell_type": "markdown",
"id": "59835d70",
"metadata": {},
"source": [
"De manière similaire, on peut créer des vecteurs grâce à `vector`. **Remarque.** les vecteurs de SageMath ne sont ni des « vecteurs lignes » ni des « vecteurs colonnes », leur direction est choisie en fonction des opérations qui sont faites. Pour l'affichage, ils sont en ligne."
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "dfe9b53c",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(1, 2, 3, 4)\n"
]
},
{
"data": {
"text/html": [
"\\(\\displaystyle \\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\mathrm{True}, \\Bold{Q}, \\Bold{Z}\\right)\\)"
],
"text/latex": [
"$\\displaystyle \\newcommand{\\Bold}[1]{\\mathbf{#1}}\\left(\\mathrm{True}, \\Bold{Q}, \\Bold{Z}\\right)$"
],
"text/plain": [
"(True, Rational Field, Integer Ring)"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"v = vector(QQ, 4, [1,2,3,4])\n",
"v1 = vector(QQ, [1,2,3,4])\n",
"v3 = vector([1,2,3,4])\n",
"print(v)\n",
"v == v1, v.base_ring(), v3.base_ring()"
]
},
{
"cell_type": "markdown",
"id": "5a55755c-6ca8-4bc3-8e4c-3f72ac877ae6",
"metadata": {},
"source": [
"On peut multiplier une matrice par un vecteur, si les dimensions sont compatibles."
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "f622fa8c-281b-4cb0-8c36-55a95adbbb4e",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(3, 4) 4\n"
]
},
{
"data": {
"text/html": [
"\\(\\displaystyle \\left(30,\\,70,\\,110\\right)\\)"
],
"text/latex": [
"$\\displaystyle \\left(30,\\,70,\\,110\\right)$"
],
"text/plain": [
"(30, 70, 110)"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"print(M.dimensions(), len(v)) # dimensions d'une matrice et d'un vecteur\n",
"M*v"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "536d8f56-21e6-4d57-b935-0b311da34d05",
"metadata": {},
"outputs": [
{
"ename": "TypeError",
"evalue": "unsupported operand parent(s) for *: 'Vector space of dimension 4 over Rational Field' and 'Full MatrixSpace of 3 by 4 dense matrices over Rational Field'",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)",
"Cell \u001b[0;32mIn[14], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[43mv\u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43mM\u001b[49m \u001b[38;5;66;03m# BOOM\u001b[39;00m\n",
"File \u001b[0;32m/private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.8/lib/python3.11/site-packages/sage/structure/element.pyx:3676\u001b[0m, in \u001b[0;36msage.structure.element.Vector.__mul__ (build/cythonized/sage/structure/element.c:33159)\u001b[0;34m()\u001b[0m\n\u001b[1;32m 3674\u001b[0m if have_same_parent(left, right):\n\u001b[1;32m 3675\u001b[0m return (left)._dot_product_(right)\n\u001b[0;32m-> 3676\u001b[0m return coercion_model.bin_op(left, right, mul)\n\u001b[1;32m 3677\u001b[0m \n\u001b[1;32m 3678\u001b[0m cpdef _dot_product_(Vector left, Vector right) noexcept:\n",
"File \u001b[0;32m/private/var/tmp/sage-10.3-current/local/var/lib/sage/venv-python3.11.8/lib/python3.11/site-packages/sage/structure/coerce.pyx:1278\u001b[0m, in \u001b[0;36msage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:16857)\u001b[0;34m()\u001b[0m\n\u001b[1;32m 1276\u001b[0m # We should really include the underlying error.\n\u001b[1;32m 1277\u001b[0m # This causes so much headache.\n\u001b[0;32m-> 1278\u001b[0m raise bin_op_exception(op, x, y)\n\u001b[1;32m 1279\u001b[0m \n\u001b[1;32m 1280\u001b[0m cpdef canonical_coercion(self, x, y) noexcept:\n",
"\u001b[0;31mTypeError\u001b[0m: unsupported operand parent(s) for *: 'Vector space of dimension 4 over Rational Field' and 'Full MatrixSpace of 3 by 4 dense matrices over Rational Field'"
]
}
],
"source": [
"v*M # BOOM"
]
},
{
"cell_type": "markdown",
"id": "27e86149",
"metadata": {},
"source": [
"**Exercice 1.**\n",
"\n",
"1. Construire la matrice $A$ et le vecteur $b$, à coefficients dans $ℚ$, associés au système \n",
" $$\\begin{cases}\n",
" \\phantom{1}x + 2y + 3z = 1\\\\\n",
" 4x + 5y + 6z = 1\\\\\n",
" 7x + 8y + 9z = 1\n",
" \\end{cases}$$\n",
"1. Vérifier que le vecteur $(9,-19,10)$ est solution du système.\n",
"1. Construire la matrice $A_{13}$ et le vecteur $v_{13}$, à coefficients dans $ℤ/13ℤ$, associés au même système.\n",
"1. Déduire un vecteur solution de la question **2.** et vérifier."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e22d0b7e-f98b-4670-98c1-6200b4fc35f0",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "0f7e79b8-b394-4dad-8f86-7e40821e673c",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "f8ac4117-9336-4c9e-8898-1cb489c65549",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "ae6f8158",
"metadata": {},
"source": [
"## 2. Algorithme de Gauss"
]
},
{
"cell_type": "markdown",
"id": "2ba7a67e-b840-4277-8ff1-824cd4955504",
"metadata": {},
"source": [
"SageMath fournit les fonctions suivantes de manipulation des matrices. _**Attention.** les indices de lignes et colonnes commencent à $0$, pas à $1$ !_"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2c023caf",
"metadata": {},
"outputs": [],
"source": [
"M = matrix(QQ, 3, 4, [[1,2,3,4],[5,6,7,8],[9,10,11,12]])\n",
"print(\"Avant :\")\n",
"pretty_print(M) # Affichage agréable (variante de print)\n",
"\n",
"M.add_multiple_of_row(1, 0, -5) # ajoute -5 fois la ligne 0 à la ligne 1 → modifie M et ne renvoie rien !\n",
"\n",
"print(\"Pendant :\")\n",
"pretty_print(M)\n",
"\n",
"M.swap_rows(0,2) # échange les lignes 0 et 2 → modifie M et ne renvoie rien !\n",
"\n",
"print(\"Après :\")\n",
"M"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7d80253b-5f8d-4cd1-8ce6-c41c5af1255f",
"metadata": {},
"outputs": [],
"source": [
"M = matrix(QQ, 3, 4, [[1,2,3,4],[5,6,7,8],[9,10,11,12]])\n",
"N = M.with_added_multiple_of_row(1, 0, -5) # Ajoute -5 fois la ligne 0 à la ligne 1 → ne modifie pas M\n",
"P = N.with_swapped_rows(0, 2) # échange les lignes 0 et 2 → ne modifie pas N\n",
"M, N, P"
]
},
{
"cell_type": "markdown",
"id": "0ff10570",
"metadata": {},
"source": [
"Pour appliquer l'algorithme de Gauss à un système défini par une matrice $A$ et un vecteur $b$, il faut construire la *matrice augmentée* $(A|b)$."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b86babf0",
"metadata": {},
"outputs": [],
"source": [
"M = matrix(QQ, 3, 4, [[1,2,3,4],[5,6,7,8],[9,10,11,12]])\n",
"v = vector(QQ, [1,1,1])\n",
"N = M.augment(v) # ne modifie pas M !\n",
"M, N"
]
},
{
"cell_type": "markdown",
"id": "c735b1ea",
"metadata": {},
"source": [
"**Exercice 2.**\n",
"1. Reprendre le système de la question précédente (dans $ℚ$), et en calculer « à la main » une forme échelonnée à l'aide de SageMath. *Afficher toutes les matrices intermédiaires.*\n",
"1. Même question pour le même système, vu cette fois dans $ℤ/13ℤ$.\n",
"1. Écrire l'algorithme de Gauss, qui prend en entrée $A$ et $b$, crée la matrice augmentée $M = (A|b)$, et renvoie $M$ sous forme échelonnée.\n",
"1. Vérifier le résultat de votre algorithme sur les deux exemples précédents, puis sur plusieurs matrices aléatoires (créées à l'aide de `random_matrix(QQ, m, n)` pour diverses valeurs de $m$ et $n$ – même des grandes !) et vecteurs aléatoires (`random_vector(QQ, m)`)."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6167d3b4-f7ae-4d74-9fa8-042b80c04053",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "2355bfe1-c356-4bc5-903d-f3b7827ed610",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "1347cd17-a2f2-4fd4-816e-117759553b95",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "aed7d7f7",
"metadata": {},
"source": [
"## 3. Algorithme de Gauss-Jordan"
]
},
{
"cell_type": "markdown",
"id": "faad0872-ece3-4f17-9a5d-259ad03733bb",
"metadata": {},
"source": [
"On peut multiplier la ligne $i$ d'une matrice $M$ par un coefficient $λ$ grâce à `M.rescale_row(i,λ)` (qui modifie $M$ et ne renvoie rien) ou `M.with_rescaled_row(i,λ)` (qui ne modifie pas $M$ et renvoie une nouvelle matrice)."
]
},
{
"cell_type": "markdown",
"id": "b24f805f-a6b3-4ded-b89a-0474fe3c84bb",
"metadata": {},
"source": [
"**Exercice 3.**\n",
"1. Reprendre les systèmes précédents, dans $ℚ$ puis dans $ℤ/13ℤ$, et calculer leurs formes échelonnées réduites « à la main », à partir de la forme échelonnée. *Afficher les résultats intermédiaires.*\n",
"1. Écrire l'algorithme de Gauss-Jordan de calcul de la forme échelonnée réduite d'un système.\n",
"1. Tester sur les deux matrices des systèmes déjà étudiés.\n",
"1. Tester sur diverses matrices aléatoires et comparer avec le résultat donné par SageMath quand on appelle `A.rref()` (pour *row reduced echelon form*). **Remarque.** Non on ne trouve pas le même résultat : expliquer la différence !"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "9da21311-58f8-4471-96a3-d8c41d79a632",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "26bfad92-37fd-4535-891c-773d5184c476",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "7304d093-86d0-4a5b-8219-3e4fbf10c4d5",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "d000f2f5-e7c3-4e6f-bd00-1ab9d531e46f",
"metadata": {},
"source": [
"## 4. Résolution de système"
]
},
{
"cell_type": "markdown",
"id": "1f19d7e5-67fd-4324-82f6-5b27bd8baf10",
"metadata": {},
"source": [
"**Exercice 4.**\n",
"1. Trouver « à la main » les solutions des deux systèmes (sur $ℚ$ et $ℤ/13ℤ$) qu'on étudie depuis le début.\n",
"1. Écrire un algorithme de résolution, qui prend en entrée $A$ et $b$ et calcule l'espace des solutions sous la forme d'une solution particulière $s$ (un vecteur) et d'une matrice $V$ telle que chaque colonne de $V$ corresponde à une variable libre.\n",
"1. Tester votre algorithme sur les deux systèmes qu'on a depuis le début. \n",
"1. Vérifier la correction de votre implantation à l'aide du test proposé ci-dessous."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "eee0e7d7",
"metadata": {},
"outputs": [],
"source": [
"def verif(A, b, s, V):\n",
" \"\"\"\n",
" Vérifie si les solutions du système A⋅x = b sont bien \n",
" s + λ1 v1 + … + λk vk \n",
" où les λi sont n'importe quelles constantes et les vi\n",
" sont les colonnes de V.\n",
" \n",
" Remarque : ne vérifie pas s'il manque des solutions !\n",
" \"\"\"\n",
" p = V.ncols()\n",
" K = A.base_ring()\n",
" for _ in range(20):\n",
" w = s + sum([K.random_element()*V.column(i) for i in range(p)])\n",
" if A*w != b: return False\n",
" return True"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c8a63a8f-aa5e-4d67-a567-7d633fd9ce31",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "0d0db92b-fad7-444c-a602-4dac0ce510e9",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"id": "a48568a5-f14c-41ba-aa01-6796ac56a531",
"metadata": {},
"source": [
"## 5. Quelques tests\n",
"\n",
"**Exercice 5.**\n",
"\n",
"1. Trouver des systèmes de $m$ équations à $n$ inconnues sur $ℚ$, avec les caractéristiques suivantes :\n",
" 1. $m < n$ et le système n'a aucune solution ;\n",
" 1. $m < n$ et le système a exactement une solution ;\n",
" 1. $m > n$ et le système a exactement une solution ;\n",
" 1. $m > n$ et le système a une infinité de solutions.\n",
"1. Dans chacun des cas de la question précédente, peut-on trouver un système avec les mêmes caractéristiques sur $ℤ/17ℤ$ ? Si ce n'est pas possible, comment doit-on modifier l'énoncé ?"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "262d05b9",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "07ed590e-9f98-44b8-a7f8-ada0cba2d0f4",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "a6bcf75f-edcb-4699-ab43-bedb4b045800",
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"id": "0cabe9b2-bac0-43b7-9836-8eec920829e7",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "SageMath 10.3",
"language": "sage",
"name": "sagemath-10.3"
},
"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.8"
}
},
"nbformat": 4,
"nbformat_minor": 5
}