0
$\begingroup$

Before this is closed for duplicate, know that I have read the following posts:

A product function for matrix products

Taking the product of a list of matrices [duplicate]

I need to multiply a series of matrices

All of these give good answer to the question of multiplying a list of matrices where the number of matrices to be multiplied is known. However, none of these work if I want to keep the number of matrices unknown, i.e. symbolic.

My particular problem is that I have a matrix sequence $A_k = \begin{bmatrix} \psi(k) & \phi(k) \\ 1 & 0 \end{bmatrix}$, and I need to be able to compute the products $\prod_{k=n}^m A_k = A_n A_{n-1}\dots A_{m+1}A_m$, when $m < n$ as a general function of $n$ and $m$.To be clear, $n$ and $m$ are not known, and will never be known throughout the problem, so making a list in the standard way won't work (Mathematica will give "Iterator does not have appropriate bounds" if the bounds are not defined). Is there a way to do this in Mathematica?

Edit: For example, suppose $\psi(k)\equiv0$. Then the product $(\prod_{k=n}^1 A_k)Y_1$ solves the recurrence relation $y_{n+2}=\phi(n)y_n$, with $Y_1 = [y_2 \ y_1]^T$ known. Solving this recurrence relation with Mathematica gives an awful mess. However, one can see that the matrix product $\prod_{k=n}^1 A_k = \begin{bmatrix} \left(\frac{1+(-1)^n}{2}\right)\prod_{j=1}^{\lfloor \frac{n}{2} \rfloor} \phi(2j) & \left(\frac{1+(-1)^{n+1}}{2}\right)\prod_{j=1}^{\lfloor \frac{n+1}{2} \rfloor} \phi(2j-1) \\ \left(\frac{1+(-1)^{n+1}}{2}\right)\prod_{j=1}^{\lfloor \frac{n-1}{2} \rfloor} \phi(2j) & \left(\frac{1+(-1)^n}{2}\right)\prod_{j=1}^{\lfloor \frac{n}{2} \rfloor} \phi(2j-1) \end{bmatrix}$ gives a much simpler solution (though still quite messy), and if we restrict $n$ to being either even or odd, it simplifies even further.

Ideally, I'd like a Mathematica function which could give me a form like this, or at least the simpler form if I add the restriction that $n$ is even or odd. Something like

matrixProduct[A[k],{k,n,1}]

or

matrixProduct[A[k],{k,n,1},Element[k/2,Integers]]

which could at least attempt to spit out a solution in this form.

$\endgroup$
  • $\begingroup$ Looks awfully like this problem. I give a solution there based on DifferenceRoot[]. $\endgroup$ – J. M. will be back soon Mar 28 '18 at 20:20
  • $\begingroup$ Thanks, I'll go check that out. Should I delete this or can it be closed? $\endgroup$ – AlexanderJ93 Mar 28 '18 at 20:23
  • $\begingroup$ If anything in there doesn't apply to your problem, just edit your question to explain why. $\endgroup$ – J. M. will be back soon Mar 28 '18 at 20:26
  • $\begingroup$ I've added an edit to the question. The method from your other answer doesn't seem to do what I need it to, though I may be misunderstanding. $\endgroup$ – AlexanderJ93 Mar 28 '18 at 23:22
1
$\begingroup$

As I wrote in the comments, your product of matrices can be cast as a three term recurrence, similar to the other answer I wrote. The catch here is that since $\psi(k)$ and $\phi(k)$ are arbitrary functions, we do not have recourse to DifferenceRoot[]. We thus fall back to the old trick for recursively evaluating functions through memoization:

y1[0] = 1; y1[1] = ψ[1];
y1[k_Integer?Positive] := y1[k] = ψ[k] y1[k - 1] + ϕ[k] y1[k - 2];
y2[0] = 0; y2[1] = ϕ[1];
y2[k_Integer?Positive] := y2[k] = ψ[k] y2[k - 1] + ϕ[k] y2[k - 2];

We can now verify that these recurrences give the same results as the explicit matrix product:

With[{n = 10}, 
     Dot @@ Table[{{ψ[k], ϕ[k]}, {1, 0}}, {k, n, 1, -1}] ==
     {{y1[n], y2[n]}, {y1[n - 1], y2[n - 1]}} // Simplify]
   True

In the "arbitrary bounds" case, just construct the product up to $m$ and the product up to $n$, and multiply one with the inverse of the other:

With[{m = 3, n = 7}, 
     Dot @@ Table[{{ψ[k], ϕ[k]}, {1, 0}}, {k, n, m, -1}] ==
     {{y1[n], y2[n]}, {y1[n - 1], y2[n - 1]}}.
     Inverse[{{y1[m - 1], y2[m - 1]}, {y1[m - 2], y2[m - 2]}}] // Simplify]
   True

As a bonus:

With[{n = 10}, 
     ContinuedFractionK[ϕ[k], ψ[k], {k, 1, n}] == y2[n]/y1[n] // Simplify]
   True
$\endgroup$
  • $\begingroup$ As far as I can tell, this has the same issue as all the other solutions: I can get a solution for a particular $m$ and $n$, but how do I use this to get a solution for $m$ and $n$ as symbols? $\endgroup$ – AlexanderJ93 Mar 29 '18 at 0:54
  • $\begingroup$ I am saying that this is the best you can do if you leave $\phi$ and $\psi$ unknown: express the matrix's entries as the solution of a three-term recurrence. (Put another way, {{y1[n], y2[n]}, {y1[n - 1], y2[n - 1]}}.Inverse[{{y1[m - 1], y2[m - 1]}, {y1[m - 2], y2[m - 2]}} is as good as you'll get without any other assumptions.) If the $\phi$ and $\psi$ are polynomials, one might try using DifferenceRoot[] and hope that it has a simpler closed form. (Had this been easier than I had presented, the theory of continued fractions would be trivial.) $\endgroup$ – J. M. will be back soon Mar 29 '18 at 0:57
  • $\begingroup$ Okay, I guess I was just overestimating the capabilities of Mathematica. Thanks for all your help! $\endgroup$ – AlexanderJ93 Mar 29 '18 at 2:47

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.