ИСТИНА

This talk is based on the joint works with Mikhail Budrevich, Gregor Dolinar, and Bojan Kuzma. Two important functions in matrix theory, determinant and permanent, look very similar: $$ \det A= \sum_{\sigma\in {\mathfrak S}_n} sgn({\sigma}) a_{1\sigma(1)}\cdots a_{n\sigma(n)} \quad \mbox{ and } \quad \per A= \sum_{\sigma\in {\mathfrak S}_n} a_{1\sigma(1)}\cdots a_{n\sigma(n)} $$ here $A=(a_{ij})\in M_n(F)$ is a matrix, ${\mathfrak S}_n$ denotes the set of all permutations of the set $\{1,2,\ldots, n\}$. The value $sgn(\sigma)\in \{-1,1\}$ is the signum of the permutation $\sigma$. Starting from the work of P\'olya, 1913, many researchers are investigating different approaches to convert the permanent into the determinant. Let $M_n$ denote the set of all $n\times n$ matrices with the entries 0 or 1 over the field of real numbers ${\mathbb R}$. Let $X\circ A$ denote the entrywise product of two matrices. A matrix $A \in M_n$ is {\em convertible\/} if there exists $X \in \Mnpm$ such that $\per A = \det (X \circ A)$. Let $v(A)$ denote the number of nonzero elements in a $(0,1)$-matrix $A$. In 1971 Gibson proved that if $A\in M_n$ is convertible matrix with $\per A>0$, then $v(A)\le \Omega_n:=(n^2+3n-2)/2$ and the equality holds if and only if there exist permutation matrices $P,Q\in M_n(\C)$ such that $A=PT_nQ$, where $T_n=(t_{ij})\in M_n$ with $$t_{ij}=\left\{ \begin{array}{ccl} 0 & \mbox{ if } & 1\le i<j<n\\ 1 & \mbox{ if } & i\ge j \mbox{ or } j=n \end{array} \right. . $$ The above theorem says that the number $\Omega_n=(n^2+3n-2)/2$ provides a barrier for the conversion, and extremal convertible matrix is unique up to the permutation equivalence. From Gibson's theorem and further investigations the following problem naturally arises: To compute the function $\omega_n$ such that for any $A\in M_n$ with $v(A)\le \omega_n$ it holds that $A$ is convertible. Our work is devoted to the complete solution of this problem. Moreover, we prove the analog of Gibson result and find the value of $\omega_n$ for the set of symmetric (0,1) matrices. Several related problems and examples will be discussed in the talk.