Hankel transform of an integer sequence

Question

A Hankel matrix is a square matrix in which each ascending skew-diagonal from left to right is constant, e.g.:

$$\begin{bmatrix} a & b & c & d \\ b & c & d & e \\ c & d & e & f \\ d & e & f & g \end{bmatrix}.$$

Given a sequence of integers \$\{a_n\}\$, we can construct a sequence of Hankel matrices \$\{H_n\}\$, where \$H_n\$ is the \$n\times n\$ Hankel matrix whose \$(i,j)\$ entry is \$a_{i+j-1}\$ (1-indexed). The Hankel transform of \$\{a_n\}\$ is defined as the sequence of determinants of the matrices \$\{H_n\}\$, i.e. \$\{\det(H_n)\}\$.

For example, the fourth Hankel matrix of the Catalan numbers \$\{1,1,2,5,14,42,132,\dots\}\$ is

$$H_4 = \begin{bmatrix} 1 & 1 & 2 & 5 \\ 1 & 2 & 5 & 14 \\ 2 & 5 & 14 & 42 \\ 5 & 14 & 42 & 132 \end{bmatrix},$$

and the determinant of \$H_1\$, \$H_2\$, \$H_3\$, and \$H_4\$ are all \$1\$. The Hankel transform of the Catalan numbers is therefore \$\{1,1,1,1,\dots\}\$.

Task

Given a finite sequence of integers \$\{a_n\}\$, output its Hankel transform \$\{\det(H_n)\}\$.

The length of the input sequence is always an odd number. If the length of the input sequence is \$2n-1\$, then the length of the output sequence should be \$n\$.

Input and output can be in any reasonable format, e.g., a list, an array, a polynomial, a function that takes \$i\$ and returns the \$i\$th term (0-indexed or 1-indexed), etc.

You may also take the input sequence and an integer \$i\$, and output the \$i\$th term (0-indexed or 1-indexed) of the output sequence.

This is code-golf, so the shortest code in bytes wins.

Testcases

[1,1,2,3,5,8,13] -> [1,1,0,0]
[0,1,2,3,4,5,6,7,8] -> [0,-1,0,0,0]
[1,0,-1,0,1,0,-1,0,1] -> [1,-1,0,0,0]
[1,2,5,14,42,132,429,1430,4862] -> [1,1,1,1,1]
[1,2,5,15,51,188,731,2950,12235] -> [1,1,1,1,1]
[1,2,6,20,70,252,924,3432,12870] -> [1,2,4,8,16]
[1,1,2,4,10,26,76,232,764,2620,9496] -> [1,1,2,12,288,34560]

Answer 1

APL (Dyalog Extended), 10 bytes

Anonymous tacit infix function taking 1-indexed \$i\$ as left argument and the sequence \$\{a_n\}\$ as right argument.

⌂det∘↑⊣↑,/

Try it online!

,/ sliding windows in \$\{a_n\}\$ of size \$i\$

⊣↑ take the first \$i\$ of those

∘↑ combine those lists as rows into a matrix, then…

⌂det compute the determinant

Answer 2

Jelly, 5 bytes

ṡḣṛÆḊ

Try it online!

Port of Adám's APL answer, so go upvote that. Sequence on the left, index on the right.

 ḣṛ      First i
ṡ        overlapping length-i slices of the sequence.
   ÆḊ    Determinant.

Answer 3

Excel, 104 99 86 bytes

With thanks to JvdV for the 18-byte save.

=MAP(
    SEQUENCE(ROWS(A1#)/2+1),
    LAMBDA(r,MDETERM(INDEX(A1#,SEQUENCE(,r)+SEQUENCE(r)-1)))
)

Input is spilled range #A1.

Answer 4

Vyxal, 4 bytes

lẎÞḊ

Try it Online!

Takes 1 based index and then the sequence. Port of @Adàm's APL answer.

l    # overlapping groups of length i
 Ẏ   # take first i
  ÞḊ # determinant

Answer 5

R, 46 42 bytes

Edit: -4 bytes thanks to @Dominic van Essen.

\(v,i)det(t(matrix(v,sum(v|1)+1,i)[1:i,]))

Attempt This Online!

Takes input as vector v of the sequence and index i.

Answer 6

Wolfram Language (Mathematica), 64 52 49 bytes

Det@Take[HankelMatrix@#,,]~Table~{,Length@#/2+1}&

Try it online!

Thanks to @alephalpha ana @att!

Answer 7

Factor + math.matrices.extras, 35 bytes

[ [ clump ] keep head determinant ]

Attempt This Online!

Port of Adám's APL answer.

Answer 8

Wolfram Language(Mathematica), 72 54 bytes

Saved 18 bytes thanks to the comment of @alephalpha

Try it online!

f=Det[Partition[#,k,1]~Take~k]~Table~{k,Length@#/2+1}&

Answer 9

05AB1E, 36 34 30 bytes

Given a list of integers \$\{a_n\}\$ and integer \$i\$, outputs its \$i^{th}\$ Hankel transform \$\det(H_{n,i})\$ (30 bytes)

ŒIùI£ā<sUœε©2.ÆíÆ.±Xε®Nèè}«P}O

Try it online or verify all test cases.

Given a list of integers \$\{a_n\}\$, outputs its Hankel transform \$\{\det(H_n)\}\$ (36 34 bytes)

gÅÉε£ŒN>ùā<sUœε©2.ÆíÆ.±Xε®Nèè}«P}O

Inspired by @Adàm's APL answer, but without any matrix builtins available..

Try it online or verify all test cases.

Explanation (of the program with list output):

Step 1: Create a list of matrices from the input-list:

g               # Push the length of the (implicit) input-list
 ÅÉ             # Pop and push a list of odd numbers <= this input-length
   ε            # Map over each odd value:
    £           #  Keep the first value amount of items from the (implicit) input-list
     Π         #  Get all sublists of that list
      N>        #  Push the (0-based) map-index, and increase it by 1
        ù       #  Only keep the sublists of that length

Try just this first step online.

Step 2: Get the determinant of each matrix, which I've done before in 05AB1E for the Determinant of an Integer Matrix challenge:

 ā              #   Push a list in the range [1, matrix-length] (without popping)
  <             #   Decrease it by 1 to make the range [0, matrix-length)
   sU           #   Swap to get the matrix again, and pop and store it in variable `X`
     œ          #   Get all permutations of the [0, matrix-length) list
      ε         #   Inner map over each permutation:
       ©        #    Store the current permutation in variable `®` (without popping)
        2.Æ     #    Get all 2-element combinations of this permutation
           í    #    Reverse each inner pair
            Æ   #    Reduce it by subtracting
             .± #    And get it's signum (-1 if a<0; 0 if a==0; 1 if a>0)
       X        #    Push the matrix from variable `X`
        ε       #    Map over each of its rows:
         ®      #     Push the current permutation of variable `®`
          Nè    #     Get the value in the permutation at the current map-index
            è   #     And use that to index into the current matrix-row
        }«      #    After the map of rows: merge it together with the signum list
          P     #    And take the product of this entire list
      }O        #   After the map of permutations: sum all values

Answer 10

Charcoal, 54 46 bytes

≔…⁰ηη⊞υ⟦⟧Ｆη≔ΣＥυＥ⁻⎇﹪λ²⮌ηηκ⁺κ⟦μ⟧υＩ↨Ｅ⮌υΠＥι§θ⁺λμ±¹

Attempt This Online! Link is to verbose version of code. Takes the sequence and index as inputs. Explanation:

≔…⁰ηη⊞υ⟦⟧Ｆη≔ΣＥυＥ⁻⎇﹪λ²⮌ηηκ⁺κ⟦μ⟧υ

Generate all of the permutations of [0..i). This is based on my answer to 1 to N column and row sums but tweaked to alternate between even and odd permutations.

Ｉ↨Ｅ⮌υΠＥι§θ⁺λμ±¹

For each permutation, add each element to its index and use that to index into the original sequence, then take the alternating sum of products, which is the determinant of the Hankel matrix as required.

Previous 54-byte version:

≔⟦ＥηＥη§θ⁺ιλ⟧θＦθ¿⊖ＬιＦＥ⊟ιＥι×Φμ⁻πλ⎇ν¹×Ｘ±¹⁺Ｌιλκ⊞θκ⊞υ⊟⊟ιＩΣυ

Try it online! Link is to verbose version of code. Takes the sequence and index as inputs. Explanation:

≔⟦ＥηＥη§θ⁺ιλ⟧θ

Construct the Hankel matrix Hᵢ.

Ｆθ¿⊖ＬιＦＥ⊟ιＥι×Φμ⁻πλ⎇ν¹×Ｘ±¹⁺Ｌιλκ⊞θκ⊞υ⊟⊟ιＩΣυ

Calculate its determinant using the following algorithm:

• Remove the last row and iterate over its elements. (This was the golfiest out of the first and last row and column, the ease of removing the last row making up for the slightly more complicated parity calculation.)
• For each element, create a new matrix by also removing its column, and multiply the first row of it with the element, but with the sign changed according to the parity of the element's original position.
• Take the sum of the determinants of the resulting trivial matrices.

Answer 11

JavaScript (ES10), 152 bytes

-1 thanks to @tsh

f=(a,b=[D=m=>q=+m||m.reduce((s,[v],i)=>s+(-1)**i*v*D(m.flatMap(([,...r])=>i--?[r]:[])),0)])=>1/D(b.map((_,y)=>b.map(_=>a[y++])))?[q,...f(a,[...b,0])]:[]

Try it online!

Commented

Determinant function

D = m =>            // m[] = matrix
+m ||               // if m[] is a non-zero singleton, return it
m.reduce((          // otherwise, for each row:
  s,                //   given the accumulator s
  [v],              //   and the first value v
  i                 //   of the i-th row
) =>                //
  s +               //   add to s
  (-1) ** i * v     //   either v or -v depending on the parity of i
  *                 //   multiplied by
  D(                //   the result of a recursive call:
    m.flatMap(      //     for each row:
      ([, ...r]) => //       remove the first value of each row
      i-- ? [r]     //       and remove the i-th row entirely
          : []      //
    )               //     end of flatMap()
  ),                //   end of recursive call
  0                 //   start with s = 0
)                   // end of reduce()

Wrapper function

f = (               // f is a recursive function taking:
  a,                //   a[] = input list
  b = [0],          //   b[] = vector, initially of size 1
  q = D(            //   q = determinant of:
    b.map((_, y) => //     the Hankel matrix built by iterating twice
      b.map(_ =>    //     over the vector b[]
        a[y++]      //     and setting each cell at (x, y) to a[x + y]
      )             //
    )               //
  )                 //
) =>                //
1 / q ?             // if q is defined:
  [ q,              //   append q
    ...f(           //   followed by the result of a recursive call:
      a,            //     pass a[] unchanged
      [...b, 0]     //     add a dummy item to b[]
    )               //   end of recursive call
  ]                 //
:                   // else:
  []                //   stop

Answer 12

Julia 0.7, 26 bytes

a*i=det(a[(s=1:i)'.+.~-s])

Try it online!

Accepts sequence a and ith term.

Answer 13

J, 11 10 bytes

-1 byte thanks to @Bubbler!

[-/ .*@{.[\

Try it online! Input format from Adàm's APL answer, but the form, although basically equivalent to his answer, was discovered independently when I wrote the below answer to work with only a sequence as input.

J, 28 27 bytes

-1 byte thanks to @Bubbler!

([-/ .*@$[\)"{~1+i.@>.@-:@#

Try it online!

The novel bit in this approach is doing more work! :P

([-/ .*@{.[\)"{~1+i.@>.@-:@#
                        -:      half
                          @#    the input size
                     >.@        rounded up
                  i.@           range [0, ^)
                1+              range [1, ^]
                                this gives us all the valid matrix sizes
(           )" ~                (equivalent to Adàm's answer) applied at
              {                 equiv. 0 _
                                every possible matrix size and the entire input sequence