Maximum du déterminant
Réponses
-
Finalement, après avoir écrit un truc, l'avoir supprimé en me disant que c'était faux, je commence à me dire que ce ne l'était sans doute pas tant que cela, je reviens donc à la charge ...Soit $A=(a_{ij})$ une matrice solution. J'appelle $A(x)$ la matrice obtenue en remplaçant $a_{11}$ par $x$. Le déterminant de $A(x)$ est un polynôme de degré au plus $1$ en $x$, il est donc soit constant, soit maximal en $1$ ou en $-1$. Donc on peut choisir $a_{11} \in \{-1,1\}$ (et même ce choix est forcé si le poly est bien de degré $1$).On fait cela avec chaque coefficient.
-
Joli.
-
Bonsoir !
On fait comment avec cette matrice?$\begin{bmatrix}x&0&1\\ 0 & 1 & 0\\ 1 &0 &0 \end{bmatrix}$ -
Ce n'est pas une matrice solution donc l'algorithme proposé ne s'applique pas.
-
Bonjour,
Ce n'est pas si ma mémoire est bonneLe problème du déterminant maximal d'Hadamard
Le 😄 Farceur -
Je mets les coefficients en un vecteur $X$ de taille $n^2$.Je cherche à maximiser une fonction $f$ sur le produit $[-1,1]^{n^2}$. Je prétends tout simplement que si $\bar{X}$ est un point de maximum, a fortiori, le maximum de la fonction $X_1 \mapsto f(X_1,\bar{X_2},\ldots,\bar{X_{n^2}})$ définie sur $[-1,1]$ est atteint (au moins) en $\bar{X_1}$.C'est cette idée qui permet de démontrer les résultats sur les extrema de fonctions de plusieurs variables à partir de ceux d'une variable.Donc revenons sur ton exercice, le maximum en fonction du premier coefficient est a fortiori atteint en $a_{11}$, les autres coefficients étant fixés à la valeur qui réalise le maximum.De deux choses l'une : soit ma fonction de $x$ est constante et auquel cas tu peux remplacer $a_{11}$ par $1$ ou $-1$ ce qui ne changera pas la valeur du déterminant, soit ta fonction n'est pas constante auquel cas nécessairement le $a_{11}$ vaut $1$ ou $-1$, sinon tu ne serais pas au maximum.
-
J'ai bien entendu oublié de dire que ton problème admet une solution en raison des propriétés classiques (maximisation d'une fonction numérique continue sur un compact non vide).
-
BonjourPour les déterminants de taille $2^k$, il n'est pas très difficile de trouver par récurrence un déterminant qui réalise le maximum $2^{k2^{k-1}}$. Et pour les tailles qui ne sont pas des puissances de 2 ? (Je ne connais pas la réponse).
-
Par le lemme de Hadamard, un majorant du maximum est $n^{n/2}$.En particulier, lorsque $n=2^k$, on remarque que c'est le maximum donné par GaBuZoMeu.
-
Une autre manière de voir les choses, mais qui nécessite un peu plus de travail (il faut gérer les arêtes).1) Je pense que l'on est d'accord que sauf en des cas "dégénérés", une forme multilinéaire $f$ ne peut pas avoir de maximum en l'intérieur de $[-1,1]^k$, car si on a un point solution $\bar{x}$ à l'intérieur, on regarde $\lambda \mapsto f(\lambda \bar{x})=\lambda^k f(\bar{x})$ qui sera strictement monotone au voisinage de $1$ (ou constante si $f(\bar{x})=0$). Donc il n'y a pas de point solution déjà dans $]-1,1[^{n^2}$ sur ton exemple (je pense qu'on est bien d'accord que sur ton exemple $f(\bar{x})\not=0$)2) Ensuite, il se pourrait que certaines composantes soient fixées à $\pm 1$ mais pas toutes. Tu regardes la multilinéarité par rapport à celles qui ne sont pas égales à $\pm 1$ ce qui te ramène au cas précédent.EDIT : suite à la gentil mp d'un membre du forum que je remercie, j'ai corrigé la faute sur arête, que j'ai toujours faite !
-
Les tailles pour lesquelles GaBuZoMeu donne une réponse ne sont pas sans rappeler celles pour lesquelles Sylvester a construit des matrices de Hadamard, i.e. des matrices orthogonales dont les coefficients valent $\pm1$.
-
La valeur maximale ne semble pas connue dans le cas général : http://oeis.org/A003433
-
L'ordinateur sature vite. Si on note $M_n$ le maximum pour une matrice de taille $n$, on a\[M_1=1,\quad M_2=2,\quad M_3=4,\quad M_4=16,\quad M_5=48.\]Mon ordinateur est en train de chauffer pour $M_6$...
Édit. Je viens seulement de voir le lien de JLT. -
Avec $7\cdot10^{10}$ matrices environ, ça va prendre un moment !
-
Effectivement, si l'existence du maximum et le fait qu'il soit atteint en des coins, question initiale, est assez simple (j'y ai répondu par des arguments classiques), caractériser sa valeur l'est moins en toute généralité.
-
J'ai fixé la première ligne de la matrice avec uniquement des un pour gagner un petit peu de temps, mais ça reste super exponentielle...
-
Plus qu'un milliard de cas, si je ne me trompe pas.
-
En effet, on a $2^{36 - 6} = 2^{30}\approx 10^{9,03}$.En comparaison pour $n=5$, on a $2^{25-5} = 2^{20}\approx 10^{6,02}$.
-
Je trouve ça sauf erreur
1 : 12 : 23 : 44 : 165 : 486 : 1607 : 5768 : 40969 : 1433610 : 7372811 : 31948812 : 121651213 : 415396814 : 20250624
Bon à partir de 11 je suis mauvais
https://oeis.org/search?q=1,2,4,16,48,160&language=french&go=Chercher -
Personnellement, je n'ai pas compris pourquoi on ne pouvait que des $1$ sur la première ligne, et encore moins pourquoi on peut le faire simultanément sur la première ligne et sur la première colonne ; en tout cas, la considération du cas $n=2$ démontre que c'est faux (le deuxième) au moins pour cette valeur de $n$.
-
Mille mercis (par matrice) !
-
Comme j'ai dit c'est un problème de déjà vuLe 😄 Farceur
-
@math2 : L'algorithme brutal est de tester toutes les matrices. On peut multiplier chaque ligne et chaque colonne où c'est nécessaire par -1 pour fixer les coefficients de la première ligne et de la première colonne à 1 : il suffit de considérer la valeur absolue du déterminant pour récupérer le maximum (Un nombre D est un déterminant possible ssi -D l'est). Le seul intérêt de cette méthode est de passer de $2^{n^2}$ matrices à tester à $2^{(n-1)^2}$.
-
Ah oui d'accord, j'étais resté sur "maximum", alors qu'effectivement en acceptant également de chercher les minima la multiplication par $-1$ sur des lignes et colonnes bien choisies est possible.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 27
+16 Invités