

Beijing–Moscow Mathematics Colloquium
April 23, 2021 11:00–12:00, Moscow, online






Values of permanent and
positive solution of WangKrauter problem
A. È. Guterman^{} ^{} Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Number of views: 
This page:  50 

Abstract:
The talk is based on the joint work with M.V. Budrevich.
The class of $(1,1)$matrices is very important in algebra and
combinatorics and in various their applications. For example, wellknown
Hadamard matrices are of this type.
An important matrix function is the permanent:
$$
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 an $n\times n$ matrix over a
field ${\mathbb F}$ and $S_n$ denotes the set of all permutations of the
set $\{1,\ldots, 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.
In this talk we discuss the permanents of $\pm 1$matrices.
In 1974 Wang posed a problem to find a decent upper bound for ${
per}(A)$ if $A$ is a square $\pm 1$matrix of rank $k$. In 1985 Krauter
conjectured some concrete upper bound.
We prove the Krauter's conjecture and thus obtain the complete answer to
the Wang's question. In particular, we characterized matrices with the
maximal possible permanent for each value of $k$.
Language: English

