Constructive Solution of the Common Invariant Cone Problem

Abstract.

Families of [Formula: see text] matrices sharing a common invariant cone enjoy special properties that are widely used in applications. However, finding this cone or even proving its existence or nonexistence is hard. This problem is known to be algorithmically undecidable for general families of matrices. We show that in many cases, it can nevertheless be solved efficiently. We present an algorithm that, given a finite family of matrices, either finds a common invariant cone or proves its nonexistence. Numerical results demonstrate that the algorithm works for a vast majority of matrix families. The structure and properties of the minimal and maximal invariant cones are analyzed. Applications to dynamical systems and combinatorics are considered.

Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SIMAX and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at gitlab.com/-tommsch/ttoolboxes/-/tree/9d933e7 . Click the button labeled “Code," and choose “zip." Then extract the zip file to a location of your choice (e.g., "C:\ttoolboxes"). After starting MATLAB, open a file in the subfolder ./demo/kone (e.g., "C:\ttoolboxes\demo_assess_kone_algorithm_primal_dual.m"), and follow the instructions therein. [Formula: see text]