Extremal eigenproblem for bivalent matrices
type: Item
instance of: scholarly article
title: Extremal eigenproblem for bivalent matrices
zbMATH Open document ID: 0855.65032
DOI: 10.1016/0024-3795(93)00285-8
published in: Linear Algebra and its Applications
publication date: 1995-09-06T00:00:00Z
review text: Introducing a maximum operation on a linearly ordered multiplicative group \(G\), the matrix-vector algebra over \(G\) may be defined by direct analogy to conventional linear algebra. An analog to the eigenproblem may be considered that is also called extremal eigenproblem with a reference to the operation that replaces summation in the standard linear algebra. For the additive group of real numbers in place of \(G\), an algorithm exists that can find the solution of the extremal eigenproblem in \(O(n^3)\) operations. The authors first develop an algorithm that can find the solution of the extremal eigenproblem for any bivalent matrix with entries equal to zero or one in \(O(m + n)\) operations, and then they extend this result to bivalent matrices over any linearly ordered, commutative radicable group.
Mathematics Subject Classification ID: 65F15
Mathematics Subject Classification ID: 15B33
Mathematics Subject Classification ID: 65J10
Mathematics Subject Classification ID: 65F30
zbMATH DE Number: 778236
zbMATH Keywords: linearly ordered multiplicative group
zbMATH Keywords: extremal eigenproblem
zbMATH Keywords: algorithm
zbMATH Keywords: bivalent matrix
author: R. A. Cuninghame-Green
author: Peter Butkovič
reviewed by: Z. Dostál
MaRDI profile type: Publication
full work available at URL: 0024-3795(93)00285-8
OpenAlex ID: W2139083327
cites work: An \(O(n^ 2)\) algorithm for the maximum cycle mean of an \(n\times n\) bivalent matrix
cites work: Q3964346
cites work: Q5583694
cites work: Optimal cycles in doubly weighted graphs and approximation of bivariate functions by univariate ones
cites work: A characterization of the minimum cycle mean in a digraph
cites work: Q4130999
cites work: Depth-First Search and Linear Graph Algorithms
cites work: Linear and combinatorial optimization in ordered algebraic structures
description: scientific article; zbMATH DE number 778236