PAGE 2
S3qs
PAGE 3
a b a b, a b a b.
PAGE 4
Ax Ax Ax
PAGE 5
A
PAGE 8
a b a b A set K endowed with two binary operations and is a monoidfield if a,b,c EK, a (b (a b) (a c), (a (a c), say that the monoidfield is a a a, a K
PAGE 9
The symbol denotes the set with and as the two binary operations and respectively. The algebraic st1"lLcture satisfies the following properties: ;z z,
PAGE 10
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
PAGE 11
A B C A B.
PAGE 12
n n n. n n n A A (Ai;),
PAGE 13
A= S. O)T.
PAGE 14
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).
PAGE 15
A a n n The system is said to be in canonical form if A, and satisfy
PAGE 16
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
PAGE 17
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)
PAGE 18
Ax, A(Ax Ab Ax, Ab AIe1b Alex, Ab, Ale k Ale k Ab.
PAGE 19
k A linear2
PAGE 20
A AxEB A
PAGE 21
A Ax A B k A
PAGE 22
subsolution Given an n n matrix A and an nvector with entries in the greatest subsolution of ezists and is given by Proof: Ai;X; bi, bi Ai;),
PAGE 23
A nxn A A A
PAGE 24
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).
PAGE 25
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.
PAGE 26
n n n. ,n.
PAGE 27
A
PAGE 28
A A22 A33 A 13 A 23 A12 13 A13
PAGE 29
3]T. Axt, t (t A A. Axo AX1 A"\xo ,n. p ,n.
PAGE 30
A A
PAGE 31
n n n = n n
PAGE 32
n=10 n=20 n=30 n=40 n=50 A Ax A a22 a23 a32 a33
PAGE 33
Ax a21 a22 a23 a32 a33 Hn n2 (n Hnz A Hn
PAGE 34
Hn n c Hnz 1JT. b n b b n n n n Hn Hn Hn Hn Hn
PAGE 35
n n. An elementary product from A is a product of n
PAGE 36
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
PAGE 37
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
PAGE 38
A (Ai;) Ai; A 2 zIAA31 A32 A33 A34 A41 A42 zI A,
PAGE 39
A
PAGE 40
y y
PAGE 41
Let the positive determinant and PA the negative determinant of A Then the following identity holds: p1(A) =PA(A). A A
PAGE 42
Synchronization and Linearity. Ars Combinatoria
