
\documentclass[a4paper,12pt]{article}

\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amssymb,amsthm,amsmath,amsfonts,mathrsfs}
\newtheoremstyle{custom}%    <name>
{\topsep}%   <space above>
{\topsep}%   <space below>
{\normalfont}%  <body font>
{}%          <indent amount>
{\bfseries}% <Theorem head font>
{.}%         <punctuation after theorem head>
{\newline}%  <space after theorem head> (default .5em)
{}%          <Theorem head spec>
\theoremstyle{custom}
\usepackage{textcomp}
%\usepackage{bbm}
\usepackage{geometry}
\usepackage{mathrsfs}
\usepackage{enumitem}
\usepackage{csquotes}
%\usepackage{esvect}       % Pour des vecteurs 
\usepackage{hyperref}      %Pour des liens hypertexte !
\hypersetup{
	% backref=true,    %permet d'ajouter des liens dans...
	% pagebackref=true,%...les bibliographies
	% hyperindex=true, %ajoute des liens dans les index.
	colorlinks=true, %colorise les liens
	%     breaklinks=true, %permet le retour à la ligne dans les liens trop longs
	%     urlcolor= blue,  %couleur des hyperliens
	%     linkcolor= black, %couleur des liens internes
	%     linktoc	=all,	%defines which part of an entry in the table of contents is made into a link
	%     citecolor=black,	%color of citation links (bibliography)
	%     filecolor=black,	%color of file links
	% bookmarks=true,  %créé des signets pour Acrobat
	bookmarksopen=true,            %si les signets Acrobat sont créés,
	%les afficher complètement.
	pdftitle={M1 algèbre effective}, %informations apparaissant dans
	pdfauthor={Samuel Le Fourn},     %dans les informations du document
}
\frenchspacing



\newtheorem{thm}{Théorème}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollaire}
\newtheorem*{thmsansnom}{Théorème}
\newtheorem*{propsansnom}{Proposition}
\newtheorem{lem}[thm]{Lemme}



\theoremstyle{custom}
\newtheorem{defi}[thm]{Définition}
\newtheorem{rem}[thm]{Remarque}
\newtheorem{exe}[thm]{Exemple}
\newtheorem{exocours}[thm]{Exercice de cours}
\newtheorem{exerciseaux}[thm]{Exercice}
%\newenvironment{exo}{\begin{exerciseaux}\leavevmode\par}{\end{exo}}
\newtheorem{exo}[thm]{Exercice}

\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\F{\mathbb{F}}
\def\1{\mathbbm{1}}
\def\Ncal{\mathcal{N}}

\DeclareMathOperator{\pgcd}{pgcd}
\DeclareMathOperator{\ppcm}{ppcm}

\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Inn}{Inn}
\DeclareMathOperator{\id}{id}
\newcommand{\Ker}{\operatorname{Ker}}

\setlist{noitemsep}
\setlist[1]{labelindent=\parindent} % < Usually \setlist[itemize]{leftmargin=*}
%d\setlist[itemize]{label = ($(\arabic*)$)}
\setlist[enumerate]{label = ($\alph*$)}



%%%%%%%%%%%%%%%%%%
% Alphabet Grec  %
%%%%%%%%%%%%%%%%%%
\renewcommand{\a}{\alpha}
\renewcommand{\b}{\beta}
\newcommand{\g}{\gamma}
\renewcommand{\d}{\delta}
\newcommand{\e}{\epsilon}
\newcommand{\f}{\varphi}
\renewcommand{\l}{\lambda}
\renewcommand{\k}{\kappa}
\newcommand{\m}{\mu}
\newcommand{\n}{\nu}
\renewcommand{\o}{\omega}
\renewcommand{\r}{\rho}
\newcommand{\s}{\sigma}
\renewcommand{\t}{\tau}
\newcommand{\z}{\zeta}
\newcommand{\D}{\Delta}
\newcommand{\G}{\Gamma}




%%%%%%%%%%%%%%%%%%%%
% Alphabet gothique%
%%%%%%%%%%%%%%%%%%%%
\newcommand{\ga}{{\mathfrak{a}}}
\newcommand{\gA}{{\mathfrak{A}}}
\newcommand{\gb}{{\mathfrak{b}}}
\newcommand{\gB}{{\mathfrak{B}}}
\newcommand{\gc}{{\mathfrak{c}}}
\newcommand{\gC}{{\mathfrak{C}}}
\newcommand{\gd}{{\mathfrak{d}}}
\newcommand{\gD}{{\mathfrak{D}}}
\newcommand{\gI}{{\mathfrak{I}}}
\newcommand{\gm}{{\mathfrak{m}}}
\newcommand{\gn}{{\mathfrak{n}}}
\newcommand{\go}{{\mathfrak{o}}}
\newcommand{\gO}{{\mathfrak{O}}}
\newcommand{\gp}{{\mathfrak{p}}}
\newcommand{\qg}{{\mathfrak{q}}}
\newcommand{\gP}{{\mathfrak{P}}}
\newcommand{\gQ}{{\mathfrak{Q}}}
\newcommand{\gq}{{\mathfrak{q}}}
\newcommand{\gR}{{\mathfrak{R}}}
\newcommand{\gS}{{\mathfrak{S}}}
\newcommand{\gJ}{{\mathfrak{J}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Alphabet calligraphique %
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Acal}{{\mathcal A}}
\newcommand{\Bcal}{{\mathcal B}}
\newcommand{\Ccal}{{\mathcal C}}
\newcommand{\Dcal}{{\mathcal D}}
\newcommand{\Ecal}{{\mathcal E}}
\newcommand{\Fcal}{{\mathcal F}}
\newcommand{\Gcal}{{\mathcal G}}
\newcommand{\Hcal}{{\mathcal H}}
\newcommand{\Ical}{{\mathcal I}}
\newcommand{\Jcal}{{\mathcal J}}
\newcommand{\Kcal}{{\mathcal K}}
\newcommand{\Lcal}{{\mathcal L}}
\newcommand{\Mcal}{{\mathcal M}}
\newcommand{\Ocal}{{\mathcal O}}
\newcommand{\Pcal}{{\mathcal P}}
\newcommand{\Qcal}{{\mathcal Q}}
\newcommand{\Rcal}{{\mathcal R}}
\newcommand{\Scal}{{\mathcal S}}
\newcommand{\Tcal}{{\mathcal T}}
\newcommand{\Ucal}{{\mathcal U}}
\newcommand{\Vcal}{{\mathcal V}}
\newcommand{\Wcal}{{\mathcal W}}
\newcommand{\Xcal}{{\mathcal X}}
\newcommand{\Ycal}{{\mathcal Y}}
\newcommand{\Zcal}{{\mathcal Z}}

%%%%%%%%%%%%%%%%%%%%
% Alphabet en gras %
%%%%%%%%%%%%%%%%%%%%
\newcommand{\ab}{\mathbf{a}}

%%%%%%%%%%%%%%%%%%%%
% Ensembles usuels %
%%%%%%%%%%%%%%%%%%%%
\renewcommand{\P}{\mathbb{P}}
\newcommand{\Fp}{{\mathbb{F}_{\! p}}}
\newcommand{\A}{{\mathbb{A}}}
\newcommand{\T}{{\mathbb{T}}}

%%%%%%%%%%%%%%%%%%%%%
% Opérateurs usuels %
%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Card}{\operatorname{Card}}
\newcommand{\Crit}{\operatorname{Crit}}
\renewcommand{\div}{\operatorname{div}}
\newcommand{\Div}{\operatorname{Div}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\Gal}{\operatorname{Gal}}
\newcommand{\SL}{\operatorname{SL}}
\newcommand{\Id}{\operatorname{Id}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\Proj}{\operatorname{Proj}}
\newcommand{\Spec}{\operatorname{Spec}}
\newcommand{\Borel}{\operatorname{Borel}}
\newcommand{\Stab}{\operatorname{Stab}}
\newcommand{\Cart}{\operatorname{Cart}}
\newcommand{\Cot}{\operatorname{Cot}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cl}{\operatorname{cl}}
\newcommand{\gr}{\operatorname{gr}}
\newcommand{\init}{\operatorname{in}}
\newcommand{\PGL}{\operatorname{PGL}}
\newcommand{\PSL}{\operatorname{PSL}}
\newcommand{\Der}{\operatorname{Der}}
\newcommand{\num}{\operatorname{num}}
\renewcommand{\Re}{\operatorname{Re}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\Jac}{\operatorname{Jac}}
\newcommand{\Vect}{\operatorname{Vect}}
\newcommand{\car}{\operatorname{car}}
\newcommand{\Sp}{\operatorname{Sp}}
\newcommand{\Pic}{\operatorname{Pic}}
\newcommand{\carac}{\textrm{char}}
\newcommand{\Tr}{\operatorname{Tr}}
\renewcommand{\mod}{\, \operatorname{mod} \,}
\newcommand{\Frac}{\operatorname{Frac}}
\newcommand{\preuve}{\textcolor{blue}{$^{(P)}$}}

%%%%%%%%%%%
% Flèches %
%%%%%%%%%%%
\newcommand{\mt}{\mapsto}	
\newcommand{\lmt}{\longmapsto}
\newcommand{\ra}{\rightarrow}
\newcommand{\lra}{\longrightarrow}
\newcommand{\La}{\Leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\Lra}{\Leftrightarrow}
\newcommand{\Llra}{\Longleftrightarrow}

\newcommand{\dessin}{\textcolor{green}{(D)}}

%%% Commandes spécifiques à la géométrie affine %%%%
%\newcommand{Evect}{\overrightarrow{E}}
%\newcommand{Fvect}{\overrightarrow{F}}
%\newcommand{uvect}{\overrightarrow{u}}
%\newcommand{vvect}{\overrightarrow{v}}



%%%%%%%%%%%%%%%%%%
% Macros utiles %%
%%%%%%%%%%%%%%%%%%

\newcommand{\fonction}[5]{\begin{array}{c|ccl}           % Pour écrire une fonction en environnement display : le nom puis espaces de départ et d'arrrivée, puis argument et résultat
		#1: & #2 & \longrightarrow & #3 \\
		& #4 & \longmapsto & #5 \end{array}}


\newcommand{\fonctionsansnom}[4]{\begin{array}{ccl}      % La même sans le nom de la fonction à mettre
		#1 & \lra & #2 \\\
		#3 & \lmt & #4 
\end{array}}


\newtheorem{enonce}[thm]{Exercice}%[section]
\newenvironment{Ex}[0]{\begin{enonce}\rm}{\bigskip \end{enonce}}
%\newtheorem{theoreme}{Th\'eor\`eme}%[section]



\geometry{top=2cm, bottom=2cm}
\begin{document}
	\newgeometry{top=1cm,bottom=2cm,left=2cm,right=2cm}
	\noindent {\large \textsc{Université Grenoble Alpes \hfill M1 \\
			\hfill M1 Algèbre effective \hfill 2024-2025}} \\
	\hrule
	\bigskip
	
	\begin{center}
		\textbf{\Large Algèbre linéaire}
	\end{center}
	\bigskip
	
	\section{Exercices}

\begin{exo}[Calcul de polynôme de matrice]
	\begin{enumerate}
		\item[]
		\item Soit $M \in M_n(K)$ et $P \in K[X]$ de degré $d$. Estimer la complexité du calcul naïf de $P(M)$.
		\item Supposons qu'on connaisse un polynôme annulateur $A$ de $M$, de degré $a<d$. Utiliser la division euclidienne pour calculer $P(M)$ de manière plus efficace, et donner la complexité du calcul.
		\item Dans le cas où $M$ est la matrice d'une symétrie, donner la complexité du calcul de $P(M)$.
		\item Lorsqu'on a $A$ un polynôme annulateur de $M$ et $A = A_1 A_2$ avec $A_1, A_2$ premiers entre eux dans $K[X]$, utiliser le lemme des noyaux pour en déduire les matrices des projecteurs associés à la décomposition 
		\[
		K^n = \Ker A_1(M) \oplus \Ker A_2(M).
		\] Combien coûte ce calcul en fonction du degré de $A_1$ et de $A_2$ ?
	\end{enumerate}
\end{exo}

\begin{exo}[Calcul du polynôme caractéristique]
	Soit un corps $K$ tel que $K$ a au moins $n+1$ éléments distincts $x_0, \cdots, x_n$ et $M \in M_n(K)$.
	
	\begin{enumerate}
		\item Expliquer comment calculer $\chi_M$ par interpolation en fonction des $\det(x_i I_n - M)$. 
		\item Donner la complexité totale de ce calcul.
		\item Si $K=\F_p$ avec $p<n$ premier, comment peut-on adapter la méthode pour calculer $\chi_M$ ?
	\end{enumerate}
\end{exo}

\begin{exo}[Recherche du polynôme minimal d'une matrice]
	\begin{enumerate}
		\item[]
		\item Soit $K$ un corps et $M \in M_n(K)$. Pour un vecteur $v \in K^n$ non nul, on note $\pi_{M,v}$ le plus petit polynôme non nul unitaire $P$ tel que $P(M)(v) = 0$. Montrer que $\pi_{M,v}| \pi_M$.
		\item Pour $v \neq 0$ fixé, indiquer comment calculer $\pi_{M,v}$ à l'aide d'un pivot de Gauss.
		\item Donner la complexité de ce calcul en nombre d'opérations dans $K$.
		\item Montrer comment retrouver $\pi_M$ en fonction de certains $\pi_{M,v}$ à l'aide du ppcm.
	\end{enumerate}
\end{exo}


\section{TP}


\begin{exo}[Noyau et image d'une matrice]
	\begin{enumerate}
		\item[]
		\item En se basant sur la commande \verb!rref! de Xcas (mais pas \verb!ker! ni \verb!image!, qu'on peut tester à part si on veut), écrire un algorithme qui à une matrice $M \in M_{m,n}(K)$ associe une base de son noyau dans $K^n$, ou une famille libre d'équations de celui-ci.
		\item Faire de même avec l'image de $M$.
		\item Déduire des deux cas précédents une fonction qui à une famille de vecteurs de $K^n$ associe une famille libre d'équations du sous-espace vectoriel qu'elle engendre, et réciproquement qui à une famille d'équations associe une base du sous-espace vectoriel qu'elle détermine.
	\end{enumerate}
\end{exo}
\begin{exo}[Calcul de déterminant de matrice dans un anneau]
	\begin{enumerate}
		\item[]
		\item Pour $M \in M_n(\Z)$ à coefficients \enquote{aléatoires} avec $n=50$ ou 100, évaluer les temps de calculs de $\det(M)$ en Xcas. Essayer d'en déduire une indication sur la complexité de l'algorithme utilisé.
		\item On définit, pour une taille de matrice $n$, la matrice dans $M_n(\Z[x_2,x_4, \cdots, x_{2n}])$ dont le $(i,j)$-ième coefficient est $x_{i+j}$. Comparer les temps de calcul de $\det(M)$ pour $n=6$ et $n=12$.  Conjecturer là aussi la complexité de l'algorithme utilisé.
	\end{enumerate}

\end{exo}

\begin{exo}[Calculs effectifs de polynômes caractéristique et minimal]
	\begin{enumerate}
		\item[]
		\item \'Ecrire un algorithme basé sur l'exercice 1.1 pour calculer le polynôme caractéristique d'une matrice aléatoire $M \in M_n(\Q)$. L'appliquer à une matrice $M \in M_{10}(\Z)$ avec des coefficients raisonnables.
		\item \'Ecrire un algorithme basé sur l'exercice 1.2 pour calculer le polynôme minimal d'une matrice $M \in M_n(\Q)$ et tester avec $M$ de taille 3 ayant des 0 sur la diagonale et des 1 ailleurs, puis avec une matrice aléatoire de taille 30.
	\end{enumerate}
\end{exo}
\begin{exo}[Modélisation d'un casse-tête]
	 On consid\`ere un damier 3 par 3 de
	pions ayant une face noire et une face blanche. On peut effectuer
	les manoeuvres suivantes~: retourner tous les pions d'une ligne,
	d'une colonne ou d'une diagonale, il y a donc 8 manoeuvres
	possibles (3 de lignes, 3 de colonnes, 2 de diagonale). 
	Il s'agit de savoir si en partant d'une configuration
	donn\'ee on peut \`a l'aide de ces manipulations arriver
	\`a la configuration o\`u tous les pions sont face noire visible,
	et le cas \'ech\'eant donner les manipulations pour s'y
	ramener. On pourra utiliser l'alg\`ebre lin\'eaire dans $(\Z/2\Z)^9$.
\end{exo}




\end{document}

 
