Citation
Eigenvalues and eigenvectors in the max-plus algebra

Material Information

Title:
Eigenvalues and eigenvectors in the max-plus algebra
Creator:
Chung, Misoo
Publication Date:
Language:
English
Physical Description:
vii, 35 leaves : ; 29 cm

Subjects

Subjects / Keywords:
Eigenvalues ( lcsh )
Eigenvectors ( lcsh )
Eigenvalues ( fast )
Eigenvectors ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaf 35).
General Note:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Applied Mathematics.
Statement of Responsibility:
by Misoo Chung.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
34233942 ( OCLC )
ocm34233942
Classification:
LD1190.L622 1995m .C48 ( lcc )

Downloads

This item is only available as the following downloads:


Full Text

PAGE 2

S-3-qs

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 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

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 AIe-1b 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 n-vector 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 zI-A-A31 -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