Combinatorics Seminar 2015

Speaker: Vladimir Yuryevich Protasov (Протасов Владимир Юрьевич), Moscow State University

Date: Mon, Nov 16, 2015

Time: 14:00 - 16:00

Venue: Middle Meeting Room

Title: Joint spectral radius of matrices: applications and computation


The joint spectral radius of a family of matrices is the exponent of the fastest possible growth of norms of their products with the length of the product. For one matrix, it coincides with the usual spectral radius which is the maximal modulus of eigenvalues of that matrix. Originated with G.C. Rota and G. Strang in 1960, the joint spectral radius has found numerous applications in dynamical systems, combinatorics, functional analysis, etc.

The problem of computation of the joint spectral radius is notoriously difficult. It is known to be NP-hard for Boolean matrices and algorithmically undecidable for large rational matrices. Nevertheless, recently several methods were elaborated. They are efficient for vast majority of matrix families.

We will discuss several applications of the joint spectral radius and a recent progress in the problem of its computation.

Slides: View slides