Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Calendar
Search
Add a seminar

RSS
Forthcoming seminars




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


On the values of permanent function

A. È. Guterman

Number of views:
This page:184

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.
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024