5
$\begingroup$

Let $k$ be a nonnegative integer, how to compute $\prod\limits_{i=1}^{n} A_i$ quickly and accurately, where $$A_i=\begin{bmatrix} 0 & 1\\ i^k & 1 \end{bmatrix}?$$

I know if $k=0$, we can use the matrix diagonalization method.

However, if $k>0$, it seems that the matrix diagonalization method is not suitable for those cases.

Given a specific $k>0$, I am having trouble finding its closed-form.

Hints and comments are welcomed.

EDIT:

An experiment for computing $\prod\limits_{i=1}^{n} A_i$ based on number theory:

STEP 1: Choose some different prime numbers $p_1,p_2,\dotsc$.

STEP 2: Compute $\prod\limits_{i=1}^{n} A_i \bmod p_1$, $\prod\limits_{i=1}^{n} A_i\bmod p_2,\dotsc$.

STEP 3: Combine the results from STEP 2.

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ For $k=2$, the lower right entry of the product seems to be $n!$. What makes you think there should be a simple closed form in general? What sort of experiments have you tried? $\endgroup$
    – Joe Silverman
    Commented Sep 4 at 21:17
  • 6
    $\begingroup$ The lower-right entry seems to be Fibonacci for $k=0$, number of involutions for $k=1$, $n!$ for $k=2$, A167449 for $k=3$ (where no formula is given), and unknown in the OEIS for $k=4$. This does not bode well for a general formula! $\endgroup$
    – Gro-Tsen
    Commented Sep 4 at 21:43
  • 3
    $\begingroup$ @Gro-Tsen, each of the entries satisfies a second-order D-finite recurrence with coefficients of degree $k$, so for some meanings of "general formula" it's not so hopeless. We have $$A_1 A_2 \cdots A_n = A_1 A_2 \cdots A_{n-1} \begin{pmatrix} (\frac{n}{n-1})^k & 0 \\ 0 & 1 \end{pmatrix} + A_1 A_2 \cdots A_{n-2} \begin{pmatrix} n^k & 0 \\ 0 & (n-1)^k \end{pmatrix}$$ $\endgroup$
    – Peter Taylor
    Commented Sep 4 at 23:31
  • 2
    $\begingroup$ @PeterTaylor Indeed, but I am merely remarking that since the number of involutions on $n$ objects is a particular case that is very well studied and since simple no closed form value for that seems known, it is very unlikely that one will be available here. But it's not even clear what user369335 wants: computing quickly and efficiently is very different from (and somewhat orthogonal to) finding a closed form. $\endgroup$
    – Gro-Tsen
    Commented Sep 5 at 8:31
  • 2
    $\begingroup$ Combinatorially, this is all about computing the sum over all subsets S of {1,...,n} of the product of the kth powers of the elements of S, with the constraint that S may not contain two adjacent integers. You can see why by drawing a trellis diagram for the matrices. (The Fibonacci numbers arise when you count the ways you can choose subsets with no adjacent elements which is why they pop up.) $\endgroup$
    – Dan Piponi
    Commented Sep 5 at 20:33

1 Answer 1

Reset to default
9
$\begingroup$

To be unambiguous about the order of multiplication, let $B(n) = A_1 A_2 \cdots A_n$. We have the D-finite recurrences

  • $B(n)_{r,1} = (\frac{n}{n-1})^k B(n-1)_{r,1} + n^k B(n-2)_{r,1}$
  • $B(n)_{r,2} = B(n-1)_{r,2} + (n-1)^k B(n-2)_{r,2}$

for $r \in \{1,2\}$.

Explicitly, $$A_1 A_2 \cdots A_n = A_1 A_2 \cdots A_{n-1} \begin{pmatrix} (\frac{n}{n-1})^k & 0 \\ 0 & 1 \end{pmatrix} + A_1 A_2 \cdots A_{n-2} \begin{pmatrix} n^k & 0 \\ 0 & (n-1)^k \end{pmatrix}$$ which was discovered experimentally but is easily verified.

This gives us, for example, that the e.g.f. of the bottom-right entry satisfies the o.d.e. $$G''(x) = G'(x) + \left(\tfrac{\textrm{d}}{\textrm{d}x}x\right)^k G(x)$$ Already at $k=3$ we have $$x^3G'''(x) + (6x^2-1) G''(x) + (7x+1)G'(x) + G(x) = 0$$ to which Maxima and Wolfram Alpha are unable to find closed form solutions. So for practical purposes, the way to calculate the matrix fast is probably to use multi-point polynomial evaluation. Let $s = \lfloor \sqrt{n} \rfloor$. Then to find $B(s^2)$ you evaluate $A_{u+1} A_{u+2} \cdots A_{u+s}$ symbolically as a matrix of polynomials in $u$; use multi-point evaluation on each of the four polynomials for $u \in \{0,s,2s,\ldots,(s-1)s\}$; and multiply the $s$ resulting matrices. Finally you multiply by $A_{s^2+1} A_{s^2+2} \cdots A_{n}$. It may also be worth looking into the number-theoretic transform for polynomial multiplication and working modulo NTT-friendly primes before a final CRT reconstruction.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Minor notes not worth bumping with an edit: it might be more useful to write the first D-finite recurrence as $\frac{B(n)_{r,1}}{n^k} = \frac{B(n-1)_{r,1}}{(n-1)^k} + (n-2)^k \frac{B(n-2)_{r,1}}{(n-k)^2}$. Since the degrees of the polynomials will be $ks$, if $k$ isn't very small relative to $n$ then the goal is probably to get $ks \sim n/s$, so take $s = \lfloor \sqrt{nk^{-1}} \rfloor$. $\endgroup$
    – Peter Taylor
    Commented Sep 6 at 12:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .