{
 "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 strictement inférieur au pivot.\n",
    "\n",
    "1. Les deux matrices suivantes sont-elles sous forme normale de Hermite ?\n",
    "   $$\\begin{pmatrix}\n",
    "     2 & 4 & -3 & 0 \\\\\n",
    "     0 & 0 &  5 & 7 \\\\\n",
    "     0 & 0 &  0 & 8\n",
    "     \\end{pmatrix}\\qquad\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 deux matrices 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. On considère les colonnes de la matrice $M∈ℤ^{m×n}$ les unes après les autres. Dans chaque colonne, on va trouver un pivot (à moins que la colonne soit nulle). Pour traiter la colonne $j$, on suppose que le pivot en colonne $j-1$ se trouve en ligne $i-1$ : on va considérer les éléments de la colonne $j$ qui sont en lignes $i$ à $m$. En multipliant les lignes qu'il faut par $-1$, on fait en sorte que tous ces éléments soient positifs. S'ils sont tous nuls, on passe à la colonne d'après. Sinon, supposons qu'il en existe deux non nuls $d_u$ et $d_v$, avec $d_u≥d_v$ (en lignes $u$ et $v$) : alors on peut faire diminuer $d_u$ en ajoutant $\\lfloor d_u/d_v\\rfloor$ fois la ligne $v$ à la ligne $u$. On peut recommencer l'opération tant qu'il existe au moins deux éléments non nuls : à la fin, on obtient un unique $d_u$ non nul entre la ligne $i$ et la ligne $m$. En échangeant les lignes $u$ et $i$, cet unique élément non nul (le *pivot*) est ramené en case $(i,j)$. Enfin, on peut utiliser la même technique pour faire diminuer les éléments au dessus du pivot pour qu'ils soient inférieurs au pivot. On peut passer à la colonne suivante.\n",
    "\n",
    "1. Appliquer l'algorithme sur la matrice \n",
    "   $$\\begin{pmatrix}\n",
    "   1 & -3 & 5\\\\\n",
    "   2 & -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()`."
   ]
  },
  {
   "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": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "4e11c248",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## 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()`.\n",
    "1. Calculer le déterminant de $U$ pour plusieurs matrices $M$ choisies aléatoirement, et conjecturer un résultat.\n",
    "1. Vérifier sur Wikipédia (ou autre !)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "1cf6c042",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "3d683f7c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "53d59eb9",
   "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}