Polya problem on the conversion between determinant and permanent
Alexander Guterman (Moscow State University)
Thursday 26 April 2012, 15.00, b-it 1.25 (cosec meeting room)
Two important functions in matrix theory, determinant and permanent, look very similar: $$ \det A= \sum_{\sigma\in { S}_n} sgn({\sigma}) a_{1\sigma(1)}\cdots a_{n\sigma(n)} \quad \mbox{ and } \quad \per A= \sum_{\sigma\in { S}_n} a_{1\sigma(1)}\cdots a_{n\sigma(n)} $$ here $A=(a_{ij})\in M_n(F)$ is an $n\times n$ matrix and ${ S}_n$ denotes the set of all permutations of the set $\{1,\ldots, n\}$. The value $sgn(\sigma)\in \{-1,1\}$ is the signum of the permutation $\sigma$.
While the computation of the determinant can be done in a polynomial time, it is still an open question, if there are such algorithms to compute the permanent. Due to this reason, starting from the work by P\'olya, 1913, different approaches to convert the permanent into the determinant were under the intensive investigation. In this regard the following two definitions naturally appear:
A transformation $T$ on a certain matrix set $S$ is called a {\em conversion on $S$\/} if $\per A=\det T(A)$ for all $A\in S$.
A single matrix $A $ is called {\em sign-convertible\/} if there exists a $(+1,-1)$ matrix $X $ such that $\per A = \det (X \circ A)$, where $X\circ A$ is the entrywise product of matrices.
Among our results we prove that there are no bijective conversions for the matrices over finite fields of sufficiently large cardinality. Also we investigate Gibson barriers (the maximal and minimal numbers of non-zero elements) for convertible $(0,1)$-matrices. Our results will be illustrated by the number of examples and counterexamples.
Joint work with Gregor Dolinar, Bojan Kuzma and Marko Orel.