A walk on max-plus algebra

Sennosuke Watanabe, Akiko Fukuda, Etsuo Segawa, Iwao Sato

Research output: Contribution to journalArticlepeer-review


Max-plus algebra is a kind of idempotent semiring over Rmax:=R∪{−∞} with two operations ⊕:=max and ⊗:=+. In this paper, we introduce a new model of a walk on one dimensional lattice on Z, as an analogue of the quantum walk, over the max-plus algebra and we call it max-plus walk. In the conventional quantum walk, the summation of the ℓ2-norm of the states over all the positions is a conserved quantity. In contrast, the summation of eigenvalues of state decision matrices is a conserved quantity in the max-plus walk. Moreover, spectral analysis on the total time evolution operator is also given.

Original languageEnglish
Pages (from-to)29-48
Number of pages20
JournalLinear Algebra and Its Applications
Publication statusPublished - 2020 Aug 1


  • Directed graph
  • Max-plus algebra
  • Quantum walk

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'A walk on max-plus algebra'. Together they form a unique fingerprint.

Cite this