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

# <div class="alert alert-block alert-info">
# <center><font size=5><b>DL n°4 (éléments propres ; réduction) : Éléments de correction</b></font></center></div>

# In[1]:


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


# In[1]:


import numpy as np
import numpy.linalg as alg


# $\require{color}$
# $%\fcolorbox{red}{yellow}{Writing on yellow background!}$
# $\newcommand{\myfbox}[1]{\fcolorbox{red}{white}{$\textrm{#1}$}}$
# $\require{stmaryrd}$
# $\require{cancel}$
# $\newcommand{\ient}{[\![}$
# $\newcommand{\fient}{]\!]}$
# $\newcommand{\R}{\mathbb R}$
# $\newcommand{\K}{\mathbb K}$
# $\newcommand{\N}{\mathbb N}$
# $\newcommand{\Z}{\mathbb Z}$
# $\newcommand{\id}{\operatorname{Id}}$
# $\newcommand{\rg}{\mathrm{rg}}$
# $\newcommand{\dis}{\displaystyle}$
# $\newcommand{\fonction}[5]{#1\ \colon \left\{\begin{array}{ccl}#2 & \longrightarrow & #3\\#4 & \longmapsto & #5\end{array}\right.}$
# $\newcommand{\tendvers}[1]{\xrightarrow[#1]{}}$

# L'énoncé qui suit est très légèrement adapté (petite indication) du sujet d'oral disponible sur le [site de Centrale](https://www.concours-centrale-supelec.fr/CentraleSupelec/SujetsOral/PC/2015-025-PC-Mat2.pdf).

# **Énoncé :**
# 
# Soient $a_1,\dots,a_n\in\R$ deux à deux distincts.
# 
# On considère la matrice $A\left(a_{1}, . ., a_{n}\right)$ suivante :
# 
# $$
# A\left(a_{1}, . ., a_{n}\right)=\begin{pmatrix}
# 0 & a_{1} & a_{2} & \cdots & a_{n-1} & a_{n} \\
# a_{1} & 0 & a_{2} & \cdots & a_{n-1} & a_{n} \\
# a_{1} & a_{2} & 0 & \cdots & a_{n-1} & a_{n} \\
# \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
# a_{1} & a_{2} & a_{3} & \cdots & a_{n} & 0
# \end{pmatrix}
# $$
# 
# **1.** On suppose dans cette question que $n=4$.
# 
# $\qquad$ **a.** Écrire une fonction Python de paramètre $(a, b, c, d)$ qui calcule la matrice $A(a, b, c, d)$.
#     
# $\qquad$ **b.** Donner les valeurs propres des matrices $A(1,2,3,4), A(4,2,3,1)$ et $A(-3,-1,1,2)$.
#     
# $\qquad\quad$En déduire une conjecture sur les valeurs propres de la matrice $A(a, b, c, d)$.
#     
# $\qquad$ **c.** Donner les vecteurs propres des matrices $A(1,2,3,4), A(4,2,3,1)$ et $A(-3,-1,1,2)$.
#     
# $\qquad\quad$*On pourra faire des rapports des coordonnées d'un vecteur pour l'identifier. On pourra par exemple quotienter par la dernière composante.*
# 
# $\qquad\quad$Que peut-on dire de la matrice dans ces trois cas?
#     
# **2.** Montrer les conjectures précédentes dans le cas général.
# 
# *Indication :* on pourra chercher des vecteurs propres pour la valeur propre $-a_k$ sous la forme $\begin{pmatrix}\alpha\\\vdots\\\alpha\\\beta\\\vdots\\\beta\end{pmatrix}$ avec le nombre adéquat de $\alpha$ intuité expérimentalement.
# 
# **3.** On suppose que les réels $\left(a_{k}\right)_{1\leqslant k\leqslant n}$ sont strictement positifs et que $\sum\limits_{k=1}^{n} a_{k}=1$.
# 
# $\quad$Que peut-on dire de la suite $\big(A\left(a_{1}, . ., a_{n}\right)^{m}\big)_{m \in \mathbb{N}} ?$

# **Correction :**

# $\fbox{$\textbf{Q1}$}$ On peut généraliser la fonction demandée à une liste de taille $n$ quelconque :

# In[17]:


def A(L):
    L=np.array(L)
    M=[]
    for i in range(5):
        M.append(np.insert(L,i,0))
    return np.array(M)


# In[73]:


A1=A([1,2,3,4])
print(A1)
print("valeurs propres :",alg.eigvals(A1))
print("vecteurs propres :")
print(alg.eig(A1)[1])


# On peut rendre les vecteurs propres pour les rendre plus lisibles, on les normalisant :

# In[155]:


sp=alg.eig(A1)[0]
vp=alg.eig(A1)[1]
print("valeur propre :",round(sp[0],2),"; vecteur propre :",vp[:,0]/vp[1,0])
print("valeur propre :",round(sp[1],2),"; vecteur propre :",vp[:,1]/vp[1,1])
print("valeur propre :",round(sp[2],2),"; vecteur propre :",3*vp[:,2]/vp[1,2])
print("valeur propre :",round(sp[3],2),"; vecteur propre :",7*vp[:,3]/vp[0,3])
print("valeur propre :",round(sp[4],2),"; vecteur propre :",2*vp[:,4]/vp[0,4])


# In[156]:


A2=A([4,2,3,1])
print(A2)
print("valeurs propres :",alg.eigvals(A2))
print("vecteurs propres :")
print(alg.eig(A2)[1])


# In[122]:


sp=alg.eig(A2)[0]
vp=alg.eig(A2)[1]
print("valeur propre :",round(sp[0],2),"; vecteur propre :",2*vp[:,0]/vp[1,0])
print("valeur propre :",round(sp[1],2),"; vecteur propre :",vp[:,1]/vp[1,1])
print("valeur propre :",round(sp[2],2),"; vecteur propre :",3*vp[:,2]/vp[1,2])
print("valeur propre :",round(sp[3],2),"; vecteur propre :",vp[:,3]/vp[0,3])
print("valeur propre :",round(sp[4],2),"; vecteur propre :",4*vp[:,4]/vp[0,4])


# In[132]:


A3=A([-3,-1,1,2])
print(A3)
print("valeurs propres :",alg.eigvals(A3))
print("vecteurs propres :")
print(alg.eig(A3)[1])


# In[152]:


sp=alg.eig(A3)[0]
vp=alg.eig(A3)[1]
print("valeur propre :",round(sp[0],2),"; vecteur propre :",vp[:,0]/vp[-1,0])
print("valeur propre :",round(sp[1],2),"; vecteur propre :",vp[:,1]/vp[-1,1])
print("valeur propre :",round(sp[2],2),"; vecteur propre :",vp[:,2]/vp[-1,2])
print("valeur propre :",round(sp[3],2),"; vecteur propre :",vp[:,3]/vp[-1,3])
print("valeur propre :",round(sp[4],2),"; vecteur propre :",vp[:,4]/vp[-1,4])


# On peut émettre la conjecture suivante :
# 
# $$\myfbox{$ \mathrm{Sp}\big(A(a_1,\dots,a_n)\big) = \left\{-a_1,\dots,-a_n,\sum\limits_{k=1}^n a_k\right\}$}$$

# Dans les 2 premiers cas ci-dessus, la somme des dimensions des espaces propres est égale à la taille de la matrice $A(a_1,\dots,a_n)$, donc $\myfbox{$A(1,2,3,4)$ et $A(4,2,3,1)$ sont diagonalisables}$ sur $\R$.
# 
# Dans le dernier cas, $1$ est valeur propre double, mais l'espace propre associé est de dimension $1$, donc $\myfbox{$A(-3,-1,1,2)$ n'est pas diagonalisable}$ .

# Plus généralement, on peut conjecturer que :
# 
# $\bullet$ Si $\sum\limits_{k=1}^n a_k\notin \left\{-a_1,\dots,-a_n\right\}$, alors $A(a_1,\dots,a_n)$ est diagonalisable
# 
# $\bullet$ Si $\sum\limits_{k=1}^n a_k\in \left\{-a_1,\dots,-a_n\right\}$, alors $A(a_1,\dots,a_n)$ n'est pas diagonalisable.

# $\fbox{$\textbf{Q2}$}$ Montrons les conjectures énoncés ci-dessus.

# $\bullet$ On peut calculer le polynôme caractéristique $\chi_A$ de $A(a_1,\dots,a_n)$ :
# 
# \begin{align*}
# \chi_A(X) &= \begin{vmatrix}
# X & -a_{1} & -a_{2} & \cdots & -a_{n-1} & -a_{n} \\
# -a_{1} & X & -a_{2} & \cdots & -a_{n-1} & -a_{n} \\
# -a_{1} & -a_{2} & X & \cdots & -a_{n-1} & -a_{n} \\
# \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
# -a_{1} & -a_{2} & -a_{3} & \cdots & -a_{n} & X
# \end{vmatrix}\\
# &= \left(X-\sum\limits_{k=1}^n a_k\right)\begin{vmatrix}
# 1 & -a_{1} & -a_{2} & \cdots & -a_{n-1} & -a_{n} \\
# 1 & X & -a_{2} & \cdots & -a_{n-1} & -a_{n} \\
# 1 & -a_{2} & X & \cdots & -a_{n-1} & -a_{n} \\
# \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
# 1 & -a_{2} & -a_{3} & \cdots & -a_{n} & X
# \end{vmatrix} \qquad C_1\leftarrow C_1+\dots+C_{n+1}\\
# &= \left(X-\sum\limits_{k=1}^n a_k\right)\begin{vmatrix}
# 1 & -a_{1} & -a_{2} & \cdots & -a_{n-1} & -a_{n} \\
# 0 & X+a_1 & 0 & \cdots & 0 & 0 \\
# 0 & a_1-a_{2} & X+a_2 & \cdots & 0 & 0 \\
# \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
# 0 & a_1-a_{2} & a_1-a_{3} & \cdots & a_1-a_{n} & X+a_n
# \end{vmatrix} \qquad \forall i\in\ient2,n+1\fient,\ L_i\leftarrow L_i-L_1\\
# &= \left(X-\sum\limits_{k=1}^n a_k\right)\begin{vmatrix}
# X+a_1 & 0 & \cdots & 0 & 0 \\
# a_1-a_{2} & X+a_2 & \cdots & 0 & 0 \\
# \vdots & \vdots & \vdots & \vdots & \vdots \\
# a_1-a_{2} & a_1-a_{3} & \cdots & a_1-a_{n} & X+a_n
# \end{vmatrix} \qquad \textrm{(en développant par rapport à $C_1$)}\\
# &= \left(X-\sum\limits_{k=1}^n a_k\right) \left(X+a_1\right)\dots \left(X+a_n\right)\qquad\textrm{(déterminant d'une matrice triangulaire)}
# \end{align*}

# On a prouvé que $\myfbox{$ \mathrm{Sp}\big(A(a_1,\dots,a_n)\big) = \left\{-a_1,\dots,-a_n,\sum\limits_{k=1}^n a_k\right\}$}$ .

# $\bullet$ On détermine les espaces propres associés :
# 
# 
# $\circ$ On calcule sans peine ${A}(a_1,\dots,a_n)\left(\begin{array}{c}1 \\ \vdots \\ 1\end{array}\right)=\left(\sum\limits_{i=1}^{n} a_{i}\right)\left(\begin{array}{c}1 \\ \vdots \\ 1\end{array}\right)$ donc $\sum\limits_{i=1}^{n} a_{i}$ est valeur propre et $\left(\begin{array}{c}1 \\ \vdots \\ 1\end{array}\right)$ est un vecteur propre associé.
# 
# $\circ$ On calcule maintenant ${A}(a_1,\dots,a_n)\left(\begin{array}{c}\alpha \\ \vdots\\ \alpha \\ \beta \\ \vdots \\ \beta\end{array}\right)=\left(\begin{array}{c}\alpha\left(a_{1}+\cdots+a_{k-1}\right)+\beta\left(a_{k}+\cdots+a_{n}\right) \\ \vdots \\ \alpha\left(a_{1}+\cdots+a_{k-1}\right)+\beta\left(a_{k}+\cdots+a_{n}\right) \\ \alpha\left(a_{1}+\cdots+a_{k}\right)+\beta\left(a_{k+1}+\cdots+a_{n}\right) \\ \vdots \\ \alpha\left(a_{1}+\cdots+a_{k}\right)+\beta\left(a_{k+1}+\cdots+a_{n}\right)\end{array}\right)$ (avec $k$ $\alpha$ dans le vecteur).
# 
# Cherchons $\alpha$ et $\beta$ pour que ce vecteur soit propre pour la valeur propre $-a_{k}$ ; il faut et il suffit que
# 
# $$
# \left\{\begin{array}{l}
# \alpha\left(a_{1}+\cdots+a_{k-1}\right)+\beta\left(a_{k}+\cdots+a_{n}\right)=-a_{k} \alpha \\
# \alpha\left(a_{1}+\cdots+a_{k}\right)+\beta\left(a_{k+1}+\cdots+a_{n}\right)=-a_{k} \beta
# \end{array} \Longleftrightarrow \alpha\left(a_{1}+\cdots+a_{k}\right)+\beta\left(a_{k}+\cdots+a_{n}\right)=0\right.
# $$
# 
# Lorsque $\left(a_{1}+\cdots+a_{k}, a_{k}+\cdots+a_{n}\right) \neq(0,0),-a_{k}$ est bien valeur propre pour le vecteur propre défini si dessus avec $\alpha=\left(a_{k}+\cdots+a_{n}\right)$ et $\beta=-\left(a_{1}+\cdots+a_{k}\right)$.

# $\bullet$ Étudions maintenant la diagonalisabilité :

# $\circ$ $\myfbox{Si $\sum\limits_{\ell=1}^n a_\ell\notin \left\{-a_1,\dots,-a_n\right\}$}$ :
# 
# alors $A(a_1,\dots,a_n)$ possède $n+1$ valeurs propres distinctes (et est de taille $n+1$), donc $\myfbox{$A(a_1,\dots,a_n)$ est diagonalisable}$ , et les vecteurs propres ont été déterminés ci-dessus.
# 
# *Remarque :* Si $\sum\limits_{\ell=1}^n a_\ell\notin \left\{-a_1,\dots,-a_n\right\}$, alors, avec les notations ci-dessus, $(\alpha,\beta)\neq(0,0)$ : sinon, on aurait $0=a_{1}+\cdots+a_{k}=-a_{k}-\cdots-a_{n}$, d'où $-a_k = \sum\limits_{\ell=1}^n a_\ell$.

# $\circ$ $\myfbox{Si $\sum\limits_{\ell=1}^n a_\ell\in \left\{-a_1,\dots,-a_n\right\}$}$ :
# 
# Alors les calculs précédents sont encore valides, sauf pour le calcul du vecteur propre de $-a_k = \sum\limits_{\ell=1}^n a_\ell$. Toutes les autres valeurs propres sont simples, et $-a_k$ est double.
# 
# On montre maintenant que la dimension de $E_{-a_k}$ vaut $1$, ce qui montre la non-diagonalisabilité de $A(a_1,\dots,a_n)$.
# 
# Il suffit pour cela de montrer que le rang de $A+a_k\mathrm{I}_n$ vaut $n$ (théorème du rang).
# 
# On suppose pour simplifier que $k=n$.

# Or :
# 
# \begin{align*}
# \rg (A+a_n\mathrm{I}_n) &= \rg \begin{pmatrix}
# a_n & a_{1} & a_{2} & \cdots & a_{n-1} & a_{n} \\
# a_{1} & a_n & a_{2} & \cdots & a_{n-1} & a_{n} \\
# a_{1} & a_{2} & a_n & \cdots & a_{n-1} & a_{n} \\
# \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
# a_{1} & a_{2} & a_{3} & \cdots & a_{n} & a_n
# \end{pmatrix}\\[5pt]
# &= \rg \begin{pmatrix}
# a_n & a_{1} & a_{2} & \cdots & a_{n-1} & 0 \\
# a_{1} & a_n & a_{2} & \cdots & a_{n-1} & 0 \\
# a_{1} & a_{2} & a_n & \cdots & a_{n-1} & 0 \\
# \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
# a_{1} & a_{2} & a_{3} & \cdots & a_{n} & 0
# \end{pmatrix}\qquad C_{n+1} \gets C_1+\dots+C_{n+1}\\[5pt]
# &= \rg \begin{pmatrix}
# a_n & a_1 & a_2 & \dots & a_{n-1} & 0\\
# a_1-a_n&a_n-a_1&  &  &  &0\\
#  & a_2-a_n&a_n-a_2&  & \dots&\vdots \\
# \\
#  &  &  &  & a_{n-1}-a_n&0
# \end{pmatrix}\qquad \begin{cases}
# L_{n+1}\gets L_{n+1}-L_{n}\\
# \vdots\\
# L_2 \gets L_2-L_1
# \end{cases}
# \end{align*}

# D'une part, puisque la dernière colonne est nulle, $\rg (A+a_n\mathrm{I}_n)\leqslant n$.
# 
# D'autre part, puisque les $n$ dernières lignes sont linéairement indépendantes (échelonnées, avec pivots non nuls par hypothèse), on obtient $\rg (A+a_n\mathrm{I}_n)=n$, comme voulu.

# $\fbox{$\textbf{Q3}$}$ Lorsque les $a_{i}$ sont strictement positifs, on dispose de $n+1$ valeurs propres deux à deux distinctes : les $-a_{k}$ et $\sum\limits_{\ell=1}^{n} a_{\ell}=1$.
# 
# Il existe donc ${P} \in \mathcal{M}_{n+1}(\mathbb{R})$ tel que :
# 
# $${A}\left(a_{1}, \ldots, a_{n}\right)={P} \operatorname{diag}\left(-a_{1}, \ldots,-a_{n}, 1\right) {P}^{-1}
# $$
# 
# où l'on a noté $\operatorname{diag}\left(-a_{1}, \ldots,-a_{n}, 1\right) =\begin{pmatrix}
# -a_1 &&&&\\
# &-a_2&&&\\
# &&\ddots&&\\
# &&&-a_n&\\\
# &&&&1
# \end{pmatrix}$.
# 
# 
# Ainsi, ${A}\left(a_{1}, \ldots, a_{n}\right)^m={P} \operatorname{diag}\Big(\left(-a_{1}\right)^{m}, \ldots,\left(-a_{n}\right)^{m}, 1\Big) {P}^{-1}$ et puisque les $a_{i}$ sont dans $] 0,1[$ :
# 
# $$\dis\lim_{m \rightarrow+\infty} {A}\left(a_{1}, \ldots, a_{n}\right)^{m}= P \operatorname{diag}(0, \ldots, 0,1) P^{-1}$$
# 
# 
# *Remarque :* il s'agit en fait de la matrice du projecteur sur le sous-espace propre associé à la valeur propre $1$, autrement dit sur $\mathrm{Vect}\left[\left(\begin{array}{l}1 \\ \vdots \\ 1\end{array}\right)\right]$, parallèlement à la somme directe des autres sous-espaces propres.