{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "453516c9",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "# Vision matricielle de l'algorithme de Gauss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "9196c09f",
   "metadata": {
    "tags": [
     "sujet"
    ]
   },
   "outputs": [],
   "source": [
    "%display latex"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "709403c1",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## Question 1\n",
    "On souhaite ré-implanter l'algorithme de Gauss, cette fois en ne modifiant pas la matrice $A$ fournie en entrée mais en renvoyant une matrice inversible $M$ telle que $M⋅A = E$ où $E$ est une forme échelonnée de $A$.\n",
    "\n",
    "1. Écrire une fonction `MatP(K,m,i,j)` qui renvoie une matrice de permutation dans $𝕂^{m×m}$ dont l'action est d'échanger les lignes $i$ et $j$.\n",
    "\n",
    "1. Écrire une fonction `MatM(K,m,i,j,λ)` qui renvoie une matrice $M_λ^{i,j}\\in𝕂^{m×m}$ dont l'action est d'ajouter $λ$ fois la $i$^ème^ ligne à la $j$^ème^.\n",
    "\n",
    "1. Écrire l'algorithme `GaussMatrice(A)` qui renvoie une matrice $M$, inversible, telle que $M⋅A$ est sous forme échelonnée (non réduite), et *ne modifie pas* $A$.\n",
    "\n",
    "**Tests.** Pour tester vos implantations, générer des matrices aléatoires (avec `random_matrix(K, m, n)` pour obtenir une matrice de $𝕂^{m×n}$) et vérifier l'action des matrices renvoyées par `MatP` et `MatM`. Vérifier également, pour `GaussMatrice`, que le résultat est correct ($M⋅A$ est sous forme échelon) et que $A$ n'est pas modifiée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "3eda56d1",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "5131e830",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "ff00aaad",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "ef64054b",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "4e7c6a16",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## Question 2\n",
    "On veut comparer les résultats calculés avec ceux renvoyés par SageMath. Pour une matrice $A$, la commande `A.LU(pivot='nonzero')` renvoie un triplet $(P,L,E)$ tel que $A = P⋅L⋅E$, avec (presque) les mêmes caractéristiques que dans le cours. \n",
    "\n",
    "1. Quelle est la relation entre les matrices de ce triplet, et la matrice $M$ renvoyée par `GaussMatrice` (si les caractéristiques étaient exactement les mêmes que dans le cours).\n",
    "1. Vérifier expérimentalement que c'est la plupart du temps le cas. Essayer de comprendre, dans les cas où la relation n'est pas vérifiée, la différence entre le triplet renvoyé et la caractérisation du cours.\n",
    "1. Observer le résultat de `A.LU(pivot='nonzero', format='compact')` et expliquer pourquoi ce format de sortie est une bonne idée. *Il est autorisé de lire la documentation !*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "31566fac",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "54034c0a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "e3d9a00e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Question 3\n",
    "\n",
    "On va implanter un algorithme d'inversion des matrices triangulaires inférieures.\n",
    "\n",
    "1. Pour le tester, on aura besoin d'une fonction qui génère une matrice triangulaire inférieure. Écrire une fonction `random_triang(K, m, inv=True)` qui renvoie une matrice triangulaire inférieure $L\\in 𝕂^{m×m}$ dont les coefficients sont choisis aléatoirement dans $𝕂$. Le booléen `inv` détermine si on impose que $L$ soit inversible ou non.\n",
    "\n",
    "1. Implanter un algorithme qui prend en entrée une matrice $L$ triangulaire inférieure, et renvoie $L^{-1}$. Vous pouvez supposer que la matrice en entrée est bien triangulaire supérieure (ou le vérifier si vous le souhaitez), et vous renverrez une erreur si la matrice n'est pas inversible, à l'aide de `raise ValueError(\"la matrice n'est pas inversible !\")` par exemple. *Prendre un papier et un crayon pour trouver l'algorithme, faire des essais, etc. C'est normal de ne pas y arriver du premier coup !*\n",
    "\n",
    "1. À l'aide de ce qu'on a vu en TD, comment passer du triplet $(P,L,E)$ renvoyé par `A.LU(pivot='nonzero')` à la matrice $M$ renvoyée par `GaussMatrice(A)` ? Vérifier expérimentalement que ça fonctionne (la plupart du temps, *cf* question précédente)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "dbf8bb1a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "f3a40ba4",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "a0ccdb19",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "ae00943a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "0b901926",
   "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
}