@inproceedings{10.1007/978-3-031-10769-6_39,
    Abstract = {The long run behaviour of linear dynamical systems is often studied by looking at eventual properties of matrices and recurrences that underlie the system. A basic problem in this setting is as follows: given a set of pairs of rational weights and matrices {\$}{\$}{\backslash}{\{}(w{\\_}1, A{\\_}1), {\backslash}ldots , (w{\\_}m, A{\\_}m){\backslash}{\}}{\$}{\$}{\{}(w1,A1),{{\l}dots},(wm,Am){\}}, does there exist an integer N s.t for all {\$}{\$}n {\backslash}ge N{\$}{\$}n≥N, {\$}{\$}{\backslash}sum {\\_}{\{}i=1{\}}^m w{\\_}i{\backslash}cdot A{\\_}i^n {\backslash}ge 0{\$}{\$}∑i=1mwi{\textperiodcentered}Ain≥0(resp. {\$}{\$}> 0{\$}{\$}>0). We study this problem, its applications and its connections to linear recurrence sequences. Our first result is that for {\$}{\$}m{\backslash}ge 2{\$}{\$}m≥2, the problem is as hard as the ultimate positivity of linear recurrences, a long standing open question (known to be {\$}{\$}{\backslash}mathsf {\{}coNP{\}}{\$}{\$}coNP-hard). Our second result is that for any {\$}{\$}m{\backslash}ge 1{\$}{\$}m≥1, the problem reduces to ultimate positivity of linear recurrences. This yields upper bounds for several subclasses of matrices by exploiting known results on linear recurrence sequences. Our third result is a general reduction technique for a large class of problems (including the above) from diagonalizable case to the case where the matrices are simple (have non-repeated eigenvalues). This immediately gives a decision procedure for our problem for diagonalizable matrices.},
    Address = {Cham},
    Author = {Akshay, S. and Chakraborty, Supratik and Pal, Debtanu},
    BookTitle = {Automated Reasoning},
    Editor = {Blanchette, Jasmin and Kov{\'a}cs, Laura and Pattinson, Dirk},
    File = {On Eventual Non-negativity and Positivity for the Weighted Sum of Powers of Matrices - 978-3-031-10769-6\_39.pdf},
    ISBN = {978-3-031-10769-6},
    Pages = {671--690},
    Publisher = {Springer International Publishing},
    Title = {On Eventual Non-negativity and Positivity for the Weighted Sum of Powers of Matrices},
    Year = {2022},
    date-added = {2023-08-09 16:07:34 +0200},
    date-modified = {2023-08-09 16:07:34 +0200},
    doi = {10.1007/978-3-031-10769-6_39}
}

@inproceedings{10.1007/978-3-031-10769-6_39, Abstract = {The long run behaviour of linear dynamical systems is often studied by looking at eventual properties of matrices and recurrences that underlie the system. A basic problem in this setting is as follows: given a set of pairs of rational weights and matrices {\$}{\$}{\backslash}{{}(w{\}1, A{\}1), {\backslash}ldots , (w{\}m, A{\}m){\backslash}{}}{\$}{\$}{{}(w1,A1),{{\l}dots},(wm,Am){}}, does there exist an integer N s.t for all {\$}{\$}n {\backslash}ge N{\$}{\$}n≥N, {\$}{\$}{\backslash}sum {\}{{}i=1{}}^m w{\}i{\backslash}cdot A{\_}i^n {\backslash}ge 0{\$}{\$}∑i=1mwi{\textperiodcentered}Ain≥0(resp. {\$}{\$}> 0{\$}{\$}>0). We study this problem, its applications and its connections to linear recurrence sequences. Our first result is that for {\$}{\$}m{\backslash}ge 2{\$}{\$}m≥2, the problem is as hard as the ultimate positivity of linear recurrences, a long standing open question (known to be {\$}{\$}{\backslash}mathsf {{}coNP{}}{\$}{\$}coNP-hard). Our second result is that for any {\$}{\$}m{\backslash}ge 1{\$}{\$}m≥1, the problem reduces to ultimate positivity of linear recurrences. This yields upper bounds for several subclasses of matrices by exploiting known results on linear recurrence sequences. Our third result is a general reduction technique for a large class of problems (including the above) from diagonalizable case to the case where the matrices are simple (have non-repeated eigenvalues). This immediately gives a decision procedure for our problem for diagonalizable matrices.}, Address = {Cham}, Author = {Akshay, S. and Chakraborty, Supratik and Pal, Debtanu}, BookTitle = {Automated Reasoning}, Editor = {Blanchette, Jasmin and Kov{\'a}cs, Laura and Pattinson, Dirk}, File = {On Eventual Non-negativity and Positivity for the Weighted Sum of Powers of Matrices - 978-3-031-10769-6_39.pdf}, ISBN = {978-3-031-10769-6}, Pages = {671--690}, Publisher = {Springer International Publishing}, Title = {On Eventual Non-negativity and Positivity for the Weighted Sum of Powers of Matrices}, Year = {2022}, date-added = {2023-08-09 16:07:34 +0200}, date-modified = {2023-08-09 16:07:34 +0200}, doi = {10.1007/978-3-031-10769-6_39} }