Solvability of Matrix-Exponential Equations

DOI10.1145/2933575.2934538zbMATH Open1395.15012arXiv1601.05002OpenAlexW2290727773MaRDI QIDQ4635944FDOQ4635944

Authors: Joël Ouaknine, Amaury Pouly, J. Sousa Pinto, James Worrell 

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Abstract: We consider a continuous analogue of Babai et al.'s and Cai et al.'s problem of solving multiplicative matrix equations. Given $k+1$ square matrices $A_1,ldots,A_k,C$, all of the same dimension, whose entries are real algebraic, we examine the problem of deciding whether there exist non-negative reals $t_1,ldots,t_k$ such that �egin{align*} prod limits_{i=1}^{k} exp(A_{i} t_{i}) = C . end{align*} We show that this problem is undecidable in general, but decidable under the assumption that the matrices $A_1,ldots,A_k$ commute. Our results have applications to reachability problems for linear hybrid automata. Our decidability proof relies on a number of theorems from algebraic and transcendental number theory, most notably those of Baker, Kronecker, Lindemann, and Masser, as well as some useful geometric and linear-algebraic results, including the Minkowski-Weyl theorem and a new (to the best of our knowledge) result about the uniqueness of strictly upper triangular matrix logarithms of upper unitriangular matrices. On the other hand, our undecidability result is shown by reduction from Hilbert's Tenth Problem.

Full work available at URL: https://arxiv.org/abs/1601.05002

Recommendations

• The explicit solutions and solvability of linear matrix equations
• A note on exact solutions to linear differential equations by the matrix exponential
• On exact solutions for some matrix equations
• scientific article; zbMATH DE number 3877356
• Solvability for a nonlinear matrix equation
• scientific article; zbMATH DE number 1159574
• scientific article; zbMATH DE number 1743693
• On solvability of matrix polynomial equations
• On equivalence and explicit solutions of a class of matrix equations
• Solvability of matrix inequalities

zbMATH Keywords

hybrid automatacommuting matricesmatrix logarithmsexponential matricesmatrix reachability

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Matrix exponential and similar functions of matrices (15A16) Matrix equations and identities (15A24) Decidability (number-theoretic aspects) (11U05)

Cited In (8)

• Title not available (Why is that?)
• Title not available (Why is that?)
• The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
• On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
• EXPLICIT SOLUTION FORMULAS FOR THE MATRIX-KP
• On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
• Closed form solutions for matrix linear systems using double matrix exponential functions
• On the decidability of membership in matrix-exponential semigroups

This page was built for publication: Solvability of Matrix-Exponential Equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635944)