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$
  • 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 '12 at 7:54
  • $\begingroup$ I'll edit it. that's a good point, @MartinSchwarz $\endgroup$ – Suresh Venkat Oct 1 '12 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 '12 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 '12 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 '12 at 19:35
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$
  • $\begingroup$ Couldn't resist posting this! :-) $\endgroup$ – SamiD Dec 12 '14 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.