Search

In this paper, we consider the conditional affine eigenvalue problem lambda x = Ax + b, lambda is an element of R, x >= 0, parallel to x parallel to = 1, where A is an n x n nonnegative matrix, b a nonnegative vector, and parallel to center dot parallel to a monotone vector norm. Under suitable hypotheses, we prove the existence and uniqueness of the solution (lambda(*), x(*)) and give its expression as the Perron root and vector of a matrix A + bc(*)(T) where c(*) has a maximizing property depending on the considered norm. The equation x (Ax + b)/ parallel to Ax + b parallel to has then a unique nonnegative solution, given by the unique Perron vector of A + bc(*)(T). (c) 2005 Elsevier Inc. All rights reserved.

The joint spectral radius of a set of matrices is a measure of the maximal asymptotic growth rate that can be obtained by forming long products of matrices taken from the set. This quantity appears in a number of application contexts but is notoriously difficult to compute and to approximate. We introduce in this paper an approximation \hat \rho that is based on ellipsoid norms, that can be computed by convex optimization, and that is such that the joint spectral radius belongs to the interval [\hat \rho/\sqrt{n},\hat \rho] where n is the dimension of the matrices. We also provide a simple approximation for the special case where the entries of the matrices are non-negative; in this case the approximation is proved to be within a factor at most m (m is the number of matrices) of the exact value.

We show that the problem of determining if a given integer linear recurrent sequence has a zero-a problem that is known as "Pisot's problem"-is NP-hard. With a similar argument we show that the problem of finding the minimal realization dimension of a one-letter max-plus rational series is NP-hard. This last result answers a folklore question raised in the control literature on the max-plus approach to discrete event systems. Our results are simple consequences of a construction due to Stockmeyer and Meyer. (C) 2002 Elsevier Science Inc. All rights reserved.