Videolibrary
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 Video Library Archive Most viewed videos Search RSS New in collection

May 25, 2017 09:20–09:30

Ïðîáëåìà Ïîëèà äëÿ ïåðìàíåíòà

A. È. Guterman
 Video records: MP4 300.3 Mb MP4 76.4 Mb

Abstract: Two important functions in matrix theory, determinant and permanent, look very similar: $\det A = \sum_{\sigma \in S_{n}} (-1)^\sigma a_{1_{\sigma(1)}} \ldots a_{n_{\sigma(n)}}$ and $\mathrm{per} A = \sum_{\sigma \in S_{n}} a_{1_{\sigma(1)}} \ldots a_{n_{\sigma(n)}}$, here $A = (a_{ij}) \in M_{n} (\mathbb F)$ is an $n \times n$ matrix over a field $\mathbb F$ and $S_{n}$ denotes the set of all permutations of the set {1, . . . , n}. 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 Polya, 1913, different approaches to convert the permanent into the determinant were under the intensive investigation. We plan to give a short exposition of this theory during the past century including our recent research results. In particular, we prove that there are no bijective converters between permanent and determinant over finite fields. We also plan to provide sharp upper bounds for permanents of (1,-1)-matrices depending on their rank, which proves the Krauter conjecture (1985) answering the question by Wang (1974).