|
|
Iskovskikh Seminar
September 10, 2020 18:00–19:30, Moscow, Steklov Mathematical Institute, room 530
|
|
|
|
|
|
On the values of permanent function
A. È. Guterman |
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 permanent-determinant conversion; Brualdi-Newman problem of non-realizable values of permanent of (0,1) matrices; the positive solution of Wang-Kraüter problem on exact upper bound for permanent of (-1,1) matrices.
|
|