On the dependence of the maximum cycle mean of a matrix on permutations of the rows and columns (Q1124653)

This paper explores the dependence of the maximum cycle mean (MCM) of a matrix with respect to the permutation of its rows and columns. For a given square matrix \(A=(a_{ij})\) of order n with entries from a radicable linearly ordered commutative group G and a cyclic permutation \(\sigma =(i_ 1,...,i_ 1)\) of a subset of \(N=\{1,2,...,n\}\) the author defines \(\mu\) (\(\sigma)\), the mean weight of \(\sigma\), as \((a_{i_ 1i_ 2}\cdot a_{i_ 2i_ 3}\cdot...\cdot a_{i_{l-1}i_ l}\cdot a_{i_ li_ 1})\) and \(\lambda\) (A), the MCM of A, as \(\max_{\sigma}\mu (\sigma)\), where \(\sigma\) ranges over all cyclic permutation of subsets of N. On this basis of the results of this work, an \(O(n^ 2)\) algorithm for checking whether \(\lambda (A)=\lambda (A')\) holds for any matrix \(A'\) which can be obtained from A by permuting its rows and columns.