{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Noyau et image d'une application linéaire\n",
    "\n",
    "Marc Lorenzi\n",
    "\n",
    "3 février 2020"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 0. Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0.1 Objectifs, notations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $f\\in\\mathcal L(E, F)$ une application linéaire entre deux $\\mathbb R$-espaces vectoriels de dimension finie. Ce notebook se propose d'utiliser les méthodes vue en cours pour le calcul pratique de certaines quantités associées à $f$ : son rang, son noyau et son image. Les fonctions que nous allons développer permettront évidemment de déterminer aussi l'espace engendrée par une famille de vecteurs le rang de cette famille.\n",
    "\n",
    "L'idée n'est pas d'avoir une boîte noire, d'excellentes bibliothèques existent déjà pour calculer ces quantités. Bien au contraire, le but est de comprendre comment on calcule un rang, un espace engendré, un noyau, etc. On laisse à l'utilisateur l'initiative des opérations à effectuer. L'automatisation viendra petit à petit ... jusqu'à l'écriture de deux fonctions `ker` et `im` qui feront toutes seules le calcul d'une base du noyau et de l'image de $f$.\n",
    "\n",
    "Nous verrons ensuite comment ce que nous avons fait permet de travailler sur les sous-espaces vectoriels de $E$ : bases, équations cartésiennes, sommes, intersections, supplémentarité, etc.\n",
    "\n",
    "__Remarque__ : Comme beaucoup de calculs pratiques font intervenir des matrices d'entiers, nous ferons en sorte que nos opérations préservent cette propriété. Tous nos calculs seront donc exacts et jamais approchés."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0.2 Matrices d'exemples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous allons bien évidemment travailler sur des matrices, que nous représenterons en Python comme des listes de listes. Voici une fonction renvoyant une matrice que nous prendrons fréquemment comme exemple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def exemple(p=3, q=3):\n",
    "    n = p * q\n",
    "    A = [q * [0] for i in range(p)]\n",
    "    for k in range(n):\n",
    "        A[k % p][k // p] = k + 1\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "exemple(5, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous aurons souvent besoin du nombre de lignes et du nombre de colonnes d'une matrice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def nblig(A): return len(A)\n",
    "def nbcol(A): \n",
    "    if A == []: raise Exception('Nombre de colonnes indetermine')\n",
    "    return len(A[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(7, 8)\n",
    "nblig(A), nbcol(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Écrivons également une fonction qui permet d'avoir un affichage des matrices plus agréable. On évalue et on stocke pour chaque colonne de la matrice la longueur maximale de la représentation de ses coefficients sous forme de chaîne de caractères. Puis on affiche la matrice ligne par ligne en utilisant les longueurs maximales pré-calculées. La matrice est alors parfaitement tabulée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prnt(A):\n",
    "    if A == []: print('_')\n",
    "    else:\n",
    "        p, q = nblig(A), nbcol(A)\n",
    "        ws = q * [0]\n",
    "        for j in range(q):\n",
    "            for i in range(p):\n",
    "                w = len('%s' % (A[i][j]))\n",
    "                if w > ws[j]: ws[j] = w\n",
    "        for i in range(p):\n",
    "            s = ''\n",
    "            for j in range(q):\n",
    "                s1 = '%d' % A[i][j]\n",
    "                sp = ws[j] - len(s1) + 1\n",
    "                s1 = (sp * ' ') + s1\n",
    "                s = s + s1\n",
    "            print(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prnt(exemple(12, 25))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous utiliserons aussi parfois des matrices aléatoires. La fonction `randmat` renvoie une matrice \"aléatoire\" de taille $p\\times q$ dont les coefficients sont des entiers de l'intervalle $[-r,r]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def randmat(p, q, r=10):\n",
    "    A = [q * [0] for i in range(p)]\n",
    "    for i in range(p):\n",
    "        for j in range(q):\n",
    "            A[i][j] = random.randint(-r, r)\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = randmat(10, 15, r=10000)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Rang, espace engendré"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On ne change pas l'espace engendré par les colonnes de la matrice $A$ (et donc pas non plus son rang) en effectuant les opérations suivantes :\n",
    "\n",
    "- Échanger deux colonnes.\n",
    "- Multiplier une colonne par un réel non nul.\n",
    "- Ajouter à une colonne un multiple d'un autre colonne.\n",
    "\n",
    "Nous allons tout d'abord définir ces opérations au moyen de quelques fonctions qui se passent de commentaires."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Échange de deux colonnes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `echanger` échange les colonnes $j_1$ et $j_2$ de la matrice $A$.\n",
    "\n",
    "$$C_{j_1}\\longleftrightarrow C_{j_2}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def echanger(A, j1, j2, dbg=True):\n",
    "    if dbg: print('C%s <-> C%s' % (j1, j2))\n",
    "    for i in range(nblig(A)):\n",
    "        A[i][j1], A[i][j2] = A[i][j2], A[i][j1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(5, 8)\n",
    "echanger(A, 3, 6)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Produit d'une colonne par un scalaire "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `mult` multiplie la colonne $j$ de la matrice $A$ par le scalaire $t$.\n",
    "\n",
    "$$C_j \\longleftarrow t C_j$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mult(A, j, t, dbg=True):\n",
    "    if dbg: print('C%s <- (%s)C%s' % (j, t, j))\n",
    "    for i in range(nblig(A)):\n",
    "        A[i][j] = t * A[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(5, 10)\n",
    "mult(A, 4, -5)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Histoire de pouvoir aussi diviser une colonne par un facteurs commun de ses éléments, définissons une fonction `div`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def div(A, j, t, dbg=True):\n",
    "    if dbg: print('C%s <- (1/%s)C%s' % (j, t, j))\n",
    "    for i in range(nblig(A)):\n",
    "        A[i][j] = A[i][j] // t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = [[5, 10], [15, 20]]\n",
    "prnt(A)\n",
    "div(A, 0, 5)\n",
    "div(A, 1, 10)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 Ajout à une colonne d'un multiple d'une autre colonne"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `add` ajoute à la colonne $j_1$ de la matrice $A$ $t$ fois la colonne $j_2$.\n",
    "\n",
    "$$C_{j_1} \\longleftarrow C_{j_1} + t C_{j_2}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add(A, j1, t, j2, dbg=True):\n",
    "    if dbg: print('C%s <- C%s + (%s)C%s' % (j1, j1, t, j2))\n",
    "    for i in range(nblig(A)):\n",
    "        A[i][j1] = A[i][j1] + t * A[i][j2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(5, 10)\n",
    "add(A, 2, -11, 0)\n",
    "add(A, 7, -36, 0)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5 Pivot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Première étape de l'automatisation, la fonction `pivoter` combine certaines des opérations déjà décrites. Soit $A$ une matrice $p\\times q$. La fonction `pivoter` prend en paramètres un indice de ligne $\\ell$ et un indice de colonne $k$ tels que $t=A_{\\ell k}\\ne 0$. Le but de `pivoter` est d'annuler les coefficients $A_{\\ell(k+1)},A_{\\ell(k+2)},\\ldots,A_{\\ell q}$. \n",
    "\n",
    "Pour $j=k+1,\\ldots,q-1$, on effectue l'opération \n",
    "\n",
    "$$C_j\\longleftarrow \\frac t \\delta C_j - \\frac u \\delta C_k$$\n",
    "\n",
    "où $u=A_{\\ell j}$ et $\\delta =pgcd(t,u)$. La fonction `pivoter` effectue au total $2(q-k)$ opérations \"élémentaires\" sur les colonnes de $A$. Elle remplit bien son rôle puisque\n",
    "\n",
    "$$\\frac t \\delta A_{\\ell j} - \\frac u \\delta A_{\\ell k}=\\frac t \\delta u - \\frac u \\delta t=0$$\n",
    "\n",
    "__Remarque__ : On pourrait automatiser `pivoter` afin que la fonction trouve elle-même les indices $\\ell$ et $k$. Nous le ferons plus loin mais pour l'instant il est du devoir de l'utilisateur d'observer la matrice $A$ et de choisir les valeurs de $\\ell$ et de $k$ qui lui semblent pertinentes !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(a, b):\n",
    "    while b != 0:\n",
    "        a, b = b, a % b\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pivoter(A, l, k, dbg=True):\n",
    "    t = A[l][k]\n",
    "    for j in range(k + 1, nbcol(A)):\n",
    "        u = A[l][j]\n",
    "        d = gcd(t, u)\n",
    "        if dbg: print('C%s <- (%s)C%s + (%s)C%s' % (j, t // d, j, -u // d, k))\n",
    "        for i in range(0, nblig(A)):\n",
    "            A[i][j] = (t // d) * A[i][j] - (u // d) * A[i][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(5, 6)\n",
    "pivoter(A, 0, 0)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maintenant que les fonctions de base sont mises en place, regardons ce que l'on peut faire avec."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Quelques exemples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Notre exemple préféré"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prenons tout d'abord notre matrice favorite."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(6, 9)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On pivote en 0,0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pivoter(A, 0, 0)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Puis en 1, 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pivoter(A, 1, 1)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Effectuons une dernière opération."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "div(A, 1, A[1][1])\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette matrice a même rang que $A$ et ses colonnes engendrent le même espace que les colonnes de $A$. Ainsi, $rg A=2$ et l'image d'une application linéaire associée à $A$ a pour base les deux premières colonnes de $A$.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Rang d'une famille de vecteurs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On se place dans $E=\\mathbb R^5$. Soient \n",
    "- $x_1=(1,2,-4,3,1)$\n",
    "- $x_2=(2,5,-3,4,8)$ \n",
    "- $x_3=(6,17,-7,10,22)$\n",
    "- $x_4=(1,3,-3,2,0)$\n",
    "Quel est le rang de la famille $(x_1,x_2, x_3,x_4)$ ? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tout d'abord, voici une fonction bien utile qui renvoie la transposée d'une matrice. Cela évite de faire de la gymnastique pour entrer les données en lignes alors qu'on nous les donne en colonnes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def transp(A):\n",
    "    if A == []: return []\n",
    "    p, q = nblig(A), nbcol(A)\n",
    "    B = [p * [0] for i in range(q)]\n",
    "    for i in range(q):\n",
    "        for j in range(p):\n",
    "            B[i][j] = A[j][i]\n",
    "    return B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = transp([[1, 2, -4, 3, 1], [2, 5, -3, 4, 8], [6, 17, -7, 10, 22], [1, 3, -3, 2, 0]])\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et maintenant, pivotons."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pivoter(A, 0, 0)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pivoter(A, 1, 1)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pivoter(A, 2, 2)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Encore une petite simplification ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "div(A, 2, -2)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le rang de la famille $(x_1,\\ldots,x_4)$ est donc 3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Matrices aléatoires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ne prenez surtout pas exemple sur la fonction qui vient ... La fonction `kamikaze` appelle `pivot` successivement sur les indices $(0, 0), (1, 1),\\ldots,(m,m)$ où $m=\\min(p,q)$, en priant pour ne jamais tomber sur un pivot nul. Cela a de bonnes chances de fonctionner sur une matrice aléatoire, et quasiment aucune chance de fonctionner sur des matrices particulières, surtout sur les matrices qui apparaissent dans les exercices classiques :-)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kamikaze(A, dbg=True):\n",
    "    m = min(nblig(A), nbcol(A))\n",
    "    for k in range(m):\n",
    "        pivoter(A, k, k, dbg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = randmat(4, 6)\n",
    "kamikaze(A, dbg=True)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Depuis quelque temps nous avons remarqué que, souvent, des entiers sont en facteurs dans les colonnes. Écrivons une fonction qui divise une colonne d'une matrice par le pgcd des coefficients de cette colonne."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcdcol(A, j):\n",
    "    d = 0\n",
    "    for i in range(nblig(A)):\n",
    "        d = gcd(d, A[i][j])\n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def normaliser_colonne(A, j, dbg):\n",
    "    d = gcdcol(A, j)\n",
    "    if d != 0:\n",
    "        div(A, j, d, dbg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici notre nouvelle fonction `kamikaze` qui simplifie, après chaque appel à pivot, la colonne dans laquelle se trouve le pivot."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kamikaze2(A, dbg=True):\n",
    "    for k in range(min(nblig(A), nbcol(A))):\n",
    "        pivoter(A, k, k, dbg)\n",
    "        normaliser_colonne(A, k, dbg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testons."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = randmat(4, 6)\n",
    "kamikaze2(A, dbg=True)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une matrice $13\\times 13$ pour terminer ? Des matrices de taille $100\\times 100$ sont parfaitement envisageables, mais inutile alors d'espérer les afficher joliment ... "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = randmat(13, 13)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En zéro seconde, `kamikaze2` renvoie le résultat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "kamikaze2(A, dbg=False)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Noyau et image"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $A\\in\\mathcal M_{pq}(\\mathbb K)$. La matrice $A$ est la matrice dans les bases canoniques de $\\mathbb K^q$ et $\\mathbb K^p$ d'une application linéaire $f$. Que valent le noyau et l'image de $f$ ?\n",
    "\n",
    "Pour l'image de $f$ c'est facile. En effet les opérations \"élémentaires\" sur les colonnes de $A$ ne changent pas l'espace engendré par les colonnes. Bref, nous avons déjà écrit une fonction qui calcule une base $Im f$. On pivote et on récupère les colonnes non nulles de la matrice finale.\n",
    "\n",
    "Pour le noyau de $f$, il va nous falloir être un peu plus soigneux. \n",
    "\n",
    "Appelons $\\mathcal B=(e_1,\\ldots,e_q)$ la base canonique de $\\mathbb K^q$. Soit $\\mathcal B'$ la base canonique de $\\mathbb K^p$. \n",
    "\n",
    "À chaque opération sur les colonnes de $A$ nous allons enregistrer quelle opération a été effectuée. Où enregistrer cela ? Dans une matrice $B\\in GL_q(\\mathbb K)$ qui est la matrice de passage d'une base de $\\mathbb K^q$ à la base $\\mathcal B$. La matrice $B$ est initialement la matrice identité $I_q=P_{\\mathcal B}^{\\mathcal B}$. Lors d'une opération élémentaire sur les colonnes de $A$ on effectue la même opération sur la matrice $B$. Et alors ? La matrice $A$ est la matrice de $f$ dans les bases $\\mathcal B$ et $\\mathcal B'$ : la $j$ème colonne de $A$ contient donc le vecteur $f(e_j)$ (ou plutôt ses coordonnées dans la base $\\mathcal B'$).\n",
    "\n",
    "Prenons un exemple concret : effectuons l'opération $C_2 \\longleftarrow C_2 + 3C_1$. La colonne 2 de $A$ contient alors $f(e_2+3e_1)$. Si l'on effectue la même opération sur la matrice $B$, celle-ci devient la matrice de passage de $\\mathcal B$ à une nouvelle base qui a les mêmes vecteurs que $\\mathcal B$, sauf le second qui vaut $e_2+3e_1$. Nous avons ainsi \"stocké\" $e_2+3e_1$ dans la matrice $B$.\n",
    "\n",
    "De façon générale, $B=P_{\\mathcal B}^{\\mathcal B_1}$ où $\\mathcal B_1$ est telle que $A=mat_{\\mathcal B_1\\mathcal B'}f$.\n",
    "\n",
    "Au travail !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Réécriture des opérations élémentaires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ces fonctions sont identiques à celles qui ont déjà été écrites, mis à part le fait qu'elle prennent un paramètre $B$ supplémentaire qui est la matrice de passage décrite au paragraphe précédent. Chaque opération sur $A$ est répercutée sur $B$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def echanger2(A, j1, j2, B):\n",
    "    for i in range(nblig(A)):\n",
    "        A[i][j1], A[i][j2] = A[i][j2], A[i][j1]\n",
    "    for i in range(nblig(B)):\n",
    "        B[i][j1], B[i][j2] = B[i][j2], B[i][j1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mult2(A, j, t, B):\n",
    "    for i in range(nblig(A)):\n",
    "        A[i][j] = t * A[i][j]\n",
    "    for i in range(nblig(B)):\n",
    "        B[i][j] = t * B[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def div2(A, j, t, B):\n",
    "    for i in range(nblig(A)):\n",
    "        A[i][j] = A[i][j] // t\n",
    "    for i in range(nblig(B)):\n",
    "        B[i][j] = B[i][j] // t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add2(A, j1, t, j2, B):\n",
    "    for i in range(nblig(A)):\n",
    "        A[i][j1] = A[i][j1] + t * A[i][j2]\n",
    "    for i in range(nblig(B)):\n",
    "        B[i][j1] = B[i][j1] + t * B[i][j2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pivoter2(A, l, k, B):\n",
    "    t = A[l][k]\n",
    "    for j in range(k + 1, nbcol(A)):\n",
    "        u = A[l][j]\n",
    "        d = gcd(t, u)\n",
    "        for i in range(0, nblig(A)):\n",
    "            A[i][j] = (t // d) * A[i][j] - (u // d) * A[i][k]\n",
    "        for i in range(0, nblig(B)):\n",
    "            B[i][j] = (t // d) * B[i][j] - (u // d) * B[i][k]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `eye` renvoie la matrice identité d'ordre $n$, valeur initiale pour la matrice $B$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def eye(n):\n",
    "    A = [n * [0] for i in range(n)]\n",
    "    for i in range(n):\n",
    "        A[i][i] = 1\n",
    "    return A"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testons sur un exemple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(5, 6)\n",
    "B = eye(6)\n",
    "prnt(A)\n",
    "print()\n",
    "prnt(B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pivoter2(A, 0, 0, B)\n",
    "prnt(A)\n",
    "print()\n",
    "prnt(B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pivoter2(A, 1, 1, B)\n",
    "prnt(A)\n",
    "print()\n",
    "prnt(B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bilan :\n",
    "\n",
    "- Le rang de $A$ est 2. \n",
    "- Une base de $Im f$ est la famille des deux premières colonnes de $A$ (les colonnes non nulles).\n",
    "- Une base de $\\ker f$ est la famille des 4 dernières colonnes de $B$, celles qui correspondent aux colonnes nulles de $A$.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Automatisons le tout"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tout le problème, à chaque étape, est la recherche du pivot. Quelles valeurs prendre pour $k$ et $\\ell$, passés en paramètres à `pivoter` ? À la $k$ième itération, le couple $(k,k)$ paraît judicieux. Mais il ne l'est pas toujours car le coefficient correspondant dans la matrice $A$ est peut-être nul. Sans justification dans ce notebook, l'idée est de choisir un couple $(\\ell, k')$ où \n",
    "\n",
    "$$\\ell=\\min\\{i\\ge k, \\exists j \\ge k, A_{i j}\\ne 0\\}$$\n",
    "\n",
    "$$k'=\\min\\{j\\ge k, A_{\\ell j}\\ne 0\\}$$\n",
    "\n",
    "Ce couple d'indices se trouve à l'aide de deux boucles imbriquées. On parcourt les lignes $k,k+1,k+2,\\ldots$ à partir de la colonne $k$ et on s'arrête dès qu'on trouve un coefficient non nul. On renvoie alors les indices de ligne et de colonne de ce coefficient. On cherche donc une ligne d'indice minimal à partir de la ligne $k$ et, pour cette ligne, un indice de colonne minimal, qui fournissent un coefficient non nul de la matrice.\n",
    "\n",
    "Si un tel coefficient n'existe pas c'est qu'il n'y a plus aucune opération à faire sur la matrice $A$ parce que tous les coefficients observés sont nuls.\n",
    "\n",
    "La fonction `chercher_pivot` cherche un tel couple $(\\ell, k)$ d'indices. Elle renvoie $(\\ell,k,True)$ si elle en trouve un, et $(-1,-1,False)$ sinon."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def chercher_pivot(A, k):\n",
    "    for i in range(k, nblig(A)):\n",
    "        for j in range(k, nbcol(A)):\n",
    "            if A[i][j] != 0: return (i, j, True)\n",
    "    return (-1, -1, False)    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `imker` automatise tout ce que nous venons de raconter. Elle prend une matrice $A$ en paramètre et renvoie un couple $(A, B)$ où $A$ est la matrice \"trigonalisée\" et $B$ est une matrice de passage.\n",
    "\n",
    "Petits détails :\n",
    "- On opère sur une __copie__ de $A$ pour ne pas modifier la matrice initiale. \n",
    "- On divise en fin de fonction les colonnes d e$A* et $B$ par les pgcd de leurs coefficients pour avoir un résultat aussi simple que possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def imker(A):\n",
    "    A = [A[i].copy() for i in range(nblig(A))]\n",
    "    B = eye(nbcol(A))\n",
    "    k = 0\n",
    "    while True:\n",
    "        i, j, b = chercher_pivot(A, k)\n",
    "        if not b: break\n",
    "        if j != k: echanger2(A, j, k, B)\n",
    "        pivoter2(A, i, k, B)\n",
    "        k = k + 1\n",
    "    for j in range(nbcol(A)): normaliser_colonne(A, j, dbg=False)\n",
    "    for j in range(nbcol(B)): normaliser_colonne(B, j, dbg=False)\n",
    "    return (A, B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testons."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(6, 10)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A1, B = imker(A)\n",
    "prnt(A1)\n",
    "print()\n",
    "prnt(B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 Noyau, image"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tout a été dit : on appelle `imker`, qui renvoie deux matrices $A_1$ et $B$. Pour obtenir une base de $Im f$ on récupère les colonnes non nulles de $A_1$. Pour obtenir une base de $\\ker f$, récupère les colonnes de $B$ qui correspondent aux colonnes nulles de $A_1$. Pourquoi cela fonctionne-t-il ?\n",
    "\n",
    "Les opérations effectuées sur $B$ ne changent pas son rang. Or, $B=I$ au début de notre algorithme. La matrice renvoyée est donc inversible. De plus, par le théorème du rang, le nombre de colonnes nulles de $A_1$ est égal à $\\dim\\ker f$. En récupérant les colonnes correspondantes de $B$ on obtient donc une famille libre de $\\ker f$ dont le cardinal est justement la dimension du noyau de $f$, c'est à dire une base."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def noyau(A):\n",
    "    A, B = imker(A)\n",
    "    return transp([col(B, k) for k in col_nulles(A)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def image(A):\n",
    "    A, B = imker(A)\n",
    "    return transp([col(A, k) for k in range(nbcol(A)) if not (est_col_nulle(A, k))])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `col` renvoie la __liste__ des coefficients de la $j$ème colonne de $A$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def col(A, j):\n",
    "    return [A[i][j] for i in range(nblig(A))]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `est_col_nulle` teste si la $j$ème colonne de $A$ ne contient que des zéros."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_col_nulle(A, j):\n",
    "    for i in range(nblig(A)):\n",
    "        if A[i][j] != 0: return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `col_nulles` renvoie la liste des numéros des colonnes nulles de $A$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def col_nulles(A):\n",
    "    return [j for j in range(nbcol(A)) if est_col_nulle(A, j)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testons sur notre exemple habituel."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(6, 10)\n",
    "prnt(noyau(A))\n",
    "print()\n",
    "prnt(image(A))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 Vérifications"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici une fonction calculant le produit de deux matrices $A$ et $B$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prodmat(A, B):\n",
    "    p, q = nblig(A), nbcol(A)\n",
    "    q1, r= nblig(B), nbcol(B)\n",
    "    if q1 != q: raise Exception('Matrices incompatibles')\n",
    "    C = [q * [0] for i in range(p)]\n",
    "    for i in range(p):\n",
    "        for j in range(r):\n",
    "            for k in range(q):\n",
    "                C[i][j] += A[i][k] * B[k][j]\n",
    "    return C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(8, 12)\n",
    "prnt(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "B = noyau(A)\n",
    "prnt(B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le produit $A B$ devrait être nul puisque (matriciellement) les colonnes de $B$ sont dans le noyau de $A$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prnt(prodmat(A, B))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "CQFD :-)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Équations cartésiennes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 Bases et équations cartésiennes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $F$ un sous-espace vectoriel de $\\mathbb R^q$ de dimension $r$. Il existe essentiellement deux façons de se donner $F$.\n",
    "\n",
    "- Par une base.\n",
    "- Par un ensemble d'équations cartésiennes.\n",
    "\n",
    "Deux questions se posent :\n",
    "\n",
    "- Étant donnée une base de $F$, comment obtenir un ensemble minimal d'équations cartésiennes (la théorie nous annonce $q-r$ équations) ?\n",
    "- Étant donné un ensemble minimal d'équations cartésiennes de $F$, comment en obtenir une base ?\n",
    "\n",
    "__Remarque__ : Nous allons bientôt être frappés de plein fouet par le problème des __matrices vides__. Imaginons que $F=\\{0\\}$. Une base de $F$ est la famille vide, représentée par la matrice $[]$ qui a zéro colonne. Oui, mais combien de lignes a-t-elle ? On ne sait pas. Et pourtant, cette information est vitale, puisqu'elle nous donne la dimension de l'espace $E$ tout entier. Même problème avec les familles d'équations cartésiennes : L'espace tout entier est représenté par zéro équation, donc par une matrice de zéro ligne. Et nous ne savons plus quelle est sa dimension. Nous devrons donc, lors de l'écriture de nos fonctions, prévoir ce cas troublant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Bases vers équations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La théorie nous dit que $F$, sev de dimension $r$ d'un espace $E$ de dimension $q$, est l'intersection de $q-r$ hyperplans $H_1,\\ldots,H_{q-r}$. Comment obtenir des équations de tels hyperplans ? Soit $\\mathcal F =(x_1,\\ldots,x_{r})$ une base de $F$. Soient $\\varphi_1,\\ldots,\\varphi_{q-r}$ $q-r$ formes linéaires non nulles dont les hyperplans cherchés sont les noyaux. Soit $f=(\\varphi_1,\\ldots,\\varphi_{q-r})$. L'appplication $f$ est linéaire de $E$ vers $\\mathbb R^{q-r}$ et son noyau est précisément $F$. Notons $A$ la matrice de $f$ dans une base  de $E$ et la base canonique de $\\mathbb R^{q-r}$. Notons $B$ la matrice de $\\mathcal F$ dans la base de $E$ susnommée. On a alors $AB=0$, ou encore\n",
    "\n",
    "$$B^TA^T=0$$\n",
    "\n",
    "où le $T$ désigne la transposition. Ainsi, les colonnes de $A^T$ sont les matrices dans la base de $E$ de vecteurs du noyau de $B^T$. Soit $g\\in\\mathcal L(\\mathbb R^{q-r}, E)$ dont la matrice dans les bases (toujours les mêmes) de $E$ et $\\mathbb R^{q-r}$ est $B^T$. Alors $A^T$ est la matrice d'une base du noyau de $g$.\n",
    "\n",
    "Or, le théorème du rang nous dit que $\\dim\\ker g +rg\\ g = \\dim E = q$. Donc, $\\dim\\ker g = q-r$. Nous obtenons exactement ce que nous cherchions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3 Mise en pratique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Conclusion de ce qui précède, nous savons déjà trouver  des équations cartésiennes d'un sev. Il suffit d'utiliser la fonction `noyau`.\n",
    "\n",
    "La fonction `base_vers_eq` ci_dessous prend en paramètre une matrice $B$ de taille $q\\times r$ censée représenter une base (une famille génératrice fonctionne aussi) d'un sous-espace vectoriel $F$ de $\\mathbb R^q$ de dimension $r$. Elle renvoie les coefficients d'une famille d'équations cartésiennes de $F$.\n",
    "\n",
    "__Remarque__ : Cette fonction __ne peut pas__ fonctionner si la matrice $B$ est vide, puisque dans ce cas on ne connaît pas la dimension de l'espace dans lequel on travaille. Voir une astuce dans les exemples qui suivent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def base_vers_eq(B):\n",
    "    C = noyau(transp(B))\n",
    "    return transp(C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.3.1 Exemples basiques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Considérons la droite $D$ de $\\mathbb R^3$ engendrée par le vecteur $(1,2,3)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = transp([[1, 2, 3]])\n",
    "prnt(base_vers_eq(A))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une famille d'équations de $D$ est donc\n",
    "\n",
    "$$-2x+y=0$$\n",
    "$$-3x+z=0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reprenons notre exemple fétiche. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(3, 3)\n",
    "prnt(base_vers_eq(image(A)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'image de l'endomorphisme associé à $A$ est le plan d'équation $x-2y+z=0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(5, 7)\n",
    "B = noyau(A)\n",
    "prnt(B)\n",
    "print()\n",
    "eq = base_vers_eq(B) \n",
    "prnt(eq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette fois-ci, le noyau de l'application linéaire de $\\mathbb R^7$ vers $\\mathbb R^5$ associée à $A$ est le sous-espace vectoriel de $\\mathbb R^7$ de dimension 5 (deux équations !) d'équations\n",
    "\n",
    "$$6x_1+5x_2+4x_3+3_4+2x_5+x_6=0$$\n",
    "$$5x_1+4x_2+3x_3+2_4+x_5-x_7=0$$\n",
    "\n",
    "Une vérification ? Facile ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prnt(prodmat(eq, B))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'espace tout entier est décrit par la famille vide d'équations cartésiennes. Cela fonctionne-t-il ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "E = eye(5)\n",
    "base_vers_eq(E)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oui, mais impossible à partir de cela de retrouver $E$ : nous avons perdu sa dimension.\n",
    "\n",
    "À l'autre extrémité, quelles sont les équations de l'espace nul ? Une description de celui-ci par la base vide ne fonctionnera pas puisqu'on ne sait plus quelle est la dimension de l'espace entier. En revanche, en écrivant que le vecteur nul engendre l'espace nul, tout fonctionne."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "F = transp([[0, 0, 0, 0]])\n",
    "prnt(base_vers_eq(F))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le sev nul de $\\mathbb R^4$ est donné par les équations $x=y=z=t=0$, ce qui, avouons-le, est logique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 4.3.2 Un hyperplan de $\\mathbb R^4$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $H$ l'hyperplan de $\\mathbb R^4$ engendré par les vecteurs $(1, 4, 2, 7)$, $(8, 6, 5, 13)$ et $(7,3,11, 1)$. Trouvons une équation cartésienne de $H$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "U = [1, 4, 2, 7]\n",
    "V = [8, 6, 5, 13]\n",
    "W = [7, 3, 11, 1]\n",
    "B = transp([U, V, W])\n",
    "Phi = base_vers_eq(B)\n",
    "prnt(Phi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vérifions :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prnt(prodmat(Phi, B))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4 Équations cartésiennes vers bases"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $M\\in\\mathcal M_{(q-r)q}(\\mathbb R)$ une matrice dont les lignes sont les coefficients des équations cartésiennes bans la base $\\mathcal B$ d'un sev $F$ de l'espace vectoriel $E$. Soit $x\\in E$. Soit $X$ la matrice de $x$ dans la base $\\mathcal B$. Le vecteur $x$ est dans $F$ si et seulement si $MX=0$. En clair, trouver une base de $F$ c'est trouver une base du noyau d'une certaine application linéaire associée à $M$. En très clair, il n'y a quà utiliser la fonction `noyau`.\n",
    "\n",
    "La fonction `eq_vers_base` prend en paramètre une matrice dont les ligne sont les coefficients des équations cartésiennes d'un sev $F$ de $E$. Elle renvoie une base de $F$. En fait, `eq_vers_base` = `noyau`.\n",
    "\n",
    "__Remarque__ : Cette fonction __ne peut pas fonctionner__ lorsque la famille d'équations est vide, c'est à dire lorsque le sev cherché est l'espace entier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def eq_vers_base(E):\n",
    "    return noyau(E)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit, par exemple, l'hyperplan de $\\mathbb R^4$ d'équation $2x+3y+6z+t=0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "prnt(eq_vers_base([[2, 3, 6, 1]]))    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une base de $F$ est $((-3,2,0,0), (-3,0,1,0), (-1,0,0,2))$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = exemple(6, 8)\n",
    "B = noyau(A)\n",
    "prnt(B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "E = base_vers_eq(B)\n",
    "prnt(E)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "B1 = eq_vers_base(E)\n",
    "prnt(B1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Opérations sur les sous-espaces vectoriels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1 Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous sommes maintenant capables de nous donner un sev $F$ d'un espace vectoriel $E$ :\n",
    "- Au moyen d'une base de $F$.\n",
    "- Au moyen d'une famille d'équations cartésiennes de $F$.\n",
    "\n",
    "Dans ce qui suit nous allons voir qu'il est désormais facile de calculer des sommes, des intersections, de sev, ou de décider d'inclusions ou d'égalités de sev.\n",
    "\n",
    "__Remarque__ : Nous supposerons que nos sev __sont donnés par une famille génératrice__. S'ils sont donnés par une famille d'équations cartésiennes, il suffit d'appeler `base` pour en obtenir une base. Si l'on en veut une base et pas seulement une famille génératrice il suffit d'appeler la fonction `image`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2 Dimension"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La dimension d'un sev est le nombre de vecteurs d'une base. Remarquer le traitement séparé de l'espace nul."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dimension(F):\n",
    "    if F == []: return 0\n",
    "    else:\n",
    "        return nbcol(image(F))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3 Somme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soient $F$, $G$ deux sev de $E$ donnés par une famille génératrice. Il suffit d'accoler les deux matrices représentant $F$ et $G$ \"l'une à côté de l'autre\" et d'appeler la fonction `image` pour obtenir une base de $F+G$. On examine à part le cas où l'un des sev est nul."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def somme(F, G):\n",
    "    if F == []: return G\n",
    "    elif G == []: return F\n",
    "    else:\n",
    "        A = transp(transp(F) + transp(G))\n",
    "        return image(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "F = transp([[1, 1, 2], [1, 0, 3]])\n",
    "G = transp([[1, -1, 1], [1, 2, 3]])\n",
    "prnt(somme(F, G))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.4 Intersection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soient $F$, $G$ deux sev de $E$ donnés par une famille génératrice. Pour obtenir une base de $F\\cap G$, il suffit de\n",
    "\n",
    "- Déterminer avec la fonction `eq_cart` des familles d'équations cartésiennes de $F$ et $G$.\n",
    "- D'accoler ces matrices \"l'une au-dessus de l'autre\" : la matrice obtenue est la matrice d'une famille d'équations cartésiennes de $F\\cap G$.\n",
    "- D'appeler la fonction `base`.\n",
    "\n",
    "On examine bien sûr à part le cas où l'un des deux espace est nul. Dans ce cas, l'intersection est l'espace nul. On renvoie la famille vide.\n",
    "\n",
    "Il faut également régler le cas où $F=G=E$. Dans ce cas, la matrice $A$ ci-dessous est vide, on renvoie alors la matrice identité, base de $E$, dont on connaît la taille en regardant $F$ ou $G$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def intersect(F, G):\n",
    "    if F == [] or G == []: return []\n",
    "    else:\n",
    "        A = base_vers_eq(F) + base_vers_eq(G)\n",
    "        if A == []:\n",
    "            if F != []: q = nblig(F)\n",
    "            else: q = nblig(G)\n",
    "            return eye(q)\n",
    "        else:\n",
    "            return eq_vers_base(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "F = transp([[1, 3, 3], [4, 5, 6]])\n",
    "G = transp([[1, -1, 0],[1, 0, 2]])\n",
    "prnt(intersect(F, G))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "F = []\n",
    "G = transp([[1, -1, 0]])\n",
    "prnt(intersect(F, G))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.5 Inclusion, égalité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soient $F$ et $G$ deux sev de $E$. Comment décider si $F\\subset G$ ? C'est facile, puisque \n",
    "\n",
    "$$F\\subset G \\Longleftrightarrow \\dim(F\\cap G)=\\dim F$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inclus(F, G):\n",
    "    return dimension(intersect(F, G)) == dimension(F)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "F = transp([[1, 1, 1]])\n",
    "G = transp([[1, 2, 3], [4, 5, 6]])\n",
    "inclus(F, G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'égalité de deux sev est alors immédiate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def egaux(F, G):\n",
    "    return inclus(F, G) and dimension(F) == dimension(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "F = transp([[7, 8, 9], [10, 11, 12]])\n",
    "G = transp([[1, 2, 3], [4, 5, 6]])\n",
    "egaux(F, G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici un dernier exemple où les deux espaces $F$ et $G$ sont égaux à $\\mathbb R^5$, cas très particulier de la fonction `intersect`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "F = exemple(5, 9)\n",
    "G = exemple(5, 12)\n",
    "egaux(F, G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.6 Somme directe, supplémentarité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Deux sev sont en somme directe si et seulement si leur intersection est $\\{0\\}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def somme_directe(F, G):\n",
    "    return dimension(intersect(F, G)) == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Deux sev sont supplémentaires si et seulement si\n",
    "- Ils sont en somme directe, et\n",
    "- La somme de leurs dimension est la dimension de l'espace.\n",
    "\n",
    "Si $F$ et $G$ sont définis par la famille vide, il est impossible de trancher. En effet, si l'espace $E$ est l'espace nul alors ils sont supplémentaires. Sinon ils ne le sont pas. Mais on n'a aucun moyen de connaître la dimension de $E$ à partir des données !\n",
    "\n",
    "Si, en revanche, l'un des deux sev est différent de $\\{0\\}$, la dimension de l'espace est le nombre de lignes de la matrice qui le définit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dim_espace(F):\n",
    "    if F == []: raise Exception('Indetermine')\n",
    "    else: return nblig(F)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def supplementaires(F, G):\n",
    "    if F == [] and G == []: raise Exception('Indetermine')\n",
    "    elif F == []: return dimension(G) == nblig(G)\n",
    "    else:\n",
    "        return somme_directe(F, G) and dimension(F) + dimension(G) == dim_espace(F)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "F = transp([[1, 2, 3]])\n",
    "G = transp([[7, 5, 2], [6, 0, 4]])\n",
    "supplementaires(F, G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.7 Bilan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'espace nul et l'espace tout entier nous ont donné un peu de fil à retordre dans les dernières fonctions que nous avons écrites. Mais nous avons réussi à nous en sortir sauf dans un seul et unique cas. Nous ne saurons hélas jamais si $\\{0\\}\\oplus \\{0\\}=E$ :-)."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.8.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}