C. R. Acad. Sci. Paris, t. 311, Série II, p. 443-448, 1990 443
C. R., 1990,2eSemestre(T. 311) SérieIl - 34
Automatique/Automation
L'algèbre (max, +) et sa symétrisation ou l'algèbre
des équilibres
Max PLUSe)
Résumé- L'algèbre(max, +) est un outil utileen RechercheOpérationnelle- la recherched'uncheminde longueurmaximaledans un graphe par exemple
—et en Automatique —l'étude dessystèmesà événementsdiscrets.Noussymétrisonsicicettestructurede façonà obtenirdesconditionsnécessaireset suffisantesd'existenceet d'unicité d'une solution d'un systèmelinéairedans cettealgèbre.
(max, +) algebra and its symmetrization or the algebra of balances
Abstract—The(max, +) algebrais a usefultool in OperationsResearch—the researchof thepathof maximumlengthin a graphfor example- and in AutomaticControl-thestudyof discrete eventsystems. The symmetrizationof this structure leads to a necessaryand sufficientconditionfor theexistenceand uniquenessof a solutionto any linearsystemin thisalgebra.
Abridged English Version — 1.1. (max, +) ALGEBRA.— We consider the set IRU {- co }
endowed with the two operations "max" and + denoted respectively by (1) and ~0. For
example x (Dy EÐz stands for max (x+y, z); the sign @ is often omitted.
EÐ is commutative, associative, has a null element denoted E equal to —GO, idempotent
(a a =a), but a 8 does not have an inverse.
(x) is distributive with respect to EÐ
a (b c) = a + max(b, c) =max (a+ b, a +c) = (a b) (a (x) c),
and defines a group on ~Rwith the identity element 0 denoted bye, and is absorbing, i. e.
(g)a = .
We call this structure max.
1. 2. LINEARCLOSUREOF max.— The equation x (Db=F, does not have a solution for
b . The following remark shows that it is not possible to obtain a symmetrization of maxin the classical sense.
Fundamental remark. —Every idempotent group d with null element is reduced to this
element.
Indeed, given a 6 A, b its additive inverse, we have =a EÐb and thus
a = a (BE= a G)(a (Db) = (a (Da) E) b = a (Db = F-.
A construction analogous to the one used to obtain from exists for max yielding a
structure which is linearly closed, i. e. every non-degenerate linear equation has a uniquesolution. For that let us consider the equivalence relation on IR^ax1
(x',x") & (y', y") <=>x' EÐy" = y' EÐx" for x':Ax" and y' =I-y",
x' = y' =x" = y" otherwise.
2max/Rhas three kinds of equivalence classes:
x' = (x', x"), x' > x" of canonical representative (x', E), called positive,
x" = (x', x"), x'<x" of canonical representative (, x"), called negative,
~x'=(.x, x') called balanced.
Note présentée par Alain BENSOUSSAN.
0764-4450/90/03110443$ 2.00 6 Académiedes Sciences
444 C. R. Acad. Sci. Paris, t. 311, Série II, p. 443-448, 1990
We denote also by 8 the class of (— , - oo). The set of positive classes (resp. negative)
(resp. balanced without ) are denoted IR:, [~*], [~*]; "*" is dropped when we add the
element c to the set: IREÐ= IR: U { }.The equivalence relation R is compatible with:— the vector addition on R^ax,— the multiplication x ®y= (x'y'© x"y", x' y" EÐx"y') with identity element (e, ),— the operator e defined by (x', x")
=(x", x') [with the usual abuse of notation we
write a b instead of a (D(E)b)].The quotient algebraic structure R^,ax/^2 is denoted by A; we also use ~ for lRœU Re.
For all a in l&, a e a belongs to , but it is in general different from . Note that we
have not really realized a symmetrization of max; we have realized the proposition: "with
each element we can associate another element such that the sum of the two is balanced".
We have the following theorem showing the interest of the notions introduced above.
THEOREM. —Vac-A*, Vbc-A, 3xEIR unique, such that: axb '; this solution is
x= b/a.
Coming back to R'a,,, this means —for a and b in a class of R —there exists a unique class
which is solution of the equation:
ax' (Ba" x" EÐb'= a" x' EÐa x" EÐb".
1. 3. APPLICATIONTOLINEARSYSTEMS.— We define the determinant of a matrix A by the
usual formula:
where n is the size of A, (J a permutation of {1, 2, ., n 1, and sgn () =e or e depending
on the parity of c.
We are interested in linear systems Ax= b. We have:
THEOREM.- SupposeA~ n and det(A)c- 9* then there exists a unique solution xeR" to
the linear system Ax b (~)n given by the formula:
x = A~b/det (A).
This is the starting point for a theory of linear systems in R. The main difference with
the classical linear theory is the conditionA#b ~n which corresponds to the loss of unique-
ness when it is not fulfilled.
Given a linear system in max, Ax=b, if we solve AxE)b c- (R*)' in n and obtain a
unique positive solution we have the solution to A x = b as well. Otherwise A x = b does not
have a unique solution. In this latter case we can affirm the existence of a unique solution
to another problem of the form A'x' @ b= A"x', "symmetrical" to the original problem.
1. L'ALGÈBRE(max, +).— On considère l'ensemble U {
—oo } muni de deux opéra-
tions « max » et « + » notées respectivement E9 et @. x®y®z signifie max (x +y, z).
Le signe (x) est souvent omis comme à l'accoutumée.
E9 est commutative, associative, admet un élément neutre noté égal à - , idempo-
tente (a E9a =a), mais a*F, n'admet pas de symétrique.
() est distributive par rapport à E9
a (S)(b E9c) = a + max (b, c) = max (a+ b, a+ c)= (a @ b) E9(a c),
C. R. Acad. Sci. Paris, t. 311, Série II, p. 443-448, 1990 445
définit une loi de groupe sur M d'élément neutre 0 noté e, et e est absorbant EQ9a= .
On appelle Rmaxcette structure.
Dans cette algèbre, on sait résoudre l'équation linéaire vectorielle :
x = Ax b,
où x et b appartiennent à ~nmaxet A est une matrice (n, n) à coefficients dans Rmax([3],
[6], [9]). On ne sait pas résoudre en général les équations :
A'x b' = A"x EBb".
Dans [1] et [3] on donne cependant la plus grande sous-solution à l'équation :
Ax=b.
Le propos de cette Note est de donner une réponse claire à ce genre de problèmes,
essentiels pour l'étude postérieure des systèmes dynamiques dans max. Pour cela, on est
amené à introduire une nouvelle structure algébrique et à résoudre les systèmes d'équations
linéaires dans cette nouvelle structure.
Le renouveau d'intérêt pour cette algèbre max provient de sa parfaite adéquation à
l'évaluation de performance de systèmes parallèles synchronisés, plus précisément les
graphes d'événements temporisés [2].
2. FERMETURELINÉAIREDE max.—
L'équation x b =E n'a pas de solution pour b*F,.
D'autre part la remarque suivante montre qu'il n'est pas possible de symétriser max au
sens habituel.
Remarque fondamentale.— Tout groupe idempotent d d'élément neutre E est réduit à
cet élément.
Démonstration. — Soit aestf, b son symétrique, on a =a EBb et donc
a =a EB =a EB(a EBb)=(a EBa) b = a EBb=.
Une construction analogue à la symétrisation qui permet de passer de N à confère au
nouvel ensemble obtenu une structure linéairement close c'est-à-dire telle que toute
équation non dégénérée admette une solution unique.Pour cela on considère sur ~2maxla relation d'équivalence :
(x', x")!!Il (y', y") o x' Et;)y"=y' Et;)X" sur x' x" et /#/' ,
x' = y' = x"=y" ailleurs.
"^max/^ possède alors trois types de classes d'équivalence :
x' = (x' x"), x'>x" de représentant canonique (x', ), dite positive,
x" = (x', x"), x'<x" de représentant canonique (, x"), dite négative,
x' = (x', x') dite équilibrée.
On note encore E la classe de (- , —).
L'ensemble des classes positives [resp. négatives] [resp. équilibrées amputées de ] seront
notées RB, [~], [IR'J (on élèvera l'étoile, par exemple , lorsqu'on rajoute à l'ensemble
correspondant l'élément ).
On constate que la relation d'équivalence 01 est compatible avec:— l'addition vectorielle de ~max,— la multiplication x y =(x' y' œ x" y", x' y" œ x"y') d'élément neutre (e, ),-
l'opérateur 8 défini par 8 (x', x") = (x", x') (on fera les mêmes abus de notation
qu'en algèbre classique en notant a 8 b l'expression a (D( b) etc.).
446 C. R. Acad. Sci. Paris, t. 311, Série II, p. 443-448, 1990
La structure algébrique quotient sera notée l&. On utilisera aussi pour lRœU1Re.
On constate alors que max et lRœ[resp. IR.]sont isomorphes. On verra les éléments de R"
comme des éléments singuliers. Tout élément en dehors de ces éléments singuliers est
inversible.
Pour tout a appartenant à fê, a a appartient à , mais est en général =FE.On n'a
donc pas réalisé une symétrisation de max. On a réalisé la proposition: « à chaqueélément on peut associer un autre élément tel que la somme des deux soit équilibrée ».
On note A pour « * » (resp. fi pour « 9* »), resp. fif pour IR)que l'on lit équilibré
(resp. déséquilibré), [resp. déséquilibré fort (l'adjectif fort ne prendra son sens que dans
le cas vectoriel au paragraphe suivant)]. Ces équilibres jouent le rôle des équationshabituellement. On a en particulier :
aA et b => a b et ab et a b
aA et cfi => a @c â et aj c
La relation entre a et b : « a b réalise un équilibre» n'est pas transitive. Les propriétéssuivantes en tiendront lieu.
THÉORÈME2.1 (fondamental des équilibres).— 1.a e b , a et b fi =>a =b,
2. a©bAet b©cAet b fi=> a© c A,3. a ©b A, cb ©dA, bfi => ca ©dA.
On s'intéresse maintenant à réaliser des équilibres au moyen de variables appartenantà IRc'est-à-dire chercher x 4f tel que g (x). Cela correspond à la résolution des équations
dans la terminologie habituelle. On a alors le théorème suivant qui fait tout l'intérêt de
l'introduction de ces notions.
THÉORÈME2.2. — V~a, Vbfif, 3xfif unique: ax©b A, cette solution vaut x = e bja.
Remarque 1. — En revenant aux couples, cela signifie qu'il y a une classe unique de IR
pour des données appartenant à une classe de ift, solution de l'équation :
a' x' œ a" x" œ b'= a" x' œ a' x" œ b".
La démonstration est immédiate en simplifiant l'équation. Elle se ramène à une discussion
selon les signes des représentants.
Remarque 2. — Dans les constructions usuelles, on peut ramener les équations a= b à
a - b = 0, ici non, mais celà est inutile pour faire la clôture linéaire d'un ensemble.
Remarque 3. - On peut poser une équation linéaire à données plus générales dans ifô.
On peut alors chercher une solution dans IR ou dans à. On vérifie alors que lorsque
l'une des données est dans R* on perd l'unicité. Bien qu'un calcul utile puisse être mené
pour gérer ces non-unicités, par souci de simplicité nous ne le ferons pas ici.
3. APPLICATIONAUXSYSTÈMESLINÉAIRES.- Les notions d'équilibre s'étendent au cas
vectoriel composante par composante :— A signifie: toutes les composantes sont équilibrées,—
fi signifie: il existe une composante déséquilibrée,—
~fifsignifie: toutes les composantes efê.
On définit le déterminant d'une matrice A par la formule habituelle :
où n désigne l'ordre de la matrice, une permutation de {1, 2, ., n1, sgn() = eou 0 e selon la parité de cr.
C. R. Acad. Sci. Paris, t. 311, Série II, p. 443-448, 1990 447
THÉORÈME3. 1. -det(A) 3x 4f, x * F, tel queAx A.
Démonstration. - Gondran-Minoux [5] dans IRmax,Gaubert [4] dans (R.
On trouvera des discussions sur diverses notions de rang dans ces algèbres dans
Wagneur [10].
On s'intéresse maintenant aux systèmes linéaires Ax = b.
THÉORÈME3.2
AA# det (A)I , A*A det (A) I , diag (A# A) = diag (AA#)= det (A) I
où l'on a noté A* la transposée de la matrice des cofacteurs de A.
Démonstration. —Adapter les résultats de Reutenauer-Straubing [8] ou la démonstra-
tion habituelle.
THÉORÈME3.3 (« de Cramer »).— Sous l'hypothèse, A#bIf. f' det(A)If., il existe une
solution unique x If.f au système linéaire A x e b A donnée par la formule
x = A#b/det (A).
Démonstration. — Olsder-Roos [7] dans des cas particuliers de max, Gaubert [4] dans
le cas général.
Remarque 4. - On peut à partir de là faire la théorie des systèmes linéaires. Une
différence avec la théorie habituelle est l'hypothèse A#b If.f qui correspond à la perted'unicité déjà observée, dans l'équation scalaire, lorsque bEIR..
Remarque 5. - Étant donné un système linéaire dans max du type Ax =b, la résolution
de Ax b dans 9 puis la constatation du caractère unique et positif de la solution
nous donne l'existence et l'unicité d'une solution au problème initial, la constatation de
l'unicité et du caractère négatif d'une composante nous prouve la non-existence. Dans ce
dernier cas on peut de plus affirmer l'existence d'une solution unique à un autre problème
du type A'x' EBb = A" x', « symétrique » du proposé.
4. EXEMPLENUMÉRIQUE.— Considérons le système à résoudre
ce qui signifie que l'on cherche les deux vecteurs: f x'
etf x"
tels queL/J L/J
~(i) r 2 nmje en r jc"-! r e_i r2 nr^'n^rs £ ir*nœ
Ye~(1) 1 e F, 1 F, e Il e e F, Il F- e y, , _8_
où l'on a noté e pour 0 (élément neutre de la multiplication 0) ou 0 classe de (0, ).On trouve
det (A) = 2
La solution est alors la classe de x" = (— 1), y' = e, x' =, y"= . On vérifie en effet que
l'on obtient111
à gauche et à droite de (1).e
448 C. R. Acad. Sci. Paris, t. 311, Série II, p. 443-448, 1990
Bien que l'objet de cette Note soit l'introduction de cette nouvelle algèbre et non pas
ses implications algorithmiques, signalons que le calcul du déterminant d'une matrice
de max se ramène à la résolution d'un problème d'affectation. Et donc les formules de
Cramer ont la complexité de la résolution de n problèmes d'affectation. Enfin, on peut
adapter l'algorithme de Gauss-Seidel à cette nouvelle situation. On a alors convergence
en un nombre fini d'itérations.
On trouvera d'autres développements de l'algèbre max ainsi que des applications
dans ([3], [9], [2]) et leurs références.
(1) Nom collectifpour un groupe de travail sur l'algèbre(max, +) à l'I.N.R.I.A., Projet META2,Marianne
Akian, Guy Cohen, StéphaneGaubert, Ramine Nikoukhah, Jean-PierreQuadrat.
Note remisele 25 avril 1990,acceptéele 21juin 1990.
RÉFÉRENCESBIBLIOGRAPHIQUES
[1] T. S. BLYTH,Matrices over ordered algabraic structures, Journal London Math. Soc., n° 39, 1964,
p. 427-432.
[2] G. COHEN,P. MOLLER,J.-P. QUADRATet M. VIOT,Algebraictools for the performanceevaluationof
discrèteevent systems,I.E.E.E. Proceedings,Specialissueon discrèteeventsystems,77,n° 1,janvier 1989.
[3] R. CUNINGHAME-GREEN,Minimax Algebra, Springer-Verlag,Lecture Notes in Economicsand Math.
Systems,n° 166,1979.
[4] S. GAUBERT,Thèse,E.N.S.M.P.(à paraître).
[5] M. GONDRANet M. MINOUX,L'indépendancelinéairedans les dioïdes, E.D.F. Bulletinde la Dir. des
Étudeset Rech.,SérieC, Math. et Inf., n° 1, 1978.
[6] M. GONDRANet M. MINOUX,Grapheset Algorithmes,Eyrolles,Paris, 1979.
[7] G. J. OLSDERet C. Ross, Cramer and CayleyHamilton Theoremsin the Max Algebra, Linear Algebra
andits Applications,n° 101,1988,p. 87-108.
[8] C. REUTENAUERet H. STRAUBING,Inversion of matrices over a commutative semi ring, Journal ofAlgebra,n° 88, 1984,p. 350-360.
[9] U. ZIMMERMAN,Linear and combinatorialoptimizationin ordered algebraicstructures,North Holland
1981.
[10]E. WAGNEUR,Moduloïdsandpseudomodules,Rapport Interne HEC Montréal, mai 1989.
I.N.R.I.A.,Domainede Voluceau,Rocquencourt,78153Le ChesnayCedex.