Solving linear systems over tropical semirings through normalization method and its applications

DOI10.1142/S0219498821501590MaRDI QIDQ5157909zbMATHOpenAlexFDO

Authors Fateme Olia, Sedighe Jamshidvand, Shaban Ghalandarzadeh, Amirhossein Amiraslani

Publication date 20 October 2021

Published in Journal of Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.00489

zbMATH Keywords

column rankrow ranktropical semiringsystem of linear equations

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Linear equations (linear algebraic aspects) (15A06) Vector spaces, linear dependence, rank, lineability (15A03) Semirings (16Y60)

Abstract: In this paper, we introduce and analyze a normalization method for solving a system of linear equations over tropical semirings. We use a normalization method to construct an associated normalized matrix, which gives a technique for solving the system. If solutions exist, the method can also determine the degrees of freedom of the system. Moreover, we present a procedure to determine the column rank and the row rank of a matrix. Flowcharts for this normalization method and its applications are included as well.

Recommendations

• On the maximal solution of a linear system over tropical semirings
• New algorithms for solving tropical linear systems
• Complexity of solving tropical linear systems
• Basics of linear algebra over the extended tropical semiring
• Tropical abstractions of MAX-plus linear systems
• An algorithm for solving an overdetermined tropical linear system using the analysis of stable solutions of subsystems
• Solving linear systems over idempotent semifields through \(LU\)-factorization
• The solvable conditions of linear system over commutative semirings
• Linear systems on tropical curves
• scientific article; zbMATH DE number 6806789

Cites work

• scientific article; zbMATH DE number 1358710 (Why is no real title available?)
• Equational theories of tropical semirings
• Graphs, dioids and semirings. New models and algorithms.
• Inner products on semimodules over a commutative semiring.
• Max-plus methods for nonlinear control and estimation.
• Note on a simple type of algebra in which the cancellation law of addition does not hold

Cited in

(8)

• Upper and lower bounds for Grigoriev's algorithm for solving integral tropical linear systems
• An algorithm to describe the solution set of any tropical linear system \(A \odot x = B \odot x\)
• Analysis of linear systems over idempotent semifields
• On matrix semiring over the extended tropical semiring
• A novel methodology for determining row and column ranks of tropical matrices
• On the maximal solution of a linear system over tropical semirings
• An algorithm for solving an overdetermined tropical linear system using the analysis of stable solutions of subsystems
• Weak dual residuations applied to tropical linear equations

This page was built for publication: Solving linear systems over tropical semirings through normalization method and its applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5157909)