Page 1 Next

Displaying 1 – 20 of 32

Showing per page

A bound for the rank-one transient of inhomogeneous matrix products in special case

Arthur Kennedy-Cochran-Patrick, Sergeĭ Sergeev, Štefan Berežný (2019)

Kybernetika

We consider inhomogeneous matrix products over max-plus algebra, where the matrices in the product satisfy certain assumptions under which the matrix products of sufficient length are rank-one, as it was shown in [6] (Shue, Anderson, Dey 1998). We establish a bound on the transient after which any product of matrices whose length exceeds that bound becomes rank-one.

A note on resolving the inconsistency of one-sided max-plus linear equations

Pingke Li (2019)

Kybernetika

When a system of one-sided max-plus linear equations is inconsistent, its right-hand side vector may be slightly modified to reach a consistent one. It is handled in this note by minimizing the sum of absolute deviations in the right-hand side vector. It turns out that this problem may be reformulated as a mixed integer linear programming problem. Although solving such a problem requires much computational effort, it may propose a solution that just modifies few elements of the right-hand side vector,...

An idempotent algorithm for a class of network-disruption games

William M. McEneaney, Amit Pandey (2016)

Kybernetika

A game is considered where the communication network of the first player is explicitly modelled. The second player may induce delays in this network, while the first player may counteract such actions. Costs are modelled through expectations over idempotent probability measures. The idempotent probabilities are conditioned by observational data, the arrival of which may have been delayed along the communication network. This induces a game where the state space consists of the network delays. Even...

An iterative algorithm for computing the cycle mean of a Toeplitz matrix in special form

Peter Szabó (2013)

Kybernetika

The paper presents an iterative algorithm for computing the maximum cycle mean (or eigenvalue) of n × n triangular Toeplitz matrix in max-plus algebra. The problem is solved by an iterative algorithm which is applied to special cycles. These cycles of triangular Toeplitz matrices are characterized by sub-partitions of n - 1 .

An iterative algorithm for testing solvability of max-min interval systems

Helena Myšková (2012)

Kybernetika

This paper is dealing with solvability of interval systems of linear equations in max-min algebra. Max-min algebra is the algebraic structure in which classical addition and multiplication are replaced by and , where a b = max { a , b } , a b = min { a , b } . The notation 𝔸 x = 𝕓 represents an interval system of linear equations, where 𝔸 = [ A ̲ , A ¯ ] and 𝕓 = [ b ̲ , b ¯ ] are given interval matrix and interval vector, respectively. We can define several types of solvability of interval systems. In this paper, we define the T4 and T5 solvability and give necessary and...

Characterizing matrices with 𝐗 -simple image eigenspace in max-min semiring

Ján Plavka, Sergeĭ Sergeev (2016)

Kybernetika

A matrix A is said to have 𝐗 -simple image eigenspace if any eigenvector x belonging to the interval 𝐗 = { x : x ̲ x x ¯ } is the unique solution of the system A y = x in 𝐗 . The main result of this paper is a combinatorial characterization of such matrices in the linear algebra over max-min (fuzzy) semiring. The characterized property is related to and motivated by the general development of tropical linear algebra and interval analysis, as well as the notions of simple image set and weak robustness (or weak stability) that...

Complete solution of tropical vector inequalities using matrix sparsification

Nikolai Krivulin (2020)

Applications of Mathematics

We examine the problem of finding all solutions of two-sided vector inequalities given in the tropical algebra setting, where the unknown vector multiplied by known matrices appears on both sides of the inequality. We offer a solution that uses sparse matrices to simplify the problem and to construct a family of solution sets, each defined by a sparse matrix obtained from one of the given matrices by setting some of its entries to zero. All solutions are then combined to present the result in a...

Controllability in the max-algebra

Jean-Michel Prou, Edouard Wagneur (1999)

Kybernetika

We are interested here in the reachability and controllability problems for DEDS in the max-algebra. Contrary to the situation in linear systems theory, where controllability (resp observability) refers to a (linear) subspace, these properties are essentially discrete in the max -linear dynamic system. We show that these problems, which consist in solving a max -linear equation lead to an eigenvector problem in the min -algebra. More precisely, we show that, given a max -linear system, then, for every natural...

Controllable and tolerable generalized eigenvectors of interval max-plus matrices

Matej Gazda, Ján Plavka (2021)

Kybernetika

By max-plus algebra we mean the set of reals equipped with the operations a b = max { a , b } and a b = a + b for a , b . A vector x is said to be a generalized eigenvector of max-plus matrices A , B ( m , n ) if A x = λ B x for some λ . The investigation of properties of generalized eigenvectors is important for the applications. The values of vector or matrix inputs in practice are usually not exact numbers and they can be rather considered as values in some intervals. In this paper the properties of matrices and vectors with inexact (interval) entries...

Distances on the tropical line determined by two points

María Jesús de la Puente (2014)

Kybernetika

Let p ' and q ' be points in n . Write p ' q ' if p ' - q ' is a multiple of ( 1 , ... , 1 ) . Two different points p and q in n / uniquely determine a tropical line L ( p , q ) passing through them and stable under small perturbations. This line is a balanced unrooted semi-labeled tree on n leaves. It is also a metric graph. If some representatives p ' and q ' of p and q are the first and second columns of some real normal idempotent order n matrix A , we prove that the tree L ( p , q ) is described by a matrix F , easily obtained from A . We also prove that...

Eigenspace of a circulant max–min matrix

Martin Gavalec, Hana Tomášková (2010)

Kybernetika

The eigenproblem of a circulant matrix in max-min algebra is investigated. Complete characterization of the eigenspace structure of a circulant matrix is given by describing all possible types of eigenvectors in detail.

Eigenspace of a three-dimensional max-Łukasiewicz fuzzy matrix

Imran Rashid, Martin Gavalec, Sergeĭ Sergeev (2012)

Kybernetika

Eigenvectors of a fuzzy matrix correspond to stable states of a complex discrete-events system, characterized by a given transition matrix and fuzzy state vectors. Description of the eigenspace (set of all eigenvectors) for matrices in max-min or max-drast fuzzy algebra was presented in previous papers. In this paper the eigenspace of a three-dimensional fuzzy matrix in max-Łukasiewicz algebra is investigated. Necessary and sufficient conditions are shown under which the eigenspace restricted to...

G-matrices, J -orthogonal matrices, and their sign patterns

Frank J. Hall, Miroslav Rozložník (2016)

Czechoslovak Mathematical Journal

A real matrix A is a G-matrix if A is nonsingular and there exist nonsingular diagonal matrices D 1 and D 2 such that A - T = D 1 A D 2 , where A - T denotes the transpose of the inverse of A . Denote by J = diag ( ± 1 ) a diagonal (signature) matrix, each of whose diagonal entries is + 1 or - 1 . A nonsingular real matrix Q is called J -orthogonal if Q T J Q = J . Many connections are established between these matrices. In particular, a matrix A is a G-matrix if and only if A is diagonally (with positive diagonals) equivalent to a column permutation of...

Isocanted alcoved polytopes

María Jesús de la Puente, Pedro Luis Clavería (2020)

Applications of Mathematics

Through tropical normal idempotent matrices, we introduce isocanted alcoved polytopes, computing their f -vectors and checking the validity of the following five conjectures: Bárány, unimodality, 3 d , flag and cubical lower bound (CLBC). Isocanted alcoved polytopes are centrally symmetric, almost simple cubical polytopes. They are zonotopes. We show that, for each dimension, there is a unique combinatorial type. In dimension d , an isocanted alcoved polytope has 2 d + 1 - 2 vertices, its face lattice is the lattice...

Maximal solutions of two–sided linear systems in max–min algebra

Pavel Krbálek, Alena Pozdílková (2010)

Kybernetika

Max-min algebra and its various aspects have been intensively studied by many authors [1, 4] because of its applicability to various areas, such as fuzzy system, knowledge management and others. Binary operations of addition and multiplication of real numbers used in classical linear algebra are replaced in max-min algebra by operations of maximum and minimum. We consider two-sided systems of max-min linear equations A x = B x , with given coefficient matrices A and B . We present a polynomial method for...

Max-min interval systems of linear equations with bounded solution

Helena Myšková (2012)

Kybernetika

Max-min algebra is an algebraic structure in which classical addition and multiplication are replaced by and , where a b = max { a , b } , a b = min { a , b } . The notation 𝐀 𝐱 = 𝐛 represents an interval system of linear equations, where 𝐀 = [ A ̲ , A ¯ ] , 𝐛 = [ b ̲ , b ¯ ] are given interval matrix and interval vector, respectively, and a solution is from a given interval vector 𝐱 = [ x ̲ , x ¯ ] . We define six types of solvability of max-min interval systems with bounded solution and give necessary and sufficient conditions for them.

Modifying the tropical version of Stickel's key exchange protocol

Any Muanalifah, Sergei Sergeev (2020)

Applications of Mathematics

A tropical version of Stickel's key exchange protocol was suggested by Grigoriev and Shpilrain (2014) and successfully attacked by Kotov and Ushakov (2018). We suggest some modifications of this scheme that use commuting matrices in tropical algebra and discuss some possibilities of attacks on these new modifications. We suggest some simple heuristic attacks on one of our new protocols, and then we generalize the Kotov and Ushakov attack on tropical Stickel's protocol and discuss the application...

Monotone interval eigenproblem in max–min algebra

Martin Gavalec, Ján Plavka (2010)

Kybernetika

The interval eigenproblem in max-min algebra is studied. A classification of interval eigenvectors is introduced and six types of interval eigenvectors are described. Characterization of all six types is given for the case of strictly increasing eigenvectors and Hasse diagram of relations between the types is presented.

On an algorithm for testing T4 solvability of max-plus interval systems

Helena Myšková (2012)

Kybernetika

In this paper, we shall deal with the solvability of interval systems of linear equations in max-plus algebra. Max-plus algebra is an algebraic structure in which classical addition and multiplication are replaced by and , where a b = max { a , b } , a b = a + b . The notation 𝔸 x = 𝕓 represents an interval system of linear equations, where 𝔸 = [ b ¯ , A ¯ ] and 𝕓 = [ b ̲ , b ¯ ] are given interval matrix and interval vector, respectively. We can define several types of solvability of interval systems. In this paper, we define the T4 solvability and give an algorithm...

On sparsity of approximate solutions to max-plus linear systems

Pingke Li (2024)

Kybernetika

When a system of one-sided max-plus linear equations is inconsistent, the approximate solutions within an admissible error bound may be desired instead, particularly with some sparsity property. It is demonstrated in this paper that obtaining the sparsest approximate solution within a given L error bound may be transformed in polynomial time into the set covering problem, which is known to be NP-hard. Besides, the problem of obtaining the sparsest approximate solution within a given L 1 error bound...

Currently displaying 1 – 20 of 32

Page 1 Next