The limits of Schur multipliers in Pólya conversion problems for the $q$-permanent function

Résumé Technique : Les Limites des Multiplicateurs de Schur dans les Problèmes de Conversion de Pólya pour la Fonction $q$-Permanent

Énoncé du Problème
Cet article examine les problèmes de conversion de Pólya généralisés concernant la fonction $q$-permanent, définie pour une matrice $A$ de taille $n \times n$ et un paramètre $q \in \mathbb{C}^*$ par :
$$P_q(A) = \sum_{\sigma \in S_n} q^{\ell(\sigma)} \prod_{i=1}^n a_{i,\sigma(i)},$$
où $\ell(\sigma)$ désigne la longueur des inversions de la permutation $\sigma$. Le $q$-permanent interpole entre le permanent ($q=1$) et le déterminant ($q=-1$).

La question centrale étend le problème classique de Pólya : Existe-t-il une transformation linéaire $\phi: \mathbb{C}^{n \times n} \to \mathbb{C}^{n \times n}$ telle que $P_q(X) = \det(\phi(X))$ (ou $P_q(X) = \text{per}(\phi(X))$) pour tout $X$ ? Plus précisément, les auteurs restreignent leur analyse aux multiplicateurs de Schur (des mises à l'échelle pondérées entrée par entrée) de la forme $\phi(A) = z^\Lambda \circ A$, où $\Lambda$ est une matrice de paramètres et $z$ un nombre complexe fixe. L'article cherche à déterminer l'existence, la structure et les propriétés géométriques de tels « exposants de conversion » $\Lambda$ et « exposants de préservation » (où $q' = q$) à travers différentes dimensions $n$ et régimes de paramètres.

Méthodologie
Les auteurs emploient un mélange de combinatoire algébrique, d'algèbre linéaire et d'analyse géométrique :

1. Formulation Algébrique : Les conditions de conversion sont traduites en systèmes d'équations linéaires impliquant les traces de la matrice d'exposants $\Lambda$ sur les permutations ($\text{Tr}_\sigma(\Lambda) = \sum \lambda_{i,\sigma(i)}$).
2. Analyse Théorique des Groupes : L'étude des groupes de préservation ($G_q$) et de leur isomorphisme avec les groupes de préservation du déterminant et du permanent est utilisée pour établir des résultats d'impossibilité pour $n \ge 3$.
3. Interprétation Géométrique : Pour $n=2$, le problème est formulé comme la recherche d'isométries linéaires entre des formes quadratiques associées au $q$-permanent et au déterminant, en utilisant le groupe orthogonal complexe $O(4, \mathbb{C})$.
4. Contraintes Combinatoires : L'analyse de « quadruplets équilibrés » de permutations est utilisée pour dériver des conditions nécessaires (relations de Monge discrètes) pour l'existence de solutions en dimensions supérieures.
5. Réductions Spécifiques aux Cas : L'article analyse des classes de matrices restreintes (par exemple, les matrices de Hessenberg inférieures) où la complexité combinatoire du groupe symétrique est réduite, permettant des constructions explicites.

Contributions et Résultats Clés

1. Impossibilité de Conversion Universelle pour $n \ge 3$
L'article établit que pour $n \ge 3$ et $q \neq \pm 1$, aucune transformation linéaire n'existe pour convertir universellement le $q$-permanent en déterminant ou en permanent. Cela est prouvé en montrant que le groupe des applications linéaires préservant le $q$-permanent ($G_q$) est structurellement distinct (et significativement plus petit) que les groupes de préservation du déterminant ou du permanent pour $n \ge 3$.

2. Classification Complète pour $n = 2$
Pour $n=2$, l'espace des solutions est entièrement classifié. L'ensemble des convertisseurs forme une variété complexe lisse de dimension six, se décomposant en deux familles distinctes :

• Famille I : Convertisseurs avec un bloc principal inversible, formant une famille affine sur $GL_2(\mathbb{C})$.
• Famille II : Convertisseurs issus du cas dégénéré où le bloc principal est nul.
  Géométriquement, cela correspond au fait qu'en dimension 2, tant le $q$-permanent que le déterminant proviennent de formes bilinéaires non dégénérées sur $\mathbb{C}^4$, les rendant isomorphes sous l'action de $O(4, \mathbb{C})$.

3. Structure des Exposants de Préservation
L'espace des multiplicateurs de Schur préservateurs est caractérisé en fonction du module de $z$ :

• Cas $|z| \neq 1$ : L'espace des solutions est un espace vectoriel de dimension $(2n-2)$ composé de matrices additives ($r_{i,j} = u_i + v_j$) satisfaisant une relation de Monge discrète. Cet espace forme un système de triplets de Jordan.
• Cas $|z| = 1$ : L'espace des solutions devient une union dénombrable de réseaux affines. Lorsque $z \to 1$, les feuilles non principales divergent vers l'infini, retrouvant la limite d'espace vectoriel continu.

4. Conversion Exacte pour les Matrices de Hessenberg Inférieures
Bien que la conversion universelle échoue pour les matrices générales, l'article prouve que pour la classe des matrices de Hessenberg inférieures (où $a_{i,j} = 0$ pour $j > i+1$), le $q$-permanent admet une réduction déterminantale explicite via un multiplicateur de Schur. Cela produit un algorithme en $O(n^3)$ pour évaluer le $q$-permanent sur cette classe spécifique, contournant efficacement la complétude $\#P$ du cas général.

5. Symétries Permutationnelles et Seuil Diédral
L'article analyse les conversions impliquant des matrices de permutation $\phi(X) = X P_\tau$.

• Pour $n \le 3$, de telles conversions existent pour tout $\tau \in S_n$.
• Pour $n \ge 4$, les symétries admissibles sont strictement restreintes au groupe diédral $D_n$. Cette rigidité découle du fait que les contraintes de trace imposées par les quadruplets équilibrés de permutations sont incompatibles avec les permutations non diédrales.

6. Conversion Mixte et Seuils Dimensionnels
Les auteurs examinent l'expression du $q$-permanent comme une combinaison linéaire du déterminant et du permanent : $P_q(A) = c_1 \text{per}(\phi_1(A)) + c_2 \det(\phi_2(A))$.

• Existence : De telles conversions mixtes existent si et seulement si $n \le 4$.
• Obstruction : Pour $n \ge 5$, l'espace des solutions est vide. La preuve repose sur une obstruction géométrique impliquant le sous-groupe diédral $D_5$, montrant que les conditions de trace requises conduisent à une contradiction ($-10 \ge -5$).
• Lieu des Zéros : Pour $n \le 4$, cette formulation mixte fournit une caractérisation algébrique du lieu des zéros du $q$-permanent via une identité de Pólya généralisée.

Signification et Revendications
L'article revendique l'établissement de seuils de rigidité nets régissant les symétries permutationnelles et les identités de conversion mixte. Il démontre que l'introduction du paramètre de déformation $q$ n'allège pas la rigidité fondamentale du problème de Pólya en hautes dimensions ($n \ge 5$), mais déplace plutôt les contraintes structurelles.

L'ouvrage fournit une image géométrique et algébrique complète de la convertibilité du $q$-permanent :

• Il identifie $n=4$ comme le seuil dimensionnel critique au-delà duquel aucune combinaison linéaire de déterminant et de permanent ne peut représenter le $q$-permanent.
• Il caractérise les espaces de solutions comme soit des espaces vectoriels continus (pour $|z| \neq 1$), soit des unions discrètes de réseaux affines (pour $|z|=1$).
• Il met en évidence que, bien que la conversion universelle soit impossible, des restrictions structurelles (comme les matrices de Hessenberg) ou des formulations mixtes (pour $n \le 4$) peuvent produire des réductions computationnellement efficaces.

Les auteurs concluent que la croissance combinatoire des contraintes d'inversion en dimensions supérieures entre en conflit avec la structure additive plate requise par les multiplicateurs de Schur, produisant des obstructions universelles spécifiques à la $q$-déformation et à la nature du groupe symétrique.