Solvability of matrix-exponential equations
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 e...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Published: |
Association for Computing Machinery
2016
|
| _version_ | 1826282004416561152 |
|---|---|
| author | Ouaknine, J Pouly, A Sousa-Pinto, J Worrell, J |
| author_facet | Ouaknine, J Pouly, A Sousa-Pinto, J Worrell, J |
| author_sort | Ouaknine, J |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T00:37:20Z |
| format | Conference item |
| id | oxford-uuid:81df8e97-aa74-4803-bb6c-c83c37ef9daf |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:37:20Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:81df8e97-aa74-4803-bb6c-c83c37ef9daf2022-03-26T21:33:14ZSolvability of matrix-exponential equationsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:81df8e97-aa74-4803-bb6c-c83c37ef9dafSymplectic Elements at OxfordAssociation for Computing Machinery2016Ouaknine, JPouly, ASousa-Pinto, JWorrell, JWe 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. |
| spellingShingle | Ouaknine, J Pouly, A Sousa-Pinto, J Worrell, J Solvability of matrix-exponential equations |
| title | Solvability of matrix-exponential equations |
| title_full | Solvability of matrix-exponential equations |
| title_fullStr | Solvability of matrix-exponential equations |
| title_full_unstemmed | Solvability of matrix-exponential equations |
| title_short | Solvability of matrix-exponential equations |
| title_sort | solvability of matrix exponential equations |
| work_keys_str_mv | AT ouakninej solvabilityofmatrixexponentialequations AT poulya solvabilityofmatrixexponentialequations AT sousapintoj solvabilityofmatrixexponentialequations AT worrellj solvabilityofmatrixexponentialequations |