Computing an eigenvector of an inverse Monge matrix in max-plus algebra

The problem of computing an eigenvector of an inverse Monge matrix in max-plus algebra is addressed. For a general matrix, the problem can be solved in at most O(n³) time. This note presents an O(n²) algorithm for computing one max-plus algebraic eigenvector of an inverse Monge matrix . It is assumed that is irreducible.     

Computing an Eigenvector of a Monge Matrix in Max-Plus Algebra

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(n ³) 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(n ²) time.     

Max-Plus Objects to Study the Complexity of Graphs

Given an undirected graph G, we define a new object H _G , called the mp-chart of G, in the max-plus algebra. We use it, together with the max-plus permanent, to describe the complexity of graphs. We show how to compute the mean and the variance of H _G in terms of the adjacency matrix of G and we give a central limit theorem for H _G . Finally, we show that the mp-chart is easily tractable also for the complement graph.     

Lattice-Ordered Matrix Rings Over Totally Ordered Rings

For an n ×n matrix algebra over a totally ordered integral domain, necessary and sufficient conditions are derived such that the entrywise lattice order on it is the only lattice order (up to an isomorphism) to make it into a lattice-ordered algebra in which the identity matrix is positive. The conditions are then applied to particular integral domains. In the second part of the paper we consider n ×n matrix rings containing a positive n-cycle over totally ordered rings. Finally a characterization of lattice-ordered matrix ring with the entrywise lattice order is given.     

Output feedback stabilization for a class of nonlinear time-evolution systems

A variety of problems in nonlinear time-evolution systems such as communication networks, computer networks, manufacturing, traffic management, etc., can be modelled as min–max-plus systems in which operations of min, max and addition appear simultaneously. Systems with only maximum (or minimum) constraints can be modelled as max-plus system and handled by max-plus algebra which changes the original nonlinear system in the traditional sense into linear system in this framework. Min-max-plus systems are extensions of max-plus systems and nonlinear even in the max-plus algebra view. Output feedback stabilization for min–max-plus systems with min–max-plus inputs and max-plus outputs is considered in this paper. Max-plus projection representation for the closed-loop system with min–max-plus output feedback is introduced and the formula to calculate the cycle time is presented. Stabilization of reachable systems with at least one observable state and a further result for reachable and observable systems are worked out, during which max-plus output feedbacks are used to stabilize the systems. The method based on the max-plus algebra is constructive in nature.     

The number of simple modules of a cellular algebra

Let n be a natural number, and let A be an indecomposable cellular algebra such that the spectrum of its Cartan matrix C is of the form {n, 1, …., 1}. In general, not every natural number could be the number of non-isomorphic simple modules over such a cellular algebra. Thus, two natural questions arise: (1) which numbers could be the number of non-isomorphic simple modules over such a cellular algebra A ? (2) Given such a number, is there a cellular algebra such that its Cartan matrix has the desired property ? In this paper, we shall completely answer the first question, and give a partial answer to the second question by constructing cellular algebras with the pre-described Cartan matrix.     

Multicomplex algebras on polynomials and generalized Hamilton dynamics

Generator of the complex algebra within the framework of general formulation obeys the quadratic equation. In this paper we explore multicomplex algebra with the generator obeying n-order polynomial equation with real coefficients. This algebra induces generalized trigonometry ((n+1)-gonometry), underlies of the nth order oscillator model and nth order Hamilton equations. The solution of an evolution equation generated by (n×n) matrix is represented via the set of (n+1)-gonometric functions. The general form of the first constant of motion of the evolution equation is established.     

Essentially doubly stochastic matrices II. Canonical forms for row equivalence,equivalence, and a special case of congruence

In this paper we obtain canonical forms for row equivalence, equivalence, and a special case of congruence in the algebra of essentially doubly stochastic (e.d.s.) matrices of order n over a field F, char(F) [nmid] n. These forms are analogues of familiar forms in ordinary matrix algebra. The canonical form for equivalence is used in showing, in a subsequent paper, that every e.d.s. matrix of rank r and order n over F, char(F) = 0 or char(F) > n, is a product of elementary e.d.s. matrices, n – r of which are singular.     

Near-boolean algebras I: Combinatorial aspects

An algebra $\textcolor{red}{}\text{=(A; ?, ?, ′, 0, 1)}$ is near-boolean if every two generated subalgebra is a boolean algebra. It is shown that for n ? 4 there is a near-boolean algebra of size n ≡ 4 or 8 (mod 12), that for n ? 16 and n ≡ 4 or 8 (mod 12) there is a near-boolean algebra of size n which is not a boolean algebra, and that the smallest near-boolean algebra which is not a boolean algebra has 16 elements.     

Hamming graphs in Nomura algebras

Let A be an association scheme on q≥3 vertices. We show that the Bose-Mesner algebra of the generalized Hamming scheme H(n,A), for n?2, is not the Nomura algebra of any type II matrix.This result gives examples of formally self-dual Bose-Mesner algebras that are not the Nomura algebras of type II matrices.     

A note on matrix subalgebras containing a full Jordan block

Let A be a subalgebra of the full matrix algebra M_n(F), and suppose J∈A, where J is the Jordan block corresponding to xⁿ. Let $\text{S}$ be a set of generators of A. It is shown that the graph of $\text{S}$ determines whether A is the full matrix algebra M_n(F).     

Automorphisms of matrix algebras over commutative rings

The automorphisms of an n × n matrix algebra over a commutative ring can fail to be inner. The extent of this failure, however, is under control. For instance, the commutator of any two automorphisms and the nth power of each of them are necessarily inner.     

Global and local definition of the Monge–Ampère operator on compact Kähler manifolds

The aim of this Note is to give a sufficient condition in order for a function in the global domain of definition of the Monge–Ampère operator not to belong to the local domain of the former in the sense of Cegrell, when one looks at the n-dimensional complex projective space. Using this result, we show that the subsolution theorem is false for functions in the local domain of definition of the Monge–Ampère operator on such a projective space.     

A fast algorithm for the recursive calculation of dominant singular subspaces

In many engineering applications it is required to compute the dominant subspace of a matrix A   of dimension m×n$m\times n$, with m?n$m?n$. Often the matrix A is produced incrementally, so all the columns are not available simultaneously. This problem arises, e.g., in image processing, where each column of the matrix A represents an image of a given sequence leading to a singular value decomposition-based compression [S. Chandrasekaran, B.S. Manjunath, Y.F. Wang, J. Winkeler, H. Zhang, An eigenspace update algorithm for image analysis, Graphical Models and Image Process. 59 (5) (1997) 321–332]. Furthermore, the so-called proper orthogonal decomposition approximation uses the left dominant subspace of a matrix A where a column consists of a time instance of the solution of an evolution equation, e.g., the flow field from a fluid dynamics simulation. Since these flow fields tend to be very large, only a small number can be stored efficiently during the simulation, and therefore an incremental approach is useful [P. Van Dooren, Gramian based model reduction of large-scale dynamical systems, in: Numerical Analysis 1999, Chapman & Hall, CRC Press, London, Boca Raton, FL, 2000, pp. 231–247].     

A condition for the strong regularity of matrices in the minimax algebra

Columns of a matrix A in the minimax algebra are called strongly linearly independent if for some b the system of equations A?x = b is uniquely solvable (cf. [3]). This paper presents a condition which is necessary and sufficient for the strong linear independence of columns of a given matrix in the minimax algebra based on a dense linearly ordered commutative group. In the case of square matrices an O(n³) method for checking this property as well as for finding at least one b such that A?x = b is uniquely solvable is derived. A connection with the classical assignment problem is formulated.     

On the geometry of positive maps in matrix algebras. II

Geometric relations among the identity map, the transpose map, and the map $\text{τ(x)?}\text{1}\text{n}\text{(x)}\text{Tr}\text{(x)1}{}_{\mathrm{n}}$ in the matrix algebra M_n are illustrated, providing parametric examples of maps which are not k+1-positive but which satisfy the matrix Schwartz inequality of order k for 1 ? k ? n ? 1.