26
$\begingroup$

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)), 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?

Improve this question
$\endgroup$
8
  • 4
    $\begingroup$ Shouldn't the title be changed to "Complexity of matrix powering"? Matrix exponentiation (see e.g. en.wikipedia.org/wiki/Matrix_exponential) is generally understood as "A=exp(B)" for matrices A,B. $\endgroup$
    – Martin Schwarz
    Oct 1, 2012 at 7:54
  • $\begingroup$ I'll edit it. that's a good point, @MartinSchwarz $\endgroup$
    – Suresh Venkat
    Oct 1, 2012 at 8:02
  • $\begingroup$ 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. $\endgroup$
    – Robert Mason
    Oct 2, 2012 at 21:12
  • $\begingroup$ @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. $\endgroup$
    – Joel
    Oct 2, 2012 at 22:09
  • 1
    $\begingroup$ @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.) $\endgroup$
    – Joel
    Oct 3, 2012 at 19:35

1 Answer 1

Reset to default
12
$\begingroup$

For matrices of sizes $k = 2,3$ the Matrix Powering Positivity Problem is in $\mathsf{P}$ (cf. this paper to appear in STACS 2015)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Couldn't resist posting this! :-) $\endgroup$
    – SamiD
    Dec 12, 2014 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.