Search

In max-min fuzzy algebra, the study of eigenvectors is important because it can help us to recognize the steady states of systems working in discrete steps. This paper investigates the properties of steady states described by max-min matrices and vectors with interval coefficients. The characteristics of the eigenspace structure and polynomial-time algorithms for recognition of tolerable and weakly-tolerable interval eigenvectors in max-min algebra are described. This research is a continuation of an earlier investigation concerning strongly-tolerable interval eigenvectors.

In this paper we consider the generalized eigenproblem in max-min (fuzzy) algebra, i.e. given matrices A, B find a vector x and a constant λ such that A x = λ B x where the standard pair of operations, plus and times, have been replaced by the operations maximum and minimum. The entries of the vector or matrix are, in practice, usually not exact numbers and can rather be considered as values in some intervals. In this paper the properties of matrices and vectors with inexact (interval) entries are studied and complete solutions of the strong, the universal, the L-controllable and the R-controllable generalized eigenproblems in max-min (fuzzy) algebra are presented. As a consequence of the obtained results, efficient algorithms for checking all equivalent conditions are introduced.

A max-plus matrix A (operations max and plus are denoted by ⊕ and ⊗ , respectively) is called X –robust if the orbit x , A ⊗ x , A 2 ⊗ x , … of any initial vector x belonging to the interval X = { x : x ≤ x ≤ x ¯ } ends up with a max-plus algebraic eigenvector of A . The X –robustness of a max-plus matrix is extended to interval vectors X using forall–exists quantification of their interval entries (so-called X A E –robustness and X E A –robustness). A complete characterization of X A E –robustness and X E A –robustness of matrices and possible (universal) X A E ( X E A )–robustness of interval circulant matrices is presented.

Max-min algebra is an algebraic structure in which classical addition and multiplication are replaced by maximum and minimum, respectively. The notation A ⊗ X ⊗ C = B , where A, B, and C are given interval matrices, represents an interval max-min matrix equation. The paper deals with the solvability of interval matrix equations in max-min algebra. We define three types of solvability of interval max-min matrix equations, namely the strongly universal, universal and weakly universal solvability. We provide the equivalent conditions for each type of solvability that can be verified in polynomial times.

Max-min algebra is defined as a linearly ordered set with two binary operations. Classical addition and multiplication are replaced by maximum and minimum, respectively. A square matrix is robust, if its eigenspace is achieved starting at arbitrary vector and it is X-robust if its eigenspace is achieved starting at each vector from a given interval vector X. The EA and AE robustness and X-robustness of interval circulant matrices over max-min algebra are defined. Polynomial algorithms for checking these types of robustness and X-robustness are given.

In max–min fuzzy algebra, the standard pair of operations—plus and times—is substituted by a different pair of operations—maximum and minimum—which are involved in many optimization problems. Investigation of the properties of eigenvectors is important for these applications. The values of vector or matrix inputs in practice are usually not exact numbers and some intervals can instead be considered as values. This paper investigates the properties of matrices and vectors with interval coefficients. In addition, a complete solution of the strong tolerance interval eigenproblem in max–min algebra is presented.

A max–min (fuzzy) matrix A (operations max and min are denoted by ⊕ and ⊗ , respectively) is called X − robust if the orbit x , A ⊗ x , A 2 ⊗ x , … of any initial vector x belonging to the interval X = { x : x ≤ x ≤ x ¯ } ends up with a max–min algebraic eigenvector of A . The X -robustness of a fuzzy matrix is extended to interval vectors X using forall–exists quantification of their interval entries (so-called X A E -robustness and X E A -robustness). A complete characterization of X A E -robustness and X E A -robustness of fuzzy matrices is presented. Moreover, O ( n 4 ) algorithms for checking the both types of robustness are described.

The Łukasiewicz conjunction (sometimes also considered to be a logic of absolute comparison), which is used in multivalued logic and in fuzzy set theory, is one of the most important t-norms. In combination with the binary operation ‘maximum’, the Łukasiewicz t-norm forms the basis for the so-called max-Łuk algebra, with applications to the investigation of systems working in discrete steps (discrete events systems; DES, in short). Similar algebras describing the work of DES’s are based on other pairs of operations, such as max-min algebra, max-plus algebra, or max-T algebra (with a given t-norm, T). The investigation of the steady states in a DES leads to the study of the eigenvectors of the transition matrix in the corresponding max-algebra. In real systems, the input values are usually taken to be in some interval. Various types of interval eigenvectors of interval matrices in max-min and max-plus algebras have been described. This paper is oriented to the investigation of strong, strongly tolerable, and strongly universal interval eigenvectors in a max-Łuk algebra. The main method used in this paper is based on max-Ł linear combinations of matrices and vectors. Necessary and sufficient conditions for the recognition of strong, strongly tolerable, and strongly universal eigenvectors have been found. The theoretical results are illustrated by numerical examples.

The optimization problems, such as scheduling or project management, in which the objective function depends on the operations maximum and plus, can be naturally formulated and solved in max-plus algebra. A system of discrete events, e.g., activations of processors in parallel computing, or activations of some other cooperating machines, is described by a systems of max-plus linear equations. In particular, if the system is in a steady state, such as a synchronized computer network in data processing, then the state vector is an eigenvector of the system. In reality, the entries of matrices and vectors are considered as intervals. The properties and recognition algorithms for several types of interval eigenvectors are studied in this paper. For a given interval matrix and interval vector, a set of generators is defined. Then, the strong and the strongly universal eigenvectors are studied and described as max-plus linear combinations of generators. Moreover, a polynomial recognition algorithm is suggested and its correctness is proved. Similar results are presented for the weak eigenvectors. The results are illustrated by numerical examples. The results have a general character and can be applied in every max-plus algebra and every instance of the interval eigenproblem.

A fuzzy algebra is a triple ( B , ⊕ , ⊗ ) , where ( B , ≤ ) is a nonempty, bounded, linearly ordered set and a ⊕ b = max ⁡ { a , b } , a ⊗ b = min ⁡ { a , b } for a , b ∈ B . A vector x is said to be a λ-eigenvector of a square matrix A if A ⊗ x = λ ⊗ x for some λ ∈ B . The aim of the paper is to solve subeigenproblem and supereigenproblem for some λ ∈ B , that is to find a solution x of A ⊗ x ≤ λ ⊗ x and A ⊗ x ≥ λ ⊗ x , x is called subeigenvector and supereigenvector, respectively. The problems are related to and motivated by the similar problems of tropical linear algebra. In this paper the properties of subeigenvectors and supereigenvectors are described and the values λ associated with subeigenvectors and supereigenvectors are characterized. As a consequence, efficient algorithms for checking all equivalent conditions are introduced.

Interval eigenvectors of interval matrices corresponding to steady states of systems with inexact data are investigated.Tolerable, strongly tolerable and weakly tolerable interval eigenvectors are described.Polynomial solutions to the recognition versions of all three types of tolerability are presented. Max-plus algebra plays a key role in the study of discrete event systems in connection with optimization problems such as scheduling or project management in which the objective function depends on the operations maximum and plus. The steady states of such systems correspond to the eigenvectors of max-plus matrices, therefore the investigation of the properties of these eigenvectors is important for applications.Matrices and vectors with interval coefficients in a max-plus algebra are studied in this paper, and polynomial algorithms are presented for the recognition problem with three types of tolerance interval eigenvector.

A vector $x$ is said to be an eigenvector of a square max-min matrix $A$ if $A\otimes x=x$. An eigenvector $x$ of $A$ is called the greatest $\textit{\textbf{X}}$-eigenvector of $A$ if $x\in\textit{\textbf{X}}=\{x; {\underline x}\leq x\leq {\overline x}\}$ and $y\leq x$ for each eigenvector $y\in\textit{\textbf{X}}$. A max-min matrix $A$ is called strongly $\textit{\textbf{X}}$-robust if the orbit $x,A\otimes x, A^2\otimes x,\dots$ reaches the greatest $\textit{\textbf{X}}$-eigenvector with any starting vector of $\textit{\textbf{X}}$. We suggest an $O(n^3)$ algorithm for computing the greatest $\textit{\textbf{X}}$-eigenvector of $A$ and study the strong $\textit{\textbf{X}}$-robustness. The necessary and sufficient conditions for strong $\textit{\textbf{X}}$-robustness are introduced and an efficient algorithm for verifying these conditions is described.

A max–min (fuzzy) matrix A (operations max and min are denoted by ⊕ and ⊗, respectively) is called weakly robust if the only possibility to arrive at an eigenvector is to start the sequence (orbit) x,A⊗x,A2⊗x,… by a vector that is itself an eigenvector. The weak robustness of a fuzzy matrix is extended to interval fuzzy matrices distinguishing two possibilities, that at least one matrix or all matrices from a given interval are weakly robust. Characterization of weak robustness of interval fuzzy matrices is presented and an O(n3) algorithm for checking the weak robustness of interval fuzzy matrices is described.

A max –plus matrix A (operations max and plus are denoted by ⊕ and ⊗ , respectively) is called weakly robust if the only possibility to arrive at an eigenvector is to start the sequence (orbit) x , A ⊗ x , A 2 ⊗ x , … by a vector that is itself an eigenvector. The weak robustness of a matrix is extended to interval max–plus matrices distinguishing two possibilities, that at least one matrix or all matrices from a given interval are weakly robust. Weakly robust interval matrices in max–plus algebra are studied and equivalent conditions for interval matrices to be weakly robust are presented. The recognition version of the problem of the existence of at least one weakly robust matrix from a given interval is proved to be NP-complete.

Robust interval matrices in max-plus algebra are studied and equivalent conditions for interval matrices to be robust are presented. The necessary and sufficient conditions for robustness of interval matrices are introduced. In addition, efficient algorithms for verifying the robustness of interval circulant and interval zero–one matrices are described.

A nonnegative matrix A is said to be strongly robust if its max-algebraic eigencone is universally reachable, i.e., if the orbit of any initial vector ends up with a max-algebraic eigenvector of A. Consider the case when the initial vector is restricted to an interval and A can be any matrix from a given interval of nonnegative circulant matrices. The main aim of this paper is to classify and characterize the six types of interval robustness in this situation. This naturally leads us also to study the max-algebraic spectral theory of circulant matrices and the relation of inclusion between attraction cones of circulant matrices in max-algebra., corrected some mistakes in Examples 3.9 and 3.10 (w.r.t. the previous version)

Fuzzy 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 } . A matrix is X -robust if its eigenspace is achieved starting at each vector from a given interval vector X . The possible and universal X -robustness of interval matrices over fuzzy algebra are defined. Polynomial algorithms for checking the possible and universal X -robustness of interval circulant matrices are described.

Strongly robust interval matrices over ( max , min ) -algebra (fuzzy matrices) are studied and strong robustness properties are proved, similar to those of classical fuzzy matrices. It is shown that a strong robustness of an interval fuzzy matrix is well-defined using the definition of classical strong robustness. Characterization of strong robustness of interval fuzzy matrices is presented and an O ( n 3 ) algorithm for checking the strong robustness of interval fuzzy matrices is described.

We investigate max-algebraic (tropical) one-sided systems $A\otimes x=b$ where $b$ is an eigenvector and $x$ lies in an interval $X$. A matrix $A$ is said to have $X$-simple image eigencone associated with an eigenvalue $\lambda$, if any eigenvector $x$ associated with $\lambda$ and belonging to the interval $X$ is the unique solution of the system $A\otimes y=\lambda x$ in $X$. We characterize matrices with $X$-simple image eigencone geometrically and combinatorially, and for some special cases, derive criteria that can be efficiently checked in practice., Comment: 25 pages

Let (B,@?) be a non-empty, bounded, linearly ordered set and [email protected]?b=max{a,b}, [email protected]?b=min{a,b} for a,[email protected]?B. A vector x is said to be a @l-eigenvector of a square matrix A if [email protected][email protected]@?x for some @[email protected]?B. A given matrix A is called (strongly) @l-robust if for every x the vector A^[email protected]?x is a (greatest) eigenvector of A for some natural number k. We present a characterization of @l-robust and strongly @l-robust matrices. Building on this, an efficient algorithm for checking the @l-robustness and strong @l-robustness of a given matrix is introduced.

The eigenspace structure for a given n×n concave Monge matrix in a max-plus algebra is described. Based on the description, an O(n) algorithm for computing the eigenspace dimension is formulated, which is faster than the previously known algorithms. Analogous results for convex Monge matrices have been published in [M. Gavalec, J. Plavka, Structure of the eigenspace of a Monge matrix in max-plus algebra, Discrete Appl. Math. 156 (2008) 596–606].

A complete description of the eigenspace structure for a given n×n Monge matrix in a max-plus algebra is presented. Based on the description, an O(n2) algorithm for computing the eigenspace dimension is formulated, which is faster than the previously known algorithms.

The steady states of a fuzzy discrete dynamic system correspond to invariants (eigenvectors) of the transition matrix of the system. The structure of the eigenspace of a given fuzzy matrix is considered for various max-T algebras, where T is some triangular norm (Godel, Eukasiewicz, product, drastic). A given transition fuzzy matrix is called (strongly) robust if for every starting vector of a fuzzy discrete dynamic system a multiplication of a power matrix with the starting vector produces a (greatest) eigenvector of the transition matrix. A transition matrix is called weakly robust if the only possibility to arrive at an eigenvector is to start of a fuzzy discrete dynamic system by a vector that is itself an eigenvector. We present characterizations of the eigenspace of a given transition matrix in various max-T algebras. Further results concern the robustness (weak, strong robustness) of a matrix and an interval matrix (matrix with inexact data). Polynomial algorithms for checking the equivalent conditions for (weak, strong) robustness of interval fuzzy matrices are presented.

The problem of finding one eigenvector of a given Monge matrix A in a max-plus algebra is considered. For a general matrix, the problem can be solved in O(n3) time by computing one column of the corresponding metric matrix Δ(Aλ), where λ is the eigenvalue of A. An algorithm is presented, which computes an eigenvector of a Monge matrix in O(n2) time.

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. The symbol diag(d1, d2,...,dn) denotes the matrix D with diagonal elements equal to d1, d2,...,dn and off-diagonal elements equal to -∞. For an arbitrary parameter e ∈ R and given square matrices A = (aij), D = diag(d1, d2,...,dl, 0,...,0), dj = e 1 ≤ j ≤ l, we study the l- parametric eigenproblem, i.e. problem of finding all xe = (x1(e), x2(e),...,xn(e)) and λel, satisfying Ael ⊗ xe = λel ⊗ xe, where Ael = A ⊗ D. We introduce some properties of general l-parametric eigenproblem and the O(n3) algorithm which gives all solutions of the 1-parametric eigenproblem with respect to e.

In calculating the solvation energy of proteins, the hydration effects, drug binding, molecular docking, etc., it is important to have an efficient and exact algorithms for computing the solvent accessible surface area and the excluded volume of macromolecules. Here we present a Fortran package based on the new exact analytical methods for computing volume and surface area of overlapping spheres. In the considered procedure the surface area and volume are expressed as surface integrals of the second kind over the closed region. Using the stereographic projection the surface integrals are transformed to a sum of double integrals which are reduced to the curve integrals. MPI Fortran version is described as well. The package is also useful for computing the percolation probability of continuum percolation models.

The problem of the strong regularity of a square matrix in a general max–min algebra is considered and a necessary and sufficient condition using the trapezoidal property is described. The results are valid without any restrictions on the underlying max–min algebra, concerning the density, or the boundedness. Previous results on this topic are special cases of the theorems presented in this paper.

An O(n2) algorithm is described for computing the maximum cycle mean (eigenvalue) for n × n matrices, A = (aij) fulfilling Monge property, aij + akl ≤ ail + akj for any i < k, j < l. The algorithm computes the value λ(A) = max(ai1i2) + +ai2j3 + ... + aikj1/k over all cyclic permutations (i1, i2,..., ik) of subsets of the set {1,2,...,n). A similar result is presented for matrices with inverse Monge property. The standard algorithm for the general case works in O(n3) time.

For a given linear mapping in max-min algebra, determined by a square matrix A, the set SA consisting of all elements with a unique pre-image (in short: the simple image set of A) is considered. It is shown that the closure of SA is a subset of the set of all eigenvectors of A, if the matrix A is generally trapezoidal. In general case, there is a permutation π, such that the closure of SA is a subset of the set of all eigenvectors permuted by π.

Let (R, ⪕) be a linearly ordered set. A bottleneck algebra is the set R together with two operations a ⊕ b = max {a, b} and a ⊗ b = min {a, b}. In this paper we suggest various definitions of linear independence of sets of n-tuples over R study their characteristics and interrelations.

Let (G,·,≤) be a radicable, linearly ordered, commutative group. Given a square matrix A=(aij) of order n with entries from G and a cyclic permutation σ=(i1,…,il) of a subset of N={1,2,…,n} we define μ(σ), the mean weight of σ, as (a i 1 i 2 ·a i 2 i3 …a il-1il ·a ilil ) 1 1 and λ(A), the maximum cycle mean (MCM) of A, as maxσμ(σ), where σ ranges over all cyclic permutations of subsets of N. We study the dependence of the MCM of a matrix on the permutations of its rows and columns and particularly we prove an O(n2) algorithm for checking whether λ(A)=λ(A') holds for any matrix A' which can be obtained from A by permuting its rows and columns.

For a given linear mapping, determined by a square matrix A in a max–min algebra, the set SA consisting of all vectors with a unique pre-image (in short: the simple image set of A) is considered. It is shown that if the matrix A is generally trapezoidal, then the closure of SA is a subset of the set of all eigenvectors of A. In the general case, there is a permutation π, such that the closure of SA is a subset of the set of all eigenvectors permuted by π. The simple image set of the matrix square and the topological aspects of the problem are also described.