Permutations of a matrix

Pour $n=1$, la matrice $(1)$ est inversible quelle que soit la manière dont on permute les coefficients. Pour $n=2$, on a le même résultat pour $\begin{pmatrix} 1 & 1 \\ 1 &2\end{pmatrix}$. On peut mettre le $2$ où l’on veut, la matrice restera inversible.

Prenons maintenant $n\geqslant3$. On va commencer par montrer que si on considère $n^2-2k$ entiers entre $1$ et $n$, pour $k\in[\![0,n-1]\!]$, alors au moins deux d’entre eux sont égaux. (C’est une conséquence du principe des tiroirs.)
En effet, si tel n’est pas le cas, alors il n’existe qu’au plus une occurence de chaque entier, et ainsi on aurait $n^2-2k\leqslant n$, ou encore $n^2\leqslant n+2k<3n$ car $k<n$. Et ainsi $n<3$, ce qui est absurde.

Utilisons maintenant ce résultat pour montrer qu’on peut permuter les éléments de notre matrice de telle sorte à avoir deux colonnes égales, ce qui rendra la matrice non-inversible.
Notre matrice possède donc $n^2$ coefficients entre $1$ et $n$, donc (en prenant $k=0$) le résultat précédent nous donne que deux d’entre eux sont égaux. On se les met de côté, il reste donc $n^2-2$ coefficients dans la matrice.
Pour $k=1$, on a donc encore deux coefficients égaux. On les remet de côté, il en reste $n^2-4$ et ainsi de suite par récurrence. On arrive finalement à $n^2-2(n-1)$ coefficients restants dans la matrice et ainsi le cas $k=n-1$ nous donne notre $n$-ème paire de coefficients égaux.
On peut ainsi former, avec ces $n$ paires de coefficients égaux, deux colonnes égales. Ce qui conclut.