Minimax Algebra

ISBN-13: 9783540091134 / Angielski / Miękka / 1979 / 258 str.

R. A. Cuninghame-Green

Opis

A number of different problems of interest to the operational researcher and the mathematical economist - for example, certain problems of optimization on graphs and networks, of machine-scheduling, of convex analysis and of approx imation theory - can be formulated in a convenient way using the algebraic structure (R, $, @) where we may think of R as the (extended) real-number system with the binary combining operations x$y, x(r)y defined to be max(x, y), (x+y) respectively. The use of this algebraic structure gives these problems the character of problems of linear algebra, or linear operator theory. This fact hB.s been independently discovered by a number of people working in various fields and in different notations, and the starting-point for the present Lecture Notes was the writer's persuasion that the time had arrived to present a unified account of the algebra of linear transformations of spaces of n-tuples over (R, $, (r)), to demonstrate its relevance to operational research and to give solutions to the standard linear-algebraic problems which arise - e.g. the solution of linear equations exactly or approximately, the eigenvector eigenvalue problem andso on.Some of this material contains results of hitherto unpublished research carried out by the writer during the years 1970-1

Spis treści

1 Motivation.- 1–1 Introduction.- 1–2 Miscellaneous Examples.- 1–2.1 Schedule Algebra.- 1–2.2 Shortest Path Problems.- 1–2.3 The Conjugate.- 1–2.4 Activity Networks.- 1–2.5 The Assignment Problem.- 1–2.6 The Dual Transportation Problem.- 1–2.7 Boolean Matrices.- 1–2.8 The Stochastic Case.- 1–3 Conclusion: Our Present Aim.- 2 The Initial Axioms.- 2–1 Some Logical Geography.- 2–2 Commutative Bands.- 2–3 Isotone Functions.- 2–4 Belts.- 2–5 Belt Homomorphisms.- 2–6 Types of Belt.- 2–7 Dual Addition.- 2–8 Duality for Belts.- 2–9 Some Specific Cases.- 3 Opening and Closing.- 3–1 The Operations ??,???,??,???.- 3–2 The Principle of Closing.- 3–3 The Principle of Opening.- 4 The Principal Interpretation.- 4–1 Blogs.- 4–2 The Principal Interpretation.- 4–3 The 3-element Blog ?.- 4–4 Further Properties of Blogs.- 5 The Spaces En and ?mn.- 5–1 Band-Spaces.- 5–2 Two-Sided Spaces.- 5–3 Function Spaces.- 5–4 Matrix Algebra.- 5–5 The Identity Matrix.- 5–6 Matrix Transformations.- 5–7 Further Notions.- 6 Duality for Matrices.- 6–1 The Dual Operations.- 6–2 Some Matrix Inequalities.- 7 Conjugacy.- 7–1 Conjugacy for Belts.- 7–2 Conjugacy for Matrices.- 7–3 Two Examples.- 8 AA* Relations.- 8–1 Pre-residuation.- 8–2 Alternating AA* Products.- 8–3 Modified AA* Products.- 8–4 Some Bijections.- 8–5 A Worked Example.- 9 Some Schedule Algebra.- 9–1 Feasibility and Compatibility.- 9–2 The Float.- 9–3 A Worked Example.- 10 Residuation and Representation.- 10–1 Some Residuation Theory.- 10–2 Residuomorphisms.- 10–3 Representation Theorems.- 10–4 Representation for Matrices.- 10–5 Analogy with Hilbert Space.- 11 Trisections.- 11–1 The Demands of Reality.- 11–2 Trisections.- 11–3 Convex Subgroups.- 11–4 The Linear Case.- 11–5 Two Examples.- 12 ? ø — Astic Matrices.- 12–1 ?ø — Asticity.- 12–2 The Generalised Question 2.- 13 / — Existence.- 13–1 / — Existence Defined.- 13–2 Compatible Trisections.- 13–3 Dually ? ø — astic Matrices.- 13–4 / — Defined Residuomorphisms.- 13–5 Omn As Operators.- 13–6 Some Questions Answered.- 14 The Equation A ? x = b Over a Bldg.- 14–1 Some Preliminaries.- 14–2 The Principal Solution.- 14–3 The Boolean Case.- 15 Linear Equations over a Linear Bldg.- 15–1 All Solutions of (14–3).- 15–2 Proving the Procedure.- 15–3 Existence and Uniqueness.- 15–4 A Linear Programming Criterion.- 15–5 Left-Right Variants.- 16 Linear Dependence.- 16–1 Linear Dependence Over El.- 16–2 The A Test.- 16–3 Some Dimensional Anomalies.- 16–4 Strong Linear Independence.- 17 Rank of Matrices.- 17–1 Regular Matrices.- 17–2 Matrix Rank Over A Linear Blog.- 17–3 Existence of Rank.- 18 Seminorms on En.- 18–1 Column-Spaces.- 18–2 Seminorms.- 18–3 Spaces of Bounded Seminorm.- 19 Some Matrix Spaces.- 19–1 Matrix Seminorms.- 19–2 Matrix Spaces.- 19–3 The Role of Conjugacy.- 20 The Zero-Lateness Problem.- 20–1 The Principal Solution.- 20–2 Case of Equality.- 20–3 Critical Paths.- 21 Projections.- 21–1 Congruence Classes.- 21–2 Operations in Rang A.- 21–3 Projection Matrices.- 22 Definite and Metric Matrices.- 22–1 Some Graph Theory.- 22–2 Definite Matrices.- 22–3 Metric Matrices.- 22–4 The Shortest Distance Matrix.- 23 Fundamental Eigenvectors.- 23–1 The Eigenproblem.- 23–2 Blocked Matrices.- 23–3 ø-Astic Definite Matrices.- 24 Aspects of the Eigenproblem.- 24–1 The Eigenspace.- 24–2 Directly Similar Matrices.- 24–3 Structure of the Eigenspace.- 25 Solving the Eigenproblem.- 25–1 The Parameter ?(A).- 25–2 Properties of ?(A).- 25–3 Necessary and Sufficient Conditions.- 25–4 The Computational Task.- 25–5 An Extended Example.- 26 Spectral Inequalities.- 26–1 Preliminary Inequalities.- 26–2 Spectral Inequality.- 26–3 The Other Eigenproblems.- 26–4 More Spectral Inequalities.- 26–5 The Principal Interpretation.- 27 The Orbit.- 27–1 Increasing Matrices.- 27–2 The Orbit.- 27–3 The Orbital Matrix.- 27–4 A Practical Case.- 27–5 More General Situations.- 27–6 Permanents.- 28 Standard Matrices.- 28–1 Direct Similarity.- 28–2 Invertible Matrices.- 28–3 Equivalence of Matrices.- 28–4 Equivalence and Rank.- 28–5 Rank of ?.- 29 References and Notations.- 29–1 Previous Publications.- 29–2 Related References.- 29–3 List of Notations.- 29–4 List of Definitions.