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

DOI10.1142/S0219498821501590zbMATH Open1490.16103arXiv1905.00489OpenAlexW3042325789MaRDI QIDQ5157909FDOQ5157909

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Max-plus methods for nonlinear control and estimation.
• Graphs, dioids and semirings. New models and algorithms.
• Note on a simple type of algebra in which the cancellation law of addition does not hold
• Inner products on semimodules over a commutative semiring.
• Complete solution of an optimization problem in tropical semifield
• Equational theories of tropical semirings

Cited In (8)

• An algorithm to describe the solution set of any tropical linear system \(A \odot x = B \odot x\)
• 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
• Upper and lower bounds for Grigoriev's algorithm for solving integral tropical linear systems
• A novel methodology for determining row and column ranks of tropical matrices
• On matrix semiring over the extended tropical semiring
• On the maximal solution of a linear system over tropical semirings
• Analysis of linear systems over idempotent semifields

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)