Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUpper bounds on the permanent of multidimensional (0,1)-matrices
137
0
0.0
(
0
)
Added by
Anna Taranenko Aleksandrovna
Publication date
2014
fields
and research's language is
English
Authors
A. A. Taranenko
Ask ChatGPT about the research
No Arabic abstract
The permanent of a multidimensional matrix is the sum of products of entries over all diagonals. By Mincs conjecture, there exists a reachable upper bound on the permanent of 2-dimensional (0,1)-matrices. In this paper we obtain some generalizations of Mincs conjecture to the multidimensional case. For this purpose we prove and compare several bounds on the permanent of multidimensional (0,1)-matrices. Most estimates can be used for matrices with nonnegative bounded entries.
rate research
Read More
The trace norm of a matrix is the sum of its singular values. This paper presents results on the minimum trace norm $psi_{n}left( mright) $ of $left( 0,1right) $-matrices of size $ntimes n$ with exactly $m$ ones. It is shown that: (1) if $ngeq2$ and $n<mleq2n,$ then $psi_{n}left( mright) leq sqrt{m+sqrt{2left( m-1right) }}$ , with equality if and only if $m$ is a prime; (2) if $ngeq4$ and $2n<mleq3n,$ then $psi_{n}left( mright) leq sqrt{m+2sqrt{2leftlfloor m/3rightrfloor }}$ , with equality if and only if $m$ is a prime or a double of a prime; (3) if $3n<mleq4n,$ then $psi_{n}left( mright) leqsqrt{m+2sqrt{m-2}}% $ , with equality if and only if there is an integer $kgeq1$ such that $m=12kpm2$ and $4kpm1,6kpm1,12kpm1$ are primes.
A $d$-dimensional matrix is called emph{$1$-polystochastic} if it is non-negative and the sum over each line equals~$1$. Such a matrix that has a single $1$ in each line and zeros elsewhere is called a emph{$1$-permutation} matrix. A emph{diagonal} of a $d$-dimensional matrix of order $n$ is a choice of $n$ elements, no two in the same hyperplane. The emph{permanent} of a $d$-dimensional matrix is the sum over the diagonals of the product of the elements within the diagonal. For a given order $n$ and dimension $d$, the set of $1$-polystochastic matrices forms a convex polytope that includes the $1$-permutation matrices within its set of vertices. For even $n$ and odd $d$, we give a construction for a class of $1$-permutation matrices with zero permanent. Consequently, we show that the set of $1$-polystochastic matrices with zero permanent contains at least $n^{n^{3/2}(1/2-o(1))}$ $1$-permutation matrices and contains a polytope of dimension at least $cn^{3/2}$ for fixed $c,d$ and even $ntoinfty$. We also provide counterexamples to a conjecture by Taranenko about the location of local extrema of the permanent. For odd $d$, we give a construction of $1$-permutation matrices that decompose into a convex linear sum of positive diagonals. These combine with a theorem of Taranenko to provide counterexamples to a conjecture by Dow and Gibson generalising van der Waerdens conjecture to higher dimensions.
We give upper bounds on the order of the automorphism group of a simple graph
We design a deterministic polynomial time $c^n$ approximation algorithm for the permanent of positive semidefinite matrices where $c=e^{gamma+1}simeq 4.84$. We write a natural convex relaxation and show that its optimum solution gives a $c^n$ approximation of the permanent. We further show that this factor is asymptotically tight by constructing a family of positive semidefinite matrices.
Let ${mathcal D}(n)$ be the maximal determinant for $n times n$ ${pm 1}$-matrices, and $mathcal R(n) = {mathcal D}(n)/n^{n/2}$ be the ratio of ${mathcal D}(n)$ to the Hadamard upper bound. Using the probabilistic method, we prove new lower bounds on ${mathcal D}(n)$ and $mathcal R(n)$ in terms of $d = n-h$, where $h$ is the order of a Hadamard matrix and $h$ is maximal subject to $h le n$. For example, $mathcal R(n) > (pi e/2)^{-d/2}$ if $1 le d le 3$, and $mathcal R(n) > (pi e/2)^{-d/2}(1 - d^2(pi/(2h))^{1/2})$ if $d > 3$. By a recent result of Livinskyi, $d^2/h^{1/2} to 0$ as $n to infty$, so the second bound is close to $(pi e/2)^{-d/2}$ for large $n$. Previous lower bounds tended to zero as $n to infty$ with $d$ fixed, except in the cases $d in {0,1}$. For $d ge 2$, our bounds are better for all sufficiently large $n$. If the Hadamard conjecture is true, then $d le 3$, so the first bound above shows that $mathcal R(n)$ is bounded below by a positive constant $(pi e/2)^{-3/2} > 0.1133$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
