# Hankel transform of an integer sequence

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]  • Should the diagonal elements be $a_0, a_2, \ldots, a_{2(n-1)}$? Commented Apr 21, 2023 at 9:21 ## 13 Answers # 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 # 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.  # Excel, 10499 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. • @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?! :-) Commented Apr 21, 2023 at 12:01 • 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 =) – JvdV Commented Apr 21, 2023 at 12:05 • By all means keep going! Commented Apr 21, 2023 at 12:20 # 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  # 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. • 42 bytes... Commented Apr 21, 2023 at 10:07 • @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 :-) Commented Apr 21, 2023 at 18:33 # Wolfram Language (Mathematica), 6452 49 bytes Det@Take[HankelMatrix@#,,]~Table~{,Length@#/2+1}&  Try it online! Thanks to @alephalpha ana @att! • HankelMatrix[#[[;;k]],#[[k;;2k-1]]] -> Take[HankelMatrix@#,k,k], and you can use infix notation for Table (Det@...~Table~{k,...}&). Commented Apr 21, 2023 at 4:39 • -3 with Null instead of k – att Commented Apr 21, 2023 at 9:10 • @att sorry i don't understand (( How is it possible? Commented Apr 21, 2023 at 10:21 • @lesobrod I think att means this trick. Commented Apr 21, 2023 at 11:39 • 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. – att Commented Apr 21, 2023 at 21:08 # Factor + math.matrices.extras, 35 bytes [ [ clump ] keep head determinant ]  Attempt This Online! Port of Adám's APL answer. # 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}&  • f@a_:=Det[Partition[a,#,1]~Take~#]&/@Range[Length@a/2+1], or Det[Partition[#,k,1]~Take~k]~Table~{k,Length@#/2+1}&. Commented Apr 21, 2023 at 4:05 • @alephalpha May be you look at my answer too and help me make shorter this awful #[[;;k]],#[[k;;2k-1]]? )) Commented Apr 21, 2023 at 4:29 • -3 with Null instead of k – att Commented Apr 21, 2023 at 9:11 # 05AB1E, 3634 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  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.. 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  # 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. # 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  • (i&1?-v:v) is (-1)**i*v. – tsh Commented Apr 24, 2023 at 5:47 # Julia 0.7, 26 bytes a*i=det(a[(s=1:i)'.+.~-s])  Try it online! Accepts sequence a and ith term. # 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

• You can change {. to \$. Commented Apr 24, 2023 at 7:21