Solvability of matrix-exponential equationsReport as inadecuate

Solvability of matrix-exponential equations - Download this document for free, or read online. Document in PDF available to download.

Reference: Ouaknine, J, Pouly, A, Sousa-Pinto, J et al., (2016). Solvability of matrix-exponential equations. Thirty-First Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016).Citable link to this page:


Solvability of matrix-exponential equations

Abstract: We consider a continuous analogue of (Babai et al. 1996)'s and (Cai et al. 2000)'s problem of solving multiplicative matrix equations. Given k + 1 square matrices A1,

., Ak, C, all of the same dimension, whose entries are real algebraic, we examine the problem of deciding whether there exist non-negative reals t1,

., tk such that We show that this problem is undecidable in general, but decidable under the assumption that the matrices A1,

., Ak 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.

Publication status:PublishedPeer Review status:Peer reviewedVersion:Publisher's versionDate of acceptance:2016-04-04Notes:Copyright © held by owner/author(s). Publication rights licensed to ACM.

Bibliographic Details

Publisher: Association for Computing Machinery

Publisher Website:

Host: Thirty-First Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016)see more from them

Publication Website:

Volume: 05-08-July-2016

Extent: 798-806

Issue Date: 2016-07Identifiers


Issn: 1043-6871

Uuid: uuid:81df8e97-aa74-4803-bb6c-c83c37ef9daf

Urn: uri:81df8e97-aa74-4803-bb6c-c83c37ef9daf

Pubs-id: pubs:593811 Item Description

Type: conference-paper;

Version: Publisher's versionKeywords: exponential matrices matrix reachability matrix logarithms commuting matrices hybrid automata


Author: Ouaknine, J - Oxford, MPLS, Computer Science - - - Pouly, A - - - Sousa-Pinto, J - - - Worrell, J - Oxford, MPLS, Computer Scienc



Related documents