# Product of matrices with symbolic bounds

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.

• Looks awfully like this problem. I give a solution there based on DifferenceRoot[]. – J. M. will be back soon Mar 28 '18 at 20:20
• Thanks, I'll go check that out. Should I delete this or can it be closed? – AlexanderJ93 Mar 28 '18 at 20:23
• If anything in there doesn't apply to your problem, just edit your question to explain why. – J. M. will be back soon Mar 28 '18 at 20:26
• 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. – AlexanderJ93 Mar 28 '18 at 23:22

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

• 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? – AlexanderJ93 Mar 29 '18 at 0:54
• 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.) – J. M. will be back soon Mar 29 '18 at 0:57
• Okay, I guess I was just overestimating the capabilities of Mathematica. Thanks for all your help! – AlexanderJ93 Mar 29 '18 at 2:47