LIGO Detectors and Data Analyses:

Stable Pairs of Matrices, Sturmian Sequences, Devil's Staircases and Conic Optimization



Université Catholique de Louvain

MONDAY, MAY 3, 2004

4:15 pm



We survey several aspects of an apparently simple matrix question: given two square matrices A and B, how to verify that all possible infinite products of the type ABBABAAAB... converge to zero?

This question arises in a number of applications, which we briefly describe (including hybrid systems, wavelets and the design of codes). We prove that the related problem of determining if all infinite products remain bounded, is algorithmically undecidable. We then exhibit the occurrence of Sturmian sequences and of a devil's staircase in the analysis of possible optimal periodic products. We conclude with a recent efficient approximation algorithm based on conic optimization and semi-definite liftings. All these results allow a better understanding of the problem, which we will nevertheless leave unsolved.

The results reported have been obtained in part with J. Tsitsiklis, A. Vladimirov and Y. Nesterov.

Return to Applied Math Colloquium home page