Open access peer-reviewed chapter

A Linear System of Both Equations and Inequalities in Max-Algebra

By Abdulhadi Aminu

Submitted: November 11th 2011Reviewed: April 24th 2012Published: July 11th 2012

DOI: 10.5772/48195

Downloaded: 2289

1. Introduction

The aim of this chapter is to present a system of linear equation and inequalities in max-algebra. Max-algebra is an analogue of linear algebra developed on the pair of operations (,)extended to matrices and vectors, where ab=max(a,b)and ab=a+bfor a,b. The system of equations Ax=cand inequalities Bxdhave each been studied in the literature. We will present necessary and sufficient conditions for the solvability of a system consisting of these two systems and also develop a polynomial algorithm for solving max-linear program whose constraints are max-linear equations and inequalities. Moreover, some solvability concepts of an inteval system of linear equations and inequalities will also be presented.

Max-algebraic linear systems were investigated in the first publications which deal with the introduction of algebraic structures called (max,+) algebras. Systems of equations with variables only on one side were considered in these publications [1], [2] and [3]. Other systems with a special structure were investigated in the context of solving eigenvalue problems in correspondence with algebraic structures or synchronisation of discrete event systems, see [4] and also [1] for additional information. Given a matrix A, a vector bof an appropriate size, using the notation =max, =plus, the studied systems had one of the following forms: Ax=b, Ax=xor Ax=xb. An infinite dimensional generalisation can be found in [5].

In [1] Cuninghame-Green showed that the problem Ax=bcan be solved using residuation [6]. That is the equality in Ax=bbe relaxed so that the set of its sub-solutions is studied. It was shown that the greatest solution of Axbis given by x¯where


The equation Ax=bis also solved using the above result as follows: The equation Ax=bhas solution if and only if Ax¯=b. Also, Gaubert [7] proposed a method for solving the one-sided system x=Axbusing rational calculus.

Zimmermann [3] developed a method for solving Ax=bby set covering and also presented an algorithm for solving max-linear programs with one sided constraints. This method is proved to has a computational complexity of O(mn), where m,nare the number of rows and columns of input matrices respectively. Akian, Gaubert and Kolokoltsov [5] extended Zimmermann's solution method by set covering to the case of functional Galois connections.

Butkovic [8] developed a max-algebraic method for finding all solutions to a system of inequalities xi-xj>bij,i,j=1,...,nusing ngenerators. Using this method Butkovic [8] developed a pseudopolynomial algorithm which either finds a bounded mixed-integer solution, or decides that no such solution exists. Summary of these results can be found in [9] and [10]

Cechla´rova and Diko [11] proposed a method for resolving infeasibility of the system Ax=b. The techniques presented in this method are to modify the right-hand side as little as possible or to omit some equations. It was shown that the problem of finding the minimum number of those equations is NP-complete.


2. Max-algebra and some basic definitions

In this section we introduce max-algebra, give the essential definitions and show how the operations of max-algebra can be extended to matrices and vectors.

In max-algebra, we replace addition and multiplication, the binary operations in conventional linear algebra, by maximum and addition respectively. For any problem that involves adding numbers together and taking the maximum of numbers, it may be possible to describe it in max-algebra. A problem that is nonlinear when described in conventional terms may be converted to a max-algebraic problem that is linear with respect to (,)=(max,+).

Definition 1The max-plus semiring ¯is the set {-}, equipped with the addition (a,b)max(a,b)and multiplication (a,b)a+bdenoted by and respectively. That is ab=max(a,b)and ab=a+b. The identity element for the addition (or zero) is -, and the identity element for the multiplication (or unit) is 0.

Definition 2The min-plus semiring minis the set {+}, equipped with the addition (a,b)min(a,b)and multiplication (a,b)a+bdenoted by 'and 'respectively. The zero is +, and the unit is 0. The name tropical semiring is also used as a synonym of min-plus when the ground set is .

The completed max-plus semiring ¯maxis the set {±}, equipped with the addition (a,b)max(a,b)and multiplication (a,b)a+b, with the convention that -+(+)=++(-)=-. The completed min-plus semiring ¯minis defined in the dual way.

Proposition 1The following properties hold for all a,b,c¯:


The statements follow from the definitions.

Proposition 2For all a,b,c¯the following properties hold:


The statements follow from definitions. The pair of operations (,) is extended to matrices and vectors as in the conventional linear algebra as follows: For A=(aij),B=(bij)of compatible sizes and αwe have:


Example 1


Example 2


Example 3


Proposition 3

For A,B,C¯m×nof compatible sizes, the following properties hold:


The statements follow from the definitions.

Proposition 4

The following hold for A,B,C, a,b,c,x,yof compatible sizes and α,β:


The statements follow from the definition of the pair of operations (,).

Definition 3Given real numbers a,b,c,, a max-algebraic diagonal matrixis defined as:


Given a vector d=(d1,d2,,dn), the diagonal of the vectordis denoted as diag(d)=diag(d1,d2,,dn).

Definition 4Max-algebraic identity matrixis a diagonal matrix with all diagonal entries zero. We denote by Ian identity matrix. Therefore, identity matrixI=diag(0,0,0,).

It is obvious that AI=IAfor any matrices Aand Iof compatible sizes.

Definition 5Any matrix that can be obtained from the identity matrix, I, by permuting its rows and or columns is called a permutation matrix. A matrix arising as a product of a diagonal matrix and a permutation matrix is called a generalised permutation matrix[12].

Definition 6A matrix A¯n×nis invertibleif there exists a matrix B¯n×n, such that AB=BA=I. The matrix Bis unique and will be called the inverseof A. We will henceforth denote Bby A-1.

It has been shown in [1] that a matrix is invertibleif and only if it is a generalised permutation matrix.

If x=(x1,,xn)we will denote x-1=(x1-1,,xn-1), that is x-1=-x, in conventional notation.

Example 4

Consider the following matrices


The matrix Bis an inverse of Abecause,


Given a matrix A=(aij)¯, the transposeof Awill be denoted by AT, that is AT=(aji). Structures of discrete-event dynamic systems may be represented by square matrices Aover the semiring:


The system is embeddable in the self-dual system:


Basic algebraic properties for 'and 'are similar to those of and described earlier. These are obtained by swapping and . Extension of the pair (',')to matrices and vectors is as follows:

Given A,Bof compatible sizes and α, we define the following:


Also, properties of matrices for the pair (',')are similar to those of (,), just swap and . For any matrix A=[aij]over ¯¯, the conjugatematrix is A*=[-aji]obtained by negation and transposition, that is A=-AT.

Proposition 5The following relations hold for any matrices U,V,Wover ¯¯.


Follows from the definitions.

3. The Multiprocessor Interactive System (MPIS): A practical application

Linear equations and inequalities in max-algebra have a considerable number of applications, the model we present here is called the multiprocessor interactive system (MPIS)which is formulated as follows:

Products P1,,Pmare prepared using nprocessors, every processor contributing to the completion of each product by producing a partial product. It is assumed that every processor can work on all products simultaneously and that all these actions on a processor start as soon as the processor is ready to work. Let aijbe the duration of the work of the jthprocessor needed to complete the partial product for Pi(i=1,,m;j=1,,n). Let us denote by xjthe starting time of the jthprocessor (j=1,,n). Then, all partial products for Pi(i=1,,m;j=1,,n)will be ready at time max(ai1+x1,,ain+xn). If the completion times b1,,bmare given for each product then the starting times have to satisfy the following system of equations:


Using the notation ab=max(a,b)and ab=a+bfor a,bextended to matrices and vectors in the same way as in linear algebra, then this system can be written as


Any system of the form () is called 'one-sided max-linear system'. Also, if the requirement is that each product is to be produced on or before the completion times b1,,bm, then the starting times have to satisfy


which can also be written as


The system of inequalities () is called 'one-sided max-linear system of inequalities'.

4. Linear equations and inequalities in max-algebra

In this section we will present a system of linear equation and inequalities in max-algebra. Solvability conditions for linear system and inequalities will each be presented. A system consisting of max-linear equations and inequalities will also be discussed and necessary and sufficient conditions for the solvability of this system will be presented.

4.1. System of equations

In this section we present a solution method for the system Ax=bas given in [3], [1], [13] and also in the monograph [10]. Results concerning the existence and uniqueness of solution to the system will also be presented.

Given A=(aij)¯m×nand b=(b1,,bm)T¯m, a system of the form


is called a one-sided max-linear system, some times we may omit 'max-linear' and say one-sided system. This system can be written using the conventional notation as follows


The system in () can be written after subtracting the right-hand sides constants as


A one-sided max-linear system whose all right hand side constants are zero is called normalised max-linear systemor just normalisedand the process of subtracting the right-hand side constants is called normalisation. Equivalently, normalisationis the process of multiplying the system () by the matrix B'from the left. That is




For instance, consider the following one-sided system:


After normalisation, this system is equivalent to


That is after multiplying the system () by


Consider the first equation of the normalised system above, that is max(x1-7,x2-4,x3-2)=0. This means that if (x1,x2,x3)Tis a solution to this system then x17,x24, x32and at least one of these inequalities will be satisfied with equality. From the other equations of the system, we have for x13, x12, hence we have x1min(7,3,2)=-max(-7,-3,-2)=-x¯1where -x¯1is the column 1 maximum. It is clear that for all jthen xjx¯j, where -x¯jis the column jmaximum. At the same time equality must be attained in some of these inequalities so that in every row there is at least one column maximum which is attained by xj. This observation was made in [3].

Definition 7A matrix Ais called doubly-astic[14], [15], if it has at least one finite element on each row and on each column.

We introduce the following notations


We now consider the cases when A=-and/or b=-. Suppose that b=-. Then S(A,b)can simply be written as


Therefore if A=-we have S(A,b)=¯n. Now, if A=-and b-then S(A,b)=. Thus, we may assume in this section that A=-and b-. If bk=-for some kMthen for any xS(A,b)we have xj=-if akj-, jN, as a result the kthequation could be removed from the system together with every column jin the matrix Awhere akj-(if any), and set the corresponding xj=-. Consequently, we may assume without loss of generality that bm.

Moreover, if bmand Ahas an -row then S(A,b)=. If there is an -column jin Athen xjmay take on any value in a solution x. Thus, in what follows we assume without loss of generality that Ais doubly -asticand bm.

Theorem 1Let A=(aij)¯m×nbe doubly -asticand bm. Then xS(A,b)if and only if


Suppose xS(A,b). Thus we have,


Hence, xx¯.

Now that xS(A,b). Since MjMwe only need to show that MjNxMj. Let kM. Since bk=akjxj>-for some jNand xj-1x¯j-1aijbi-1for every iMwe have xj-1=akjbk-1=maxiMaijbi-1. Hence kMjand xj=x¯j.

Suppose that xx¯and jNxMj=M. Let kM, jN. Then akjxjbkif akj=-. If akj-then


Therefore Axb. At the same time kMjfor some jNsatisfying xj=x¯j. For this jboth inequalities in () are equalities and thus Ax=b. The following is a summary of prerequisites proved in [1] and [12]:

Theorem 2Let A=(aij)¯m×nbe doubly -asticand bm. The system Ax=bhas a solution if and only if x¯(A,b)is a solution.

Follows from Theorem .

Since x¯(A,b)has played an important role in the solution of Ax=b. This vector x¯is called the principal solutionto Ax=b[1], and we will call it likewise. The principal solution will also be used when studying the systems Axband also when solving the one-sided system containing both equations and inequalities. The one-sided systems containing both equations and inequalities have been studied in [16] and the result will be presented later in this chapter.

Note that the principal solution may not be a solution to the system Ax=b. More precisely, the following are observed in [12]:

Corollary 1Let A=(aij)¯m×nbe doubly -asticand bm. Then the following three statements are equivalent:


The statements follow from Theorems and .

For the existence of a unique solution to the max-linear system Ax=bwe have the following corollary:

Corollary 2Let A=(aij)¯m×nbe doubly -asticand bm. Then S(A,b)={x¯(A,b)}if and only if


Follows from Theorem . The question of solvability and unique solvability of the system Ax=bwas linked to the set covering and minimal set covering problem of combinatorics in [12].

4.2. System of inequalities

In this section we show how a solution to the one-sided system of inequalities can be obtained.

Let A=(aij)m×nand b=(b1,,bm)T. A system of the form:


is called one-sided max-linear system of inequalitiesor just one-sided system of inequalities. The one-sided system of inequalities has received some attention in the past, see [3], [1] and [17] for more information. Here, we will only present a result which shows that the principal solution, x¯(A,b)is the greatest solution to (). That is if () has a solution then x¯(A,b)is the greatest of all the solutions. We denote the solution set of () by S(A,b,). That is


Theorem 3xS(A,b,)if and only if xx¯(A,b).

Suppose xS(A,b,). Then we have


and the proof is now complete. The system of inequalities


was discussed in [18] where the following result was presented.

Lemma 1A system of inequalities () has a solution if and only if Cx¯(A,b)d

4.3. A system containing of both equations and inequalities

In this section a system containing both equations and inequalities will be presented, the results were taken from [16]. Let A=(aij)k×n, C=(cij)r×n, b=(b1,,bk)Tkand d=(d1,,dr)Tr. A one-sided max-linear system with both equations and inequalitiesis of the form:


We shall use the following notation throughout this paper


We also define the vector x^=(x^1,x^2,...,x^n)T, where


and Nx^={jN;x^j=x¯j}.

Theorem 4Let A=(aij)k×n, C=(cij)r×n, b=(b1,,bk)Tkand d=(d1,,dr)Tr. Then the following three statements are equivalent:


(i)(ii). Let xS(A,C,b,d), therefore xS(A,b)and xS(C,d,). Since xS(C,d,), it follows from Theorem that xx¯(C,d). Now that xS(A,b)and also xS(C,d,), we need to show that x¯j(C,d)x¯j(A,b)for all jNx(that is NxJ). Let jNxthen xj=x¯j(A,b). Since xS(C,d,)we have xx¯(C,d)and therefore x¯j(A,b)x¯j(C,d)thus jJ. Hence, NxJand by Theorem jJKj=K. This also proves (i)(iii)

(iii)(i). Suppose jJKj=K. Since x^(A,C,b,d)x¯(C,d)we have x^(A,C,b,d)S(C,d,). Also x^(A,C,b,d)x¯(A,b)and Nx^Jgives jNx^(A,C,b,d)KjjJKj=K. Hence jNx^(A,C,b,d)Kj=K, therefore x^(A,C,b,d)S(A,b)and x^(A,C,b,d)S(C,d,). Hence x^(A,C,b,d)S(A,C,b,d)(that is S(A,C,b,d)) and this also proves (iii)(ii).

Theorem 5Let A=(aij)k×n, C=(cij)r×n, b=(b1,,bk)Tkand d=(d1,,dr)Tr. Then xS(A,C,b,d)if and only if


() Let xS(A,C,b,d), then xx¯(A,b)and xx¯(C,d). Since x^(A,C,b,d)=x¯(A,b)'x¯(C,d)we have xx^(A,C,b,d). Also, xS(A,C,b,d)implies that xS(C,d,). It follows from Theorem that jNxKj=K.

() Suppose that xx^(A,C,b,d)=x¯(A,b)'x¯(C,d)and jNxKj=K. It follows from Theorem that xS(A,b), also by Theorem xS(C,d,). Thus xS(A,b)S(C,d,)=S(A,C,b,d).

We introduce the symbol |X|which stands for the number of elements of the set X.

Lemma 2Let A=(aij)k×n, C=(cij)r×n, b=(b1,,bk)Tkand d=(d1,,dr)Tr. If |S(A,C,b,d)|=1then |S(A,b)|=1.

Suppose |S(A,C,b,d)|=1, that is S(A,C,b,d)={x}for an xn. Since S(A,C,b,d)={x}we have xS(A,b)and thus S(A,b). For contradiction, suppose |S(A,b)|>1. We need to check the following two cases: (i) Land (ii) L=where L=NJ, and show in each case that |S(A,C,b,d)|>1.

Proof of Case (i), that is L: Suppose that Lcontains only one element say nNi.e L={n}. Since xS(A,C,b,d)it follows from Theorem that x^(A,C,b,d)S(A,C,b,d). That isx=x^(A,C,b,d)=(x¯1(A,b),x¯2(A,b),,x¯n-1(A,b),x¯n(C,d))S(A,C,b,d). It can also be seen that, x¯(C,d)n<x¯n(A,b)and any vector of the formz=(x¯1(A,b),x¯2(A,b),,x¯n-1(A,b),α)S(A,C,b,d), where αx¯n(C,d). Hence |S(A,C,b,d)|>1. If Lcontains more than one element, then the proof is done in a similar way.

Proof of Case (ii), that is L=(J=N): Suppose that J=N. Then we have x^(A,C,b,d)=x¯(A,b)x¯(C,d). Suppose without loss of generality that x,x'S(A,b)such that xx'. Then xx¯(A,b)x¯(C,d)and also x'x¯(A,b)x¯(C,d). Thus, x,x'S(C,d,). Consequently, x, x'S(A,C,b,d)and xx'. Hence |S(A,C,b,d)|>1.

Theorem 6Let A=(aij)k×n, C=(cij)r×n, b=(b1,,bk)Tkand d=(d1,,dr)Tr. If |S(A,C,b,d)|=1then J=N.

Suppose |S(A,C,b,d)|=1. It follows from Theorem thatjJKj=K. Also, |S(A,C,b,d)|=1implies that |S(A,b)|=1(Lemma ). Moreover, |S(A,b)|=1implies that jNKj=Kand jN'KjK,N'N,N'N(Theorem ). Since JNand jJKj=K, we have J=N.

Corollary 3Let A=(aij)k×n, C=(cij)r×n, b=(b1,,bk)Tkand d=(d1,,dr)Tr. If |S(A,C,b,d)|=1then S(A,C,b,d)={x¯(A,b)}.

The statement follows from Theorem and Lemma .

Corollary 4Let A=(aij)k×n, C=(cij)r×n, b=(b1,,bk)Tkand d=(d1,,dr)Tk. Then, the following three statements are equivalent:


(i)(ii)Follows from Lemma and Theorem .

(ii)(i)Let J=N, therefore x¯x¯(C,d)and thus S(A,b)S(C,d,). Therefore we have S(A,C,b,d)=S(A,b)S(C,d,)=S(A,b). Hence |S(A,C,b,d)|=1.

(ii)(iii)Suppose that S(A,b)={x}and J=N. It follows from Theorem that jNKj=Kand jN'KjK,N'N,N'N. Since J=Nthe statement now follows from Theorem .

(iii)(ii)It is immediate that J=Nand the statement now follows from Theorem .

Theorem 7Let A=(aij)k×n, C=(cij)r×n, b=(b1,,bk)Tkand d=(d1,,dr)Tk. If |S(A,C,b,d)|>1then |S(A,C,b,d)|is infinite .

Suppose |S(A,C,b,d)|>1. By Corollary we have jJKj=K, for some JN, JN(that is jNsuch that x¯j(A,b)>x¯j(C,d)). Now JNand jJKj=K, Theorem implies that any vector x=(x1,x2,...,xn)Tof the form


is in S(A,C,b,d), and the statement follows.

Remark 1From Theorem we can say that the number of solutions to the one-sided system containing both equations and inequalities can only be 0,1,or.

The vector x^(A,C,b,d)plays an important role in the solution of the one-sided system containing both equations and inequalities. This role is the same as that of the principal solution x¯(A,b)to the one-sided max-linear system Ax=b, see [19] for more details.

5. Max-linear program with equation and inequality constraints

Suppose that the vector f=(f1,f2,...,fn)Tnis given. The task of minimizing [maximizing]the function f(x)=fTx=max(f1+x1,f1+x2...,fn+xn)subject to () is called max-linear program with one-sided equations and inequalities and will be denoted by MLPminand [MLPmax]. We denote the sets of optimal solutions by Smin(A,C,b,d)and Smax(A,C,b,d), respectively.

Lemma 3Suppose fnand let f(x)=fTxbe defined on n. Then,

(i) f(x)is max-linear, i.e. f(λxμy)=λf(x)μf(y)

for every x,yn.

(ii) f(x)is isotone, i.e. f(x)f(y)for every x,yn, xy.

(i) Let α. Then we have


and the statement now follows.

(ii) Let x,ynsuch that xy. Since xy, we have


Note that it would be possible to convert equations to inequalities and conversely but this would result in an increase of the number of constraints or variables and thus increasing the computational complexity. The method we present here does not require any new constraint or variable.

We denote by


A variable xjwill be called activeif xj=f(x), for some jN. Also, a variable will be called activeon the constraint equation if the value (Ax)iis attained at the term xjrespectively. It follows from Theorem and Lemma that x^(A,C,b,d)Smax(A,C,b,d). We now present a polynomial algorithm which finds xSmin(A,C,b,d)or recognizes that Smin(A,B,c,d)=. Due to Theorem either x^(A,C,b,d)S(A,C,b,d)or S(A,C,b,d)=. Therefore, we assume in the following algorithm that S(A,C,b,d)and also Smin(A,C,b,d).

ONEMLP-EI(Max-linear program with one-sided equations and inequalities)f=(f1,f2,...,fn)Tn, b=(b1,b2,...bk)Tk, d=(d1,d2,...dr)Tr, A=(aij)Rk×nand C=(cij)Rr×n.xSmin(A,C,b,d).

  1. Find x¯(A,b), x¯(C,d), x^(A,C,b,d)and Kj, jJ;J={jN;x¯j(C,d)x¯j(A,b)}

  2. x:=x^(A,C,b,d)

  3. H(x):={jN;fj+xj=f(x)}

  4. J:=JH(x)

  5. If


    then stop (xSmin(A,C,b,d))

  6. Set xjsmall enough (so that it is not active on any equation or inequality) for every jH(x)

  7. Go to 3

Theorem 8The algorithm ONEMLP-EI is correct and its computational complexity is O((k+r)n2).

The correctness follows from Theorem and the computational complexity is computed as follows. In Step 1 x¯(A,b)is O(kn), while x¯(C,d), x^(A,C,b,d)and Kjcan be determined in O(rn), O(k+r)nand O(kn)respectively. The loop 3-7 can be repeated at most n-1times, since the number of elements in Jis at most nand in Step 4 at least one element will be removed at a time. Step 3 is O(n), Step 6 is O(kn)and Step 7 is O(n). Hence loop 3-7 is O(kn2).

5.1. An example

Consider the following system max-linear program in which f=(5,6,1,4,-1)T,


We now make a record run of Algorithm ONEMLP-EI. x¯(A,b)=(5,-1,3,3,-1)T, x¯(C,d)=(2,1,7,3,-1)T, x^(A,C,b,d)=(2,-1,3,3,-1)T, J={2,3,4,5}and K2={1,2}, K3={1,2}, K4={2,3}and K5={3}. x:=x^(A,C,b,d)=(2,-1,3,3,-1)Tand H(x)={1,4}and J¬H(x). We also have J:=JH(x)={2,3,5}and K2K3K5=K. Then set x1=x4=10-4(say) and x=(10-4,-1,3,10-4,-1)T. Now H(x)={2}and J:=JH(x)={3,5}. Since K3K5=Kset x2=10-4(say) and we have x=(10-4,10-4,3,10-4,-1)T. Now H(x)={3}and J:=JH(x)={5}. Since K5Kthen we stop and an optimal solution is x=(10-4,10-4,3,10-4,-1)Tand fmin=4.


6. A special case of max-linear program with two-sided constraints

Suppose c=(c1,c2,...,cm)T,d=(d1,d2,...,dm)Tm,A=(aij)and B=(bij)m×nare given matrices and vectors. The system


is called non-homogeneous two-sided max-linear system and the set of solutions of this system will be denoted by S. Two-sided max-linear systems have been studied in [20], [21], [22] and [23].

Optimization problems whose objective function is max-linear and constraint () are called max-linear programs (MLP). Max-linear programs are studied in [24] and solution methods for both minimization and maximization problems were developed. The methods are proved to be pseudopolynomial if all entries are integer. Also non-linear programs with max-linear constraints were dealt with in [25], where heuristic methods were develeoped and tested for a number of instances.

Consider max-linear programs with two-sided constraints (minimization), MLPmin


where f=(f1,,fn)Tn, c=(c1,,cm)T,d=(d1,,dm)Tm, A=(aij)and B=(bij)m×nare given matrices and vectors. We introduce the following:


diag(f)means a diagonal matrix whose diagonal elements are f1,f2,...,fnand off diagonal elements are -. It therefore follows from () that


Hence, by substituting () and () into () we have


where 0Tis transpose of the zero vector, A'=A(diag(f))-1and B'=B(diag(f))-1

Therefore we assume without loss of generality that f=0and hence () is equivalent to


The set of feasible solutions for () will be denoted by Sand the set of optimal solutions by Smin. A vector is called constantif all its components are equal. That is a vector xnis constant if x1=x2==xn. For any xSwe define the set Q(x)={iM;(Ax)i>ci}. We introduce the following notation of matrices. Let A=(aij)Rm×n, 1i1<i2<<iqmand 1j1<j2<<jrn. Then,


where, Q={i1,,iq}, R={j1,,jr}. Similar notation is used for vectors c(i1,,ir)=(ci1cir)T=c(R). Given MLPminwith cd, we define the following sets


We also define the following matrices:


An easily solvable case arises when there is a constant vector xSsuch that the set Q(x)=. This constant vector xsatisfies the following equations and inequalities


where A=,A>,B=,B>, c=and c>are defined in (). The one-sided system of equation and inequalities () can be written as




Recall that S(G,H,p,q)is the set of solutions for ().

Theorem 9Let Q(x)=for some constant vector x=(α,,α)TS. If zSminthen zS(G,H,p,q).

Let x=(α,,α)TS. Suppose Q(z)=and zSmin. This implies that f(z)f(x)=α. Therefore we have, jN, zα. Consequently, zxand (Az)i(Ax)ifor all iM. Since, Q(z)=and zS(G,H,p,q).

Corollary 5If Q(x)=for some constant vector xSthen SminSmin(G,H,p,q).

The statement follows from Theorem .

7. Some solvability concepts of a linear system containing of both equations and inequalities

System of max-separable linear equations and inequalities arise frequently in several branches of Applied Mathematics: for instance in the description of discrete-event dynamic system [4], [1] and machine scheduling [10]. However, choosing unsuitable values for the matrix entries and right-handside vectors may lead to unsolvable systems. Therefore, methods for restoring solvability suggested in the literature could be employed. These methods include modifying the input data [11], [26] or dropping some equations [11]. Another possibility is to replace each entry by an interval of possible values. In doing so, our question will be shifted to asking about weak solvability, strong solvability and control solvability.

Interval mathematics was championed by Moore [27] as a tool for bounding errors in computer programs. The area has now been developed in to a general methodology for investigating numerical uncertainty in several problems. System of interval equations and inequalities in max-algebra have each been studied in the literature. In [26] weak and strong solvability of interval equations were discussed, control sovability, weak control solvability and universal solvability have been dealt with in [28]. In [29] a system of linear inequality with interval coefficients was discussed. In this section we consider a system consisting of interval linear equations and inequalities and present solvability concepts for such system.

An algebraic structure (B,,)with two binary operations and is called max-plus algebra if


for any a,b.

Let m,n,rbe given positive integers and a, we use throughout the paper the notation M={1,2,...,m},N={1,2,...,n},R={1,2,...,r}and a-1=-a. The set of all m×n, r×nmatrices over Bis denoted by B(m,n)and B(r,n)respectively. The set of all n-dimensional vectors is denoted by B(n). Then for each matrix AB(n,m)and vector xB(n)the product Axis define as


For a given matrix interval 𝐀=[A̲,A¯]with A̲,A¯B(k,n),A̲A¯and given vector interval 𝐛=[b̲,b¯]with b̲,b¯B(n),b̲b¯the notation


represents an interval system of linear max-separable equations of the form


Similarly, for a given matrix interval 𝐂=[A̲,A¯]with C̲,C¯B(r,n),C̲C¯and given vector interval 𝐝=[d̲,d¯]with d̲,d¯B(n),b̲b¯the notation


represents an interval system of linear max-separable inequalities of the form


Interval system of linear max-separable equations and inequalities have each been studied in the literature, for more information the reader is reffered to . The following notation


represents an interval system of linear max-separable equations and inequalities of the form


where A𝐀,C𝐂,b𝐛and d𝐝.

The aim of this section is to consider a system consisting of max-separable linear equations and inequalities and presents some solvability conditions of such system. Note that it is possible to convert equations to inequalities and conversely, but this would result in an increase in the number of equations and inequalities or an increase in the number of unknowns thus increasing the computational complexity when testing the solvability conditions. Each system of the form () is said to be a subsystem of (). An interval system () has constant matrices if A̲=A¯and C̲=C¯. Similarly, an interval system has constant right hand side if b̲=b¯and d̲=d¯. In what follows we will consider A(k,n)and C(r,n).

7.1. Weak solvability

Definition 8A vector yis a weak solution to an interval system () if there exists A𝐀,C𝐂,b𝐛and d𝐝such that


Theorem 10A vector xnis a weak solution of () if and only if




Let i={1,...,m}be an arbitrary chosen index and x=(x1,x2,...,xn)Tnfixed. If A𝐀then (Ax)iis isotone and we have


Hence, xis a weak solution if and only if


Similarly, if C̲xd¯then xis obviously a weak solution to


That is


Also from () xis a weak solution if and only if


That is


Definition 9An interval system () is weakly solvable if there exists A𝐀,C𝐂,b𝐛and d𝐝such that () is solvable.

Theorem 11An interval system () with constant matrix A=A̲=A¯, C=C̲=C¯is weakly solvable if and only if


The (if) part follows from the definition. Conversely, Let


be solvable subsystem for b[b̲i,b¯i]. Then we have


7.2. Strong solvability

Definition 10A vector xis a strong solution to an interval system () if for each A𝐀,C𝐂and each b𝐛,d𝐝there is an xsuch that () holds.

Theorem 12a vector xis a strong solution to () if and only if it is a solution to




If xis a strong solution of (), it obviously satisfies (). Conversely, suppose xsatisfies () and let A˜𝐀,C˜𝐂,b˜𝐛,d˜𝐝such that A˜xb˜and C˜x>d˜. Then i(1,2,...,m)such that either (A˜x)i<b˜ior (A˜x)i>b˜iand (C˜x)i>d˜i. Therefore, (A̲x)i<(A˜x)i<bi, (A¯x)i(A˜x)i>biand (C¯x)i>(C˜x)i>diand the theorem statement follows.


The author is grateful to the Kano University of Science and Technology, Wudil for paying the publication fee.

© 2012 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Abdulhadi Aminu (July 11th 2012). A Linear System of Both Equations and Inequalities in Max-Algebra, Linear Algebra - Theorems and Applications, Hassan Abid Yasser, IntechOpen, DOI: 10.5772/48195. Available from:

chapter statistics

2289total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Efficient Model Transition in Adaptive Multi-Resolution Modeling of Biopolymers

By Mohammad Poursina, Imad M. Khan and Kurt S. Anderson

Related Book

First chapter

Cramer’s Rules for the System of Two-Sided Matrix Equations and of Its Special Cases

By Ivan I. Kyrchei

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us