#!/usr/bin/env python
# coding: utf-8

# <div class="alert alert-block alert-info">
# <center><font size=5><b>DL n°3 (algèbre linéaire) : Éléments de correction</b></font></center></div>

# In[1]:


get_ipython().run_line_magic('matplotlib', 'inline')


# In[2]:


import numpy as np
import matplotlib.pyplot as plt
from numpy.polynomial import Polynomial
import numpy.linalg as alg


# **Énoncé :**
# >Soient $P \in \mathbb{C}_{p}[X], Q \in \mathbb{C}_{q}[X]$ et $u(A, B)=A P+B Q$ définie sur $\mathbb{C}_{q-1}[X] \times \mathbb{C}_{p-1}[X]$.
# >
# >Soit $\mathscr B=\left((1,0), \ldots,\left(X^{q-1}, 0\right),(0,1), \ldots,\left(0, X^{p-1}\right)\right)$, base de $\mathbb{C}_{q-1}[X] \times \mathbb{C}_{p-1}[X]$.
# > 1. Donner la matrice $M_{P, Q}$ de $u$ dans $\mathscr B$ et la base canonique de $\mathbb C_{p+q-1}[X]$ en fonction des coefficients de $P$ et $Q$.
# > 2. Écrire un programme Python qui prend les polynômes $P$ et $Q$ en paramètres et renvoie la matrice $M_{P,Q}$.
# > 3. On choisit $P(X)=X^{4}+X^{3}+1$ et $Q(X)=X^{3}-X+1$. Montrer qu'il existe un unique $\left(A_{0}, B_{0}\right) \in \mathbb{C}_{2}[X] \times \mathbb{C}_{3}[X]$ tel que $A_{0} P+B_{0} Q=1$
# > 4. On pose, pour $t\in\mathbb R$, $P=(X-1)(X-2)(X+2)$ et $Q_{t}=X(X+1)(X-t)$.
# >
# >Tracer sur $[-2,1 ; 2,1]$, la fonction $d(t)=\operatorname{det}\left(M_{P Q_{t}}\right)$.
# >
# >Expliquer les racines observées.

# **Correction :**

# $\fbox{$\textbf{ Q1. }$}$ On pose $\displaystyle P=\sum_{k=0}^{p} a_k X^k$ et $\displaystyle Q=\sum_{k=0}^q b_k X^k$. On obtient la matrice suivante, de taille $p+q$, appelée *matrice de Sylvester* de $P$ et $Q$ :
# 
# $$M_{P,Q} = \begin{pmatrix} 
# a_{0} & 0 & \cdots & 0 & b_{0} & 0 & \cdots & 0 \\ a_{1} & a_{0} & \cdots & 0 & b_{1} & b_{0} & \cdots & 0 \\ a_{2} & a_{1} & \ddots & 0 & b_{2} & b_{1} & \ddots & 0 \\ \vdots & \vdots & \ddots & a_{0} & \vdots & \vdots & \ddots & b_{0} \\ a_{p} & a_{p-1} &  & \vdots & b_{q} & b_{q-1} & \cdots & \vdots \\ 0 & a_{p} & \ddots & \vdots & 0 & b_{q} & \ddots & \vdots \\ \vdots & \vdots & \ddots & a_{p-1} & \vdots & \vdots & \ddots & b_{q-1} \\ 0 & 0 &  & a_{p} & 0 & 0 & \cdots & b_{q}
# \end{pmatrix}
# $$
# 

# $\fbox{$\textbf{ Q2. }$}$ On peut écrire la fonction Python suivante :

# In[3]:


def M(P,Q):
    p=P.degree()
    q=Q.degree()
    M=np.zeros((p+q,p+q))
    for j in range(q):
        for i in range(p+1):
            M[i+j,j]=P.coef[i]
    for j in range(p):
        for i in range(q+1):
            M[i+j,q+j]=Q.coef[i]
    return M


# $\fbox{$\textbf{ Q3. }$}$ Avec $P(X)=X^{4}+X^{3}+1$ et $Q(X)=X^{3}-X+1$, on obtient $\det M_{P,Q} = 1$ :

# In[4]:


P=Polynomial([1,0,0,1,1])
Q=Polynomial([1,-1,0,1])
alg.det(M(P,Q))


# Ainsi, $u$ est un isomorphisme ; en particulier $1$ admet un unique antécédant par $u$, $i.e.$ :
# 
# $$\exists ! (A_0,B_0) \in \mathbb C_{2}[X]\times \mathbb C_{3}[X],\ 1 = u(A_0,B_0) = A_0P+B_0Q.$$

# $\fbox{$\textbf{ Q4. }$}$ Avec $P=(X-1)(X-2)(X+2)$ et $Q_{t}=X(X+1)(X-t)$, on obtient :

# In[5]:


def d(t):
    X=Polynomial([0,1])
    P=(X-1)*(X-2)*(X+2)
    Q=X*(X+1)*(X-t)
    return alg.det(M(P,Q))


# In[6]:


T=np.linspace(-2.1,2.1,100)
D=[d(t) for t in T]
plt.plot(T,D)
plt.grid()
plt.show()


# On peut donc conjecturer que la fonction $d$ s'annule en $1$ et $\pm 2$, et est non nulle ailleurs. Prouvons-le.

# - Si $t\notin \{1,-2,2\}$ :
# >Les polynômes $P$ et $Q_t$ n'ont aucune racine commune. Montrons qu'alors $u$ est un isomorphisme.
# >
# >Supposons $u$ non injectif. Alors : $\exists (A,B)\in \mathbb C_2[X]\times \mathbb C_2[X], AP+BQ_t=0$.
# >
# >On a alors $AP = -BQ_t$. Puisque $P$ et $Q_t$ n'ont aucune racine commune, toutes les racines de $P$ (avec multiplicité) sont racines de $B$, d'où $P \mid B$. En particulier, $\deg B \geqslant \deg P$, contradiction.
# >
# >Ainsi, $u$ est injectif et est donc un isomorphisme (par l'égalité des dimensions des espaces de départ et d'arrivée).
# >
# >En particulier, $d(t) = \det (M_{P,Q_t}) \neq 0$, comme voulu.
# 
# 
# - Si $t\in \{1,-2,2\}$ :
# > Alors $P$ et $Q_t$ ont exactement une racine commune. On écrit :
# $$ 
# \begin{cases}
# P &\!\!\!\!\!\!= (X-t)\tilde{P}\\
# Q_t &\!\!\!\!\!\!= (X-t) \tilde{Q_t}
# \end{cases}
# $$
# avec $\tilde{P}$ et $\tilde{Q_t}$ sans racine commune. Alors $\tilde Q_t P - \tilde P Q = 0$, donc $(\tilde Q_t,-\tilde P)\in \ker u$. Puisque $(\tilde Q_t,-\tilde P)\neq (0,0)$, on vient de prouver que $u$ n'est pas injectif, et donc $d(t)=\det M_{P,Q_t}= 0$.

# **Remarque :** on peut même montrer que :
# $$\forall t\in\mathbb R,\  d(t) = -24(t-1)(t-2)(t+2)$$

# **Remarque :** le déterminant $\det (M_{P,Q})$ est appelé *résultant* des polynômes $P$ et $Q$, et est noté $\operatorname{Res}(P,Q)$.
# 
# La preuve ci-dessus s'adapte dans le cas général, et a on donc le résultat suivant :
# $$\forall P,Q \in \mathbb C[X],\ \left(\operatorname{Res}(P,Q)=0 \iff \textrm{$P$ et $Q$ ont une racine commune dans $\mathbb C$.} \right)$$
#