%0 Journal Article
%T Spectrum of Permanent¡¯s Values and Its Extremal Magnitudes in and
%A Vladimir Shevelev
%J Journal of Optimization
%D 2013
%R 10.1155/2013/289829
%X Let denote the class of square matrices containing in each row and in each column exactly 1¡¯s. The minimal value of , for which the behavior of the permanent in is not quite studied, is . We give a simple algorithm for calculation of upper magnitudes of permanent in and consider some extremal problems in a generalized class , the matrices of which contain in each row and in each column nonzero elements , , and and zeros. 1. Introduction The definition of permanent of a square matrix of order is , where sum is over all permutations of numbers . This definition is very combinatorial. For example, if is -matrix, then is the number of arrangements of nonattacking each other rooks on positions of 1¡¯s of . Therefore, the most natural applications of the permanent are in combinatorics: enumerating the Latin rectangles and squares, permutations with restricted positions, and different problems in the theory of graphs. Many interesting examples of applications of the permanent one can find in [1], chapter 8 (and not only in Mathematics!). To applications of the permanent there promoted celebrate proofs of the best known van der Waerden¡¯s and Minc¡¯s conjectures by Egorychev [2], Falikman [3], and Br¨¨gman [4], respectively. For example, Alon and Friedland [5] excellently used the Minc-Bregman inequality for permanent of -matrices for finding the maximum number of perfect matchings in graphs with a given degree sequence. Let denote the class of square matrices containing in each row and in each column exactly 1¡¯s. If , then matrix is doubly stochastic, since all its row and column sums equal 1. Therefore, -matrices are also called doubly stochastic (0,1)-matrices. These matrices have especially simple and attractive structure and have many applications. It is important that especially class in permanent¡¯s history was a nontrivial test area for different researches of the permanent. For example, one can mention a remarkable Merriell research [6] of the maximum of permanent on class . An author¡¯s research [7] of the permanent on -matrices (see Section 9) has led to the disproof of an important Balasubramanian conjecture [8] which would yield a full proof of 1967 Ryser hypothesis [9] on transversals of Latin squares. In the present paper we consider many other problems for . We study also the following natural generalization of . For given real or complex nonzero numbers , , and , denote by the class of square matrices containing every number from exactly one time in each row and in each column, such that the other elements are 0¡¯s. It is clear that, if and , then the
%U http://www.hindawi.com/journals/jopti/2013/289829/