\documentclass[11pt, francais]{smfart}
\usepackage{amsfonts, amssymb, amsmath, latexsym}
\usepackage{mathptmx}
\usepackage[frenchb]{babel}

\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{textcomp}


\input xy
\xyoption{all}

\addtolength{\hoffset}{-25mm}
%\addtolength{\voffset}{-5mm}
\addtolength{\topmargin}{-30mm} \addtolength{\headsep}{5mm}
\addtolength{\textwidth}{40mm} \addtolength{\textheight}{50mm}

\newcommand{\rP}{\mathrm{P}}
\newcommand{\B}{\mathrm{B}}
\newcommand{\I}{\mathrm{I}}
\newcommand{\J}{\mathrm{J}}
\newcommand{\A}{\mathrm{A}}
\newcommand{\M}{\mathrm{M}}
\newcommand{\D}{\mathrm{D}}

\begin{document}
\noindent \textbf{Math III-Alg\`ebre - Automne 2007} \hfill \textbf{Universit\'e Claude Bernard Lyon 1}
\vspace{0.1cm}
\hrule

\vspace{0.5cm}

\begin{center}
{\bfseries Mise en bouche}
\end{center}

\vspace{0.5cm}

\noindent \textbf{* Exercice 1.} Un vecteur directeur de la droite $\Delta$ est $e=\left(\begin{array}{l} 5 \\ 3 \\ 1\end{array}\right)$. Comme la droite $\Delta$ n'est pas contenue dans le plan $\Pi$, $\mathbb{R}^3 = \Delta \oplus \Pi$.
\begin{enumerate}
\item La projection $u$ envoie le point $\rP$ de coordonn\'ees $\left(\begin{array}{l}x \\ y \\ z\end{array}\right)$ dans la base canonique sur le point $u(\rP)$ dont les coordonn\'ees $\left(\begin{array}{l} x' \\ y' \\ z'\end{array}\right)$ dans la base canonique sont caract\'eris\'es par les deux conditions suivantes : \\ (i) $\left(\begin{array}{l}x' \\ y' \\ z'\end{array}\right) - \left(\begin{array}{l}x \\ y \\ z\end{array}\right) \in \mathbb{R}\left(\begin{array}{l}5 \\ 3 \\ 1\end{array}\right)$ \\ (ii) $x'+3y'+5z'=0$.
    
\vspace{0.1cm}
    \textbf{Remarque} : \emph{la premi\`ere condition traduit le fait que le point $u(\rP)$ appartient \`a la droite parall\`ele \`a $\Delta$ passant par $\rP$ ; la seconde traduit l'appartenance du point $u(\rP)$ au plan $\Pi$.}
\vspace{0.1cm}

    Soit $\lambda \in \mathbb{R}$ tel que $\left(\begin{array}{l}x'-x \\ y'-y \\ z'-z\end{array}\right) = \lambda\left(\begin{array}{l}5 \\ 3 \\ 1\end{array}\right)$ ; on a alors $(x+5\lambda)+3(y+3\lambda)+5(z+\lambda)=0$, soit $\lambda = \frac{1}{19}(x+3y+5z)$, et donc
    $$\left\{\begin{array}{lll}x' & = & \frac{14}{19}x - \frac{15}{19}y - \frac{25}{19}z \\ y' & = & -\frac{3}{19}x + \frac{10}{19}y - \frac{15}{19}z \\ z' & = & -\frac{1}{19}x - \frac{3}{19}y + \frac{14}{19}z \end{array} \right.$$
    La matrice de $u$ dans la base canonique est par cons\'equent $$\frac{1}{19}\left(\begin{array}{lll}14 & -15 & -25 \\ -3 & 10 & -15 \\ -1 & -3 & 14\end{array}\right).$$
\item La restriction de $u$ au plan $\Pi$ (resp. \`a la droite $\Delta$) est l'identit\'e (resp. est identiquement nulle). Quelle que soit par cons\'equent la base $(\varepsilon_1, \varepsilon_2)$ du plan $\Pi$, $(\varepsilon_1, \varepsilon_2, e)$ est une base de $\mathbb{R}^3$ dans laquelle la matrice de $u$ est $$\left(\begin{array}{lll} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0\end{array}\right).$$
\end{enumerate}
\noindent \textbf{* Exercice 2.} \begin{enumerate} \item Si un vecteur $x$ de $\mathbb{C}^n$ s'\'ecrit sous la forme $x = x_1 + x_2$ avec $x_1 \in \mathrm{Ker}(u - \mathrm{id})$ et $x_2 \in \mathrm{Ker}(u + \mathrm{id})$, alors $u(x) = u(x_1) + u(x_2) = x_1 - x_2$ et donc $$x_1 = \frac{x+u(x)}{2}, \ x_2 = \frac{x-u(x)}{2}.$$ R\'eciproquement, comme $$\frac{x+u(x)}{2} \in \mathrm{Ker}(u-\mathrm{id}), \ \frac{x-u(x)}{2} \in \mathrm{Ker}(u+\mathrm{id}) \ \textrm{ et } x = \frac{x+u(x)}{2} + \frac{x-u(x)}{2}$$ pour tout vecteur $x$ de $\mathbb{C}^n$, l'espace $\mathbb{C}^n$ est la somme directe des sous-espaces vectoriels $\mathrm{Ker}(u - id)$ et $\mathrm{Ker}(u + id)$.
\item Si $u \neq \mathrm{id}$ et $u \neq -\mathrm{id}$, les deux sous-espaces vectoriels $\mathrm{Ker}(u - \mathrm{id})$ et $\mathrm{Ker}(u + \mathrm{id})$ de $\mathbb{C}^n$ sont de dimensions respectives $p$ et $q$ avec $1 \leq p,q \leq n-1$ ; comme la restriction de $u$ au premier (resp. au second) est l'identit\'e (resp. l'oppos\'ee de l'identit\'e), ces sous-espaces sont stables par $u$ et, si $(e_1, \ldots, e_p)$ (resp. $(e_{p+1}, \ldots, e_n)$ est une base du premier (resp. du second),la matrice de $u$ dans la base $(e_1, \ldots, e_n)$ de $\mathbb{C}^n$ est $$\left(\begin{array}{ll} \I_p & 0 \\ 0 & -\I_q\end{array} \right).$$ 
    \end{enumerate}

\noindent \textbf{* Exercice 3.}  \begin{enumerate} \item Calcul imm\'ediat. \item Le rang de la matrice $\B$, et donc de l'endomorphisme $u$, est $1$ ; on a en outre  $\mathrm{Im}(u) = \mathrm{Ker}(u) = \mathbb{R} \left(\begin{array}{l}1 \\ -1 \end{array} \right)$.
\item On a $u\left(\begin{array}{l}1 \\ 1\end{array}\right) = 2\left(\begin{array}{l}1 \\ -1\end{array}\right)$ et $u\left(\begin{array}{l}1 \\ -1\end{array}\right) = 0$ donc la matrice de $u$ dans la base $\left\{\left(\begin{array}{l}1 \\ -1\end{array}\right), \left(\begin{array}{l} 1\\ 1\end{array} \right) \right\}$ de $\mathbb{R}^2$ est $$\left(\begin{array}{ll} 0 & 2 \\ 0 & 0\end{array} \right).$$
\end{enumerate}

\noindent \textbf{* Exercice 4.}  \begin{enumerate}
\item $\A = b\J+(a-b)\I_n$.
\item On d\'emontre facilement par r\'ecurrence sur l'entier $k$ que $\J^k = n^{k-1} \J$ pour tout $k$. Comme les matrices $J$ et $\I_n$ commutent, \begin{eqnarray*} \A^k & = & (b\J + (a-b)\I_n)^k \\ & = & \sum_{\ell =0}^{k} \binom{k}{\ell} b^\ell (a-b)^{k - \ell}\J^\ell\I_n \\ & = & \sum_{\ell=1}^{k} \binom{k}{\ell} n^{\ell-1}(a-b)^{k-\ell} \J + (a-b)^k\I_n\\ & = & \frac{1}{n} \left[\sum_{\ell = 0}^{k} \binom{k}{\ell} (nb)^\ell(a-b)^{k - \ell} - (a-b)^k \right]\J + (a-b)^k \I_n \\ & = & \frac{1}{n} \left[(a+(n-1)b)^k - (a-b)^k \right]\J + (a-b)^k \I_n \end{eqnarray*}
\end{enumerate}

\noindent \textbf{* Exercice 5.}  \begin{enumerate}
\item Calcul imm\'ediat ; on trouve $\lambda = 1,\ \mu=4$.
\item Quel que soit l'entier $n \geq 1$, on note respectivement $\ell(n;p,p), \ell(n;p,q), \ell(n;q,p)$, $\ell(n;q,q)$ le nombre de chemins de longueur $n$ entre $p$ et $p$, $p$ et $q$, $q$ et $p$, $q$ et $q$. En observant qu'un chemin de longueur $n+1$ entre $p$ et $p$ est compos\'e d'un chemin de longueur $1$ entre $p$ et $p$ puis d'un chemin de longueur $n$ entre $p$ et $p$ ou bien d'un chemin de longueur $1$ entre $p$ et $q$ puis d'un chemin de longueur $n$ entre $q$ et $p$, on obtient la formule de r\'ecurrence
\begin{eqnarray*}\ell(n+1;p,p) & = & \ell(1;p,p)\ell(n;p,p) + \ell(1;p,q)\ell(n;q,p) \\
& = & 2\ell(n;p,p) + \ell(n;q,p). \end{eqnarray*}
Un raisonnement analogue conduit aux formules
$$\ell(n+1;p,q) = 2\ell(n;p,q) + \ell(n;q,q), \ \ell(n+1;q,p) = 3\ell(n;q,p) + 2\ell(n;p,p)$$ et $$\ell(n+1;q,q) = 3\ell(n;q,q) + 2\ell(n;p,q)$$
et on en d\'eduit imm\'ediatement les nombres demand\'es : il y a $$\ell(2; p,p) + \ell(2; p, q) + \ell(2 ; q,p) + \ell(2;q,q) = 32$$ chemins de longueur 2, $$\ell(3; p,p) + \ell(3; p, q) + \ell(3;q,p) + \ell(3;q,q) = 128$$ chemins de longueur 3 et $$\ell(; p,p) + \ell(4; p, q) + \ell(4 ; q,p) + \ell(4;q,q) = 512$$ chemins de longueur 4.
\item Il est plus facile de calculer directement ces puissances plut\^ot que d'utiliser $\D$ ; l'int\'er\^et de l'\'ecriture $\M = \rP^{-1} \D \rP$ appara\^{\i}t par contre si l'on veut une formule explicite pour $\M^n$. On obtient $$\M^2 = \left(\begin{array}{ll} 6 & 5 \\ 10 & 11 \end{array}\right), \ \M^3 = \left(\begin{array}{ll} 22 & 21 \\ 42 & 43 \end{array}\right) \ \textrm{ et } \M^4 = \left(\begin{array}{ll} 86 & 85 \\ 170 & 171 \end{array}\right).$$ Il faut observer que, pour $n \in \{2,3,4\}$, le nombre de chemins de longueur $n$ est la somme des coefficients de $\M^n$. Ce fait est bien entendu g\'en\'eral : les r\'ecurrences du d\'ebut peuvent en effet s'\'ecrire sous la forme $$\left( \begin{array}{l} \ell(n+1;p,p) \\ \ell(n+1;q,p)\end{array} \right) = \left(\begin{array}{ll} \ell(1;p,p) & \ell(1;p,q) \\ \ell(1;q,p) & \ell(1;q,q) \end{array}\right) \left(\begin{array}{l} \ell(n;p,p) \\ \ell(n;q,p)\end{array} \right)$$ et  $$\left( \begin{array}{l} \ell(n+1;p,q) \\ \ell(n+1;q,q)\end{array} \right) = \left(\begin{array}{ll} \ell(1;p,p) & \ell(1;p,q) \\ \ell(1;q,p) & \ell(1;q,q) \end{array}\right) \left(\begin{array}{l} \ell(n;p,q) \\ \ell(n;q,q)\end{array} \right),$$ soit encore $$\left(\begin{array}{ll} \ell(n+1;p,p) & \ell(n+1;p,q) \\ \ell(n+1;q,p) & \ell(n+1 ; q,q)\end{array} \right) = \M \left(\begin{array}{ll} \ell(n;p,p) & \ell(n;p,q) \\ \ell(n;q,p) & \ell(n ; q,q)\end{array} \right).$$ On en d\'eduit $$\left(\begin{array}{ll} \ell(n;p,p) & \ell(n;p,q) \\ \ell(n;q,p) & \ell(n;q,q)\end{array} \right) = \M^n$$ pour tout $n \in \mathbb{N}$ et on constate que le nombre de chemins de longueur $n$ dans le graphe est la somme des coefficients de la matrice $\M^n$.
\item Le raisonnement est le m\^eme qu'avec le premier graphe. La matrice d'incidence du second graphe est $$\M = \left(\begin{array}{ll} \ell(1;p,p) & \ell(1;p,q) \\ \ell(1;q,p) & \ell(1 ; q,q)\end{array} \right) = \left(\begin{array}{ll} 1 & n \\ n & 1\end{array} \right).$$ Cette matrice est diagonalisable sous la forme $$\M = \rP^{-1} \left(\begin{array}{ll} n+1 & 0 \\ 0 & 1-n\end{array} \right) \rP$$ avec $\rP = \left(\begin{array}{ll} 1 & 1 \\ 1 & -1\end{array} \right) \textrm{ et } \rP^{-1} = \frac{1}{2}\rP$, ce qui permet de calculer explicitement la puissance $k$-\`eme de $\M$ : 
$$\M^k  = \frac{1}{2}\left(\begin{array}{ll} (1+n)^k + (1-n)^k & (1+n)^k-(1-n)^k \\ (1+n)^k - (1-n)^k & (1+n)^k + (1-n)^k\end{array} \right)$$ et donc d'obtenir le nombre de chemins de longueur $k$ : $$\frac{1}{2} \left(2[(1+n)^k + (1-n)^k] + 2[(1+n)^k - (1-n)^k] \right) = 2 (n+1)^k.$$  
\end{enumerate}
\end{document} 