Conference item icon

Conference item

On matrix powering in low dimensions

Abstract:
We investigate the Matrix Powering Positivity Problem, PosMatPow: given an m×m square integer matrix M, a linear function f : Z m×m → Z with integer coefficients, and a positive integer n (encoded in binary), determine whether f(Mn) ≥ 0. We show that for fixed dimensions m of 2 and 3, this problem is decidable in polynomial time
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
  • (Version of record, pdf, 638.2KB)
Publisher copy:
10.4230/LIPIcs.STACS.2015.329

Authors


More by this author
Institution:
University of Oxford
Oxford college:
St John's College
Role:
Author
More by this author
Institution:
University of Oxford
Oxford college:
Green Templeton College
Role:
Author

Contributors

Role:
Editor
Role:
Editor
Publisher:
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Host title:
Leibniz International Proceedings in Informatics, LIPIcs
Journal:
Leibniz International Proceedings in Informatics, LIPIcs More from this journal
Volume:
30
Pages:
329-340
Publication date:
2015-01-01
DOI:
ISSN:
1868-8969
ISBN:
9783939897781
Keywords:
Pubs id:
pubs:510390
UUID:
uuid:1e307bb5-4289-4014-ad04-cb4639dc603e
Local pid:
pubs:510390
Source identifiers:
510390
Deposit date:
2016-08-11

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP