Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices

Vincent Blondel and Yu Nesterov
Additional contact information
Vincent Blondel: UNIVERSITE CATHOLIQUE DE LOUVAIN, Division of Applied Mathematics
Yu Nesterov: Université catholique de Louvain (UCL). Center for Operations Research and Econometrics (CORE)

No 2008034, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We propose two simple upper bounds for the joint spectral radius of sets of nonnegative matrices. These bounds, the joint column radius and the joint row radius, can be computed in polynomial time as solutions of convex optimization problems. We show that for general matrices these bounds are within a factor 1/n of the exact value, where n is the size of the matrices. Moreover, for sets of matrices with independent column uncertainties of with independent row uncertainties, the corresponding bounds coincide with the joint spectral radius. In these cases, the joint spectral radius is also given by the largest spectral radius of the matrices in the set. As a byproduct of these results, we propose a polynomial-time technique for solving Boolean optimization problems related to the spectral radius. We also consider economics and engineering applications of our results which were never considered practice due to their intrinsic computational complexity.

Keywords: joint spectral radius; joint column radius; joint row radius; nonnegative matrices; asynchronous systems; convex optimization; Leontief model. (search for similar items in EconPapers)
Date: 2008-05-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2008.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2008034

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().