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

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. The proposed algorithm is implemented in MATLAB, using max-plus algebra toolbox. Computationally speaking, our algorithm has a clear advantage over the power algorithm presented by Subiono and van der Woude. Because our algorithm takes 0.088783 s to solve the eigenvalue problem for Latin square presented in Example 2, while the compared one takes 1.718662 s for the same problem. Furthermore, a time complexity comparison is presented, which reveals that the proposed algorithm is less time consuming when compared with some of the existing algorithms.

1. Introduction

Time evolution of discrete event dynamic systems can be described through equations composed using three operations the maximum, the minimum and the addition. Such systems are described as min-max-plus systems. The bipartite min-max-plus systems are determined by the union of two sets of equations: one set of equations containing the maximization and the addition; and another set of equations containing the minimization and the addition.

The idea of max-plus algebra was first seen in the 1950s or even at an earlier period. Nowadays, it has been studied intensively. In [1], the authors have investigated the set of invertible linear operators over a subalgebra of max-plus algebra. For a matrix in max-plus algebra, some necessary and sufficient conditions have been established to possess various types of g-inverses including Moore–Penrose inverse [2]. In [3], the authors have characterized the linear operators which preserve the maximal column rank of matrices over max-plus algebra.

Max-plus algebra has many applications in mathematics as well as in different areas such as mathematical physics, optimization, combinatorics, and algebraic geometry [4]. Max-plus algebra is used in machine scheduling, telecommunication networks, control theory, manufacturing systems, parallel processing systems, and traffic control [5,6,7]. Max-plus algebra is also used in image steganography [8]. Max-plus algebra can be used to model disk events related to synchronization and time delays [9]. In [10] the authors have shown how max-plus algebra can be helpful for the dynamic programming of algorithms. In [11], the author has described the whole Dutch railway system by a max-plus system.

The eigenproblems for a matrix A of order $n\times n$ are the problems to find out an eigenvalue $\lambda$ and the eigenvector v, such that $Av=\lambda v$. In this article, we consider eigenproblems for the bipartite min-max-plus systems. Mostly, power algorithm [12], is used to compute the eigenvalue and eigenvectors in an iterative way. Umer et al. [13] developed an efficient algorithm to solve the eigenvalue problem in max-plus systems, which computes the eigenvalue as a maximal cycle mean and use an iterative approach to determine the eigenvectors. In [14], the authors have demonstrated that the presence of eigenvectors (non-trivial) depend on the position of the greatest and the least elements in the Latin squares in a bipartite min-max-plus system. For further study of eigenproblems for discrete event systems, see [10,14,15,16].

As per our knowledge and from the literature review, one of the open problems in the max-plus algebra is to come up with an efficient and fast algorithm to solve the eigenproblems for these systems. In this paper, a robust algorithm is developed, that can calculate the eigenvectors corresponding to an eigenvalue $\lambda$ in an iterative way. In particular, we apply this algorithm to find the eigenvectors (trivial and non-trivial) for Latin squares in bipartite min-max-plus systems. A computational comparison of the proposed algorithm and the power algorithm presented by Subiono and van der Woude [12] is given, which shows the efficiency of the proposed algorithm.

The structure of the paper is along these lines. First of all, some preliminary notions and bipartite min-max-plus systems are presented in Section 2, then a robust algorithm is developed for determining the eigenvalue and eigenvectors of such systems. In Section 3, we present these systems for the Latin squares and calculate trivial and non-trivial eigenvectors for such models. The proposed algorithm and the power algorithm presented by Subiono and van der Woude [12], are implemented in MATLAB (using max-plus algebra toolbox for MATLAB [17]). A time complexity comparison of these algorithms has been given at the end of Section 3. Finally, the conclusion are made in Section 4.

2. Bipartite Min-Max-Plus Systems

First of all we denote the set of real numbers and the set of whole numbers by $\mathbb{R}$ and $\mathbb{W}$ respectively, then we define ${\mathbb{R}}_{ϵ}=\mathbb{R}\cup \left\{ϵ\right\}$, ${\mathbb{R}}_{\tau }=\mathbb{R}\cup \left\{\tau \right\}$, where $ϵ=-\infty$, $\tau =+\infty$. A matrix or a vector where all components equal to $-\infty$ is represented by $\mathbf{ϵ}$, whereas a matrix or a vector where all components equal to $+\infty$ is represented by $\mathit{\tau }$. $\underline{n}$ denotes the set of first n positive integers, i.e., $\underline{n}=\{1,\dots ,n\}$. The following scalar operations are introduced as;

$$\begin{array}{cccc}\hfill r\oplus s& =& \max \{r,s\},\hfill & \mathrm{for}\mathrm{each}r,s\in {\mathbb{R}}_{ϵ}\hfill \\ \hfill r{\oplus }^{\prime }s& =& \min \{r,s\},\hfill & \mathrm{for}\mathrm{each}r,s\in {\mathbb{R}}_{\tau }\hfill \\ \hfill r\otimes s& =& r+s,\hfill & \mathrm{for}\mathrm{each}r,s\in \mathbb{R}.\hfill \end{array}$$

The algebraic structure ${\mathbb{R}}_{\min }=({\mathbb{R}}_{\tau },{\oplus }^{\prime },\otimes )$ represents min-plus algebra and ${\mathbb{R}}_{\max }=({\mathbb{R}}_{ϵ},\oplus ,\otimes )$ represents max-plus algebra. Since in both ${\mathbb{R}}_{\min }$ and ${\mathbb{R}}_{\max }$ the multiplication operator is defined by addition, therefore in both systems the notation for multiplication operator is the same.

The collection of all matrices of order $m\times n$ in min-plus and max-plus algebra is represented as ${\mathbb{R}}_{\min }^{m\times n}$ and ${\mathbb{R}}_{\max }^{m\times n}$ respectively. While ${\mathbb{R}}_{\min }^m$ and ${\mathbb{R}}_{\max }^m$ denotes the set of all vectors in min-plus and max-plus algebra respectively. The scalar operations to matrices are extended as follows.

Suppose that $A=\left[a_{ij}\right]$, $B=\left[b_{ij}\right]$, $U=\left[u_{ij}\right]$, $V=\left[v_{ij}\right]$ such that $A,B\in {\mathbb{R}}_{\max }^{m\times n}$; $U,V\in {\mathbb{R}}_{\min }^{m\times n}$ and $\alpha \in \mathbb{R}$ then

$$\begin{array}{ccc}\hfill A\oplus B& =& \left[c_{ij}\right],\mathrm{where}{c}_{ij}=\max \{a_{ij},b_{ij}\},\hfill \\ \hfill U{\oplus }^{\prime }V& =& \left[w_{ij}\right],\mathrm{where}{w}_{ij}=\min \{u_{ij},v_{ij}\},\hfill \\ \hfill \alpha \otimes A& =& \alpha \otimes \left[a_{ij}\right]=\alpha +\left[a_{ij}\right],\hfill \end{array}$$

$$\mathrm{for} i\in \underline{m}, j\in \underline{n}.$$

If $A\in {\mathbb{R}}_{\max }^{m\times r}$, $B\in {\mathbb{R}}_{\max }^{r\times n}$, $U\in {\mathbb{R}}_{\min }^{m\times r}$ and $V\in {\mathbb{R}}_{\min }^{r\times n}$, then

$$\begin{array}{ccc}\hfill A\otimes B& =& \left[c_{ij}\right],\mathrm{where}{c}_{ij}=\underset{k=1}{\overset{r}{⨁}}(a_{ik}\otimes b_{kj})=\max \{a_{ik}+b_{kj}\},\hfill \\ \hfill U{\otimes }^{\prime }V& =& \left[w_{ij}\right],\mathrm{where}{w}_{ij}=\underset{k=1}{\overset{r}{⨁}}\prime (u_{ik}\otimes v_{kj})=\min \{u_{ik}+v_{kj}\},\hfill \end{array}$$

$$\mathrm{for}k\in \underline{r},i\in \underline{m},j\in \underline{n}.$$

One can see that the notation of the multiplication operator in both systems is different. The addition is defined as maximum (minimum) in ${\mathbb{R}}_{\max }$ (respectively, ${\mathbb{R}}_{\min }$). A bipartite min-max-plus system can be represented as:

$$\begin{array}{ccc}\hfill u_i(l+1)& =& max\{a_{i1}+w_1\left(l\right),\dots ,a_{in}+w_n\left(l\right)\}\hfill \\ \hfill w_j(l+1)& =& min\{b_{j1}+u_1\left(l\right),\dots ,b_{jm}+u_m\left(l\right)\},\hfill \end{array}$$

where $u_i\left(l\right),a_{ij}\in {\mathbb{R}}_{ϵ}$; $w_j\left(l\right),b_{ji}\in {\mathbb{R}}_{\tau }$; $l\in \mathbb{W}$ for all $i\in \underline{m}$; $j\in \underline{n}$. These equations can be written as;

$$\begin{array}{ccc}\hfill u_i(l+1)& =& \underset{j=1}{\overset{n}{⨁}}(a_{ij}\otimes w_j\left(l\right)),\hfill \\ \hfill w_j(l+1)& =& \underset{i=1}{\overset{m}{⨁}}\prime (b_{ji}\otimes u_i\left(l\right)).\hfill \end{array}$$

The above equations can be denoted as;

$$\begin{array}{c}\hfill \left.\begin{array}{c}u(l+1)=A\otimes w\left(l\right),forl\in \mathbb{W}\hfill \\ w(l+1)=B{\otimes }^{\prime }u\left(l\right),forl\in \mathbb{W}\hfill \end{array}\right\},\end{array}$$

(1)

where $\mathbb{W}$ is the set of whole numbers and

$$u\left(l\right)=\left(\begin{array}{c}{u}_1\left(l\right)\\ u_2\left(l\right)\\ ·\\ ·\\ ·\\ u_m\left(l\right)\end{array}\right)\in {\mathbb{R}}_{ϵ}^m,w\left(l\right)=\left(\begin{array}{c}{w}_1\left(l\right)\\ w_2\left(l\right)\\ ·\\ ·\\ ·\\ w_n\left(l\right)\end{array}\right)\in {\mathbb{R}}_{\tau }^n$$

$$A=\left(\begin{array}{ccccc}{a}_{11}& a_{12}& a_{13}& \cdots & a_{1n}\\ a_{21}& a_{22}& a_{23}& \cdots & a_{2n}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& a_{m3}& \cdots & a_{mn}\end{array}\right)\in {\mathbb{R}}_{ϵ}^{m\times n},$$

$$B=\left(\begin{array}{ccccc}{b}_{11}& b_{12}& b_{13}& \cdots & b_{1m}\\ b_{21}& b_{22}& b_{23}& \cdots & b_{2m}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ b_{n1}& b_{n2}& b_{n3}& \cdots & b_{nm}\end{array}\right)\in {\mathbb{R}}_{\tau }^{n\times m}.$$

Compactly, system $\left(1\right)$ can be written by a mapping $\mathcal{M}(·)$, such that

$$x(l+1)=\mathcal{M}\left(x\right(l\left)\right),$$

(2)

$$\mathrm{where} x\left(l\right)=\left(\begin{array}{c}u\left(l\right)\\ w\left(l\right)\end{array}\right),\mathcal{M}\left(\begin{array}{c}\left(\begin{array}{c}u\left(l\right)\\ w\left(l\right)\end{array}\right)\end{array}\right)=\left(\begin{array}{c}A\otimes w\left(l\right)\\ B{\otimes }^{\prime }u\left(l\right)\end{array}\right), \mathrm{for} l\in \mathbb{W}.$$

For a system of type $\left(2\right)$, the notion of eigenvalue and eigenvectors is defined as follows. A real number $\lambda \in \mathbb{R}$ is said to be an eigenvalue corresponding to an eigenvector $v\in {\mathbb{R}}^{m+n}$ if

$$\mathcal{M}\left(v\right)=\lambda \otimes v.$$

(3)

The cycle time vector in a system of type $\left(2\right)$ is defined as

$$\eta (A,B)=\underset{l\to \infty }{lim}x\left(l\right).$$

The cycle time vector $\eta (A,B)\in {\mathbb{R}}_{ϵ}^n$ is a vector such that each component is equal to the eigenvalue for the given system of type (2). The cycle time vector is independent of initial vector $x\left(0\right)$. In this section, we determine the eigenvalue $\lambda$ by computing cycle time vector. To compute the eigenvectors, we propose an iterative algorithm. For this purpose, define $A_{\lambda }=-\lambda \otimes A$ and $B_{\lambda }=-\lambda \otimes B$, corresponding to the eigenvalue $\lambda$ of a system of type (2). Also define

$$\left.\begin{array}{c}{u}^{*}(l+1)=A_{\lambda }\otimes w^{*}\left(l\right)\hfill \\ w^{*}(l+1)=B_{\lambda }{\otimes }^{\prime }{u}^{*}\left(l\right)\hfill \end{array}\right\}$$

(4)

for $l\in \mathbb{W}$, where $u^{*}\left(l\right)\in {\mathbb{R}}_{ϵ}^m$ and $w^{*}\left(l\right)\in {\mathbb{R}}_{\tau }^n$.

System (4) can be denoted as,

$$x^{*}(l+1)=\mathcal{N}\left(x^{*}\left(l\right)\right)$$

(5)

$$\mathrm{where} x^{*}\left(l\right)=\left(\begin{array}{c}{u}^{*}\left(l\right)\\ w^{*}\left(l\right)\end{array}\right),\mathcal{N}\left(\begin{array}{c}\left(\begin{array}{c}{u}^{*}\left(l\right)\\ w^{*}\left(l\right)\end{array}\right)\end{array}\right)=\left(\begin{array}{c}{A}_{\lambda }\otimes w^{*}\left(l\right)\\ B_{\lambda }{\otimes }^{\prime }{u}^{*}\left(l\right)\end{array}\right),$$

for $l\in \mathbb{W}$. Let v be a vector, then ${\mathcal{N}}^l\left(v\right)$ represents a vector obtained after applying $\mathcal{N}$ on the vector v by l times. A relation between (2) and (5) is shown in the following theorem.

Theorem 1.

Let λ be an eigenvalue for a system of type (2) and $v=\left(\begin{array}{c}u\left(l\right)\\ w\left(l\right)\end{array}\right)$ be a vector, then

$$\mathcal{M}\left(v\right)=\lambda \otimes \mathcal{N}\left(v\right).$$

Proof. 

Since

$$\begin{array}{ccc}\hfill \mathcal{M}\left(v\right)& =\hfill & \left(\begin{array}{c}A\otimes w\left(l\right)\\ B{\otimes }^{\prime }u\left(l\right)\end{array}\right)\hfill \\ & =\hfill & \lambda \otimes (-\lambda )\otimes \left(\begin{array}{c}A\otimes w\left(l\right)\\ B{\otimes }^{\prime }u\left(l\right)\end{array}\right)\hfill \\ & =\hfill & \lambda \otimes \left(\begin{array}{c}(-\lambda )\otimes A\otimes w\left(l\right)\\ (-\lambda )\otimes B{\otimes }^{\prime }u\left(l\right)\end{array}\right)\hfill \\ & =\hfill & \lambda \otimes \left(\begin{array}{c}{A}_{\lambda }\otimes w\left(l\right)\\ B_{\lambda }{\otimes }^{\prime }u\left(l\right)\end{array}\right)\hfill \\ & =\hfill & \lambda \otimes \mathcal{N}\left(v\right).\hfill \end{array}$$

 □

Corollary 1.

Let v be an eigenvector corresponding to the eigenvalue λ of a system of type $\left(2\right)$. Then

$$\mathcal{N}\left(v\right)=v.$$

Proof. 

By definition, $\mathcal{M}\left(v\right)=\lambda \otimes v$. Using Theorem 1, we get, $\lambda \otimes \mathcal{N}\left(v\right)=\lambda \otimes v$. Hence $\mathcal{N}\left(v\right)=v$.  □

Theorem 2.

Let λ be an eigenvalue of a system of type (2) and let

$$x^{*}(l+1)=\mathcal{N}\left(x^{*}\left(l\right)\right)$$

for $l\in \mathbb{W}$, where $x^{*}\left(0\right)$ is an initial state vector. If $x^{*}\left(r\right)=x^{*}\left(s\right)$ for some integers $r>s\ge 0$, then

$$\mathcal{M}\left(v\right)=\lambda \otimes v,$$

where

$$v=x^{*}\left(s\right)\oplus \dots \oplus x^{*}(r-1).$$

Proof. 

From Theorem 1,

$$\begin{array}{ccc}\hfill \mathcal{M}\left(v\right)& =\hfill & \lambda \otimes \mathcal{N}\left(v\right)\hfill \\ & =\hfill & \lambda \otimes \left\{\left(\begin{array}{c}{A}_{\lambda }\otimes w^{*}\left(s\right)\\ B_{\lambda }{\otimes }^{\prime }{u}^{*}\left(s\right)\end{array}\right)\oplus \dots \oplus \left(\begin{array}{c}{A}_{\lambda }\otimes w^{*}(r-1)\\ B_{\lambda }{\otimes }^{\prime }{u}^{*}(r-1)\end{array}\right)\right\}\hfill \\ & =\hfill & \lambda \otimes \{x^{*}(s+1)\oplus \dots \oplus x^{*}\left(r\right)\}\hfill \\ & =\hfill & \lambda \otimes v.\hfill \end{array}$$

 □

Now we present Algorithm 1 in the following, which gives the eigenvectors corresponding to the eigenvalue $\lambda$. But, first we give three basic assumptions in the following that are necessary for the convergence of the algorithm.

• For any arbitrary initial vector $x\left(0\right)$, the system of type (2), ends up in a periodic behavior, after a finite number of iterations.
• Eigenvalue of the system exists.
• Every periodic behavior has the same average weight, equal to eigenvalue.

Algorithm 1 Eigenvectors for systems of type (2)

Compute the eigenvalue $\lambda$, by calculating the cycle time vector $\eta (A,B)$. Define $A_{\lambda }=-\lambda \otimes A$, and $B_{\lambda }=-\lambda \otimes B$. Take an initial state vector $x^{*}\left(0\right)$. Iterate $x^{*}(l+1)=\mathcal{N}\left(x^{*}\left(l\right)\right)=\left(\begin{array}{c}{A}_{\lambda }\otimes w^{*}\left(l\right)\\ B_{\lambda }{\otimes }^{\prime }{u}^{*}\left(l\right)\end{array}\right)$, for $l\in \mathbb{W}$, until there are positive integers $r>s\ge 0$, such that $x^{*}\left(r\right)=x^{*}\left(s\right)$. Compute the candidate eigenvector $$v=x^{*}\left(s\right)\oplus \dots \oplus x^{*}(r-1).$$ If $\mathcal{N}\left(v\right)=v$ then v is the correct eigenvector and algorithm stops. Else if $\mathcal{N}\left(v\right)\ne v$ then go to the following step. Take v as new starting vector and iterate $x^{*}(l+1)=\mathcal{N}\left(x^{*}\left(l\right)\right)$, until for some $t\ge 0$, it holds that $x^{*}(t+1)=x^{*}\left(t\right)$. Finally $x^{*}\left(t\right)$ is an eigenvector.

Theorem 3.

Let λ be an eigenvalue and v be a vector computed as in Algorithm 1 for a system of type (2), then

$$\mathcal{N}\left(v\right)\ge v.$$

Proof. 

From the given algorithm

$$\begin{array}{ccc}\hfill v& =\hfill & x^{*}\left(s\right)\oplus \dots \oplus x^{*}(r-1)\hfill \\ & \ge \hfill & x^{*}\left(l\right)\mathrm{for}\mathrm{all}l\in \{s,\dots ,r-1\}.\hfill \end{array}$$

Hence

$$\begin{array}{cccc}\hfill \mathcal{N}\left(v\right)& \ge \hfill & \mathcal{N}\left(x^{*}\left(l\right)\right)\hfill & \mathrm{for}\mathrm{all}l\in \{s,\dots ,r-1\}\hfill \\ & =\hfill & x^{*}(l+1)\hfill & \mathrm{for}\mathrm{all}l\in \{s,\dots ,r-1\}.\hfill \end{array}$$

These inequalities imply that

$$\mathcal{N}\left(v\right)\ge x^{*}(s+1)\oplus \dots \oplus x^{*}\left(r\right)=v.$$

 □

Lemma 1.

Let v be a vector computed as in the above Algorithm 1 for a bipartite min-max-plus system. Let (5) be restarted with $x^{*}\left(0\right)=v$, then

$$x^{*}(l+1)\ge x^{*}\left(l\right)\mathrm{for}\mathrm{all}l=0,1,2,\dots$$

Proof. 

Since $x^{*}\left(l\right)={\mathcal{N}}^l\left(v\right)$, which implies that

$$\begin{array}{ccc}\hfill x^{*}(l+1)& =\hfill & {\mathcal{N}}^{l+1}\left(v\right)\hfill \\ & =\hfill & {\mathcal{N}}^l\left(\mathcal{N}\left(v\right)\right)\hfill \\ & \ge \hfill & {\mathcal{N}}^l\left(v\right)\hfill \\ & =\hfill & x^{*}\left(l\right).\hfill \end{array}$$

 □

Proof of Algorithm 1.

Since the system ends up in a periodic behavior aftera finite number of iterations, therefore step 3 of the algorithm performs. If $\mathcal{N}\left(v\right)=v$ then v is the correct eigenvector and clearly algorithm can stop. If $\mathcal{N}\left(v\right)\ne v$ then start by considering $x^{*}\left(0\right)=v$ as new initial vector and iterate (5).

By first assumption, there exist integers $r>s\ge 0$, with $x^{*}\left(r\right)=x^{*}\left(s\right)$. By Lemma 1, $x^{*}(l+1)\ge x^{*}\left(l\right)$ for all $l\in \{s,\dots ,r-1\}$. Our goal is to show that $x^{*}(l+1)=x^{*}\left(l\right)$ for all $l\in \{s,\dots ,r-1\}$. Suppose on contrary that $x_{j^{\prime }}^{*}(l^{\prime }+1)>x_{j^{\prime }}^{*}\left(l^{\prime }\right)$, for some integers $l^{\prime },j^{\prime }$ such that, $s\le l^{\prime }\le r-1$ and $1\le j^{\prime }\le n$. We obtain that $x_{j^{\prime }}^{*}\left(r\right)>x_{j^{\prime }}^{*}\left(s\right)$, which is a contradiction because $x^{*}\left(r\right)=x^{*}\left(s\right)$. Hence $x^{*}(l+1)=x^{*}\left(l\right)$ for all $l\in \{s,\dots ,r-1\}$. Which completes the proof.  □

Example 1.

Consider a system of type (2), given as follows:

$$A=\left[\begin{array}{ccc}2& 0& 3\\ 1& 5& ϵ\\ ϵ& 2& 4\end{array}\right],B=\left[\begin{array}{ccc}\tau & 3& 1\\ 2& 4& 4\\ 5& \tau & 0\end{array}\right].$$

Since the cycle time vector is equal to ${(2 2 2 2 2 2)}^T$. Therefore the eigenvalue $\lambda =2$.

We get,

$$A_{\lambda }=\left[\begin{array}{ccc}0& -2& 1\\ -1& 3& ϵ\\ ϵ& 0& 2\end{array}\right],B_{\lambda }=\left[\begin{array}{ccc}\tau & 1& -1\\ 0& 2& 2\\ 3& \tau & -2\end{array}\right].$$

Now, take the initial state vector

$$x^{*}\left(0\right)=\left(\begin{array}{c}{u}^{*}\left(0\right)\\ w^{*}\left(0\right)\end{array}\right)with{u}^{*}\left(0\right)=\left(\begin{array}{c}0\\ 1\\ 0\end{array}\right),w^{*}\left(0\right)=\left(\begin{array}{c}1\\ 0\\ 1\end{array}\right).$$

The following sequence is obtained, after iterating (5),

$$\begin{array}{ccccccccccc}\hfill x^{*}\left(0\right)& \to & x^{*}\left(1\right)& \to & x^{*}\left(2\right)& \to & x^{*}\left(3\right)& \to & x^{*}\left(4\right)& \to & x^{*}\left(5\right)\\ \hfill \left(\begin{array}{c}0\\ 1\\ 0\\ 1\\ 0\\ 1\end{array}\right)& \to & \left(\begin{array}{c}2\\ 3\\ 3\\ -1\\ 0\\ -2\end{array}\right)& \to & \left(\begin{array}{c}-1\\ 3\\ 0\\ 2\\ 2\\ 1\end{array}\right)& \to & \left(\begin{array}{c}2\\ 5\\ 3\\ -1\\ -1\\ -2\end{array}\right)& \to & \left(\begin{array}{c}-1\\ 2\\ 0\\ 2\\ 2\\ 1\end{array}\right)& \to & \left(\begin{array}{c}2\\ 5\\ 3\\ -1\\ -1\\ -2\end{array}\right).\end{array}$$

Since $x^{*}\left(5\right)=x^{*}\left(3\right)$, therefore $s=3$, $r=5$. To compute a corresponding eigenvector we proceed with the computation of the vector v.

$$\begin{array}{ccc}\hfill v& =\hfill & x^{*}\left(s\right)\oplus \dots \oplus x^{*}(r-1)\hfill \\ & =\hfill & x^{*}\left(3\right)\oplus x^{*}\left(4\right)\hfill \end{array}$$

$$\begin{array}{ccc}\hfill v& =\hfill & \left(\begin{array}{c}2\\ 5\\ 3\\ -1\\ -1\\ -2\end{array}\right)\oplus \left(\begin{array}{c}-1\\ 2\\ 0\\ 2\\ 2\\ 1\end{array}\right)=\left(\begin{array}{c}2\\ 5\\ 3\\ 2\\ 2\\ 1\end{array}\right).\hfill \end{array}$$

Now verify that either v is the correct eigenvector or not. So

$$\mathcal{M}\left(v\right)=\left(\begin{array}{c}4\\ 7\\ 5\\ 4\\ 4\\ 3\end{array}\right)=\lambda \otimes v.$$

Which shows that the eigenvector v is the correct eigenvector obtained by Algorithm 2.

3. Latin Squares in Bipartite (Min, Max, Plus)-Systems

A Latin square is a square matrix of order n, with elements from n independent variables over ${\mathbb{R}}^{+}$ in such a way that each row and each column is a different permutation of the n variables [18]. In the following, an example of a Latin square of order 4 is given

$$L=\left(\begin{array}{cccc}3& 2& 4& 1\\ 4& 1& 3& 2\\ 2& 4& 1& 3\\ 1& 3& 2& 4\end{array}\right).$$

We consider the Latin squares of size n in a system of type (2). We have four possibilities for the Latin squares in a system of type (2): (1) The entries of both matrices A and B are $\underline{n}$; (2) The entries of matrix A are ${\underline{n}}_{ϵ}$ and the entries of matrix B are $\underline{n}$; (3) The entries of matrix A are $\underline{n}$ and the entries of matrix B are ${\underline{n}}_{\tau }$; (4) The entries of matrix A are ${\underline{n}}_{ϵ}$ and the entries of matrix B are ${\underline{n}}_{\tau }$, where ${\underline{n}}_{ϵ}=\{1,\dots ,n-1,ϵ\}$ and ${\underline{n}}_{\tau }=\{1,\dots ,n-1,\tau \}$.

In this section, we consider Latin squares for systems of type (2) and Algorithm 1 is extended to calculate the eigenvalue and eigenvectors for such type of systems. In [14], authors show that for Latin squares in a system of type (2), the eigenvalue $\lambda$ is determined as

$$\lambda ={\displaystyle \frac{\max \left(A\right)+\min \left(\mathrm{B}\right)}{2}}.$$

(6)

Now, we propose Algorithm 2 to solve eigenvalue problem for Latin squares in a system of type (2) as follows:

Algorithm 2 Eigenvalue and Eigenvectors for Latin squares in a system of type (2)

Compute the eigenvalue as, $\lambda ={\displaystyle \frac{\max \left(A\right)+\min \left(\mathrm{B}\right)}{2}}$. Define $A_{\lambda }=-\lambda \otimes A$, and $B_{\lambda }=-\lambda \otimes B$. Take a starting vector $x^{*}\left(0\right)$. Iterate (5), until for some integers $r>s\ge 0$, it holds that $x^{*}\left(r\right)=x^{*}\left(s\right)$. Determine the eigenvector as, $$v=x^{*}\left(s\right)\oplus \dots \oplus x^{*}(r-1).$$ If $\mathcal{N}\left(v\right)=v$ then v is the correct eigenvector corresponding to the eigenvalue $\lambda$ and algorithm can stops. Else if $\mathcal{N}\left(v\right)\ne v$ then go to the following step. Take v as initial state vector and iterate $x^{*}(l+1)=\mathcal{N}\left(x^{*}\left(l\right)\right)$, until for some $t\ge 0$, it holds that $x^{*}(t+1)=x^{*}\left(t\right)$. Finally $x^{*}\left(t\right)$ is an eigenvector.

Here we find the eigenvalue and eigenvectors for Latin squares in systems of type (2) by using Algorithm 2. First, recall the power algorithm (Algorithm 3) for systems of type (2), proposed by Subiono and van der Woude [12], then we compare it with Algorithm 2.

Algorithm 3 Eigenproblems for Bipartite (Min, Max, Plus)-Systems

Define a starting vector $x\left(0\right)$. Iterate (2), until there exist a real number c and positive integers $r;s$, such that $r>s\ge 0$ with $x\left(r\right)=c\otimes x\left(s\right)$. The eigenvalue is obtained as, $\lambda ={\displaystyle \frac{c}{r-s}}.$ Determine the eigenvector as, $v={\oplus }_{j=1}^{r-s}({\lambda }^{\otimes (r-s-j)}\otimes x(s+j-1)).$ If $\mathcal{M}\left(v\right)=\lambda \otimes v$ then v is the required eigenvector corresponding to the eigenvalue $\lambda$ and algorithm can stop. If $\mathcal{M}\left(v\right)\ne \lambda \otimes v$, then the algorithm has to be continued as follows. Define $x\left(0\right)=v$ as new starting vector and restart (2), until for some r, there holds $x(r+1)=\lambda \otimes x\left(r\right)$. Then $x\left(r\right)$ is a correct eigenvector of system (2).

To illustrate the Algorithms 2 and 3, consider the following example. In this example, we consider a system of type (2), where A and B are Latin Squares with entries in ${\underline{n}}_{ϵ}$ and ${\underline{n}}_{\tau }$ respectively.

Example 2.

Let A and B are Latin squares in a system of type (2), given as follows:

$$A=\left[\begin{array}{cccc}3& 2& ϵ& 1\\ ϵ& 1& 3& 2\\ 2& 3& 1& ϵ\\ 1& ϵ& 2& 3\end{array}\right],B=\left[\begin{array}{cccc}2& 3& \tau & 1\\ 3& \tau & 1& 2\\ 1& 2& 3& \tau \\ \tau & 1& 2& 3\end{array}\right].$$

1. 

The eigenvalue λ is given as,

$$\lambda ={\displaystyle \frac{\max \left(A\right)+\min \left(\mathrm{B}\right)}{2}}=2.$$

By Algorithm 2,

$$A_{\lambda }=\left[\begin{array}{cccc}1& 0& ϵ& -1\\ ϵ& -1& 1& 0\\ 0& 1& -1& ϵ\\ -1& ϵ& 0& 1\end{array}\right],B_{\lambda }=\left[\begin{array}{cccc}0& 1& \tau & -1\\ 1& \tau & -1& 0\\ -1& 0& 1& \tau \\ \tau & -1& 0& 1\end{array}\right].$$

Now, take the initial state vector

$$x^{*}\left(0\right)=\left(\begin{array}{c}{u}^{*}\left(0\right)\\ w^{*}\left(0\right)\end{array}\right)with{u}^{*}\left(0\right)=\left(\begin{array}{c}0\\ 1\\ 0\\ 1\end{array}\right),w^{*}\left(0\right)=\left(\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right).$$

The following sequence is obtained, after iterating (5),

$$\begin{array}{ccccccccccccc}\hfill x^{*}\left(0\right)& \to & x^{*}\left(1\right)& \to & x^{*}\left(2\right)& \to & x^{*}\left(3\right)& \to & x^{*}\left(4\right)& \to & x^{*}\left(5\right)& \to & x^{*}\left(6\right)\\ \hfill \left(\begin{array}{c}0\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0\end{array}\right)& \to & \left(\begin{array}{c}2\\ 2\\ 1\\ 1\\ 0\\ -1\\ -1\\ 0\end{array}\right)& \to & \left(\begin{array}{c}1\\ 0\\ 0\\ 1\\ 0\\ 0\\ 1\\ 1\end{array}\right)& \to & \left(\begin{array}{c}1\\ 2\\ 1\\ 2\\ 0\\ -1\\ 0\\ -1\end{array}\right)& \to & \left(\begin{array}{c}1\\ 1\\ 0\\ 0\\ 1\\ 0\\ 0\\ 1\end{array}\right)& \to & \left(\begin{array}{c}2\\ 1\\ 1\\ 2\\ -1\\ -1\\ 0\\ 0\end{array}\right)& \to & \left(\begin{array}{c}0\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0\end{array}\right).\end{array}$$

Since $x^{*}\left(6\right)=x^{*}\left(0\right)$, therefore $s=0,r=6$. The required eigenvector v is computed as,

$$\begin{array}{ccc}\hfill v& =\hfill & x^{*}\left(s\right)\oplus \dots \oplus x^{*}(r-1)\hfill \\ & =\hfill & x^{*}\left(0\right)\oplus \dots \oplus x^{*}\left(5\right)\hfill \\ & =\hfill & \left(\begin{array}{c}0\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0\end{array}\right)\oplus \left(\begin{array}{c}2\\ 2\\ 1\\ 1\\ 0\\ -1\\ -1\\ 0\end{array}\right)\oplus \left(\begin{array}{c}1\\ 0\\ 0\\ 1\\ 0\\ 0\\ 1\\ 1\end{array}\right)\oplus \left(\begin{array}{c}1\\ 2\\ 1\\ 2\\ 0\\ -1\\ 0\\ -1\end{array}\right)\oplus \left(\begin{array}{c}1\\ 1\\ 0\\ 0\\ 1\\ 0\\ 0\\ 1\end{array}\right)\oplus \left(\begin{array}{c}2\\ 1\\ 1\\ 2\\ -1\\ -1\\ 0\\ 0\end{array}\right)=\left(\begin{array}{c}2\\ 2\\ 1\\ 2\\ 1\\ 0\\ 1\\ 1\end{array}\right).\hfill \end{array}$$

Now verify that either v is the correct eigenvector or not. So

$$\mathcal{M}\left(v\right)=\left(\begin{array}{c}4\\ 4\\ 3\\ 4\\ 3\\ 2\\ 3\\ 3\end{array}\right)=\lambda \otimes v.$$

Which shows that the eigenvector v is the correct eigenvector obtained by Algorithm 2.

2. 

For Algorithm 3, take the initial vector

$$x\left(0\right)=\left(\begin{array}{c}u\left(0\right)\\ w\left(0\right)\end{array}\right)\mathrm{with}u\left(0\right)=\left(\begin{array}{c}0\\ 1\\ 0\\ 1\end{array}\right),w\left(0\right)=\left(\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right).$$

The following sequence is obtained, after iterating (2)

$$\begin{array}{ccccccccccccc}\hfill x\left(0\right)& \to & x\left(1\right)& \to & x\left(2\right)& \to & x\left(3\right)& \to & x\left(4\right)& \to & x\left(5\right)& \to \hfill & x\left(6\right)\\ \hfill \left(\begin{array}{c}0\\ 1\\ 0\\ 1\\ 1\\ 0\\ 1\\ 0\end{array}\right)& \to & \left(\begin{array}{c}4\\ 4\\ 3\\ 3\\ 2\\ 1\\ 1\\ 2\end{array}\right)& \to & \left(\begin{array}{c}5\\ 4\\ 4\\ 5\\ 4\\ 4\\ 5\\ 5\end{array}\right)& \to & \left(\begin{array}{c}7\\ 8\\ 7\\ 8\\ 6\\ 5\\ 6\\ 5\end{array}\right)& \to & \left(\begin{array}{c}9\\ 9\\ 8\\ 8\\ 9\\ 8\\ 8\\ 9\end{array}\right)& \to & \left(\begin{array}{c}12\\ 11\\ 11\\ 12\\ 9\\ 9\\ 10\\ 10\end{array}\right)& \to & \left(\begin{array}{c}12\\ 13\\ 12\\ 13\\ 13\\ 12\\ 13\\ 12\end{array}\right).\end{array}$$

Since $x\left(6\right)=12\otimes x\left(0\right)$. It follows that $s=0,r=6$, and $c=12$. The corresponding eigenvector v is obtained as

$$\begin{array}{ccc}\hfill v& =\hfill & {\oplus }_{j=1}^{r-s}({\lambda }^{\otimes (r-s-j)}\otimes x(s+j-1))\hfill \\ & =\hfill & {\oplus }_{j=1}^6({\lambda }^{\otimes (6-j)}\otimes x(j-1))\hfill \\ & =\hfill & {\lambda }^{\otimes \left(5\right)}\otimes x\left(0\right)\oplus {\lambda }^{\otimes \left(4\right)}\otimes x\left(1\right)\oplus {\lambda }^{\otimes \left(3\right)}\otimes x\left(2\right)\oplus {\lambda }^{\otimes \left(2\right)}\otimes x\left(3\right)\oplus \lambda \otimes x\left(4\right)\oplus x\left(5\right)\hfill \\ & =\hfill & \left(\begin{array}{c}10\\ 11\\ 10\\ 11\\ 11\\ 10\\ 11\\ 10\end{array}\right)\oplus \left(\begin{array}{c}12\\ 12\\ 11\\ 11\\ 10\\ 9\\ 9\\ 10\end{array}\right)\oplus \left(\begin{array}{c}11\\ 10\\ 10\\ 11\\ 10\\ 10\\ 11\\ 11\end{array}\right)\oplus \left(\begin{array}{c}11\\ 12\\ 11\\ 12\\ 10\\ 9\\ 10\\ 9\end{array}\right)\oplus \left(\begin{array}{c}11\\ 11\\ 10\\ 10\\ 11\\ 10\\ 10\\ 11\end{array}\right)\oplus \left(\begin{array}{c}12\\ 11\\ 11\\ 12\\ 9\\ 9\\ 10\\ 10\end{array}\right)\hfill \end{array}$$

Finally, we obtain

$$v=\left(\begin{array}{c}12\\ 12\\ 11\\ 12\\ 11\\ 10\\ 11\\ 11\end{array}\right).$$

Which is the correct eigenvector.

Using Algorithm 3 in Example 2, system ends up in a periodic behaviour after 6th iteration and we get $s=0$, $r=6$ and $c=12$. If we consider $x\left(0\right)={(0 0 0 0 0 0 0)}^T$ in Example 2, then we get $s=0$, $r=2$ and $c=4$. So in case of Algorithm 3, one can get different value of c for different initial state vectors, while in Algorithm 2, we need not a real number c.

Remark 1.

The main focus in this paper is to develop an efficient algorithm to find out the eigenvectors for systems of type (2). Also, we have made computational experiment to compare the Algorithms 2 and 3 for Latin squares. We have implemented both algorithms in MATLAB for $r\in A_1$, $s\in A_2$ and $c\in A_3$ such that $|A_i|=n_i,i=1,2,3$. Here $|A_i|$ represents the cardinality of each set $A_i$. In case of Algorithm 3, it stops if there exists a positive integers $r>s\ge 0$ and a real number c with $x\left(r\right)=x\left(s\right)\otimes c$, while in that of Algorithm 2, it stops if for some integers $r>s\ge 0$ it holds $x^{*}\left(r\right)=x^{*}\left(s\right)$. Therefore, the time complexity of Algorithm 3 is $\mathcal{O}\left(n_1{n}_2{n}_3\right)$, while the time complexity of Algorithm 2 is $\mathcal{O}\left(n_1{n}_2\right)$. Thus the proposed algorithm takes less time than the compared one.

The computational efficiency of the proposed method can be seen by comparing the runtimes of Algorithm 2 and 3. Both algorithms are executed under the same Laptop environment with 1.70 GHz CPU, 4 GB RAM, MATLAB (R2015a) simulation software. We computed the time of calculating eigenvalue and eigenvector for Example 2 by both algorithms. The time consumptions of Algorithm 2 and 3 are 0.088783 s and 1.718662 s respectively, which clearly reveals that the proposed algorithm is faster than the other one. Also in case of Algorithm 2, we obtain the eigenvector v by a simple formula, given as $v=x^{*}\left(s\right)\oplus \dots \oplus x^{*}(r-1)$ however, while using that Algorithm 3 an eigenvector is obtained as

$$v={\oplus }_{j=1}^{r-s}({\lambda }^{\otimes (r-s-j)}\otimes x(s+j-1)).$$

which is quite difficult compared to Algorithm 2.

4. Conclusions

The eigenproblem of bipartite min-max-plus systems for Latin squares has been discussed in this work. The iterative Algorithm 1 was developed for the computation of the eigenvectors (trivial and nontrivial) for systems of type (2). In particular, this algorithm was extended to compute the eigenvalue and eigenvectors for Latin squares in a system of type (2). At the end, a computational comparison has been given. Experimental result shows that the proposed Algorithm 2 is much more computationally efficient than the compared one. Of course, Algorithm 2 is only for Latin squares in a system of type (2), while Algorithm 3 may be used for all bipartite min-max-plus systems. Similarly, one can derive an algorithm to calculate the eigenvalue and eigenvectors for separated min-max-plus systems.