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

Technical Summary: The Limits of Schur Multipliers in Pólya Conversion Problems for the q-Permanent Function

Problem Statement
This paper investigates generalized Pólya conversion problems concerning the $q$-permanent function, defined for an $n \times n$ matrix $A$ and a parameter $q \in \mathbb{C}^*$ as:
$$P_q(A) = \sum_{\sigma \in S_n} q^{\ell(\sigma)} \prod_{i=1}^n a_{i,\sigma(i)},$$
where $\ell(\sigma)$ denotes the inversion length of the permutation $\sigma$. The $q$-permanent interpolates between the permanent ($q=1$) and the determinant ($q=-1$).

The central inquiry extends the classical Pólya problem: Does there exist a linear transformation $\phi: \mathbb{C}^{n \times n} \to \mathbb{C}^{n \times n}$ such that $P_q(X) = \det(\phi(X))$ (or $P_q(X) = \text{per}(\phi(X))$) for all $X$? Specifically, the authors restrict their analysis to Schur multipliers (weighted entry-wise scalings) of the form $\phi(A) = z^\Lambda \circ A$, where $\Lambda$ is a parameter matrix and $z$ is a fixed complex number. The paper seeks to determine the existence, structure, and geometric properties of such "converter exponents" $\Lambda$ and "preserver exponents" (where $q' = q$) across different dimensions $n$ and parameter regimes.

Methodology
The authors employ a blend of algebraic combinatorics, linear algebra, and geometric analysis:

1. Algebraic Formulation: The conversion conditions are translated into systems of linear equations involving the traces of the exponent matrix $\Lambda$ over permutations ($\text{Tr}_\sigma(\Lambda) = \sum \lambda_{i,\sigma(i)}$).
2. Group Theoretic Analysis: The study of preserver groups ($G_q$) and their isomorphism to the preserver groups of the determinant and permanent is used to establish impossibility results for $n \ge 3$.
3. Geometric Interpretation: For $n=2$, the problem is framed as finding linear isometries between quadratic forms associated with the $q$-permanent and the determinant, utilizing the complex orthogonal group $O(4, \mathbb{C})$.
4. Combinatorial Constraints: The analysis of "balanced quadruples" of permutations is used to derive necessary conditions (discrete Monge relations) for the existence of solutions in higher dimensions.
5. Case-Specific Reductions: The paper analyzes restricted matrix classes (e.g., lower Hessenberg matrices) where the combinatorial complexity of the symmetric group is reduced, allowing for explicit constructions.

Key Contributions and Results

1. Impossibility of Universal Conversion for $n \ge 3$
The paper establishes that for $n \ge 3$ and $q \neq \pm 1$, no linear transformation exists that converts the $q$-permanent to the determinant or permanent universally. This is proven by showing that the group of linear maps preserving the $q$-permanent ($G_q$) is structurally distinct (and significantly smaller) than the preserver groups of the determinant or permanent for $n \ge 3$.

2. Complete Classification for $n = 2$
For $n=2$, the solution space is fully classified. The set of converters forms a smooth complex variety of dimension six, decomposing into two distinct families:

• Family I: Converters with an invertible leading block, forming an affine family over $GL_2(\mathbb{C})$.
• Family II: Converters arising from the degenerate case where the leading block is zero.
  Geometrically, this corresponds to the fact that in dimension 2, both the $q$-permanent and determinant arise from non-degenerate bilinear forms on $\mathbb{C}^4$, making them isomorphic under the action of $O(4, \mathbb{C})$.

3. Structure of Preserver Exponents
The space of Schur multiplier preservers is characterized based on the modulus of $z$:

• Case $|z| \neq 1$: The solution space is a $(2n-2)$-dimensional vector space consisting of additive matrices ($r_{i,j} = u_i + v_j$) satisfying a discrete Monge relation. This space forms a Jordan triple system.
• Case $|z| = 1$: The solution space becomes a countable union of affine lattices. As $z \to 1$, non-principal sheets diverge to infinity, recovering the continuous vector space limit.

4. Exact Conversion for Lower Hessenberg Matrices
While universal conversion fails for general matrices, the paper proves that for the class of lower Hessenberg matrices (where $a_{i,j} = 0$ for $j > i+1$), the $q$-permanent admits an explicit determinantal reduction via a Schur multiplier. This yields an $O(n^3)$ algorithm for evaluating the $q$-permanent on this specific class, effectively bypassing the $\#P$-completeness of the general case.

5. Permutational Symmetries and the Dihedral Threshold
The paper analyzes conversions involving permutation matrices $\phi(X) = X P_\tau$.

• For $n \le 3$, such conversions exist for all $\tau \in S_n$.
• For $n \ge 4$, admissible symmetries are strictly restricted to the dihedral group $D_n$. This rigidity arises because the trace constraints imposed by balanced quadruples of permutations are incompatible with non-dihedral permutations.

6. Mixed Conversion and Dimensional Thresholds
The authors investigate expressing the $q$-permanent as a linear combination of the determinant and permanent: $P_q(A) = c_1 \text{per}(\phi_1(A)) + c_2 \det(\phi_2(A))$.

• Existence: Such mixed conversions exist if and only if $n \le 4$.
• Obstruction: For $n \ge 5$, the solution space is empty. The proof relies on a geometric obstruction involving the dihedral subgroup $D_5$, showing that the required trace conditions lead to a contradiction ($-10 \ge -5$).
• Zero Locus: For $n \le 4$, this mixed formulation provides an algebraic characterization of the zero locus of the $q$-permanent via a generalized Pólya identity.

Significance and Claims
The paper claims to establish sharp rigidity thresholds governing permutational symmetries and mixed conversion identities. It demonstrates that the introduction of the deformation parameter $q$ does not alleviate the fundamental rigidity of the Pólya problem in high dimensions ($n \ge 5$), but rather shifts the structural constraints.

The work provides a complete geometric and algebraic picture of the $q$-permanent's convertibility:

• It identifies $n=4$ as the critical dimensional threshold beyond which no linear combination of determinant and permanent can represent the $q$-permanent.
• It characterizes the solution spaces as either continuous vector spaces (for $|z| \neq 1$) or discrete unions of affine lattices (for $|z|=1$).
• It highlights that while universal conversion is impossible, structural restrictions (like Hessenberg matrices) or mixed formulations (for $n \le 4$) can yield computationally efficient reductions.

The authors conclude that the combinatorial growth of inversion constraints in higher dimensions conflicts with the flat additive structure required by Schur multipliers, producing universal obstructions that are specific to the $q$-deformation and the nature of the symmetric group.