{ "cells": [ { "cell_type": "markdown", "id": "453516c9", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "# Forme normale de Hermite" ] }, { "cell_type": "code", "execution_count": 0, "id": "9196c09f", "metadata": { "tags": [ "sujet" ] }, "outputs": [], "source": [ "%display latex" ] }, { "cell_type": "markdown", "id": "7dfbff7f", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "On s'intéresse dans ce TP à des matrices à coefficients entiers, et à un équivalent de la forme échelonnée d'une matrice dans ce cas. On rappelle que l'algorithme de Gauss calculant une forme échelonnée introduit des divisions, et donc sort de l'ensemble des entiers. Ici, on ne travaillera qu'avec des matrices à coefficients entiers. L'objectif général peut par exemple être de résoudre un système $A⋅x = b$ où $A∈ℤ^{m×n}$ et $b∈ℤ^m$, c'est-à-dire trouver s'il existe un $s∈ℤ^n$ tel que $A⋅s = b$ (ou tous les $s$, etc.)." ] }, { "cell_type": "markdown", "id": "930cb180", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "## Question 1\n", "\n", "On dit qu'une matrice $H∈ℤ^{m×n}$ est sous forme normale de Hermite si les conditions suivantes sont vérifiées :\n", "- les lignes nulles de $H$ sont ses dernières ;\n", "- le pivot (= élément non nul le plus à gauche) d'une ligne non nulle est strictement à droite du pivot de la ligne précédente ;\n", "- les pivots sont tous strictement positifs ;\n", "- les éléments au dessus d'un pivot sont positifs et strictement inférieur au pivot.\n", "\n", "1. Les deux matrices $M$ et $N$ suivantes sont-elles sous forme normale de Hermite ?\n", " $$M = \\begin{pmatrix}\n", " 2 & 4 & -3 & 0 \\\\\n", " 0 & 0 & 5 & 7 \\\\\n", " 0 & 0 & 0 & 8\n", " \\end{pmatrix}\\qquad\n", " N = \\begin{pmatrix}\n", " 7 & 2 & 4 & 0 \\\\\n", " 0 & 0 & 3 & -3 \\\\\n", " 0 & 0 & 0 & 8\n", " \\end{pmatrix}\n", " $$\n", " \n", "2. La méthode `hermite_form()` des matrices entières calcule la forme normale de Hermite. L'appliquer aux matrices $M$ et $N$ précédentes et observer le résultat." ] }, { "cell_type": "code", "execution_count": 0, "id": "87228b6a", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "94d6b7d2", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "## Question 2\n", "On va montrer l'existence de la forme normale de Hermite pour toute matrice entière, en décrivant un algorithme qui calcule cette forme normale. Comme pour l'algorithme de Gauss-Jordan, l'algorithme aura trois types d'opérations élémentaires :\n", "- multiplier une ligne par $-1$ ;\n", "- échanger deux lignes ;\n", "- ajouter un multiple *entier* d'une ligne à une autre.\n", "\n", "L'idée de l'algorithme est assez similaire à l'algorithme de Gauss, et résumée ci-dessous : on parcourt les colonnes ; dans chaque colonne, on trouve un pivot (non nul), qu'on prend ici minimal en valeur absolue ; par échange de lignes, on ramène ce pivot *en haut* de la matrice et on le rend positif si nécessaire ; on utilise ensuite le pivot pour que les autres éléments de la colonne soient positifs et inférieurs au pivot ; on passe à la colonne suivante.\n", "\n", "```\n", "0. i_min ← 0\n", "1. Pour j=0 à n-1 (parcours des colonnes) :\n", "2. Si M[i,j] = 0 pour i ≥ i_min, passer à la colonne suivante\n", "3. Pour i=i_min à m-1 : si nécessaire, multiplier la ligne i par -1 pour avoir M[i,j] ≥ 0\n", "4. Tant qu'il existe au moins 2 lignes i1, i2 ≥ i_min telles que 0 < M[i1,j] ≤ M[i2,j] :\n", "5. Ajouter un multiple* de la ligne i1 à la ligne i2, pour avoir 0 ≤ M[i2,j] < M[i1,j]\n", "6. Échanger la ligne i_min avec la seule ligne i ≥ i_min où M[i,j] ≠ 0\n", "7. Pour i=0 à i_min-1, si M[i,j] ≠ 0 :\n", "8. Ajouter un multiple de la ligne i_min à la ligne i pour avoir 0 ≤ M[i,j] < M[i_min,j]\n", "9. i_min ← i_min + 1\n", "```\n", "\n", "1. En ligne `5.`, il faut trouver le multiple à ajouter. Soit $a = M[i_1,j]$ et $b = M[i_2,j]$. Le but est de remplacer $b$ par $b\\bmod a$ (reste dans la division euclidienne de $b$ par $a$) : quel multiple de la ligne $i_{\\min}$ doit on ajouter à la ligne $i$ pour cela ?\n", "\n", "1. Même question pour la ligne 8. *Attention, en ligne 8, $M[i,j]$ peut être négatif. Vérifier, avec des tests, la valeur à utiliser dans ce cas là.*\n", "\n", "1. Appliquer l'algorithme sur la matrice \n", " $$\\begin{pmatrix}\n", " 2 & -3 & 5\\\\\n", " 7 & -6 & 8\n", " \\end{pmatrix}.$$\n", "1. Vérifier le résultat obtenu avec la méthode `hermite_form()`.\n", "1. Implanter l'algorithme décrit, et vérifier avec `hermite_form()`. *Tester sur des matrices aléatoires de taille $10×10$ à coefficients dans $ℤ$." ] }, { "cell_type": "code", "execution_count": 0, "id": "dc646d70", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "6b424b00", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "2b88a771", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "583d62a9", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "e681b710", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "586a0b6b", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "\n", "\n", "## Question 3\n", "\n", "1. Puisqu'on n'effectue que des opérations élémentaires, il existe une matrice $U$ inversible telle que $H = U⋅M$ où $H$ est une forme normale de Hermite de $M$. Trouver comment calculer $U$ avec la méthode `hermite_form()`. *Lire la documentation !*\n", "1. Calculer le déterminant de $U$ pour plusieurs matrices $M$ choisies aléatoirement, et expliquer le résultat." ] }, { "cell_type": "code", "execution_count": 0, "id": "1cf6c042", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "3d683f7c", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "2e49c67b", "metadata": { "deletable": false, "editable": false, "run_control": { "frozen": true } }, "source": [ "## Question 4\n", "\n", "On s'intéresse à la forme de Hermite d'une matrice $M\\in ℤ^{m×1}$ (c'est-à-dire une matrice colonne), et en premier lieu au cas $m = 2$ : on veut la forme de Hermite d'une matrice $M = \\begin{pmatrix} a\\\\b\\end{pmatrix}$.\n", "\n", "1. Calculer les formes de Hermite de plusieurs matrices $M = \\begin{pmatrix} a\\\\b\\end{pmatrix}$, en faisant varier les valeurs de $a$ et $b$, et conjecturer le résultat.\n", "\n", "1. Faire de même, mais avec également la matrice $U$ de transformation. À quoi correspondent les coefficients de la première ligne ? *Vérifier avec la commande correspondante de SageMath.*\n", "\n", "1. On va généraliser les observations aux matrices $M\\in ℤ^{m×1}$. Pour cela, calculer la forme de Hermite et la matrice de transformation pour deux types de matrices $M$ : i. des matrices d'entiers aléatoires ; ii. une matrice de la forme $(N/p_1, N/p_2, …, N/p_m)^⊤$ où $p_1$, …, $p_m$ sont des nombres premiers distincts et $N = \\prod_i p_i$. Que peut-on dire de la première ligne de la matrice de transformation ?" ] }, { "cell_type": "code", "execution_count": 0, "id": "53d59eb9", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "28ccaf65", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "ee85a344", "metadata": { "scrolled": true }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "6a694c1a", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 0, "id": "e5929b94", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.5", "language": "sage", "name": "sagemath" }, "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.10.12" } }, "nbformat": 4, "nbformat_minor": 5 }