On generalized inverses and Green’s relations

We study generalized inverses on semigroups by means of Green’s relations. We first define the notion of inverse along an element and study its properties. Then we show that the classical generalized inverses (group inverse, Drazin inverse and Moore-Penrose inverse) belong to this class.     

On local integrability and transience of convolution semigroups of measures

The analytic proof due to M. Itô of the Kesten-Ornstein transience criterion for continuous convolution semigroups of nonnegative contraction measures on a compactly generated Abelian locally compact group has been reworked and given a self-contained form. The new proof still relies on the existence of the equilibrium measure but dispenses with the complete maximum principle.     

Nonnegative matrices with prescribed spectrum and elementary divisors

In this paper we give new sufficient conditions for the existence and construction of nonnegative matrices with prescribed elementary divisors, which drastically improve and contain some of the previous known conditions. We also show how to perturb complex eigenvalues of a nonnegative matrix while keeping its nonnegativity. These results allow us, under certain conditions, to easily decide if a given list is realizable with prescribed elementary divisors.     

Ω-compact semigroups having congruence extension property

The congruence extension property (CEP) of semigroups has been extensively studied by a number of authors. We call a compact semigroup S an Ω-compact semigroup if the set of all regular elements of S forms an ideal of S. In this note, we characterize the Ω-compact semigroup having (CEP). Our result extends a recent result obtained by X.J. Guo on the congruence extension property of strong Ω-compact semigroups which is a semigroup containing precisely one regular D-class.     

On visualization scaling, subeigenvectors and Kleene stars in max algebra

The purpose of this paper is to investigate the interplay arising between max algebra, convexity and scaling problems. The latter, which have been studied in nonnegative matrix theory, are strongly related to max algebra. One problem is that of strict visualization scaling, defined as, for a given nonnegative matrix A, a diagonal matrix X such that all elements of X^-1AX are less than or equal to the maximum cycle geometric mean of A, with strict inequality for the entries which do not lie on critical cycles. In this paper such scalings are described by means of the max algebraic subeigenvectors and Kleene stars of nonnegative matrices as well as by some concepts of convex geometry.     

Nonnegative matrix semigroups with finite diagonals

Let S be a multiplicative semigroup of matrices with nonnegative entries. Assume that the diagonal entries of the members of S form a finite set. This paper is concerned with the following question: Under what circumstances can we deduce that S itself is finite?     

Temperley-Lieb Immanants

We use the Temperley-Lieb algebra to define a family of totally nonnegative polynomials of the form . The cone generated by these polynomials contains all totally nonnegative polynomials of the form , where, are matrix minors. We also give new conditions on the sets I,...,K′ which characterize differences of products of minors which are totally nonnegative. Received September 30, 2004     

Google PageRanking problem: The model and the analysis

The spectral and Jordan structures of the Web hyperlink matrix G(c)=cG+(1−c)ev^T have been analyzed when G is the basic (stochastic) Google matrix, c is a real parameter such that 0<c<1, v is a nonnegative probability vector, and e is the all-ones vector. Typical studies have relied heavily on special properties of nonnegative, positive, and stochastic matrices. There is a unique nonnegative vector y(c) such that y(c)^TG(c)=y(c)^T and y(c)^Te=1. This PageRank vector y(c) can be computed effectively by the power method.We consider a square complex matrix A and nonzero complex vectors x and v such that Ax=λx and v^∗x=1. We use standard matrix analytic tools to determine the eigenvalues, the Jordan blocks, and a distinguished left λ-eigenvector of A(c)=cA+(1−c)λxv^∗ as a function of a complex variable c. If λ is a semisimple eigenvalue of A, there is a uniquely determined projection N such that lim_c→1y(c)=Nv for all v; this limit may fail to exist for some v if λ is not semisimple. As a special case of our results, we obtain a complex analog of PageRank for the Web hyperlink matrix G(c) with a complex parameter c. We study regularity, limits, expansions, and conditioning of y(c) and we propose algorithms (e.g., complex extrapolation, power method on a modified matrix etc.) that may provide an efficient way to compute PageRank also with c close or equal to 1. An interpretation of the limit vector Nv and a related critical discussion on the model, on its adherence to reality, and possible ways for its improvement, represent the contribution of the paper on modeling issues.     

Semigroup of matrices acting on the max-plus projective space

We investigate the action of semigroups of d×d matrices with entries in the max-plus semifield on the max-plus projective space. Recall that semigroups generated by one element with projectively bounded image are projectively finite and thus contain idempotent elements.In terms of orbits, our main result states that the image of a minimal orbit by an idempotent element of the semigroup with minimal rank has at most d! elements. Moreover, each idempotent element with minimal rank maps at least one orbit onto a singleton.This allows us to deduce the central limit theorem for stochastic recurrent sequences driven by independent random matrices that take countably many values, as soon as the semigroup generated by the values contains an element with projectively bounded image.     

Algorithmic copositivity detection by simplicial partition

We present new criteria for copositivity of a matrix, i.e., conditions which ensure that the quadratic form induced by the matrix is nonnegative over the nonnegative orthant. These criteria arise from the representation of the quadratic form in barycentric coordinates with respect to the standard simplex and simplicial partitions thereof. We show that, as the partition gets finer and finer, the conditions eventually capture all strictly copositive matrices. We propose an algorithmic implementation which considers several numerical aspects. As an application, we present results on the maximum clique problem. We also briefly discuss extensions of our approach to copositivity with respect to arbitrary polyhedral cones.     

Triangularizability of Polynomially Compact Operators

An operator on a complex Banach space is polynomially compact if a non-zero polynomial of the operator is compact, and power compact if a power of the operator is compact. Theorems on triangularizability of algebras (resp. semigroups) of compact operators are shown to be valid also for algebras (resp. semigroups) of polynomially (resp. power) compact operators, provided that pairs of operators have compact commutators.     

Enveloping semigroups in topological dynamics

This is a survey of the theory of enveloping semigroups in topological dynamics. We review the, already classical, theory of enveloping semigroups, due mainly to Robert Ellis, and then proceed to describe some new connections which were discovered in the last few years between three seemingly unrelated theories: of enveloping semigroups, of chaotic behavior, and of representation of dynamical systems on Banach spaces.     

Bounds on the number of numerical semigroups of a given genus

Lower and upper bounds are given for the number n_g of numerical semigroups of genus g. The lower bound is the first known lower bound while the upper bound significantly improves the only known bound given by the Catalan numbers. In a previous work the sequence n_g is conjectured to behave asymptotically as the Fibonacci numbers. The lower bound proved in this work is related to the Fibonacci numbers and so the result seems to be in the direction to prove the conjecture. The method used is based on an accurate analysis of the tree of numerical semigroups and of the number of descendants of the descendants of each node depending on the number of descendants of the node itself.     

Permanent Semigroups

A permanent semigroup is a semigroup of n × n matrices on which the permanent function is multiplicative. If the underlying ring is an infinite integral domain with characteristic p > n or characteristic 0 we prove that any permanent semigroup consists of matrices with at most one nonzero diagonal. The same result holds if the ring is a finite field with characteristic p > n and at least n²+n elements. We also consider the Kronecker product of permanent semigroups and show that the Kronecker product of permanent semigroups is a permanent semigroup if and only if the pennanental analogue of the formula for the determinant of a Kronecker product of two matrices holds. This latter result holds even when the matrix entries are from a commutative ring with unity.     

Totally nonnegative cells and matrix Poisson varieties

We describe explicitly the admissible families of minors for the totally nonnegative cells of real matrices, that is, the families of minors that produce nonempty cells in the cell decompositions of spaces of totally nonnegative matrices introduced by A. Postnikov. In order to do this, we relate the totally nonnegative cells to torus orbits of symplectic leaves of the Poisson varieties of complex matrices. In particular, we describe the minors that vanish on a torus orbit of symplectic leaves, we prove that such families of minors are exactly the admissible families, and we show that the nonempty totally nonnegative cells are the intersections of the torus orbits of symplectic leaves with the spaces of totally nonnegative matrices.     

Intervals of totally nonnegative matrices

Totally nonnegative matrices, i.e., matrices having all their minors nonnegative, and matrix intervals with respect to the checkerboard ordering are considered. It is proven that if the two bound matrices of such a matrix interval are nonsingular and totally nonnegative (and in addition all their zero minors are identical) then all matrices from this interval are also nonsingular and totally nonnegative (with identical zero minors).