15
\$\begingroup\$

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 , 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]
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Should the diagonal elements be \$a_0, a_2, \ldots, a_{2(n-1)}\$? \$\endgroup\$
    – Noodle9
    Apr 21 at 9:21

13 Answers 13

9
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ @JvdV Great golfing! Not only the use of MAP, but also INDEX in place of OFFSET. And how do you manage to always save bytes by not using LET?! :-) \$\endgroup\$ Apr 21 at 12:01
  • \$\begingroup\$ I just found your answer so interesting that I spend the last few hours staring at it while so now and then I found a way of shortening things piece by piece =) \$\endgroup\$
    – JvdV
    Apr 21 at 12:05
  • \$\begingroup\$ By all means keep going! \$\endgroup\$ Apr 21 at 12:20
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 42 bytes... \$\endgroup\$ Apr 21 at 10:07
  • \$\begingroup\$ @DominicvanEssen nice trick, thanks! I was so annoyed that det didn't work for i=1 case, that I took whatever came first to my mind :-) \$\endgroup\$
    – pajonk
    Apr 21 at 18:33
4
\$\begingroup\$

Wolfram Language (Mathematica), 64 52 49 bytes

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

Try it online!

Thanks to @alephalpha ana @att!

\$\endgroup\$
6
  • 3
    \$\begingroup\$ HankelMatrix[#[[;;k]],#[[k;;2k-1]]] -> Take[HankelMatrix@#,k,k], and you can use infix notation for Table (Det@...~Table~{k,...}&). \$\endgroup\$
    – alephalpha
    Apr 21 at 4:39
  • 1
    \$\begingroup\$ -3 with Null instead of k \$\endgroup\$
    – att
    Apr 21 at 9:10
  • 1
    \$\begingroup\$ @att sorry i don't understand (( How is it possible? \$\endgroup\$
    – lesobrod
    Apr 21 at 10:21
  • 1
    \$\begingroup\$ @lesobrod I think att means this trick. \$\endgroup\$
    – alephalpha
    Apr 21 at 11:39
  • 1
    \$\begingroup\$ Syntax::com warns against implicit nulls, which is exactly what Null tricks (ab)use. You can Off@Syntax::com before the definition to suppress the message. \$\endgroup\$
    – att
    Apr 21 at 21:08
3
\$\begingroup\$

Factor + math.matrices.extras, 35 bytes

[ [ clump ] keep head determinant ]

Attempt This Online!

Port of Adám's APL answer.

\$\endgroup\$
3
\$\begingroup\$

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}&
\$\endgroup\$
3
  • 3
    \$\begingroup\$ f@a_:=Det[Partition[a,#,1]~Take~#]&/@Range[Length@a/2+1], or Det[Partition[#,k,1]~Take~k]~Table~{k,Length@#/2+1}&. \$\endgroup\$
    – alephalpha
    Apr 21 at 4:05
  • 1
    \$\begingroup\$ @alephalpha May be you look at my answer too and help me make shorter this awful #[[;;k]],#[[k;;2k-1]]? )) \$\endgroup\$
    – lesobrod
    Apr 21 at 4:29
  • \$\begingroup\$ -3 with Null instead of k \$\endgroup\$
    – att
    Apr 21 at 9:11
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 54 46 bytes

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

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

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

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.

I↨E⮌υΠEι§θ⁺λμ±¹

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:

≔⟦EηEη§θ⁺ιλ⟧θFθ¿⊖LιFE⊟ιEι×Φμ⁻πλ⎇ν¹×X±¹⁺Lιλκ⊞θκ⊞υ⊟⊟ιIΣυ

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

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

Construct the Hankel matrix Hᵢ.

Fθ¿⊖LιFE⊟ιEι×Φμ⁻πλ⎇ν¹×X±¹⁺Lιλκ⊞θκ⊞υ⊟⊟ιIΣυ

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.
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ (i&1?-v:v) is (-1)**i*v. \$\endgroup\$
    – tsh
    Apr 24 at 5:47
2
\$\begingroup\$

Julia 0.7, 26 bytes

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

Try it online!

Accepts sequence a and ith term.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ You can change {. to $. \$\endgroup\$
    – Bubbler
    Apr 24 at 7:21
  • \$\begingroup\$ Nice catch, thank you @Bubbler! \$\endgroup\$ Apr 24 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.