a b a b, a b a b.
Ax Ax Ax
a b a b A set K endowed with two binary operations and is a monoid-field if a,b,c EK, a (b (a b) (a c), (a (a c), say that the monoid-field is a a a, a K
The symbol denotes the set with and as the two binary operations and respectively. The algebraic st1"lLcture satisfies the following properties: ;z z,
for all The algebraic structure is an idempotent commutative monoid field (There is no inverse under with and e a, b a) a =IThe set endowed with the operations and as and and with the convention that is denoted n n
A B C A B.
n n n. n n n A A (Ai;),
A= S. O)T.
4 n), AXl O)T AX2 (3,2,3,2,3,3,3,3,2,2,3,2,2,2,2,2,2l AXa 2)T AX4 (5,4,5,4,4,4,4,5,4,4,4,4,4,4,4,4,3)T Axs 4)T Ax6= (6,6,6,6,6,6,6,6,6,5,6,6,6,5,6,5,5)T Ax7 7,7,7,7,6,6,7,7,6,7,6,6,6)T Axs 7,6)T. 4 2 ) 4 4 ) 4 AX9 = A(6X2) 6Ax2 k 4 7).
A a n n The system is said to be in canonical form if A, and satisfy
Ax The precedence graph of a square n n matriz A with entries in is a weighted digraph with n nodes and an arc if Ai; =Iin which case the weight this arc receives the numerical value of Ai;. The precedence graph is denoted G(A). A
A A If there are only circuits of nonpositive weight in G(A), there is a solution to which is given by where An An+1 Moreover, if the circuit weights are all negative, the solution 'ts umque. a b a b, Proof: G(A)
Ax, A(Ax Ab Ax, Ab AIe-1b Alex, Ab, Ale k Ale k Ab.
k A linear2
A AxEB A
A Ax A B k A
subsolution Given an n n matrix A and an n-vector with entries in the greatest subsolution of ezists and is given by Proof: Ai;X; bi, -bi Ai;),
A nxn A A A
An An+l A.; ,ilc) The mean weight of a path is defined as the sum of the weights of the individual arcs of this path, divided by the length of this path. If the path is denoted p, then the mean weight equals If such a path is a circuit one talks about the mean weight of the circuit, simply the cycle mean. If G(A) is strongly connected, there exists one and only one eigenvalue (but possibly several eigenvectors). This eigenvalue is equal to the maximum cycle mean of the graph: P where p ranges over the set of circuits of G(A).
Proof: B -AA, ma.x !p!w/!p!l. G(B) B B+ BB B+ k k k Btk. Bk B. B -AA, B+ BB B B+, Bt BZ BBZ Bt BZ -AABZ BZ ABZ ABZ BZ Bt A A2. AV2 t n, A2. =IA2.
n n n. ,n.
A A22 A33 A 13 A 23 A12 13 A13
-3]T. Axt, t (t A A. Axo AX1 A"\xo ,n. p ,n.
n n n = n n
n=10 n=20 n=30 n=40 n=50 A Ax A a22 a23 a32 a33
Ax a21 a22 a23 a32 a33 Hn n2 (n Hnz A Hn
Hn n c Hnz 1JT. b n b b n n n n Hn Hn Hn Hn Hn
n n. An elementary product from A is a product of n
entries of exactly one from each row and each column. positive elementary product is an elementary product Alil A2i2 Ani.. where the permutation (it,j2, ... ,jn) is even. A negative elementary product is an elementary product Alil A2i:a Ani .. where the permutation j2, ,jn) is odd. The characteristic polynomial of is defined by PA(X) det(xI where I is the identity matrix. PA (x) is the sum of all positive and negative elementary products from xl The characteristic equation is given by p1(x) PA(x), where the positive determinant p1(x) is the sum of all positive terms from PA(X) and the negative determinant PA x) the sum of all negative terms from PA (x). A (Aii) Aii [ X An xl A -A21 -A3l -A13] -A23 x -A33
A A33), (-A12)( -A23)( -A3l), (-A13)( -A21)( -A32). A -A23)( -A32), -A12)( A33), A22)( -A3l). (-A12)( -A23)( -A3l) (-A13)( -A21)( -A32) -A23)( -A32) -A12)( A33) A22)( -A3l) A22 +(AUA22 AUA33 AU A22A33, -A13 A21A32 AU A23A32' A12A21A33, A13A22A3l p1 (AUA22 AUA33 ffiAuA23A32 A12A21A33 A13A22A 3h
A (Ai;) Ai; A 2 zI-A-A31 -A32 A33 -A34 -A41 -A42 zI A,
Let the positive determinant and PA the negative determinant of A Then the following identity holds: p1(A) =PA(A). A A
Synchronization and Linearity. Ars Combinatoria