An Efficient Algorithm for Latin Squares in a Bipartite Min-Max-Plus System

Anurag Agarwal; Fazal Abbas; Mubasher Umer; Petko Kitanov; Umar Hayat

REVIEW 3 major objections 4 minor 13 references

An Efficient Algorithm for Latin Squares in a Bipartite Min-Max-Plus System

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For Latin squares in a bipartite min-max-plus system, once the normalized iteration repeats a state, the componentwise maximum over that cycle is an eigenvector, so no restart loop is needed.

desk verdict The paper's efficiency trick rests on a min-max interchange that is false in general, so the central theorem does not hold as stated; the worked example works, but the proof gap is real and the efficiency comparison is data-free. read the letter →

arxiv 1908.08371 v1 pith:JGUPPF6H submitted 2019-08-22 math.RA math.CO

Mubasher Umer , Umar Hayat , Fazal Abbas , Anurag Agarwal , Petko Kitanov This is my paper · ORCID

classification math.RAmath.CO MSC 15A1805B2008A99

keywords bipartitemin-max-plussystemsLatinsquareseigenvalueeigenvectormax-plusalgebramin-pluspoweralgorithmperiodicorbit

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's target is the eigenproblem for Latin-square matrices inside a bipartite min-max-plus system, where the state update alternates a max-plus step and a min-plus step. It claims that once the normalized iteration $x^*(l+1)=N(x^*(l))$ revisits a state, the componentwise maximum $v=x^*(s)\oplus\dots\oplus x^*(r-1)$ over the detected cycle is already an eigenvector, so $M(v)=\lambda\otimes v$ holds. If this is right, the computation shortens: the restart-and-iterate fallback used by earlier power algorithms is unnecessary, and the eigenvector comes from one cycle of the normalized map. The paper illustrates the construction on Latin squares of order 4 and argues by example that it is simpler than the existing power algorithm.

What carries the argument

The carrying device is the normalized map $N$, defined by $N((u,w)^\top)=(A_\lambda\otimes w,\,B_\lambda\otimes' u)^\top$ with $A_\lambda=-\lambda\otimes A$ and $B_\lambda=-\lambda\otimes B$. It turns the eigenproblem $M(v)=\lambda\otimes v$ into the search for a fixed point $N(v)=v$, and its iterates produce the sequence $x^*(0),x^*(1),\dots$ in which a repeated state marks a cycle. The componentwise maximum $\oplus$ over that cycle is the candidate eigenvector; the argument that $N$ distributes over this maximum is what makes the candidate exact. For Latin squares, the explicit eigenvalue formula supplies $\lambda$ before any iteration begins.

What would settle it

Choose a Latin-square pair $A,B$ of order $n$ in one of the four entry-type cases, run Algorithm 2, and after detecting $x^*(r)=x^*(s)$ compute both $M(v)$ and $\lambda\otimes v$; if the two vectors differ, Theorem 2 fails for that case.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2: if the normalized orbit satisfies $x^*(r)=x^*(s)$ for integers $r>s\ge 0$, then $M(v)=\lambda\otimes v$ for $v=x^*(s)\oplus\dots\oplus x^*(r-1)$, meaning the pointwise maximum over one full cycle is an eigenvector. For Latin squares, the eigenvalue is known in advance, $\lambda=(\max(A)+\min(B))/2$, so Algorithm 2 only has to form $A_\lambda=-\lambda\otimes A$ and $B_\lambda=-\lambda\otimes B$, iterate the normalized map until a state repeats, and take the componentwise maximum over the period. The paper claims that in the Latin-square cases it examines this yields the correct eigenvector directly, without the fallback of restarting from $v$ and iterating until a fixed point of $N$ is reached.

Load-bearing premise

The argument assumes an interchange of order: combining several states by taking coordinate-wise maxima and then applying the evolution rule must give the same result as evolving each state first and then combining, which is not automatic in systems that mix max and min operations.

Editorial extensions

If this is right

For any Latin-square system in the paper's class, the eigenvector can be computed from one detected cycle of the normalized map, with no restart loop.
Because the eigenvalue is known from $\lambda=(\max(A)+\min(B))/2$, the algorithm fully separates eigenvalue computation from eigenvector computation.
The same cycle-max rule is claimed to produce both trivial and nontrivial eigenvectors, depending on the starting vector.
Stopping at an exact state repetition $x^*(r)=x^*(s)$ is simpler to detect than the power algorithm's scalar-shift condition $x(r)=c\otimes x(s)$.
The construction also suggests how an analogous algorithm might be derived for separated min-max-plus systems, as the paper's conclusion proposes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural next test is to run Algorithm 2 on random Latin-square pairs in all four entry-type cases; if the fallback step ever fires, the efficiency gain is not universal.
A cheap safeguard would be to check $N(v)=v$ before accepting the cycle-max vector, since the proof's interchange step is the only non-mechanical part of the argument.
The cycle-max rule can be read as a tropical analogue of averaging over a periodic orbit; in non-Latin systems one may need several cycles before such an aggregate stabilizes into an eigenvector.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Bottom line: the central proof doesn't go through. Theorem 2 claims that if the shifted orbit x* is periodic from s to r, then the componentwise max v of one period is already an eigenvector. The proof needs N(v)=N(x*(s))⊕...⊕N(x*(r−1)). That holds for the A-block because max-plus matrix multiplication distributes over max, but for the B-block it requires min_i max_l(b_ji+u_i(l)) = max_l min_i(b_ji+u_i(l)). In general only one inequality holds. The 2×2 array [[0,10],[9,1]] separates them. The paper gives no Latin-square-specific reason equality holds on the orbit it generates, so Theorem 2 is unproved and Algorithm 2's step-5 early stop is unsupported. The proof of Algorithm 1 also slips: Lemma 2 is about the restarted orbit, not the original cycle, so the contradiction 'x(r)=x(s) implies no coordinate can increase' does not follow.

What is good: the problem is real and the setup is clear. For Latin squares, using the known eigenvalue formula from [11] and then shifting by λ is sensible. The worked example is fully worked and numerically correct; they verify M(v)=λ⊗v. The algorithm is understandable. It is an honest, modest extension of Subiono's power algorithm.

Soft spots: the load-bearing issue above is not minor; it is the difference between a one-pass algorithm and a restart. Also, Remark 4 mentions numerical experiments comparing algorithms 2 and 3, but no experiment is reported. The efficiency claim rests on one illustrative example. That is a separate weakness but easy to fix.

Who it's for: specialists in max-plus/min-max-plus and discrete-event systems who care about Latin-square eigenproblems. It is not a field-changer.

Recommendation: I'd send it to a referee who knows min-max-plus well, because the flaw is precise and possibly repairable—if the authors prove the missing inequality on this class, or show the algorithm still works after the restart, the note has value. But as it stands, I would not accept it; rejection with an encouraging report is the right outcome.

Referee Report

3 major / 4 minor

Summary. The paper studies eigenproblems for bipartite min-max-plus systems of the form u(l+1)=A⊗w(l), w(l+1)=B⊗'u(l), specializing to the case where A and B are Latin squares. It imports the eigenvalue formula λ=(max(A)+min(B))/2 from earlier work and proposes Algorithm 2, which iterates the shifted map N until a cycle x*(r)=x*(s) is found, forms v as the componentwise maximum over one cycle, and asserts that M(v)=λ⊗v. If this check fails, the algorithm restarts from v and iterates until a fixed point. The paper compares the algorithm with the power algorithm (Algorithm 3) on a single 4×4 example and claims greater efficiency.

Significance. If the central claim were correct, the paper would provide a simple cycle-based eigenvector computation for Latin-square bipartite min-max-plus systems, and the comparison with the power algorithm would be of interest to the discrete-event-systems community. The paper is clearly organized and the worked example is explicitly verified. However, the main theorem is not established: the proof relies on an invalid min-max interchange, and the efficiency claim rests on numerical experiments that are not reported. The manuscript gives no machine-checked proofs, reproducible code, or experimental data, so the significance is currently unsupported.

major comments (3)

[Section 2, proof of Theorem 2] The proof passes the shifted map N through the componentwise maximum ⊕ without justification. For the w-block this requires Bλ⊗'(⊕_l u*(l)) = ⊕_l (Bλ⊗'u*(l)), that is, for each j, min_i max_l (b_{ji}+u_i(l)) = max_l min_i (b_{ji}+u_i(l)). Only the inequality max_l min_i ≤ min_i max_l holds in general; for the 2×2 array [[0,10],[9,1]], the left-hand side is 9 and the right-hand side is 1. Since no Latin-square-specific argument is given to restore equality on the orbits produced by Algorithm 2, Theorem 2 is not established for general bipartite min-max-plus systems. This is load-bearing: Algorithm 2 uses Theorem 2 to stop at step 5 without the restart loop, and the claimed efficiency advantage over Algorithm 3 depends on that step.
[Section 2, 'Proof of Algorithm 1' and Lemma 2] Lemma 2 and Theorem 3 only prove N(v)≥v, not N(v)=v. The proof of Algorithm 1 then assumes that the restarted orbit is eventually periodic and concludes that a nondecreasing eventually periodic orbit must be constant. No proof of eventual periodicity of the restarted orbit is supplied; the periodicity of the original orbit x*(l) is not transferred to the orbit starting from v. Since min-max-plus maps can have bounded orbits that are not exactly eventually periodic, the termination of step 7 of Algorithm 2 is not justified.
[Section 3, Remark 4] Remark 4 states that numerical experiments were made to compare Algorithms 2 and 3, but no experimental data, tables, or reproducibility details are included. The only evidence is the single 4×4 example in Example 3. The conclusion that the proposed method is 'more efficient' is therefore unsupported; at minimum a table of iteration counts or a complexity analysis for several Latin-square sizes is needed.

minor comments (4)

[Abstract] The abstract contains small writing errors: 'propose method' should be 'proposed method', and 'Islam abad' should be 'Islamabad'.
[Section 3, Example 3] The initial state vector is chosen without explanation; it would be useful to state whether the resulting eigenvector is independent of the starting vector, or to explain the choice.
[Section 2, Theorem 3] The componentwise order '≥' used for vectors in R^{m+n} is not explicitly defined; the manuscript should state that inequalities are understood componentwise.
[Section 3, general notation] The symbol n is used both for the order of the Latin square and for the set {1,...,n}; the surrounding text would be clearer if the set were denoted by a different symbol such as [n] or n̲.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found; the eigenvector candidate is explicitly checked and the eigenvalue formula is imported from prior external work.

full rationale

The paper's derivation chain is not circular. Algorithm 2 computes the eigenvalue for Latin-square bipartite systems from the externally cited formula λ = (max(A) + min(B))/2 from reference [11], by authors other than the present ones, and then constructs a candidate eigenvector by taking the componentwise maximum over one period of the normalized orbit. The candidate is verified directly by evaluating M(v) and checking M(v) = λ⊗v (steps 5–6 of Algorithm 2). Thus the claimed eigenvector is not fitted to the desired output; the check is an independent verification. The only self-citation, reference [13] by Umer, Hayat, and Abbas, appears in the introduction as related work and is not load-bearing for the algorithm or theorem. The main mathematical concern is Theorem 2's proof, which implicitly assumes that the min-plus operator Bλ⊗' distributes over the max ⊕ when applied to the w-block; this is an unproved min-max interchange and a correctness risk, not a circularity. It does not reduce the conclusion to its inputs by definition or by a fitted parameter. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No fitted parameters appear. The load-bearing assumptions are the cited eigenvalue formula, unproved eventual periodicity, a false distribution identity for N over ⊕ on the min side, and the Latin-square restrictions on A and B.

assumptions (4)

domain assumption The eigenvalue of a Latin-square bipartite min-max-plus system is λ=(max(A)+min(B))/2.
Algorithm 2 step 1 uses this formula directly; the paper cites [11] but gives no proof.
domain assumption Iterating the shifted map N eventually produces a periodic orbit from any initial vector.
The proof of Algorithm 1 begins 'Since the system ends up in a periodic behavior after a number of iterations'; this is asserted, not proved.
ad hoc to paper The map N commutes with componentwise maximum on the min-plus component, i.e. Bλ⊗'(⊕_l u*(l)) equals ⊕_l(Bλ⊗'u*(l)).
This identity is used in the proof of Theorem 2 to write N(v) as the maximum of the shifted successors. It is not valid for general bipartite min-max-plus systems and no Latin-square-specific justification is supplied.
domain assumption The matrices A and B are Latin squares with entries drawn from {n, n_ε, n_τ} as defined in Section 3.
All algorithmic claims are restricted to this matrix class; no results are established outside it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of An Efficient Algorithm for Latin Squares in a Bipartite Min-Max-Plus System." pith.science (2026). https://pith.science/paper/JGUPPF6H

@misc{pith2026190808371,
  author       = {Pith},
  title        = {Pith review of: An Efficient Algorithm for Latin Squares in a Bipartite Min-Max-Plus System},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JGUPPF6H}},
  note         = {Machine review of arXiv:1908.08371}
}

read the original abstract

In this paper, we consider the eigenproblems for Latin squares in a bipartite min-max-plus system. The focus is upon developing a new algorithm to compute the eigenvalue and eigenvectors (trivial and non-trivial) for Latin squares in a bipartite min-max-plus system. We illustrate the algorithm using some examples. Furthermore, we compare the results of our algorithm with some of the existing algorithms which shows that the propose method is more efficient.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[11]

S.; Adzkiya, D

Subiono; Muﬁd, M. S.; Adzkiya, D. Eigenproblems of latin squares in bipartite (min, max, plus)-systems. Discret. Event Dyn. Syst. 2016, 26, 657–668

work page 2016
[1]

Best approximation in m axplus semi- modules

Akian, M.; Gaubert, S.; Nitica, V.; Singer, I. Best approximation in m axplus semi- modules. Linear Algebra Its Appl. 2011, 435, 3261–3296

work page 2011
[2]

The power algorithm in max algebra

Braker, J.G.; Olsder, G.J. The power algorithm in max algebra. Linear Algebra Its Appl. 1993, 182, 67–89

work page 1993
[3]

Lecture notes in economics and mathem atical systems

Cuninghame-Green, R.A. Lecture notes in economics and mathem atical systems. In Minimax Algebra; Springer-Verlag: New York, NY, USA, 1979. 13

work page 1979
[4]

On the ultimate behavior of the sequence of cons ecutive powers of a matrix in the max-plus algebra

De Shutter, B. On the ultimate behavior of the sequence of cons ecutive powers of a matrix in the max-plus algebra. Linear Algebra Its Appl. 2000, 307, 103–117

work page 2000
[5]

Eigenvectors of permutation m atrices

Garca-Planas, M.I.; Magret, M.D. Eigenvectors of permutation m atrices. Adv. Pure Math. 2015, 5, 390–394

work page 2015
[6]

Methods and applications of (max,+) linear algebra

Gaubert, S. Methods and applications of (max,+) linear algebra. I n An- nual Symposium on Theoretical Aspects of Computer Science ; Springer-Verlag: Berlin/Heidelberg, Germany, 1997, 261–282

work page 1997
[7]

Tropical nevanlinna theory and ultra- discrete equa- tions

Halburd, R.G.; Southall, N.J. Tropical nevanlinna theory and ultra- discrete equa- tions. Int. Math. Res. Not. 2009, 5, 887–911

work page 2009

Show all 13 references

[8]

On the number of Latin squares

McKay, B.D.; Wanless, I.M. On the number of Latin squares. Ann. Comb. 2005, 9, 334–344

2005
[9]

On Max-Plus Algebra and Its Applica tion on Image Steganography

Santoso, K.A.; Suprajitno, H. On Max-Plus Algebra and Its Applica tion on Image Steganography. Sci. World J. 2018, 6718653

2018
[10]

Subiono on Classes of Min-Max-Plus Systems and Their Application . Ph.D. Thesis, Delft University of Technology, Delft , The Netherlands, 2000

2000
[12]

Power algorithms for (max,+)- and b ipartite (min,max,+)-systems

Subiono; van der Woude, J. Power algorithms for (max,+)- and b ipartite (min,max,+)-systems. Discret. Event Dyn. Syst. 2000, 10, 369–389

2000
[13]

An Eﬃcient Algorithm for Nontrivia l Eigenvectors in Max-Plus Algebra

Umer, M.; Hayat, U.; Abbas, F. An Eﬃcient Algorithm for Nontrivia l Eigenvectors in Max-Plus Algebra. Symmetry, 2019, 11, 1–9. 14

2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [11]

S.; Adzkiya, D

Subiono; Muﬁd, M. S.; Adzkiya, D. Eigenproblems of latin squares in bipartite (min, max, plus)-systems. Discret. Event Dyn. Syst. 2016, 26, 657–668

work page 2016

[2] [1]

Best approximation in m axplus semi- modules

Akian, M.; Gaubert, S.; Nitica, V.; Singer, I. Best approximation in m axplus semi- modules. Linear Algebra Its Appl. 2011, 435, 3261–3296

work page 2011

[3] [2]

The power algorithm in max algebra

Braker, J.G.; Olsder, G.J. The power algorithm in max algebra. Linear Algebra Its Appl. 1993, 182, 67–89

work page 1993

[4] [3]

Lecture notes in economics and mathem atical systems

Cuninghame-Green, R.A. Lecture notes in economics and mathem atical systems. In Minimax Algebra; Springer-Verlag: New York, NY, USA, 1979. 13

work page 1979

[5] [4]

On the ultimate behavior of the sequence of cons ecutive powers of a matrix in the max-plus algebra

De Shutter, B. On the ultimate behavior of the sequence of cons ecutive powers of a matrix in the max-plus algebra. Linear Algebra Its Appl. 2000, 307, 103–117

work page 2000

[6] [5]

Eigenvectors of permutation m atrices

Garca-Planas, M.I.; Magret, M.D. Eigenvectors of permutation m atrices. Adv. Pure Math. 2015, 5, 390–394

work page 2015

[7] [6]

Methods and applications of (max,+) linear algebra

Gaubert, S. Methods and applications of (max,+) linear algebra. I n An- nual Symposium on Theoretical Aspects of Computer Science ; Springer-Verlag: Berlin/Heidelberg, Germany, 1997, 261–282

work page 1997

[8] [7]

Tropical nevanlinna theory and ultra- discrete equa- tions

Halburd, R.G.; Southall, N.J. Tropical nevanlinna theory and ultra- discrete equa- tions. Int. Math. Res. Not. 2009, 5, 887–911

work page 2009