Exponentiation-by-squaring is usually phrased as the problem of computing X^n, but its actually usually more natural to ask about X^n Y. Unlike finding X^n directly, this reduces directly to another instance of the same problem.

  X^n Y = (X^2)^(n/2) Y if n is even
  X^n Y = X^(n-1) (XY) if n is odd

So you don't really need to take a full matrix-matrix product; you only need to square a matrix, X^2, and take a matrix-vector product, XY.

In the case of Fibonacci matrices, they can be represented with their first column only since they have the form

  A  B
  B A+B

so these are just

  square (A, B) = (AA+BB, 2AB+BB)
  mulVec (A, B) (u, v) = (Au+Bv, Av+B(u+v))