Solvability of Matrix-Exponential Equations

DOI10.1145/2933575.2934538MaRDI QIDQ4635944zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1601.05002, https://ora.ox.ac.uk/objects/uuid:81df8e97-aa74-4803-bb6c-c83c37ef9daf

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)

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.

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

Cited in

(8)

• On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
• 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
• The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
• scientific article; zbMATH DE number 7559488 (Why is no real title available?)
• EXPLICIT SOLUTION FORMULAS FOR THE MATRIX-KP
• On the decidability of membership in matrix-exponential semigroups
• scientific article; zbMATH DE number 1159574 (Why is no real title available?)

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)