New permanent approximation inequalities via identities (Q779828)

Computing the permanent of an \(n\times n\) matrix is in general difficult for \(n\) being a large natural number. There are some known explicit formulae, the most efficient of which is Ryser's formula. Unfortunately this formula requires at least \(\mathcal{O}(n2^n)\) arithmetic operations. Many lower and upper bounds were obtained, but in the literature a few explicit inequalities for approximant matrices are known. The goal of this paper is to present new upper bounds for the distance between a properly normalized permanent of a rectangular matrix and the product of the arithmetic means of its column entries. By properly normalized permanents is meant dividing them by the number of summands, a good approximation for the permanent of a matrix when the matrix rows are approximately equal. The results obtained here are permanent approximation inequalities and improve earlier research in the area. The proofs use some new identities for the above mentioned difference and are also valid for matrices over a rational commutative unital algebra.