<p>For matrices of sizes $k = 2,3$ the <strong>Matrix Powering Positivity Problem</strong> is in $\mathsf{P}$ (cf. <a href="https://www.cs.ox.ac.uk/people/joel.ouaknine/publications/matrix-powering15abs.html">this</a> paper to appear in STACS 2015)</p>

CC BY-SA 3.0
2014-12-12T20:03:54.520Z
Couldn't resist posting this! :-)
SamiD
CC BY-SA 3.0
2014-12-12T20:02:33.120Z
2014-12-12T20:02:33.120Z
SamiD
<p>Let $M$ be a square integer matrix, and let $n$ be a positive integer. I am interested in the complexity of the following decision problem:</p>

<p>Is the top-right entry of $M^n$ positive?</p>

<p>Note that the obvious approach of iterated squaring (or any other explicit calculation) requires us to potentially handle integers of doubly exponential magnitude, i.e., having exponentially many bits. However the problem is easily seen to be in Allender et al.'s "PosSLP" class (<a href="http://epubs.siam.org/doi/abs/10.1137/070697926">"On the Complexity of Numerical Analysis", SIAM J. Comput. 38(5)</a>), and therefore in the fourth level of the counting hierarchy.</p>

<p>1) Is it possible to place this matrix powering problem in a lower complexity class?</p>

<p>2) If not, could it conceivably be PosSLP-hard?</p>

<p>3) I am especially interested in the matrix powering problem for low-dimensional matrices, i.e. up to and including 6x6 matrices. Might the complexity be lower for such matrices?</p>

CC BY-SA 3.0
2012-10-01T07:54:06.577Z
Shouldn't the title be changed to "Complexity of matrix powering"? Matrix exponentiation (see e.g. http://en.wikipedia.org/wiki/Matrix_exponential) is generally understood as "A=exp(B)" for matrices A,B.
Martin Schwarz
CC BY-SA 3.0
2012-10-01T08:02:56.130Z
I'll edit it. that's a good point, @MartinSchwarz
Suresh Venkat
CC BY-SA 3.0
2012-10-02T21:12:48.180Z
If you transform the matrix into PDP-1 form (which for a small matrix and sufficiently high power of n can be considered constant), then you can know the sign of each entry of the diagonal entries trivially.  Then it's easy to figure out the remaining two matrix multiplications.
Robert Mason
CC BY-SA 3.0
2012-10-02T22:09:08.157Z
@Robert Mason: I'm not exactly sure what you're suggesting. If D is the Jordan canonical form of M, so that M^n = P^(-1) D^n P, then the entries of D will typically be complex algebraic numbers, so what do you mean by their "sign"? I agree you can compute D and P in polynomial time (assuming standard representations of algebraic numbers), but the expression you get for the top-right entry of M^n = P^(-1) D^n P will be an expression involving various algebraic numbers raised to the power n, and I don't see how you can determine the sign of this expression efficiently.
Joel
CC BY-SA 3.0
2012-10-02T22:11:07.907Z
P.S. We can't necessarily assume that M is diagonalisable, but even if it is, I still don't see how this approach can yield anything more efficient than PosSLP...
Joel
CC BY-SA 3.0
2012-10-03T12:26:24.540Z
You are correct.  It somehow slipped my mind that this is only efficient for invertable matrices, which is a tiny subset of the square matrices.
Robert Mason
CC BY-SA 3.0
2012-10-03T19:35:32.173Z
@Robert Mason: I still don't understand -- how/why is this efficient for invertible matrices? (And incidentally, "most" matrices are invertible, rather than the opposite.)
Joel
CC BY-SA 3.0
2013-10-23T19:59:06.803Z
From Threshold Circuits for iterated Matrix Product and Powering by
Carlo Mereghetti and Beatrice Palano (where the problem for unary powers
has been dealt with; see Section 3), it is clear that we need to find
$x^N \bmod{\chi(x)}$ where $\chi(x)$ is the characteristic polynomial of the
matrix $A$ and we want to find $A^N$. This is so because if we write:
$x^N = q(x)\chi(x) + r(x)$ where $deg(r) < deg(\chi)$ then by
the Cayley Hamilton Theorem, $A^N = r(A)$. Note that $r(x)$ will have
doubly exponential coefficients if $N$ is an $n$-bit number.
SamiD
<cc.complexity-theory><linear-algebra><matrices>
Complexity of matrix powering
Joel
# Complexity of matrix powering

(Asked by: username_0 on 2012-10-01)

Let $M$ be a square integer matrix, and let $n$ be a positive integer. I am interested in the complexity of the following decision problem:

Is the top-right entry of $M^n$ positive?

Note that the obvious approach of iterated squaring (or any other explicit calculation) requires us to potentially handle integers of doubly exponential magnitude, i.e., having exponentially many bits. However the problem is easily seen to be in Allender et al.'s "PosSLP" class (["On the Complexity of Numerical Analysis", SIAM J. Comput. 38(5)](http://epubs.siam.org/doi/abs/10.1137/070697926)), and therefore in the fourth level of the counting hierarchy.

1) Is it possible to place this matrix powering problem in a lower complexity class?

2) If not, could it conceivably be PosSLP-hard?

3) I am especially interested in the matrix powering problem for low-dimensional matrices, i.e. up to and including 6x6 matrices. Might the complexity be lower for such matrices?

**Tags:** cc.complexity-theory, linear-algebra, matrices

> **Comments:**
> **username_1**: Shouldn't the title be changed to "Complexity of matrix powering"? Matrix exponentiation (see e.g. http://en.wikipedia.org/wiki/Matrix_exponential) is generally understood as "A=exp(B)" for matrices A,B.  
> **username_2**: I'll edit it. that's a good point, @MartinSchwarz  
> **username_3**: If you transform the matrix into PDP-1 form (which for a small matrix and sufficiently high power of n can be considered constant), then you can know the sign of each entry of the diagonal entries trivially.  Then it's easy to figure out the remaining two matrix multiplications.  
> **username_0**: @username_3: I'm not exactly sure what you're suggesting. If D is the Jordan canonical form of M, so that M^n = P^(-1) D^n P, then the entries of D will typically be complex algebraic numbers, so what do you mean by their "sign"? I agree you can compute D and P in polynomial time (assuming standard representations of algebraic numbers), but the expression you get for the top-right entry of M^n = P^(-1) D^n P will be an expression involving various algebraic numbers raised to the power n, and I don't see how you can determine the sign of this expression efficiently.  
> **username_0**: P.S. We can't necessarily assume that M is diagonalisable, but even if it is, I still don't see how this approach can yield anything more efficient than PosSLP...  
> **username_3**: You are correct.  It somehow slipped my mind that this is only efficient for invertable matrices, which is a tiny subset of the square matrices.  
> **username_0**: @username_3: I still don't understand -- how/why is this efficient for invertible matrices? (And incidentally, "most" matrices are invertible, rather than the opposite.)  
> **username_4**: From Threshold Circuits for iterated Matrix Product and Powering by Carlo Mereghetti and Beatrice Palano (where the problem for unary powers has been dealt with; see Section 3), it is clear that we need to find $x^N \bmod{\chi(x)}$ where $\chi(x)$ is the characteristic polynomial of the matrix $A$ and we want to find $A^N$. This is so because if we write: $x^N = q(x)\chi(x) + r(x)$ where $deg(r) < deg(\chi)$ then by the Cayley Hamilton Theorem, $A^N = r(A)$. Note that $r(x)$ will have doubly exponential coefficients if $N$ is an $n$-bit number.  

---

## 1 answers

### Answer by username_4 on 2014-12-12. Score: 12

For matrices of sizes $k = 2,3$ the **Matrix Powering Positivity Problem** is in $\mathsf{P}$ (cf. [this](https://www.cs.ox.ac.uk/people/joel.ouaknine/publications/matrix-powering15abs.html) paper to appear in STACS 2015)

> **Comments:**
> **username_4**: Couldn't resist posting this! :-)  

---

