Powers of matrices over an extremal algebra with applications to periodic graphs

Consider the extremal algebra=({},min,+), using + and min instead of addition and multiplication. This extremal algebra has been successfully applied to a lot of scheduling problems. In this paper the behavior of the powers of a matrix over is studied. The main result is a representation of the complete sequence (A ^m ) _m which can be computed within polynomial time complexity. In the second part we apply this result to compute a minimum cost path in a 1-dimensional periodic graph.     

Polynomial identities for matrices over the Grassmann algebra

We determine minimal Cayley–Hamilton and Capelli identities for matrices over a Grassmann algebra of finite rank. For minimal standard identities, we give lower and upper bounds on the degree. These results improve on upper bounds given by L. Márki, J. Meyer, J. Szigeti and L. van Wyk in a recent paper.     

Rank preservers of matrices over max algebra

The max algebra consists of the nonnegative real numbers equipped with two binary operations, maximization and multiplication. We consider the semimodules over max algebra and study the properties of the weak basis and weak dimension of the semi-modules. Moreover, we obtain the characterizations of those linear operators that preserve rank of matrices over max-algebra.     

Rank preservers of matrices over max algebra

The max algebra consists of the nonnegative real numbers equipped with two binary operations, maximization and multiplication. We consider the semimodules over max algebra and study the properties of the weak basis and weak dimension of the semi-modules. Moreover, we obtain the characterizations of those linear operators that preserve rank of matrices over max-algebra.     

A normality criterion for an algebra of matrices

It is shown that the real algebra generated by a pair A,B of n × n (complex) matrices consists entirely of normal matrices if and only if A,B,AB,A + B and A + AB are normal.     

Invertible commutativity preservers of matrices over max algebra

The max algebra consists of the nonnegative real numbers equipped with two binary operations, maximization and multiplication. We characterize the invertible linear operators that preserve the set of commuting pairs of matrices over a subalgebra of max algebra.     

Identities of an algebra of triangular matrices

This paper deals with the ideals of identities of certain associative algebras over a field F of characteristic zero. An algebra W of matrices of the form ,,,M, where and , are F-algebras with unity and M is a (,)-bimodule, is considered. Under certain natural restrictions on M one obtains the equality of ideals of identities T(W)=T()T(), if [[x₁,x₂], x₃[x₄,x₅]]T().Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 114, pp. 7–27, 1982.     

Eigenvectors of interval matrices over max–plus algebra

The behaviour of a discrete-event dynamic system is often conveniently described using a matrix algebra with operations max and plus. Such a system moves forward in regular steps of length equal to the eigenvalue of the system matrix, if it is set to operate at time instants corresponding to one of its eigenvectors. However, due to imprecise measurements, it is often unappropriate to use exact matrices. One possibility to model imprecision is to use interval matrices. We show that the problem to decide whether a given vector is an eigenvector of one of the matrices in the given matrix interval is polynomial, while the complexity of the existence problem of a universal eigenvector remains open. As an aside, we propose a combinatorial method for solving two-sided systems of linear equations over the max–plus algebra.     

An extremal problem for positive defintie matrices

A problem studied by Flanders (1975) is minimize the function f(R)=tr(SR+TR^-1) over the set of positive definite matrices R, where S and T are positive semi-definite matrices. Alternative proofs that may have some intrinsic interest are provided. The proofs explicitly yield the infimum of f(R). One proof is based on a convexity argument and the other on a sequence of reductions to a univariate problem.     

On the identities of subalgebras of matrices over the Grassmann algebra

The polynomial identities of certain subalgebras of matrices, over the Grassmann algebra, are studied in terms of their cocharacters. Our present knowledge of such characters for matrices over a fieldF (charF=0) plays a role here, and some of these results are extended to these subalgebras. In particular, we obtain bounds for the codimensions of these algebras (Theorem 0.1 below). Partially supported by an N. S. F. Grant.     

Linear maps that strongly preserve regular matrices over the Boolean algebra

The set of all m × n Boolean matrices is denoted by $ \mathbb{M} $ \mathbb{M} _m,n . We call a matrix A ∈ $ \mathbb{M} $ \mathbb{M} _m,n regular if there is a matrix G ∈ $ \mathbb{M} $ \mathbb{M} _n,m such that AGA = A. In this paper, we study the problem of characterizing linear operators on $ \mathbb{M} $ \mathbb{M} _m,n that strongly preserve regular matrices. Consequently, we obtain that if min{m, n} ⩽ 2, then all operators on $ \mathbb{M} $ \mathbb{M} _m,n strongly preserve regular matrices, and if min{m, n} ⩾ 3, then an operator T on $ \mathbb{M} $ \mathbb{M} _m,n strongly preserves regular matrices if and only if there are invertible matrices U and V such that T(X) = UXV for all X ε $ \mathbb{M} $ \mathbb{M} _m,n , or m = n and T(X) = UX ^T V for all X ∈ $ \mathbb{M} $ \mathbb{M} _n .     

Some extremal problems for strictly totally positive matrices

For a strictly totally positive M × N matrix A we show that the ratio $\text{∥A}\text{x}\text{∥}{}_{\mathrm{p}}\text{∥}\text{x}\text{∥}{}_{\mathrm{p}}$ has exactly R = min{ M, N} nonzero critical values for each fixed p? (1, ∞). Letting λ_i denote the ith critical value, and xⁱ an associated critical vector, we show that λ₁ > … > λ_R > 0 and xⁱ (unique up to multiplication by a constant) has exactly i ? 1 sign changes. These critical values are generalizations to l^p of the s-numbers of A and satisfy many of the same extremal properties enjoyed by the s-numbers, but with respect to the l^p norm.     

Stratified modules over an extension algebra

Let A be a standard Koszul standardly stratified algebra and X an A-module. The paper investigates conditions which imply that the module Ext* _A (X) over the Yoneda extension algebra A* is filtered by standard modules. In particular, we prove that the Yoneda extension algebra of A is also standardly stratified. This is a generalization of similar results on quasi-hereditary and on graded standardly stratified algebras.     

Triangular truncation and its extremal matrices

The triangular truncation operator is a linear transformation that maps a given matrix to its strictly lower triangular part. The operator norm (with respect to the matrix spectral norm) of the triangular truncation is known to have logarithmic dependence on the dimension, and such dependence is usually illustrated by a specific Toeplitz matrix. However, the precise value of this operator norm as well as on which matrices can it be attained is still unclear. In this article, we describe a simple way of constructing matrices whose strictly lower triangular part has logarithmically larger spectral norm. The construction also leads to a sharp estimate that is very close to the actual operator norm of the triangular truncation. This research is directly motivated by our studies on the convergence theory of the Kaczmarz type method (or equivalently, the Gauß‐Seidel type method), the corresponding application of which is also included. Copyright © 2016 John Wiley & Sons, Ltd.     

Eigenproblem for optimal-node matrices in max-plus algebra

The eigenproblem for optimal-node matrices in max-plus algebra is shown to be solved. First, the definition of optimal-node matrix is introduced. Then for a given optimal-node matrix, it is revealed that it is easy to find all its eigenvalues and eigenvectors, which correspond to the interval time of two continuous stages and the start times of every stage of all the machines in the multi-machine interactive production process, respectively.     

An extremal property of the eigenvalue of irreducible matrices in idempotent algebra and solution of the Rawls location problem

An extremal property of the eigenvalue of an irreducible matrix in idempotent algebra is studied. It is shown that this value is the minimum value of some functional defined using this matrix on the set of vectors with nonzero components. The minimax problem of location of a single facility (the Rawls problem) on a plane with rectilinear distance is considered. For this problem, we give the corresponding representation in terms of idempotent algebra and suggest a new algebraic solution, which is based on the results of investigation of the extremal property of eigenvalue and reduces to finding the eigenvalue and eigenvectors of a certain matrix.     

Dominant matrices and max algebra

We study the class of so-called totally dominant matrices in the usual algebra and in the max algebra in which the sum is the maximum and the multiplication is usual. It turns out that this class coincides with the well known class of positive matrices having positive the determinants of all 2×2 submatrices. The closure of this class is closed not only with respect to the usual but also with respect to the max multiplication. Further properties analogous to those of totally positive matrices are proved and some connections to Monge matrices are mentioned.