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

Nour-Eddine Fahssi · 2026

Read The limits of Schur multipliers in Pólya conversion problems for the 𝒒 q -permanent function by Nour-Eddine Fahssi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-24349.txt.

Introduction

Fahssi studies Polya switch for the q-permanent, proving a sharp threshold. For n at least 3 and q not plus or minus 1, switch to the det or permanent is ruled out. Schur keepers are listed for n equal to 2, with powers of size twice n minus 2. For lower Hessenberg grids, the block lifts, giving a det cut and a cubic-time method. Swap powers are listed too: for n at least 4, patterns sit inside the mirror group. A mixed switch problem has answers only for n up to 4.

Catalog record

CREATORNour-Eddine Fahssi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66922
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.24349

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The limits of Schur multipliers in Pólya conversion problems for the 𝒒 q -permanent function Nour-Eddine Fahssi Abstract . This paper studies generalized Pólya conversion problems for the q q -permanent. We establish a sharp threshold governing the transition from low-dimensional algebraic flexibility to higher-dimensional combinatorial rigidity. For n ≥ 3 n\geq 3 and q ≠ ± 1 q\neq\pm 1 , we prove that the q q -permanent is not linearly convertible to the determinant or permanent. Conversely, we completely classify the space of Schur multiplier preservers for n = 2 n=2 . Focusing on Schur multipliers, we characterize the preserver exponents as a ( 2 ​ n − 2 ) (2n-2) -dimensional space of additive matrices. We show that for lower Hessenberg matrices, the general geometric obstruction disappears, yielding an explicit determinantal reduction and an 𝒪 ⁡ ( n 3 ) \mathcal{O}(n^{3}) evaluation algorithm. Furthermore, we classify permutational converter exponents, proving that for n ≥ 4 n\geq 4 , admissible symmetries are strictly constrained to the dihedral group. Finally, we resolve a mixed conversion problem, showing the solution space is nonempty only for n ≤ 4 n\leq 4 , which provides a direct algebraic characterization of the q q -permanent’s zero locus in low dimensions. 2020 Mathematics Subject Classification 15A15, 05E15, 05A05 1. Introduction Let \mathbb{F}^{n\times n} denote the vector space of n\times n matrices over a field \mathbb{F} . The determinant and permanent are fundamental matrix functions, yet they exhibit a well-known computational dichotomy: while the determinant can be evaluated efficiently in polynomial time, computing the permanent is #P-complete. Motivated by this disparity, Pólya [ 10 ] asked in 1913 whether there exists a uniform rule for assigning signs \pm 1 to the entries of a generic matrix A to obtain a matrix B satisfying \mathrm{per}(A)=\det(B) . Szegö [ 12 ] demonstrated that this procedure fails for n\geq 3 . Marcus and Minc [ 7 ] generalized this negative result, proving that no linear transformation \varphi satisfies \mathrm{per}(X)=\det(\varphi(X)) for n\geq 3 . A closely related question is the linear preserver problem, which asks us to characterize all linear maps \varphi such that F(\varphi(X))=F(X) for a given matrix function F . Frobenius [ 6 ] characterized determinant preservers, and Marcus and May [ 8 ] provided the analogous characterization for the permanent. In this work, we investigate the conversion problems for the q -permanent. For a matrix A and a parameter q\in\mathbb{C}^{\times} , the q -permanent is defined by [ 13 ] (1.1) \mathrm{Per}_{q}(A)\coloneqq\sum_{\sigma\in\mathfrak{S}_{n}}q^{\ell(\sigma)}\prod_{i=1}^{n}a_{i,\sigma(i)}, where \mathfrak{S}_{n} is the symmetric group and \ell(\sigma) is the inversion length of \sigma . The q -permanent interpolates between the permanent ( q=1 ) and the determinant ( q=-1 ). Marques de Sá [ 9 , Theorem 3.3] characterized the group \mathcal{G}_{q} of q -permanent preservers for q\notin\{-1,1\} . This group is generated by the reversal permutation \sigma_{0}(i)=n+1-i and diagonal scalings. We define the q -permanent to be linearly convertible to the determinant (resp. permanent) if there exists an injective linear map \varphi such that, for all X\in\mathbb{C}^{n\times n} , (1.2) \mathrm{Per}_{q}(X)=\det(\varphi(X))\quad(\text{resp.}\ \mathrm{Per}_{q}(X)=\per(\varphi(X))). This formulation provides a natural q -analog of the classical Pólya problem. Furthermore, we formalize the extended linear conversion problem as follows: characterize all linear maps \varphi and scalars q^{\prime}\in\mathbb{C}^{*} (potentially depending on \varphi and q ) satisfying the identity (1.3) \mathrm{Per}_{q}(X)=\mathrm{Per}_{q^{\prime}}(\varphi(X))\quad\text{for all }X\in\mathbb{C}^{n\times n}. This framework unifies the classical preserver problem ( q=q^{\prime} ) and the converter problem ( q\neq q^{\prime} ). Specifically, we investigate whether the q -permanent permits conversions to the determinant or permanent via Schur multipliers (weighted entry-wise scalings) of the form (1.4) \varphi:A\longmapsto\left[z^{\lambda_{i,j}}a_{i,j}\right]=z^{\Lambda}\circ A,\quad z\in\mathbb{C}^{\times}, where \circ is the Hadamard product. For an n\times n matrix \Lambda=[\lambda_{i,j}] , we write z^{\Lambda}\coloneqq[z^{\lambda_{i,j}}]_{i,j=1}^{n} . If the matrix \Lambda satisfies the conversion or preservation conditions, it is called a converter exponent or preserver exponent , respectively. Organization and contributions Section 2 establishes that a general linear conversion is impossible for n\geq 3 (Theorem 2.1 ). For n=2 , we completely classify the linear converters and show that the solution space decomposes into two distinct families (Theorem 2.2 ). Section 3 characterizes the set of preserver exponents (Theorem 3.1 ) as a (2n-2) -dimensional subspace defined by a discrete Monge condition. Section 4 shows that for lower Hessenberg matrices, the general obstruction disappears, yielding an explicit determinantal conversion and, consequently, an \mathcal{O}(n^{3}) evaluation algorithm (Theorem 4.1 ). Section 5 classifies permutational converter exponents, proving that while solutions exist for all permutations when n\leq 3 , admissible symmetries are strictly constrained to the dihedral group D_{n} for n\geq 4 (Theorem 5.2 ). Finally, Section 6 addresses a mixed conversion problem expressing the q -permanent as a linear combination of the determinant and permanent. We show that the corresponding solution space is nonempty if and only if n\leq 4 , which provides a direct algebraic characterization of the q -permanent’s zero locus in low dimensions (Theorem 6.1 ). Section 7 concludes the paper with a summary and a discussion of possible directions for future research. Notations . Throughout the paper, we assume q\neq 0 . For each \sigma\in\mathfrak{S}_{n} , P_{\sigma} denotes the associated n\times n permutation matrix. Let J_{n} be the all-ones matrix in \mathbb{C}^{n\times n} , and let E_{i,j} denote the standard matrix units. For a matrix M and a permutation \sigma , we define the diagonal product and the \sigma -trace by \mathrm{wt}_{\sigma}(M)\coloneqq\prod_{i=1}^{n}m_{i,\sigma(i)},\qquad\tr_{\sigma}(M)\coloneqq\sum_{i=1}^{n}m_{i,\sigma(i)}. The standard matrix trace corresponds to \sigma=\mathrm{id} . We denote by \sigma_{0} the reversal permutation defined by \sigma_{0}(i)=n+1-i . 2. General Impossibility and the n=2 Classification Our first result extends the Pólya–Szegö rigidity phenomenon for the permanent to the q -permanent. Theorem 2.1 . For n\geq 3 and q\neq-1 , there is no linear transformation that satisfies ( 1.2 ) for all A\in\mathbb{C}^{n\times n} . Proof. Let q\neq\pm 1 , and let F denote the determinant or permanent function. Suppose that there exists a linear transformation \varphi such that \mathrm{Per}_{q}(X)=F(\varphi(X)) for all X\in\mathbb{C}^{n\times n} . We first demonstrate that such a transformation must be invertible. Assume that \varphi is singular, that is, \varphi(A)=0 for some non-zero matrix A=\left[a_{ij}\right] . Consequently, the q -permanent must be translation-invariant by A : \mathrm{Per}_{q}(X+A)=F(\varphi(X+A))=F(\varphi(X))=\mathrm{Per}_{q}(X) , for all X\in\mathbb{C}^{n\times n}. Using the fact that row and column permutations change F only by a sign, F(\Pi X\Sigma)=\pm F(X) for permutation matrices \Pi and \Sigma , we may assume without loss of generality that a_{11}\neq 0 . Let B be the matrix defined by: b_{ij}=\begin{cases}-a_{1j}&\text{if }i=1,\\ \delta_{ij}&\text{if }i>1.\end{cases} The matrix B+A has a zero first row, which implies \mathrm{Per}_{q}(B+A)=0 . However, the matrix B itself is upper triangular with diagonal entries (-a_{11},1,\dots,1) . Thus, \mathrm{Per}_{q}(B)=-a_{11}\neq 0 . This contradicts the translation invariance condition \mathrm{Per}_{q}(B)=\mathrm{Per}_{q}(B+A) . Therefore, we can infer that \varphi is invertible. If T\in\mathcal{G}_{q} , then for any X , F(\varphi T\varphi^{-1}(X))=\mathrm{Per}_{q}(T\varphi^{-1}(X))=\mathrm{Per}_{q}(\varphi^{-1}(X))=F(X). Thus, the conjugation map \Phi:T\mapsto\varphi T\varphi^{-1} preserves F and yields a group isomorphism \mathcal{G}_{q}\cong\mathcal{G}_{\pm 1} . Since \varphi is a linear isomorphism, \Phi is an isomorphism of linear algebraic groups over \mathbb{C} . As such, \mathcal{G}_{q} and \mathcal{G}_{\pm 1} must share the same dimension for their identity component \dim(\mathcal{G}^{\circ}) and the same cardinality for their finite group of connected components |\mathcal{G}/\mathcal{G}^{\circ}| . According to the characterization by Marques de Sá [

Read the complete text