61 research outputs found
Simple image set of (max,+) linear mappings
No full textAbstractLet us denote a⊕b=max(a,b) and a⊗b=a+b for a,b∈R and extend this pair of operations to matrices and vectors in the same way as in conventional linear algebra, that is if A=(aij), B=(bij), C=(cij) are real matrices or vectors of compatible sizes then C=A⊗B if cij=∑k⊕aik⊗bkj for all i,j.If A is a real n×n matrix then the mapping x↦A⊗x from Rn to Rn(n>1) is neither surjective nor injective. However, for some of such mappings (called strongly regular) there is a nonempty subset (called the simple image set) of the range, each element of which has a unique pre-image. We present a description of simple image sets, from which criteria for strong regularity follow. We also prove that the closure of the simple image set of a strongly regular mapping f is the image of the kth iterate of f after normalization for any k⩾n−1 or, equivalently, the set of fixed points of f after normalization
Simple image set of (max,+) linear mappings
No full textAbstract Let us denote a ⊕ b = max(a; b) and a ⊗ b = a + b for a; b ∈ R and extend this pair of operations to matrices and vectors in the same way as in conventional linear algebra, that is if A = (aij), B = (bij), C = (cij) are real matrices or vectors of compatible sizes then If A is a real n × n matrix then the mapping x → A ⊗ x from R n to R n (n ¿ 1) is neither surjective nor injective. However, for some of such mappings (called strongly regular) there is a nonempty subset (called the simple image set) of the range, each element of which has a unique pre-image. We present a description of simple image sets, from which criteria for strong regularity follow. We also prove that the closure of the simple image set of a strongly regular mapping f is the image of the kth iterate of f after normalization for any k¿n − 1 or, equivalently, the set of ÿxed points of f after normalization.
On integer images of max-plus linear mappings
No full textLet us extend the pair of operations (max,+) over real numbers to matrices in the same way as in conventional linear algebra.We study integer images of max-plus linear mappings. The question whether Ax (in the max-plus algebra) is an integer vector for at least one x has been studied for some time but polynomial solution methods seem to exist only in special cases. In the terminology of combinatorial matrix theory this question reads: is it possible to add constants to the columns of a given matrix so that all row maxima are integer? This problem has been motivated by attempts to solve a class of job-scheduling problems.We present two polynomially solvable special cases aiming to move closer to a polynomial solution method in the general case.<br/
Finding a bounded mixed-integer solution to a system of dual network inequalities
No full textWe show that using max-algebraic techniques it is possible to generate the set of all solutions to a system of inequalities x(i) - x(j) >= b(ij), i,j = 1,..., n using n generators. This efficient description enables us to develop a pseudopolynomial algorithm which either finds a bounded mixed-integer solution, or decides that no such solution exists. (c) 2008 Elsevier B.V. All rights reserved
School of Mathematics Pre Print Series, 2003/24:Max-algebraic eigenvalues: the reducible case
No full text- …
