Page 1 Next

Displaying 1 – 20 of 21

Showing per page

An idempotent algorithm for a class of network-disruption games

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

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

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 $\oplus$ and $\otimes$, where $a\oplus b=max\left\{a,b\right\},a\otimes b=min\left\{a,b\right\}$. The notation $𝔸\otimes x=𝕓$ represents an interval system of linear equations, where $𝔸=\left[\underline{A},\overline{A}\right]$ and $𝕓=\left[\underline{b},\overline{b}\right]$ 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

Kybernetika

A matrix $A$ is said to have $𝐗$-simple image eigenspace if any eigenvector $x$ belonging to the interval $𝐗=\left\{x:\underline{x}\le x\le \overline{x}\right\}$ is the unique solution of the system $A\otimes 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...

Controllability in the max-algebra

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

Distances on the tropical line determined by two points

Kybernetika

Let ${p}^{\text{'}}$ and ${q}^{\text{'}}$ be points in ${ℝ}^{n}$. Write ${p}^{\text{'}}\sim {q}^{\text{'}}$ if ${p}^{\text{'}}-{q}^{\text{'}}$ is a multiple of $\left(1,...,1\right)$. Two different points $p$ and $q$ in ${ℝ}^{n}/\sim$ uniquely determine a tropical line $L\left(p,q\right)$ 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}^{\text{'}}$ and ${q}^{\text{'}}$ 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\left(p,q\right)$ is described by a matrix $F$, easily obtained from $A$. We also prove that...

Eigenspace of a circulant max–min matrix

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

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

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}^{-\mathrm{T}}={D}_{1}A{D}_{2}$, where ${A}^{-\mathrm{T}}$ denotes the transpose of the inverse of $A$. Denote by $J=\mathrm{diag}\left(±1\right)$ a diagonal (signature) matrix, each of whose diagonal entries is $+1$ or $-1$. A nonsingular real matrix $Q$ is called $J$-orthogonal if ${Q}^{\mathrm{T}}JQ=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...

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

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\otimes x=B\otimes x$, with given coefficient matrices $A$ and $B$. We present a polynomial method for...

Max-min interval systems of linear equations with bounded solution

Kybernetika

Max-min algebra is an algebraic structure in which classical addition and multiplication are replaced by $\oplus$ and $\otimes$, where $a\oplus b=max\left\{a,b\right\},\phantom{\rule{4pt}{0ex}}a\otimes b=min\left\{a,b\right\}$. The notation $𝐀\otimes 𝐱=𝐛$ represents an interval system of linear equations, where $𝐀=\left[\underline{A},\overline{A}\right]$, $𝐛=\left[\underline{b},\overline{b}\right]$ are given interval matrix and interval vector, respectively, and a solution is from a given interval vector $𝐱=\left[\underline{x},\overline{x}\right]$. We define six types of solvability of max-min interval systems with bounded solution and give necessary and sufficient conditions for them.

Monotone interval eigenproblem in max–min algebra

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

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 $\oplus$ and $\otimes$, where $a\oplus b=max\left\{a,b\right\}$, $a\otimes b=a+b$. The notation $𝔸\otimes x=𝕓$ represents an interval system of linear equations, where $𝔸=\left[\overline{b},\overline{A}\right]$ and $𝕓=\left[\underline{b},\overline{b}\right]$ 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 the problem $Ax=\lambda Bx$ in max algebra: every system of intervals is a spectrum

Kybernetika

We consider the two-sided eigenproblem $A\otimes x=\lambda \otimes B\otimes x$ over max algebra. It is shown that any finite system of real intervals and points can be represented as spectrum of this eigenproblem.

On the weak robustness of fuzzy matrices

Kybernetika

A matrix $A$ in $\left(max,min\right)$-algebra (fuzzy matrix) is called weakly robust if ${A}^{k}\otimes x$ is an eigenvector of $A$ only if $x$ is an eigenvector of $A$. The weak robustness of fuzzy matrices are studied and its properties are proved. A characterization of the weak robustness of fuzzy matrices is presented and an $O\left({n}^{2}\right)$ algorithm for checking the weak robustness is described.

On tropical Kleene star matrices and alcoved polytopes

Kybernetika

In this paper we give a short, elementary proof of a known result in tropical mathematics, by which the convexity of the column span of a zero-diagonal real matrix $A$ is characterized by $A$ being a Kleene star. We give applications to alcoved polytopes, using normal idempotent matrices (which form a subclass of Kleene stars). For a normal matrix we define a norm and show that this is the radius of a hyperplane section of its tropical span.

Rational algebra and MM functions

Kybernetika

MM functions, formed by finite composition of the operators min, max and translation, represent discrete-event systems involving disjunction, conjunction and delay. The paper shows how they may be formulated as homogeneous rational algebraic functions of degree one, over (max, +) algebra, and reviews the properties of such homogeneous functions, illustrated by some orbit-stability problems.

Reachability and observability of linear systems over max-plus

Kybernetika

This paper discusses the properties of reachability and observability for linear systems over the max-plus algebra. Working in the event-domain, the concept of asticity is used to develop conditions for weak reachability and weak observability. In the reachability problem, residuation is used to determine if a state is reachable and to generate the required control sequence to reach it. In the observability problem, residuation is used to estimate the state. Finally, as in the continuous-variable...

Soluble approximation of linear systems in max-plus algebra

Kybernetika

We propose an efficient method for finding a Chebyshev-best soluble approximation to an insoluble system of linear equations over max-plus algebra.

Solving systems of two–sided (max, min)–linear equations

Kybernetika

A finite iteration method for solving systems of (max, min)-linear equations is presented. The systems have variables on both sides of the equations. The algorithm has polynomial complexity and may be extended to wider classes of equations with a similar structure.

Page 1 Next