On the dependence of the maximum cycle mean of a matrix on permutations of the rows and columns
type: Item
instance of: scholarly article
title: On the dependence of the maximum cycle mean of a matrix on permutations of the rows and columns
zbMATH Open document ID: 0679.15017
DOI: 10.1016/0166-218X(89)90034-6
published in: Discrete Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 15B33
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 90C08
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 4112784
zbMATH Keywords: stationary matrices
zbMATH Keywords: triangularity
zbMATH Keywords: maximum cycle mean
zbMATH Keywords: permutation
author: Peter Butkovič
author: Ján Plavka
MaRDI profile type: Publication
cites work: Q3964346
cites work: Q5583694
cites work: A characterization of the minimum cycle mean in a digraph
full work available at URL: 0166-218x(89)90034-6
OpenAlex ID: W2025505454
Recommended article: The complexity of finding the minimal of the maximum cycle means of similar zero-one matrices
Recommended article: Maximum of the Characteristic Polynomial for a Random Permutation Matrix
Recommended article: On the distribution of the mth maximal cycle lengths of random A-permutations
Recommended article: Static maxium cycle mean problem of a trivalent matrix
Recommended article: Asymptotic freeness of random permutation matrices with restricted cycle lengths
Recommended article: On matrices whose spectrum is affected in a predictable way by column permutations
Recommended article: An \(O(n^ 2)\) algorithm for the maximum cycle mean of an \(n\times n\) bivalent matrix
Recommended article: On the number ofk-cycles in the assignment problem for random matrices
Recommended article: Bounding the row sum arithmetic mean by Perron roots of row-permuted matrices
Recommended article: The distribution of permutation matrix entries under randomized basis
description: scientific article; zbMATH DE number 4112784