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?

$\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$ Oct 1, 2012 at 7:54
  • $\begingroup$ I'll edit it. that's a good point, @MartinSchwarz $\endgroup$ 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$ 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

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)

$\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, privacy policy and cookie policy

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