% Probl{\`e}me commun ENS Lyon-Cachan M' 1996 - par E. Amiot  -- eMail  chucky@wanadoo.fr.fr
% Probl{\`e}me sur les permanents et l'ensemble des matrices bistochastiques. 
% D{\'e}but topologie, suite plus g{\'e}om{\'e}trique.
% Quelques questions ne seront
% accessibles qu'aux meilleurs {\'e}l{\`e}ves, avec des efforts. On d{\'e}montre tout de m{\^e}me
% la conjecture de Van der Waerden sur le permanent !
% Programme couvert : matrices, d{\'e}terminants, convexes, compacts.
% Objection : une grande partie de la fin est trait{\'e}e dans l'excellent (et c{\'e}l{\`e}bre) recueil de
% Monier, avec d'ailleurs plus d'indications...


\magnification 1100
%
% On red{\'e}finit les caract{\`e}res ;:!? pour avoir des espaces corrects
%
\catcode`\@=11
\catcode`\;=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@% abr{\'e}v. pour dire " > 0 "
\unskip\fi\kern.2em\fi\string;\kern.5em}
\catcode`\:=\active
\def:{\relax\ifhmode \ifdim\lastskip>\z@\unskip\fi
\penalty\@M\kern.2em\fi\string:\kern.5em\penalty0\ignorespaces}
\catcode`\!=\active
\def!{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern.2em\fi\string!}
\catcode`\?=\active
\def?{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern.2em\fi\string?\kern.5em}
\catcode`\@=12
%
\def\titre#1{\centerline{\encadre{\fontitre #1}}\bigskip}
\def\myvsize#1cm{\vsize#1cm}
\def\mynopagenumbers{\nopagenumbers}
\def\encadreLR#1{\ifmmode{|#1|}%
\else{$|#1|$}\fi}
\def\encadre#1{\leavevmode\thinspace\hbox{\vrule\vtop{\vbox{
\hrule\kern1pt\hbox{\vphantom{/}\thinspace{#1}\thinspace}}
\kern1pt\hrule}\vrule}\thinspace}
\def\para#1{\goodbreak\leavevmode\llap{\hbox{\bf #1 \ }}}

\font\fontitre=cmbx10 scaled 1500
\font\xiibx=cmbx12

% cadre
% Usage: \cadre{10pt}{texte} pour avoir un cadre de 10 points de large
%
\newdimen\hcadre
\newdimen\pcadre
\def\cadre#1#2{\setbox1=\hbox{\kern #1{#2}\kern #1}%
\hcadre=\ht1\advance\hcadre by#1\pcadre=\dp1\advance\pcadre by#1%
\setbox1=\hbox{\vrule height\hcadre depth\pcadre\box1\vrule}%
\setbox1=\vbox{\hrule\box1\hrule}\advance\hcadre by#1\ht1=\hcadre%
\advance\pcadre by#1\dp1=\pcadre\null\kern#1\box1\kern#1\relax}

\def\cadrerelief#1#2{\setbox1=\hbox{\kern #1{#2}\kern #1}%
\hcadre=\ht1\advance\hcadre by#1\pcadre=\dp1\advance\pcadre by#1%
{\advance\hcadre by-0.8pt\global\ht1=\hcadre}
\setbox2=\hbox{\vrule height\hcadre depth\pcadre\kern-0.5pt\copy1\vrule\vrule
height\ht1 depth\pcadre width0.6pt}%
\setbox1=\vbox{\offinterlineskip\hbox{\vrule height0.4pt depth0pt width 0.1pt%
\vrule width\wd1}%
\box2\hbox{\vrule height0pt depth0.4pt width0.9pt%
\vrule height0pt depth1.2pt width\wd1}}%
\advance\hcadre by#1\ht1=\hcadre\advance\pcadre by#1\dp1=\pcadre\kern#1%
\box1\kern#1\relax}

\def\boxit#1#2{\setbox1=\hbox{\kern#1{#2}\kern#1}%
\dimen1=\ht1 \advance\dimen1 by #1 \dimen2=\dp1 \advance\dimen2 by #1
\setbox1=\hbox{\vrule height\dimen1 depth\dimen2\box1\vrule}%
\setbox1=\vbox{\hrule\box1\hrule}%
\advance\dimen1 by .4pt \ht1=\dimen1
\advance \dimen2 by .4pt \dp1=\dimen2 \box1\relax}
%
\newskip\linesize\linesize=\hsize\advance\linesize by-\leftskip
\advance\linesize by-\rightskip
\newskip\enmargeg\enmargeg=5truemm
\def\retrait{\kern -\enmargeg}
\def\margeg{\kern \enmargeg}
\def\filet #1{\hfill\hbox to #1{\hrulefill}\hfill }%

%
\def\up#1{\raise 1ex\hbox{\sevenrm#1}}
%
\def\grostitre#1{\centerline{\fontitre{#1}}\par\noindent\filet{\linesize}\medskip}
\def\encadre#1{\smallskip\centerline{\cadre{4pt}{#1}}\smallskip}
\def\titrecadre#1{\centerline{\cadre{4pt}{\xiibx{#1}}}\medskip}
\def\titrecentre#1{\medskip\centerline{\bf#1}\medskip}
\def\titre#1{\medskip\hskip-\leftskip{\bf#1}\medskip}

% Num{\'e}rotation des parties, questions ...
%
\newcount\pno\pno=0
\newcount\qno\qno=0
\newcount\sqno\sqno=96
\newcount\qlet\qlet=64
\newcount\spno\spno=64

\def\partie
{\qno=0\qlet=64\sqno=96\spno=64\advance\pno by1\penalty-200\vskip 0.5cm%
\noindent{\hfill\bf{Partie\
\ifcase\pno\or I \or II \or III \or IV \or V \or VI \or VII \or VIII \or IX
\fi}\hfill}
\nobreak\par\medskip}

\def\partietitre#1

{\qno=0\sqno=96\qlet=64\spno=64\advance\pno by1\penalty-200\vskip 0.5cm%
\noindent{\hfill\bf{Partie\
\ifcase\pno\or I \or II \or III \or IV \or V \or VI \or VII \or VIII \or IX
\fi}\ :
#1\hfill\null}\par\nobreak\vskip4mm minus 1mm}


\def\question
{\global\sqno=96\global\advance\qno by1\goodbreak\smallbreak\medskip
\noindent{\retrait\oldstyle\bf \the\qno \up{o})\ \ }\nobreak}


\def\sousquestion
{\ifnum\sqno>96\goodbreak\smallbreak\fi\noindent\retrait\global\advance\sqno
by1{\bf \char\sqno\sevenrm )}\ \ }

\def\Reponse#1#2{\setbox1=\vbox{\hbox{#1}\hbox{#2}}\par
\centerline{\cadrerelief{4pt}{\box1}}}	% deux r{\'e}ponses accol{\'e}es.
\def\reponse#1{\par\smallskip\centerline{\cadrerelief{4pt}{#1}}}

\def\fin{\bigskip\centerline{- FIN -}}
\def\lafin{ \par\bigskip\bigskip
\centerline{\hbox to 200pt{\downbracefill}}
\vskip -12pt
\centerline{\hbox to 200pt{\upbracefill}} }

% mise en page
\overfullrule=0pt
\parindent=0pt
\pretolerance=200
\tolerance=1000
\vsize 27 truecm
\voffset -1.6 truecm

\nopagenumbers
%

%
% Fontes "blackboard"
%
\font\tenmsbm=msbm10
\font\sevenmsbm=msbm7
\font\fivemsbm=msbm5
\newfam\fambb
\def\Bbb{\fam\fambb\tenmsbm}
\textfont\fambb=\tenmsbm
\scriptfont\fambb=\sevenmsbm
\scriptscriptfont\fambb=\fivemsbm
\def\C{{\Bbb C}}
\def\D{{\Bbb D}}
\def\K{{\Bbb K}}
\def\N{{\Bbb N}}
\def\Z{{\Bbb Z}}
\def\Q{{\Bbb Q}}
\def\R{{\Bbb R}}
\def\U{{\Bbb U}}

%
% Op{\'e}rateurs math{\'e}matiques divers
%
\def\argch{\mathop{\rm arg\,ch}\nolimits}
\def\argsh{\mathop{\rm arg\,sh}\nolimits}
\def\argth{\mathop{\rm arg\,th}\nolimits}
\def\Card{\mathop{\rm Card}\nolimits}
\def\ch{\mathop{\rm ch}\nolimits}
\def\com{\mathop{\rm com}\nolimits}
\def\cotan{\mathop{\rm cotan}\nolimits}
\def\im{\mathop{\rm Im}\nolimits}
\def\re{\mathop{\rm Re}\nolimits}
\def\rg{\mathop{\rm rg}\nolimits}
\def\sh{\mathop{\rm sh}\nolimits}
\def\th{\mathop{\rm th}\nolimits}
\def\tr{\mathop{\rm tr}\nolimits}
\def\val{\mathop{\rm val}\nolimits}
\def\Vect{\mathop{\rm Vect}\nolimits}
\def\grsym{\mathop{\hbox{\eulerfmten S}}\nolimits}
\def\dt{\kern 0.25em\hbox{d}\kern 0.1em t}				% dans une int{\'e}grale.
\def\somme{\dst\sum_{n=0}^{+\infty }}               %  un · pr{\'e}d{\'e}fini
\def\eps{{\relax\ifmmode\varepsilon\else$\varepsilon$\fi}}
\def\frac#1#2{\textstyle{{#1}\over{#2}}}
\def\Frac#1#2{\displaystyle{{#1}\over{#2}}}
\def\adots{\mathinner{\mkern2mu\raise1pt\hbox{.}\mkern3mu\raise4pt\hbox{.}\mkern1mu\raise7pt\hbox{.}}}
% Trois points ÇantidiagonauxÈ  (sym{\'e}trique de \ddots)

\def\Int{\displaystyle\int}
\def\Ker{\mathop{\rm Ker}\nolimits}
\def\Lim{\displaystyle\lim}
\def\Max{\displaystyle\max}
\def\Min{\displaystyle\min}
\def\Prod{\displaystyle\prod}
\def\Sum{\displaystyle\sum}
\def\Sup{\displaystyle\sup}
\let\tend=\rightarrow

\def\ssi{si, et seulement si}
\def\ie{{\it ie\/}}
\let\dst=\displaystyle

\def\picture #1 by #2 (#3){
  \vbox to #2{
    \hrule width #1 height 0pt depth 0pt
    \vfill
    \special{picture #3} % this is the low-level interface
    }
  }
\def\Prod{\dst\prod}
% \frac=\Frac

\let\phi=\varphi
\let\ll = \lambda
\let\eps = \varepsilon
\def\per{\mathop{\bf per}}
\def\un={\ifmmode {\bf 1} \else $\bf 1$ \fi}


\grostitre{Corrig{\'e} de l'{\'e}preuve commune M' --- Lyon--Cachan 1996}

\partietitre{G{\'e}n{\'e}ralit{\'e}s sur les convexes compacts de E}

\question 
Les deux sous-espaces sont naturellement $H^+ = \{\phi>\ll\}$ et $H^- = \{\phi <\ll\}$ ; il
n'est que de d{\'e}montrer que ce sont des ouverts convexes, car il est clair qu'ils r{\'e}alisent une
partition de $E\backslash H$.

Or, $\phi - \ll$ {\'e}tant continue, $H^+$ et $H^-$ sont les images inverses continues des
ouverts $\R_+^*$ et $\R_-^*$, donc sont ouverts. Par ailleurs, si par exemple
$x\in H^+$ et $y\in H^+$, on a par lin{\'e}arit{\'e} de $\phi$
$$\forall \mu\in[0,1] \qquad
				\phi(\mu x + (1-\mu)y) = \mu \phi(x) + (1-\mu)\phi(y)
			 \ge  \mu \ll + (1-\mu)\ll = \ll$$
donc $[x,y]\subset H^+$, cqfd. (de m{\^e}me pour $H^-$)

\question
Image continue du compact $C$.
\question
Consid{\'e}rons deux points $c_1, c_2$ o{\`u} le minimum de $c\in C\mapsto |x-c|$ soit atteint, et
leur milieu $m$ : il est encore dans $C$ par convexit{\'e}. Mais le triangle 
$(c_1 x c_2)$ {\'e}tant isoc{\`e}le, $(xm)$, sa hauteur, est plus courte que les deux c{\^o}t{\'e}s issus de $x$
, ce qui contredit la minimalit{\'e} de $c_1, c_2$, sauf si le triangle se r{\'e}duit {\`a} un segment.

On a ainsi d{\'e}fini une projection sur tout convexe compact.
\question
Nous allons d{\'e}montrer que l'angle $\widehat{x p(x) c}$ est obtus. En effet, si ce n'{\'e}tait pas le
cas, il serait strictement aigu autrement dit on aurait
$\langle p(x)-x, p(x) - c\rangle >0$. Mais alors, le m{\^e}me argument que ci-dessus permettrait
de contredire la minimalit{\'e} de $p(x)$ : en effet, $c$ (ou tout point
int{\'e}rieur au segment $[c, p(x)]$ d'ailleurs) est dans $C$, et est plus proche de $x$
que $p(x)$.
\question
On va montrer mieux : que $p$ est 1-lipschitzienne (c'est g{\'e}n{\'e}ral {\`a} la distance {\`a} un
sous-ensemble, quel qu'il soit).

En effet, dans le quadrilat{\`e}re (gauche) $x\, y\, p(x)\, p(y)$, les angles en $p(x)$ et $p(y)$
{\'e}tant obtus {\bf {\'e}cartent} la figure et donc $|x - y|\ge  |p(x) - p(y)|$.  On peut bien entendu
v{\'e}rifier cela par un petit calcul trigonom{\'e}trique si l'on pr{\'e}f{\`e}re.
\question
On a $(C\backslash H_k)\subset H_k^-$ d'apr{\`e}s la question {\bf 4} : en effet, si l'on a pour
$c\in C$ $\langle p(x_k) - x_k, p(x_k) - c\rangle = 0$, c'est que $c\in H_k$; sinon, on a bien
$\langle p(x_k) - x_k, p(x_k) - c\rangle < 0$ \ie\ $c\in H_k^-$, cqfd.
\question
Bien entendu on utilise la question pr{\'e}c{\'e}dente. Le probl{\`e}me est de passer {\`a} la limite sur une
suite d'hyperplans ! notons d{\'e}j{\`a} que la suite $(p(x_k))_{k\in\N}$ tend vers $c=p(c)$ par
continuit{\'e} de $p$. 

La suite de terme g{\'e}n{\'e}ral $u_k = \Frac{x_k - p(x_k)}{|x_k - p(x_k)|}$ est bien
d{\'e}finie (c'est ``le" vecteur normal unitaire {\`a} $H_k$ pointant vers l'ext{\'e}rieur de $C$), elle ne
converge pas forc{\'e}ment h{\'e}las, comme on le voit quand par exemple $C$ est r{\'e}duit {\`a} un point.
Mais elle se trouve confin{\'e}e {\`a} la sph{\`e}re unit{\'e}, qui est compacte, et donc on peut en extraire
une sous-suite convergente, que je noterai encore $(u_k)$.
\smallskip
On a {\'e}tabli en un sens la convergence de la (sous-)suite d'hyperplans $H_k$ vers l'hyperplan
$H$ orthogonal {\`a} $u=\lim u_k$ passant par $c = \lim x_k = \lim p(x_k)$. Reste {\`a}
montrer que la propri{\'e}t{\'e} d'{\^e}tre d'appui passe {\`a} la limite. Observons que pour tout
$c'\in C$, on a
$\langle u_k, c' - p(x_k) \rangle \le  0$ d'apr{\`e}s {\bf 4)}. Donc, on a
$\langle u  , c' - c \rangle \le  0$  et le caract{\`e}re obtus de cet angle prouve bien comme au {\bf
6)} que $C$ est d'un seul c{\^o}t{\'e} de $H = \lim H_k$, cqfd.


\partietitre{Points extr{\'e}maux}

\qno=-1
\question
Pour un segment, par d{\'e}finition il n'y a que les extr{\'e}mit{\'e}s qui soient extr{\'e}males !

Pour un carr{\'e} plein, il y a les quatre coins : tout autre point du bord est {\`a} l'int{\'e}rieur d'un c{\^o}t{\'e},
sans parler des points int{\'e}rieurs qui sont {\`a} l'int{\'e}rieur d'une infinit{\'e} de segments comme leur
nom l'indique.

Enfin, pour un disque, tout point int{\'e}rieur au disque est {\`a} l'int{\'e}rieur d'une corde, donc n'est
pas extr{\'e}mal. R{\'e}ciproquement, tous les points du cercle fronti{\`e}re sont extr{\'e}maux car tout
segment contenu dans le disque est une corde, dont l'int{\'e}rieur ne coupe pas le cercle fronti{\`e}re.
\question
Une implication est toujours triviale : les segments du convexe $C\cap H$ font partie des
segments de $C$, donc \par
\centerline{ extr{\'e}mal sur $C$ \quad $\Rightarrow$ \quad extr{\'e}mal sur $C\cap H$}
\smallskip
La r{\'e}ciproque ne marche qu'avec l'hypoth{\`e}se suppl{\'e}mentaire que $H$ est d'appui.  En effet,
si $c$ est int{\'e}rieur -- par exemple, au milieu -- {\`a} un segment $[a, b] \subset C$, ce segment ne
peut {\^e}tre dans $H$ par hypoth{\`e}se, mais si $H$ est d'appui il doit se trouver d'un seul c{\^o}t{\'e} de
$H$, ce qui est absurde (heuristiquement, il ``d{\'e}passe").
\question
Une remarque : on peut toujours supposer qu'un convexe (non r{\'e}duit {\`a} un point) est
d'int{\'e}rieur non vide, si l'on se restreint {\`a} l'espace affine qu'il engendre.

Consid{\'e}rons une droite quelconque passant par $c$, elle coupe $C$ en un convexe compact,
une droite {\'e}tant convexe et ferm{\'e}e -- donc un segment $[x, y]$. $c$ est int{\'e}rieur {\`a} $[x, y]$ par
hypoth{\`e}se, et $x, y$ sont des points fronti{\`e}re de $C$ au sens du {\bf I} : ils sont limites de
points (de la droite) ext{\'e}rieurs {\`a} $C$, donc d'apr{\`e}s le {\bf I.7} ils sont tous deux contenus
dans des hyperplans d'appui.
\question
On vient de d{\'e}montrer que $C$ est {\sl inclus\/} dans l'enveloppe convexe de ses points
extr{\'e}maux.  Mais la r{\'e}ciproque est triviale : $C$ est convexe et contient ses points extr{\'e}maux,
donc tous leurs barycentres,\ie\ leur enveloppe convexe.

\partietitre{Matrices bistochastiques}

% {\sl Remarque : que voil{\`a}une jolie d{\'e}finition, inutile de surcro{\^\i}t}
\def\mnr{{\cal M}_n(\R)}
\question
Moins trivial qu'il ne semble. $J_n$ est l'intersection des noyaux des $2n$ formes lin{\'e}aires
(sommes des lignes, sommes des colonnes), ou si l'on pr{\'e}f{\`e}re l'orthogonal du sous-espace du
dual de $\mnr$ engendr{\'e} par ces $2n$ formes.

Il suffit donc de d{\'e}montrer que le rang de cette famille de $2n$ formes lin{\'e}aires est {\'e}gal {\`a}
$2n-1$, on en d{\'e}duira la dimension de l'orthogonal.

Or il est clair que les formes sont li{\'e}es : la somme des sommes des lignes est {\'e}gale {\`a} la somme
des sommes des colonnes. Donc le rang est inf{\'e}rieur ou {\'e}gal {\`a} $2n-1$.

Il est un peu moins clair que  le rang n'est pas strictement inf{\'e}rieur. Pour cela, il suffit
d'observer que si l'on prend $2n-2$ formes parmi ces $2n$, les deux autres n'en sont pas 
combinaison lin{\'e}aire. Ce qui sera {\'e}vident si l'on arrive {\`a} annuler ces $2n-2$ formes sans
annuler les suivantes. Si l'on {\sl laisse} de c{\^o}t{\'e} les formes correspondant {\`a} la $i\up{{\`e}me} $
ligne et {\`a} la $j\up{i{\`e}me}$ colonne, il suffit de consid{\'e}rer une matrice dont le seul terme non nul
est $c_{i,j}$ : toutes les autres formes lin{\'e}aires donneront 0.

Si on laisse de c{\^o}t{\'e} deux lignes, par exemple les deux premi{\`e}res, il suffit de les prendre
oppos{\'e}es (et non nulles !). Idem dans le dernier cas, de deux colonnes.

Dans tous les cas, on a montr{\'e} que $2n-2$ de ces $2n$ formes ne suffisent pas {\`a} engendrer la
famille enti{\`e}re : donc le rang est bien $2n-1$, cqfd.
\question
On admet donc la convexit{\'e} de $B_n$ : sans doute trop facile$\dots$

Remarquons que $B_n$ est born{\'e}e (pour toute norme) puisque tout coefficient d'une matrice
de $B_n$ est entre 0 et 1.

Par ailleurs, $B_n$ est ferm{\'e} pour toutes sortes de raisons, par exemple comme intersection
de deux ferm{\'e}s : l'ensemble des matrices {\`a} coefficients positifs ou nuls (image inverse
continue d'un ferm{\'e}) et d'un espace affine, $I + J_n$.

On est en dimension finie, donc $B_n$ est compact.

{\sl Remarque : $B_n$ est l'ensemble des matrices {\`a} coefficients $\ge 0$ tels que les sommes des
lignes et des colonnes valent toutes 1, d'o{\`u} leur nom : les $c_{i,j}$ correspondent {\`a} des
probabilit{\'e}s dans les deux directions, verticale et horizontale.}
\question
Notons que $\alpha$ et $\beta$ pourraient en effet difficilement {\^e}tre bijectives !

Essayons de comprendre : $C_{\alpha, \beta}$ est  un ensemble de matrices bistochastiques
qui ont exactement deux {\'e}l{\'e}ments non nuls par ligne. 

Consid{\'e}rons $C\in C_{\alpha, \beta}$ et $\eps>0$ : il suffit de prendre $\eps $ plus petit que
tous les $c_{i, \alpha(i)}(B)$ et $c_{i, \beta(i)}(B)$ pour que les coefficients de $BÊ-\eps C$ 
restent positifs (ou nuls), d'apr{\`e}s les d{\'e}finitions de
$B$ et de $C_{\alpha, \beta}$ (tout coefficient de $C$ {\'e}tant $\le 1$). Bien entendu il en est de
m{\^e}me de $B +\eps C$.

Observons que, par lin{\'e}arit{\'e}, on a alors 
$\Frac1{1+\eps}(B+\eps C) \in B_n$ et $\Frac1{1-\eps}(B -\eps C) \in B_n$. Mais alors
$B$ est entre ces deux points :
$$B = \Frac{1-\eps}2 \Frac{B - \eps C}{1 - \eps} + \Frac{1+\eps}2 \Frac{B + \eps C}{1 +\eps}
 \qquad\Frac{1-\eps}2 + \Frac{1+\eps}2 = 1
 \qquad (\eps<1)$$

On a bien d{\'e}montr{\'e} que $B$ n'est pas extr{\'e}mal\dots {\`a} condition qu'une matrice $C$
 existe, c'est {\`a} dire que $C_{\alpha, \beta}$ soit non vide ! ce qui n'est pas vrai pour tout
couple d'applications $\alpha, \beta$ (ex : constantes).

En fait, la condition sur $B$ permet de d{\'e}finir, ou tout au moins de choisir, $\alpha, \beta$
de fa{\c c}on raisonnable. cf. question suivante :
\question
S'il existe $\alpha, \beta$ comme ci-dessus, $B$ ne peut {\^e}tre extr{\'e}male. Or ce sera le cas s'il
existe (au moins) deux {\'e}l{\'e}ments non nuls dans chaque ligne. Pour un {\'e}l{\'e}ment extr{\'e}mal de
$B_n$, il existe donc une ligne avec un seul {\'e}l{\'e}ment non nul, qui ne peut {\^e}tre que 1.  Soit 
$c_{i,j}(B) = 1$ cet {\'e}l{\'e}ment : en anticipant sur les notations du {\bf IV}, on remarque que
$B_{i,j} \in B_{n-1}$.  Cette construction identifie $B_{n-1}$ {\`a} l'intersection de $B_n$ et de
l'hyperplan (d'appui) d'{\'e}quation $c_{i,j} = 1$ : par le {\bf II 1)}, l'extr{\'e}malit{\'e} est h{\'e}r{\'e}ditaire.
Une r{\'e}currence descendante permet donc d'affirmer le
\proclaim Th{\'e}or{\`e}me. Un point extr{\'e}mal de $B_n$ est une matrice de permutation.\par
En effet, les seuls {\'e}l{\'e}ments autoris{\'e}s sont des z{\'e}ros ou des 1, et il n'y aura qu'un 1 par ligne
ou par colonne : la matrice permute donc les vecteurs de la base canonique de $\R^n$.

La r{\'e}ciproque est vraie, toute matrice de cette forme {\'e}tant clairement extr{\'e}male. En effet, si
pour fixer les id{\'e}es on a
$c_{i,j}(B) = 1$, tout couple $(A, C)\in B_n^2$ tel que $B\in [A, C]$ devrait v{\'e}rifier
$c_{i,j}(A) = c_{i,j}(C) = 1$.  Donc les $i\up{i{\`e}mes}$ lignes et $j\up{i{\`e}mes}$ colonnes de $A,
B, C$ sont identiques, et de proche en proche $A = B = C$, \ie\ $B$ est extr{\'e}male.

Il y en a donc exactement $n!$.
% Rem du correcteur : ou bien j'ai rat{\'e} des id{\'e}es plus simples, ou bien le sujet et
% ses indications sont singuli{\`e}rement vaseux dans cette r{\'e}gion.

Exemple : consid{\'e}rons un $n$--cycle, par exemple la matrice
$C =\pmatrix{
																			0           & 1 & 0 & \ldots & 0 \cr
																			\vdots & 0 & 1 & 0 \ldots      & \vdots \cr
                   	\vdots & 0 & 0 & 1 \ldots      & \vdots\cr
                   	0            & 0 & 0 & 0 \ldots      & 1 \cr                    
																				1					& 0    & \ldots  &  \ldots  & 0 \cr
                   }$. \par
Alors l'isobarycentre $\frac1n (I + C + C^2 + \dots + C^{n-1})$ n'est autre que la
matrice dont tous les coefficients valent $1/n$.                   
                   
\question
Notons que  le permanent est une expression plus simple que le d{\'e}terminant : ce sont les
m{\^e}mes termes, avec toujours le signe plus et sans la signature de $\sigma$.

Il suffit d'{\'e}tablir la deuxi{\`e}me propri{\'e}t{\'e} : si elle est vraie, on aura
$$\hbox{per}(M) \ge  \prod_{i=1}^n c_{i, \sigma(i)}(M) > 0$$
\dots et r{\'e}ciproquement, tous les termes de la somme d{\'e}finissant le permanent {\'e}tant $\ge 0$.

Contrairement aux apparences, on va utiliser le th{\'e}or{\`e}me de Birkhoff que l'on vient d'{\'e}tablir.
Soit en effet $S$ une des matrices de permutation (point extr{\'e}mal de $B_n$) dont $C$ est
barycentre : $C = \ll S + \ll' S' +\dots$ o{\`u} $0<\ll\le 1$. Mais $S$ est une matrice o{\`u} l'on trouve 1
pour les {\'e}l{\'e}ments de la forme 
$c_{i, \sigma(i)}(S)$ o{\`u} $\sigma$ est une permutation -- les
autres {\'e}tant nuls. Comme tous les coefficients de toutes les matrices $\ll' S', \ll''  S''\dots$ sont
$\ge 0$, on en d{\'e}duit
$$\forall i\in\{1,\dots, n\} \qquad c_{i, \sigma(i)}(C) \ge  \ll > 0$$
Donc $\per(C) = \Sum_{\sigma} \prod_{k=1}^n c_{kn \sigma(k)}(C) \ge \ll^n > 0$.

\question
L'application $\per$ est clairement continue (polynomiale), donc atteint son minimum sur le
compact $B_n$. Ce minimum {\'e}tant atteint en une matrice $B\in B_n$, est strictement positif.
C'est une vieille conjecture de Van der W\ae rden, que $m_n = n!/n^n$ c'est {\`a} 
dire qu'il est atteint ``au centre'' de $B_n$, que nous allons d{\'e}montrer
dans les deux derni{\`e}res parties.

\partietitre{In{\'e}galit{\'e}s sur les permanents de matrices $\ge 0$}

\question
La propri{\'e}t{\'e} ${\cal P}_2$ s'{\'e}crit :

si $\per\pmatrix{a & a' \cr b & b'} = 0$, avec $a, b>0$, alors 
$\per\pmatrix{a' & a' \cr b' & b'} \le  0$ avec {\'e}galit{\'e} ssi $a' = b' = 0$.

Comme les permanents en question valent  $ab' + a'b$ et $2a'b'$, c'est clair : le premier ne
peut {\^e}tre nul que si $a'$ et $b'$ sont de signes contraires, et dans ces conditions le second
est n{\'e}gatif ; si il est nul, alors (par exemple) $a' = 0$ et la nullit{\'e} du premier permanent exige
aussi que $b'$ soit nul. La r{\'e}currence est initialis{\'e}e.

\question
En d{\'e}veloppant $\per(x_1, \dots, x_{n-2}, e_n, x)$ par rapport {\`a} $e_n$, on trouve le
permanent  de la matrice $^n(x_1, \dots, x_{n-2}, x)$ qui d\'esignera la matrice
$(x_1, \dots, x_{n-2}, x)\in{\cal M}_{n, n-1}$ o{\`u} on barre la
$n\up{i{\`e}me}$ ligne.

Par l'hypoth{\`e}se de r{\'e}currence, on en d{\'e}duit que
$$\per\ ^n(x_1, \dots,  x_{n-3}, \widehat{x_{n-2}}, x, x) \le  0
\qquad\hbox{et plus g{\'e}n{\'e}ralement} \quad
\per\ ^n(x_1, \dots , \widehat{x_{k}}, \dots, x, x) \le  0
$$
 quitte {\`a} permuter les premi{\`e}res colonnes (le symbole
$\widehat{x_k}$ signifiera qu'on retire la colonne $x_k$).

Ne reste plus qu'{\`a} d{\'e}velopper 
$\per (x_1, \dots, x_{n-2}, x, x)$ par rapport {\`a} ses derni{\`e}res colonnes. Remarquons que la
derni{\`e}re coordonn{\'e}e de $x$ ``ne joue pas'' : elle est en facteur du permanent qu'on a suppos{\'e}
nul. \`A quoi ressemblent les autres termes ? ils contiennent, faute de $n\up{i{\`e}me}$
coordonn{\'e}e de $x$, une $n\up{i{\`e}me}$ coordonn{\'e}e d'un $x_k, k\le n-2$. Sans perte de
g{\'e}n{\'e}ralit{\'e}, on peut consid{\'e}rer le cas o{\`u} $k=n-2$, ces $x_k$ {\'e}tant 
interchangeables. On trouve
en facteur de la $n\up{i{\`e}me}$ coordonn{\'e}e de $x_{n-2}$, qui est $>0$, le permanent
$\per\,^n(x_1, \dots, x_{n-3}, x, x)$, qui est n \'egatif d'apr{\`e}s ${\cal P}_{n-1}$.

Au total, le permanent $\per (x_1, \dots, x_{n-2}, x, x)$ est donc 
somme de termes n{\'e}gatifs, voire
nuls. Ils seront tous nuls ssi les derni{\`e}res colonnes de
$^n(x_1, \dots,\widehat{x_k}, \dots, x_{n-2}, x, x)$ le sont, autrement dit si $x$ est multiple
de $e_n$ : cette difficile question est achev{\'e}e.

\question
Remarque : $\ll \mapsto \per(x_1, \dots, x_{n-2}, e_n, x+\ll x_{n-1})
= \per(x_1, \dots, e_n, x) + \ll \per(x_1, \dots, e_n, x_{n-1})$ est une fonction affine de
$\ll$, donc la fonction est monotone : elle s'annule pour une unique valeur de $\ll$
que nous fixons (rem: c'est vrai pour tout $\ll$ si $\per(x_1, \dots, e_n, x_{n-1})=0$).

On en d{\'e}duit, via la question pr\'ec\'edente, que
$$\per(x_1, \dots, x_{n-2}, x+\ll x_{n-1}, x+\ll x_{n-1}) \le  0$$
avec {\'e}galit{\'e} ssi $x+\ll x_{n-1}$ est colin{\'e}aire {\`a} $e_n$.

En d\'eveloppant par multilin{\'e}arit{\'e}, si l'on suppose que 
$\per(x_1, \dots, x_{n-1}, x) = 0$, il ne reste que
$$\per(x_1, \dots,x_{n-2}, x, x) + \ll^2 \per(x_1, \dots,x_{n-2}, x_{n-1}, x_{n-1}) \le  0$$
Comme le deuxi{\`e}me permanent est strictement positif (tous les termes de la matrice le sont),
on en d{\'e}duit que $\per(x_1, \dots, x, x) \le  0$.

Si on particularise en $\per(x_1, \dots, x, x) =  0$, il faut
que $\ll = 0$ et donc $x=x+\ll x_{n-1}$ colin{\'e}aire {\`a} $e_n$ : mais
si $x=\mu e_n$, comme $\per(x_1, \dots, e_n, e_n) > 0$ et 
$\per(x_1, \dots, x,x)=\mu^2 \per(x_1, \dots, e_n, e_n)=0$
on a forc\'ement $x = 0$, cqfd.

Cette d{\'e}monstration rappelle celle d'une in\'egalit\'e c\'el\`ebre, mais moins que la suivante\dots

\question
On reconna{\^\i}t (!!!) la condition demand{\'e}e comme la positivit{\'e} du discriminant du trin{\^o}me
$$ \eqalign{
\ll^2 \per(x_1, \dots, x_{n-2}, x_n, x_n) +& 2\ll \per(x_1, \dots, x_{n-2}, x_{n-1}, x_n) +
		 \per(x_1, \dots, x_{n-2}, x_{n-1}, x_{n-1}) \cr
   & =\per(x_1, \dots, x_{n-2}, x_{n-1} + \ll x_n, x_{n-1} + \ll x_n)}$$ 
qui est de la forme $\per(x_1, \dots, x_{n-2}, x, x)$ avec $x = x_{n-1} + \ll x_n$. Or comme on
l'a vu, on peut toujours choisir $\ll$ pour que $\per(x_1, \dots, x_{n-2}, x_{n-1}, x)$ s'annule et
donc le trin{\^o}me prend des valeurs n{\'e}gatives, ce qui prouve que son discriminant est positif.

Il sera impossible de le rendre {\sl strictement\/} n{\'e}gatif ssi $x = 0$, \ie\ $x_{n-1}$ et $x_n$
proportionnels, cqfd.

\question
On montre l'in{\'e}galit{\'e} pour une matrice {\`a} coefficients strictement positifs, 
elle passera sans probl{\`e}me {\`a} la limite par continuit \'e (in{\'e}galit{\'e}s larges).

Quitte {\`a} permuter les colonnes, on peut supposer que $i=n-1$ et $j=n$. En notant que
$\sum_k c_{k,i} \per(M_{k,i}) = \sum_k c_{k,n-1} \per(M_{k,n-1})$ (par exemple) ne serait autre
que le d{\'e}veloppement de
$\per(x_1, \dots, x_{n-1}, x_n)$ par rapport {\`a} la $n-1\up{i{\`e}me}$ colonne, on reconna{\^\i}t
exactement la formule de la question pr{\'e}c{\'e}dente (qui est une forme du th{\'e}or{\`e}me
d'Alexandrov).


\partietitre{Minimum du permanent sur $B_n$}

\qno=-1
\question
 Soit $\vec{F}$ la direction de $F$ ; puisque $f$ atteint un extremum sur $F$ en $x$,  on a pour
tout $h\in\vec{F} \quad df_x (h) = \vec0$
(en notant $df_x$ la diff{\'e}rentielle au point $x$, qui est une forme lin{\'e}aire).

Donc $df_x$ est orthogonale (au sens de la dualit{\'e}) {\`a} $\vec{F}$. Mais l'orthogonal de 
$\vec{F}$ est pr{\'e}cisement vect$(\phi_1, \dots, \phi_i, \dots)$ : cqfd.
\question
Si on permute les lignes et les colonnes de $M$ pour se ramener {\`a} avoir les premiers indices
dans $S$ et les derniers dans $T$, on comprend un peu mieux la notion : une matrice est
d{\'e}composable ssi une telle manipulation y laisse appara{\^\i}tre une matrice nulle en bas {\`a}
gauche : $C = \pmatrix{A & B \cr O & A'}$ o{\`u} $A, A'$ sont carr{\'e}es.

D{\'e}montrons la propri{\'e}t{\'e} de sym{\'e}trie demand{\'e}e {\`a} l'aide de cette remarque :
disons que $A \in {\cal M}_{p}(\R)$, alors chaque colonne de $A$ a pour somme 1, donc la
somme de tous les coefficients de $A$ est $p$. De m{\^e}me, la somme de $A'$ est $n-p$. Comme
la somme de $C$ est $n = p + (n-p)$, cela veut dire que la pauvre matrice $B$ (dont les
coefficients sont $\ge 0$, ne l'oublions pas) n'a que des 0, cqfd.

Si l'on veut {\'e}viter ce subterfuge, la d{\'e}monstration est moins lisible : on remarque que
$$\Sum_{{i \in S} \atop {j\in S}} c_{ij} = \Sum_{i \in S}c_{ij} = p = \hbox{card}(S)
\hskip 5em
\Sum_{{i\in T} \atop {j\in T}}c_{ij} = \Sum_{j \in T} c_{ij}= n - p
$$
Comme $\Sum_{i,j} c_{ij} = n$, il reste 
$\Sum_{{i\in T} \atop {j\in S}} c_{ij} = n - \Sum_{{i\in T} \atop {j\in T}}c_{ij} 
- \Sum_{{i \in S}} c_{ij} = 0$ d'o{\`u} 
$ c_{ij} = 0$ quand $i\in T$ et $j \in S$, cqfd.

\question
Il est clair que {\bf 1} est vecteur propre (commun {\`a} tous les {\'e}l{\'e}ments de $B_n$), le probl{\`e}me
est dans le cas o{\`u} il existe un vecteur propre $x$ non {\bf colin{\'e}aire {\`a} 1} (petite erreur
d'{\'e}nonc{\'e}), tel que $M.x = x$. Prenons pour $S$ l'ensemble des indices $i$ tels que la
coordonn{\'e}e $x_i$ soit minimale, et $T$ le compl{\'e}mentaire. En abr\'egeant
$c_{ij}$ pour $c_{ij}(M)$, $M.x=x$ donne
$$\forall i\in S \qquad x_i =\Sum_k  c_{ik} . x_k \ge  \Sum_k  c_{ik} . x_i = x_i$$
et l'in{\'e}galit{\'e} sera stricte s'il se trouve un $k\in T$ (ie $x_k > x_i$) tel que $c_{ik}>0$ : cela {\'e}tant
impossible, on a d{\'e}montr{\'e} que $M$ est d{\'e}composable.

La r{\'e}ciproque pourrait {\^e}tre utile : soit $M$ d{\'e}composable, $S$ et $T$ associ{\'e}s, 
et le vecteur $x$ de
coordonn{\'e}es $\cases{x_k = 0 & si $k\in S$ \cr x_k = 1 & si $k\in T$}$. On a pour 
$i\in S \quad \Sum_k  c_{ik} . x_k = \Sum_{k\in T}  c_{ik} = 0$ puisque $M$ est
d{\'e}composable. 
 De m{\^e}me, pour
$i\in T \quad \Sum_k  c_{ik} . x_k = \Sum_{k\in T}  c_{ik} = 0 = \Sum_k c_{ik} = 1$.

On a donc exhib{\'e} un vecteur fixe non colin{\'e}aire {\`a} {\bf 1} d{\`e}s que $M$ est d{\'e}composable.
\question
\def\tM{\widetilde{M}}
	% La matrice minimale.
Tout comme dans l'exercice classique du calcul de la diff{\'e}rentielle du d{\'e}terminant, on voit
que les termes du premier ordre en $\eps$ de $\per(\tM + \eps \tM')$ sont les coefficients
de $\tM'$ multipli{\'e}s par leurs ``cofacteurs'' dans $\tM$ : ainsi la limite est
$$\eqalign{
\lim_{\eps\to 0} \Frac{\per(\tM + \eps\tM') - \per(\tM)}\eps & =
\Sum_{i,j} c_{i,j}(\tM')\times \per(\tM_{ij}) \cr
&=  \per(\tM_{s,\sigma(t)}) +  \per(\tM_{t, \sigma(s)})
-   \per(\tM_{s, \sigma(s)}) -  \per(\tM_{t, \sigma(t)})}
$$
\'Enum{\'e}rons quelques lemmes :

\proclaim Lemme 1.
Pour $\eps\ge 0$ assez petit, on a $\tM + \eps \tM \in B_n$.\par

En effet, comme $c_{s, \sigma(s)}(\tM)$ et $c_{t, \sigma(t)}(\tM)$ sont par
hypoth{\`e}se non nuls, la matrice $\tM +\eps. \tM'$ a des coefficients positifs pour $\eps\ge 0$
assez petit, et vu la forme particuli{\`e}re de $\tM'$ les sommes des lignes et colonnes ne
changent pas : $\tM +\eps. \tM' \in B_n$ pour $\eps$ petit.

\proclaim Lemme 2. $S$ et $T$ sont stables par $\sigma$.
\par
On a $c_{s, \sigma(s)}(\tM) > 0$ et $s\in S$, donc $\sigma(s) \notin T$ \ie\ $\sigma(s) \in S$.
De m{\^e}me $\sigma(t)\in T$. On en d{\'e}duit que
$$c_{s, \sigma(t)}(\tM) = c_{t, \sigma(s)}(\tM) = 0$$
\proclaim Lemme 3. On a $\per \tM_{s, \sigma(s)} > 0 , \per \tM_{s, \sigma(t)} = 0$
d{\`e}s que $s\in S, t\in T$.
\par
En d'autres termes, sortir du ``droit chemin'' est fatal.

D'abord, $\prod c_{k, \sigma(k)} > 0 $ par hypoth{\`e}se : donc $\per \tM_{s, \sigma(s)} > 0$
car son d\'eveloppement contient (un morceau de) ce produit.

Ensuite, dans tout terme (produit) du d{\'e}veloppement de $\per \tM_{s, \sigma(t)}$
on va trouver forc{\'e}ment un  $c_{i,\sigma(j)}$ avec $(i,j)\in S\times T$ ou $T\times S$ : si on
appelle {\sl sages\/} les termes de la forme $c_{i,\sigma(j)}$ avec $(i,j)\in S^2 \cup T^2$,
comme le terme manquant (le facteur du cofacteur, $c_{s, \sigma(t)}$) n'est pas sage, il doit y avoir un autre
terme pas sage dans le produit pour que $i$ et $\sigma(j)$ d{\'e}crivent effectivement $S$ et $T$
entiers.

Moralit{\'e} : la fonction $\eps \mapsto \per(\tM + \eps \tM')$, d{\'e}finie pour $\eps$ assez petit
($\eps<1$ notamment) a une d\'eriv\'ee $<0$, elle est donc {\bf d{\'e}croissante} 
pr{\`e}s de 0, ce qui contredit la minimalit{\'e} de
$\per(\tM)$. $\tM$ ne saurait donc {\^e}tre r{\'e}ductible.

\question
Remarque : il n'est pas vrai que l'ind{\'e}composabilit{\'e} de $M$ entra{\^\i}ne celle de $^tM.M$ :
exemple $M = \pmatrix{0&1\cr 1&0}$. Il faut donc utiliser plus.
 
Permuter les lignes ou les colonnes ne change ni le caract{\`e}re
bistochastique, ni le permanent, ni la d\'ecomposabilit\'e. 
On peut donc (si $\sigma$ est comme ci-dessus) mettre les
$c_{i, \sigma(i)}(\tM)>0$ sur la diagonale par permutation des lignes.
Ce qui donne $c_{i, i}(\tM)>0$ pour la nouvelle matrice (encore not\'e $\tM$). 
Alors la diagonale de $^t \tM. \tM$ est strictement
positive, puisque son $i$\up{\`eme} terme sera 
$c_{i,i}(\tM.^t\tM) = c_{i, i}^2(\tM)+\dots \ge c_{i, i}^2(\tM)>0$.

Soit un terme nul de $^t \tM. \tM$, disons que
$$0 = c_{i, j}(^t \tM. \tM) = \sum_k c_{k,i}(\tM).c_{k,j}(\tM) \ge c_{i,i}(\tM).c_{i,j}(\tM)\ge 0$$

Moralit{\'e}, $c_{i, j}(\tM) = 0$ d{\`e}s que  $c_{i, j}(^t \tM.\tM) = 0$ : mais alors 
si $^t \tM.\tM$ \'etait d{\'e}composable, 
 $\tM$ le serait automatiquement, c'est donc impossible.
\question
On prend $F = B_n \cap \{ c_{i,j} = 0\mid (i,j)\in Z \}$ en notant un peu abusivement
$c_{i,j}$ pour une forme lin{\'e}aire. On retire les coefficients qui vont {\^e}tre nuls en $\tM$ pour
pouvoir d{\'e}river (par rapport aux autres).

Posons $f = \per \mid_F$. C'est certainement en $\tM$ une application de classe ${\cal C}^1$
et m{\^e}me plus, car elle est polyn{\^o}miale.

On peut appliquer ${\bf V.0}$ : la diff{\'e}rentielle de $f$ en $\tM$ est une combinaison lin{\'e}aire
des formes (somme d'une ligne) et (somme d'une colonne), et des $c_{i,j} \mid (i,j)\in Z$
car ce sont les formes qui d\'efinissent $F$. Autrement dit, il existe
des coefficients $\ll_i, \mu_j, \gamma_{i,j}$ tels que pour $A\in\vec{F}$:
$$d\per\! _{ \tM} (A) = \sum_{i,j} \per(\tM_{i,j}) a_{i,j}
= \sum_i \ll_i \sum_j a_{i,j} + \sum_j \mu_j \sum _i a_{i,j} 
					+ \sum_{(i,j)\in Z} \gamma_{i,j}.a_{i,j} 
			= \sum_{i,j} (\ll_i + \mu_j) a_{i, j}	+ \sum_{(i,j)\in Z} \gamma_{i,j}.a_{i,j}$$
Par identification, on a bien
$$\forall(i,j)\notin Z \qquad \per(\tM_{i,j}) = \ll_i + \mu_j$$
Remarque : personne n'a dit que $\ll_i$ ou $\mu_j$ fussent d{\'e}termin{\'e}s de mani{\`e}re unique.
Comme on le voit {\`a} la toute derni{\`e}re question, il suffit que $\ll_i + \mu_j = 1/n$.

Autre remarque : on a pour {\bf tout} couple $(i,j)\quad 
c_{i,j}(\tM)\per(\tM_{i,j}) = (\ll_i +\mu_j)c_{ij}(\tM)$.

\question
Fixons $i$ : en posant pour simplifier $m_{i,k} =  c_{i,k}(\tM)$ on a
$$\per(\tM) = \sum_k m_{i,k} \per(\tM_{i,k}) =  \sum_k m_{i,k}(\ll_i + \mu_k)
		= \ll_i + \sum_k m_{i,k}\mu_k 
  $$
  d'o{\`u} (de m{\^e}me pour $^t\tM$) et en posant (par ex) $\ll = {}^t (\ll_1, \dots, \ll_n)$ le
\proclaim Lemme. On a $\ll + \tM.\mu = \mu. + ^t\tM.\ll = \per(\tM).{\bf 1}$\par
Rappelons que {\bf 1} est un vecteur fixe par toute matrice bistochastique. Donc en
composant l'{\'e}galit{\'e} du lemme par $\tM$ (resp. $^t\tM$) on obtient bien
$$\tM.^t\tM.\mu = \per(\tM).{\bf 1} - \tM.\mu = \ll \qquad
\hbox{ et de m{\^e}me} \quad
		^t\tM.\tM.\ll = \ll$$

Puisque $\tM ^t\tM$ est ind{\'e}composable, et que $\ll$ en est un vecteur propre fixe, c'est qu'il
est proportionnel {\`a} {\bf 1} d'apr{\`e}s {\bf V.2}. De m{\^e}me pour $\mu$ (au pire, ils sont nuls : {\c c}a ne
g{\^e}ne pas).
Moralit{\'e}, la quantit{\'e} $\ll_i  + \mu_j$ est constante, et donc aussi $\per(\tM_{i,j})$ quand
$(i,j)\notin Z$ d'apr{\`e}s ce qui pr{\'e}c{\`e}de. Soit $k$ sa valeur :
$$\per(\tM) = \sum_{j } c_{1,j}(\tM) \per(\tM_{1,j})
= \!\!\sum_{j \mid (1,j)\notin Z}\!\! c_{i,j}(\tM) k
= k \!\! \sum_{j \mid (1,j)\notin Z} c_{i,j}
= k  \sum_{j } c_{i,j} = k$$
CQFD.

\question
$\tM' = I - \tM $ est jolie, et $\tM  + \eps\tM' \in B_n$ pour $0<\eps<1$ : donc la fonction
$\eps\mapsto \per(\tM  + \eps\tM' )$ n'a pas le droit d'{\^e}tre d{\'e}croissante en 0. Or
$$\eqalign{
\lim_{\eps\to 0} \Frac{\per(\tM  + \eps\tM' ) - \per(\tM)}{\eps}
			&	 = \sum_{i,j} \per(\tM_{i,j}) . c_{i,j}(\tM')  = \sum_{(i,j)\notin Z} + \sum_{(i,j) \in Z} \cr
   & = \per(\tM) \sum_{(i,j)\notin Z} c_{i,j}(\tM') 
								+ \sum_{(i,j)\in Z} c_{i,j}(\tM').\per(\tM_{i,j})\cr
}
$$
Or $\sum c_{i,j}(\tM') = 0$, d'o{\`u} 
$\sum_{(i,j)\notin Z} c_{i,j}(\tM')  = - \sum_{(i,j)\in Z} c_{i,j}(\tM') = -1$ car $(1,1)$ est le
seul {\'e}l{\'e}ment $(i,j)$ de $Z$ tel que $c_{i,j}(\tM')\not= 0$.

Il reste comme d{\'e}riv{\'e}e : $\per(\tM) - \per(\tM_{1,1})$, qui doit {\^e}tre n{\'e}gatif par mimimalit{\'e}
de $\per(\tM)$ comme ci-avant : cqfd.

\question
Si $(i,j)\notin Z$ c'est fait. Sinon il faut faire comme pr{\'e}c{\'e}demment, en se ramenant au cas
du coefficient $(1,1)$ par permutation de lignes et de colonnes.
\question
Supposons l 'existence d' un $\per(\tM_{i_0,j}) > \per(\tM)$. On a en particulier $c_{i_0,j} = 0$, ou
encore $(i_0,j)\in Z$. Comme le permanent n'est pas nul, il existe forc{\'e}ment un $k$ tel que
$c_{i_0,k} \not=0$. Donc
$$c_{i_0, k} \per(\tM_{i_0, j}) > c_{i_0, k}\per(\tM)
\qquad
  \sum_i c_{i,k} \per(\tM_{i,j}) > \sum_i c_{i,k} \per(\tM)
  $$
Mais par {\bf IV.5} on sait que
$$\per(\tM)^2 \ge  \left( \sum_i c_{i,k} \per(\tM_{i,j})\right)
																																\left( \sum_i c_{i,j} \per(\tM_{i,k})\right)
                                \eqno \forall i,j
$$
avec $\Sum_i c_{i,j} \per(\tM_{i,k}) \ge \Sum_i c_{i,j} \per(\tM) = \per(\tM)$, d'o{\`u}
$\per(\tM)^2 > \per(\tM).\per(\tM) !! $

Notre hypoth{\`e}se est intenable, et donc tous les ``mineurs'' sont {\'e}gaux ({\`a} $\per(\tM)$).

\question
On va d{\'e}montrer un petit moins que ce qui est demand{\'e} pour commencer : que l'on peut
remplacer {\bf une} colonne par sa moyenne avec une autre. Soit en effet $\tM'$ obtenue en
rempla{\c c}ant la colonne $\tM_s$ par $(\tM_s + \tM_t)/2$. D{\'e}veloppons le permanent par
rapport {\`a} cette colonne : on trouve
$$\sum_i \Frac{c_{i,s}+ c_{i,t}}2 \per(\tM'_{i,t})
				= \sum_i \Frac{c_{i,s} + c_{i,t}}2 \per(\tM_{i,t})
    = \per(\tM). \sum_i \Frac{c_{i,s} + c_{i,t}}2
    = \per(\tM)
$$
En reprenant des notations plus voisines de la partie pr{\'e}c{\'e}dente, on a montr{\'e} que
$$\per(x_1, \dots, x_{n-1}, \frac12 (x_{n-1} + x_n)) = \per(x_1, \dots, x_n)$$ 
ou encore par lin{\'e}arit{\'e} et sym{\'e}trie des r{\^o}les
$$\per(x_1, \dots, x_{n-1}, x_{n-1} ) = \per(x_1, \dots, x_{n-1}, x_n)
 = \per(x_1, \dots, x_n, x_n)$$
Maintenant, par bilin{\'e}arit{\'e} par rapport aux deux derni{\`e}res colonnes, on en d{\'e}duit ais{\'e}ment
que
$$\per(x_1, \dots,  \frac12 (x_{n-1} + x_n), \frac12 (x_{n-1} + x_n)) = \per(x_1, \dots, x_n)
\eqno \hbox{CQFD}$$ 
\question
						On ne touche pas {\`a} la colonne $\tM_j$, mais si $\tM_k$ a son $i\up{i{\`e}me}$ terme nul,
on la remplace par sa moyenne avec une autre colonne $\tM_l$ dont le $i\up{i{\`e}me}$ terme
est non nul (il en existe, sinon le permanent serait nul).
Cette proc{\'e}dure retire des z{\'e}ros, mais n'en fait jamais appara{\^\i}tre : donc en un nombre fini
d'{\'e}tapes, on peut retirer tous les z{\'e}ros (d'autant qu'en fait il n'y en a aucun !)
\question
Consid{\'e}rons donc une matrice minimale dont toutes les colonnes sont $>0$, sauf peut-{\^e}tre la
derni{\`e}re : $\tM = (x_1, \dots, x_n)$. En d{\'e}veloppant par rapport {\`a} la derni{\`e}re colonne, on
s'aper{\c c}oit que $\per(x_1, \dots, x_{n-1}, x_{n-1}) = \per(x_1, \dots, x_{n-1}, x_n)
= \per(x_1, \dots, x_n, x_n)$ (les deux nouvelles ne sont plus bistochastiques mais cela n'a
pas d'importance). Donc
$$\per(x_1, \dots, x_{n-1}, x_n)^2 =
			\per(x_1, \dots, x_{n-1}, x_{n-1}) .\per(x_1, \dots, x_n, x_n)$$
   et par {\bf  IV.5} on en d{\'e}duit que les colonnes $x_{n-1}$ et $x_n$ sont proportionnelles.
Comme $\tM\in B_n$, elles sont m{\^e}me {\'e}gales.

De proche en proche, toutes les colonnes sont {\'e}gales. De m{\^e}me, toutes les lignes. Donc la
matrice minimale $\tM$ a tous ses coefficients {\'e}gaux, forc{\'e}ment {\`a} $1/n$, et 
$$m_n = \Frac{n!}{n^n}
\eqno\hbox{Th{\'e}or{\`e}me d'Egorychev \oldstyle 1980}$$

% Monier donn\'e en bibliographie
% KNUTH : A permanent inequality, Amer. Math. Mon., Vol88-10, pp. 737-740.
\bye

