

Iskovskikh Seminar
September 10, 2020 18:00–19:30, Moscow, Steklov Mathematical Institute, room 540






On the values of permanent function
A. È. Guterman^{} 
Number of views: 
This page:  82 
Photo Gallery

Abstract:
Two matrix functions determinant and permanent are important in algebra, combinatorics, and their applications and look quite similar:
$$ \det A= \sum_{\sigma\in { S}_n} (1)^{\sigma} a_{1\sigma(1)}\cdots a_{n\sigma(n)} \quad {\mathrm and } \quad
{\mathrm per} A= \sum_{\sigma\in { S}_n} a_{1\sigma(1)}\cdots a_{n\sigma(n)}, $$
here $A=(a_{ij})\in M_n({\mathbb F})$ is $n\times n$ matrix over a certain field ${\mathbb F}$ and $S_n$ denotes the symmetric group on $\{1,\ldots, n\}$.
However the properties of permanent function are much more involved.
For example, by Gauss elimination algorithm determinant can be computed in polynomial time, but the existence of polynomial algorithm to compute permanent is an open problem. Due to this reason series of open problems concerning the values of permanent and relations between permanent and determinant are actual.
In the talk we discuss the results of a series of joint works with M.V. Budrevich, G. Dolinar, B. Kuzma, I.A. Spiridonov, K.A. Taranin, devoted to our recent progress in the following directions:
Polya problem of permanentdeterminant conversion; BrualdiNewman problem of nonrealizable values of permanent of (0,1) matrices; the positive solution of WangKraüter problem on exact upper bound for permanent of (1,1) matrices.

