{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "988ed001",
   "metadata": {},
   "source": [
    "# Séance 8\n",
    "\n",
    "\n",
    "```{admonition} Objectifs\n",
    "* Polynômes\n",
    "* Réduction matricielle\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Polynômes\n",
    "\n",
    "### Anneau de polynômes\n",
    "\n",
    "Avant de construire un polynôme, il faut définir la structure algébrique qui le contient, à savoir un **anneau de polynômes**. Le constructeur de cet anneau se nomme `PolynomialRing`. Pour l'utiliser, il faut choisir dans quelle structure vivent les **coefficients** de ces polynômes, et également un nom d'affichage pour la variable.\n",
    "\n",
    "Par exemple, si les coefficients sont des entiers relatifs et si l'on souhaite que la variable soit affichée comme `X`, alors on entre :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dc9d3cd2",
   "metadata": {},
   "outputs": [],
   "source": [
    "A = PolynomialRing(ZZ, \"X\")\n",
    "print(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70237265",
   "metadata": {},
   "source": [
    "Observons que, dans ce cas, la variable `X` n'est **pas encore déclarée**. On doit donc la définir nous-même :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e504b86",
   "metadata": {},
   "outputs": [],
   "source": [
    "X = A.gen()\n",
    "print(X)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a636427",
   "metadata": {},
   "source": [
    "**Remarque.** Par commodité (mais pas par simplicité...), il existe une manière de déclarer **simultanément** un anneau de polynômes et sa variable :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "30aeaa27",
   "metadata": {},
   "outputs": [],
   "source": [
    "B.<Y> = PolynomialRing(ZZ)\n",
    "print(B)\n",
    "print(Y)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b929ac4",
   "metadata": {},
   "source": [
    "### Construction de polynômes\n",
    "\n",
    "Il existe essentiellement deux manières de construire un polynôme :\n",
    "1. en appliquant des opérations élémentaires sur la variable `X` (somme, puissances, etc.),\n",
    "1. en fournissant une liste de coefficents au constructeur de l'anneau de polynômes `A`.\n",
    "\n",
    "\n",
    "**Méthode 1.** Les opérations usuelles sur les polynômes permettent de définir un polynôme dans SageMath. Par exemple pour le polynôme $P(X) = X^3 - 2X + 1$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f35f59b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "P = X**3 - 2 * X + 1\n",
    "print(P)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbeb74af",
   "metadata": {},
   "source": [
    "**Méthode 2.** En construisant la liste de coefficients de $P$ (dans l'ordre croissant des degrés), et la donnant en paramètre du constructeur de `A`, on obtient le même résultat :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cb08680c",
   "metadata": {},
   "outputs": [],
   "source": [
    "P = A([1, -1, 0, 1])\n",
    "print(P)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5827a73d",
   "metadata": {},
   "source": [
    "Observons que la **classe parente** de `P` est bien l'anneau de polynômes créé précédemment, et ses coefficients sont bien des entiers (on accède à l'anneau des coefficients par la méthode `base_ring()`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3e0281ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(P.parent())\n",
    "print(P.base_ring())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27242dea",
   "metadata": {},
   "source": [
    "**Remarque :** un meilleur affichage graphique peut être obtenu avec la commande `show`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "62bfd26f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# show(P)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "425af6b4",
   "metadata": {},
   "source": [
    "### Opérations usuelles\n",
    "\n",
    "\n",
    "On peut calculer des **sommes**, des **produits**, et **multiplier** des polynômes entre eux ou par des scalaires par les opérateurs usuels :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e62948b",
   "metadata": {},
   "outputs": [],
   "source": [
    "P1 = X**3 - 2 * X + 1\n",
    "P2 = X**2 - 5\n",
    "print(P1 + P2)\n",
    "print(P1 * P2)\n",
    "print( - 3 * P1**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "773f0d94",
   "metadata": {},
   "source": [
    "Il est également possible de **composer** des polynômes et de leur appliquer des **opérations arithmétiques** comme le reste de la division euclidienne :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7c70e62c",
   "metadata": {},
   "outputs": [],
   "source": [
    "Q = P(X**2 - 1)\n",
    "R = Q % (X**2 - 1)\n",
    "print(\"Q =\", Q)\n",
    "print(\"R =\", R)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f25a3f06",
   "metadata": {},
   "source": [
    "Observons que l'opérateur `//` effectue bien la **division euclidienne** des polynômes, tandis que `/` calcule une **fraction rationnelle** :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d313dbc8",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(Q // (X**2 - 1))\n",
    "print(Q /  (X**2 - 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02650521",
   "metadata": {},
   "source": [
    "Les calculs de **pgcd** et de **ppcm** sont également possibles :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ac23f0c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "P = (X-1)*(X-2)\n",
    "Q = (X-1)*(X-3)\n",
    "print(gcd(P, Q))\n",
    "print(lcm(P, Q))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5e93f2c",
   "metadata": {},
   "source": [
    "### Accès aux coefficients et autres propriétés\n",
    "\n",
    "\n",
    "Pour retrouver les **coefficients d'un polynôme**, il faut faire attention. La commande de base **ne retourne que les coefficients non-nuls**, dans l'ordre de degré croissant :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9702ac2d",
   "metadata": {},
   "outputs": [],
   "source": [
    "P = X**12 - 3*X**3 + 1\n",
    "print(P)\n",
    "print(P.coefficients())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e826cb3",
   "metadata": {},
   "source": [
    "Si l'on souhaite la liste de **tous** les coefficients (y compris les $0$ intermédiaires), il **faut** ajouter l'argument `sparse=False`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f9786f6b",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(P.coefficients(sparse=False))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1495b520",
   "metadata": {},
   "source": [
    "Ensute, on peut accéder au coefficient associé au monôme d'un certain degré, comme si on raisonnait avec une liste :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8c1fae62",
   "metadata": {},
   "outputs": [],
   "source": [
    "P[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04f03afc",
   "metadata": {},
   "source": [
    "Enfin, il existe des méthodes pour obtenir le **degré** d'un polynôme, son **coefficient dominant**, et son **coefficient constant**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fb5d769c",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(P.degree())\n",
    "print(P.leading_coefficient())\n",
    "print(P.constant_coefficient())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c6a44aa",
   "metadata": {},
   "source": [
    "### Opérations plus avancées\n",
    "\n",
    "**Dérivation**. Pour dériver un polynôme, on utilise la méthode `derivative()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "655b69ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "P = X**4 - X\n",
    "P.derivative()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f31a9b9b",
   "metadata": {},
   "source": [
    "**Factorisation.** On peut également essayer de factoriser un polynôme dans la structure à laquelle il appartient (donc ici, dans $\\mathbb{Z}[X]$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c8810252",
   "metadata": {},
   "outputs": [],
   "source": [
    "P.factor()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2fe8023b",
   "metadata": {},
   "source": [
    "**Évaluation.** On peut évaluer un polynôme en une entrée, c'est-à-dire **substituer** la variable par une **valeur** et effectuer le calcul correspondant. Pour cela, on utilise la syntaxe naturelle :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "120e084f",
   "metadata": {},
   "outputs": [],
   "source": [
    "P(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b3e5c08",
   "metadata": {},
   "source": [
    "Notons qu'on peut évaluer un polynôme sur un élément **d'un type autre** que celui de l'anneau de ses coefficents. Il faut néanmoins que Sagemath sache effectuer les opérations entre les coefficients et la valeur de substitution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4d499169",
   "metadata": {},
   "outputs": [],
   "source": [
    "P(1/2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9f28331",
   "metadata": {},
   "source": [
    "**Racines.** Il existe une fonction générique pour obtenir les racines d'un polynôme. Cette fonction retourne la **liste des racines appartenant à l'anneau des coefficients du polynôme** considéré, avec leur **multiplicité d'annulation**.\n",
    "\n",
    "Dans l'exemple suivant, il est écrit que $4$ est une racine de $P(X)$ de multiplicité $1$. En revanche, les racines $1/2$ et $1/3$ sont omises, car $P$ a été défini sur l'anneau des entiers, et non le corps des rationnels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8bb1e421",
   "metadata": {},
   "outputs": [],
   "source": [
    "P = (X - 4) * (2*X - 1) * (3*X - 1)\n",
    "print(P)\n",
    "print(P.roots())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4b96418d",
   "metadata": {},
   "source": [
    "Pour **obtenir davantage de racines**, on peut préciser l'anneau dans lequel on souhaite des obtenir. Par exemple, pour avoir toutes les racines rationnelles, on ajouter le corps des rationnels en argument optionnel de la méthode `roots` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "95b1c994",
   "metadata": {},
   "outputs": [],
   "source": [
    "P.roots(QQ)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78f89c7a",
   "metadata": {},
   "source": [
    "**Affichage graphique.** Enfin, pour tracer le graphe d'un polynôme, il y a toujours la fonction `plot()`  :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ba25e3ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "plot(P, xmin=-0.5, xmax=4.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2680f9a6",
   "metadata": {},
   "source": [
    "## Application : réduction matricielle, algèbre matricielle\n",
    "\n",
    "Soit $M$ la matrice $3 \\times 3$ à coefficients entiers (donc rationnels) suivante :\n",
    "\n",
    "$$\n",
    "M = \\left(\\begin{array}{rrr}\n",
    "8 & -2 & -7 \\\\\n",
    "-12 & 3 & 12 \\\\\n",
    "2 & -2 & -1\n",
    "\\end{array}\\right)\n",
    "$$\n",
    "\n",
    "On veut étudier si $M$ est diagonalisable, et si c'est le cas, la diagonaliser."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a5886baf",
   "metadata": {},
   "outputs": [],
   "source": [
    "M = matrix(QQ, 3, 3, [8, -2, -7, -12, 3, 12, 2, -2, -1 ])\n",
    "print(M)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01ddef54",
   "metadata": {},
   "source": [
    "Pour cela, on peut calculer son **polynôme caractéristique**, puis chercher ses racines :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0b7dfdb4",
   "metadata": {},
   "outputs": [],
   "source": [
    "P = M.characteristic_polynomial()\n",
    "print(P)\n",
    "print(P.roots())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9916b8eb",
   "metadata": {},
   "source": [
    "On observe que le polynôme caractéritique a $3$ racines simples distinctes : la matrice est donc **diagonalisable**. Notons que l'on aurait pu tester si $M$ est diagonalisable directement avec la méthode `is_diagonalizable()`, et calculer ses valeurs propres directement avec la méthode `eigenvalues()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "247d0d97",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(M.is_diagonalizable())\n",
    "valeurs_propres = M.eigenvalues()\n",
    "print(valeurs_propres)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12d630ad",
   "metadata": {},
   "source": [
    "**Diagonalisation effective.** La diagonalisation peut se faire \"à la main\" (en calculant une base de vecteurs propres avec les méthodes d'algèbre linéaire de la semaine passée), mais on va se l'épargner. En effet, la méthode  `diagonalization()` nous donne directement le résultat sous la forme d'un couple de matrices $(D, A)$, de sorte que $D$ est diagonale et $M = A D A^{-1}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "14bcdffb",
   "metadata": {},
   "outputs": [],
   "source": [
    "D, A = M.diagonalization()\n",
    "print(\"A =\")\n",
    "print(A)\n",
    "\n",
    "print(\"\\nD =\")\n",
    "print(D)\n",
    "\n",
    "print(\"\\nVérification :\")\n",
    "print(A * D * A**(-1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e10f7de",
   "metadata": {},
   "source": [
    " \n",
    "\n",
    "\n",
    "**Remarque.** Il est également possible d'obtenir la liste des **sous-espaces propres** :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fd21142c",
   "metadata": {},
   "outputs": [],
   "source": [
    "print(M.eigenspaces_right())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dffcd900",
   "metadata": {},
   "source": [
    "## Récapitulatif des instructions à connaître\n",
    "\n",
    "\n",
    "**Tableau récapitulatif** de quelques instructions à connaître sur les polynômes :\n",
    "\n",
    "| Méthode, fonction, instruction | Description |\n",
    "|:---:|:---:|\n",
    "| `A = PolynomialRing(R, \"X\")` | Crée et stocke dans `A` l'anneau des polynômes à coefficients dans un anneau `R`, en une variable qui s'affichera `X` |\n",
    "| `X = A.gen()` | Stocke dans `X` l'indéterminée de l'anneau de polynômes `A` |\n",
    "| `A(liste)` | Crée le polynôme dont les coefficients sont donnés par `liste`, dans l'ordre croissant des degrés |\n",
    "| `+`, `-`, `*`, `**`, `//`, `%` | Opérations arithmétiques élémentaires |\n",
    "| `gcd(P, Q)` et `lcm(P, Q)` | Pgcd et ppcm de deux polynômes `P` et `Q` |\n",
    "| `P.coefficients(sparse=False)` | Liste des coefficients du polynômes `P` |\n",
    "| `P[i]` | Coefficient de degré `i` du polynôme `P` |\n",
    "| `P.degree()` | Degré du polynôme `P` |\n",
    "| `P.derivative(i)` | Dérivé d'ordre `i` du polynôme `P` (`i` est optionnel, s'il est omis il vaut $1$) |\n",
    "| `P(valeur)` | Évaluation du polynôme `P` en `valeur` |\n",
    "| `P.roots(S)` | Racines du polynôme `P` dans l'anneau `S` (`S` est optionnel, s'il est omis il vaut l'anneau de coefficients de `P`) |\n",
    "\n",
    "**Tableau récapitulatif** des instructions à connaître pour la réduction de matrices :\n",
    "\n",
    "| Méthode, fonction, instruction | Description |\n",
    "|:---:|:---:|\n",
    "| `M.characteristic_polynomial()` | Polynômes caractéristique d'une matrice `M` |\n",
    "| `M.eigenvalues()` | Valeurs propres d'une matrice `M` |\n",
    "| `M.is_diagonalizable()` | Retourne `True` si `M` est diaginalisable, `False` sinon |\n",
    "| `M.diagonalization()` | Retourne la diagonalisation de `M` (voir détails ci-dessus)  |"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Sagemath",
   "language": "python",
   "name": "sagemath"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}