Premium
Multidimensional Permanents and an Upper Bound on the Number of Transversals in Latin Squares
Author(s) -
Taranenko A. A.
Publication year - 2015
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21413
Subject(s) - mathematics , combinatorics , transversal (combinatorics) , latin square , matrix (chemical analysis) , order (exchange) , upper and lower bounds , diagonal , square (algebra) , corollary , main diagonal , symbol (formal) , discrete mathematics , geometry , mathematical analysis , rumen , chemistry , materials science , food science , finance , fermentation , computer science , economics , composite material , programming language
The permanent of a multidimensional matrix is the sum of products of entries over all diagonals. A nonnegative matrix whose every 1‐dimensional plane sums to 1 is called polystochastic. A latin square of order n is an n × n array of n symbols in which each symbol occurs exactly once in each row and each column. A transversal of such a square is a set of n entries such that no two entries share the same row, column, or symbol. Let T(n) be the maximum number of transversals over all latin squares of order n. Here, we prove that over the set of multidimensional polystochastic matrices of order n the permanent has a local extremum at the uniform matrix for whose every entry is equal to 1 / n . Also, we obtain an asymptotic value of the maximal permanent for a certain set of nonnegative multidimensional matrices. In particular, we get that the maximal permanent of polystochastic matrices is asymptotically equal to the permanent of the uniform matrix, whence as a corollary we have an upper bound on the number of transversals in latin squares T ( n ) ≤ n n e − 2 n + o ( n ) .