Orbits and critical components of matrices in max-min algebra
type: Item
instance of: scholarly article
title: Orbits and critical components of matrices in max-min algebra
zbMATH Open document ID: 1128.15008
author: Blanka Semančíková
published in: Linear Algebra and its Applications
publication date: 2007-09-14T00:00:00Z
review text: The paper deals with a speed-up of a known \(O(n^3)\) algorithm computing the period of a periodic orbit in max-min algebra. An orbit in the max-min algebra is a sequence of the state vectors \(x(r)\), \(r\in \mathbb{N}\) of a max-min system \(x(r+1)=A\otimes x(r)\), where the matrix multiplication is defined with respect to the operations \(\oplus=\max\) and \(\otimes=\min\). In 2006, the author gave an \(O(n^3)\) algorithm computing the period of a periodic orbit [ibid. 414, No.~1, 38--63 (2006; Zbl 1125.15020)]. In this paper, the computational complexity of this algorithm is decreased by using only those coordinate-orbits, which correspond to the minimal non-trivial threshold components, called the critical components, of the transition matrix. All parts of the new algorithm except the computing of the critical components have complexity \(O(n^2)\). The formula for the orbit period presented in this paper is optimal in the following sense: the number of coordinate-orbits in the formula cannot be reduced. The formula is also helpful in solving the converse problem: generating an orbit with a prescribed period. This is demonstrated by examples. Furthermore, the paper shows that the non-critical coordinates of the state vector after \(n-1\) steps can be ignored, how to generate a known periodic regime by using a small number of coordinates of the state vector and that the difference between the defect of an orbit and the quasidefect of its critical coordinates is small. The final part deals with the situation when the matrix is reduced after the orbit has reached its periodic regime.
reviewed by: Rodica Covaci
Mathematics Subject Classification ID: 15A30
Mathematics Subject Classification ID: 15B33
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 37C27
zbMATH DE Number: 5190950
zbMATH Keywords: max-min algebra
zbMATH Keywords: powers of matrices
zbMATH Keywords: orbit of matrix
zbMATH Keywords: algorithm
zbMATH Keywords: periodic orbit
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
full work available at URL: j.laa.2007.05.017
OpenAlex ID: W1983555120
cites work: Computing a graph's period quadratically by node condensation
cites work: Combinatorial matrix theory
cites work: Eigenvectors in Bottleneck algebra
cites work: On the powers of matrices in bottleneck/fuzzy algebra
cites work: Powers of matrices over distributive lattices -- a review
cites work: Residuation in fuzzy algebra and some applications
cites work: Q4886968
cites work: Computing matrix period in max--min algebra
cites work: Q4509104
cites work: Computing orbit period in max-min algebra
cites work: Q3958592
cites work: Orbits in max--min algebra
DOI: 10.1016/J.LAA.2007.05.017
description: scientific article; zbMATH DE number 5190950