Help me accelerate linear recurrence relation!

Question

Background

A linear recurrence relation is a description of a sequence, defined as one or more initial terms and a linear formula on last \$k\$ terms to calculate the next term. (For the sake of simplicity, we only consider homogeneous relations, i.e. the ones without a constant term in the formula.)

A formal definition of a linear recurrence relation looks like this, where \$y_n\$ is the desired sequence (1-based, so it is defined over \$n\ge 1\$) and \$x_i\$'s and \$a_i\$'s are constants:

$$ y_n = \begin{cases} x_n, & 1\le n\le k \\ a_1y_{n-1}+a_2y_{n-2}+\cdots+a_ky_{n-k}, & k<n \end{cases} $$

In this challenge, we will accelerate this sequence by converting it to a matrix form, so that the \$n\$-th term can be found by repeated squaring of the matrix in \$O(\log n)\$ steps, followed by inner product with the vector of initial terms.

For example, consider the famous Fibonacci sequence: its recurrence relation is \$y_n=y_{n-1} + y_{n-2}\$ with \$k=2\$, and let's use the initial values \$x_1=x_2=1\$. The recurrence relation can be converted to a matrix form:

$$ \begin{bmatrix} y_{n-1} \\ y_{n} \end{bmatrix} = \begin{bmatrix} y_{n-1} \\ y_{n-1}+y_{n-2} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} y_{n-2} \\ y_{n-1} \end{bmatrix} $$

So multiplying the matrix once advances the sequence by one term. Since this holds for any \$n\$, it can be extended all the way until we reach the initial terms:

$$ \begin{bmatrix} y_{n-1} \\ y_{n} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} y_{n-2} \\ y_{n-1} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^2\begin{bmatrix} y_{n-3} \\ y_{n-2} \end{bmatrix} \\ = \cdots = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n-2}\begin{bmatrix} y_{1} \\ y_{2} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n-2}\begin{bmatrix} 1 \\ 1 \end{bmatrix} $$

In general, one way to construct such a matrix is the following:

$$ \begin{bmatrix} y_{n-k+1} \\ y_{n-k+2} \\ \vdots \\ y_{n-1} \\ y_{n} \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ & \vdots & & & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ a_k & a_{k-1} & a_{k-2} & \cdots & a_1 \end{bmatrix}\begin{bmatrix} y_{n-k} \\ y_{n-k+1} \\ \vdots \\ y_{n-2} \\ y_{n-1} \end{bmatrix} $$

Note that, if you reverse the vectors and the matrix in every dimension, the equation still holds, retaining the property of "advancing a term by matmul-ing once". (Actually any permutation will work, given that the rows and columns of the matrix are permuted in the same way.)

Challenge

Given the list of coefficients \$a_1,\cdots,a_k\$, construct a matrix that represents the recurrence relation (so that its powers can be used to accelerate the computation of \$n\$-th term of the sequence).

You can take the coefficients in reverse order, and you can optionally take the value \$k\$ as a separate input. \$k\$ (the number of terms) is at least 1.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

In all cases, any other matrix that can be formed by permuting rows and columns in the same way is also valid.

Input
[1,1]
Output
[[0, 1],
 [1, 1]]
Input
[5]
Output
[[5]]
Input
[3, -1, 19]
Output
[[0, 1, 0],
 [0, 0, 1],
 [19, -1, 3]]
or reversed in both dimensions:
[[3, -1, 19],
 [1, 0, 0],
 [0, 1, 0]]
or cycled once in both dimensions:
[[3, 19, -1],
 [0, 0, 1],
 [1, 0, 0]]
etc.

Answer 1

MATL, ^{(削除) 8 (削除ここまで)} 7 bytes

-1 byte thanks to @LuisMendo

Xy4LY)i

Takes the coefficients in reverse order

Try it online!

Explanation

Xy4LY)i
Xy : Create an identity matrix of size equal to input
 4LY) : Remove the first row
 i : Insert input onto the stack

Answer 2

J, ¹⁰ 8 bytes

Returns the matrix reversed in both dimensions.

,}:@=@/:

Try it online!

How it works

 ,}:@=@/: input: 3 _1 19
 /: indices that sort: 1 0 2
 (just to get k different numbers)
 =@ self-classify: 1 0 0
 0 1 0
 0 0 1
 }:@ drop last row: 1 0 0
 0 1 0
 , prepend input: 3 _1 19
 1 0 0
 0 1 0

Answer 3

JavaScript (ES6), 36 bytes

a=>a.map((_,i)=>i?a.map(_=>+!--i):a)

Try it online!

Returns:

$$ \begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_{k-1} & a_k \\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 \end{bmatrix} $$

Answer 4

Io, 56 bytes

method(a,a map(i,v,if(i<1,a,a map(I,v,if(I==i-1,1,0)))))

Try it online!

Explanation

method(a, ) // Input an array.
 a map(i,v, ) // Map. i = index, v = value
 if(i<1, ) // If the indice is 0,
 a, // Return the inputted list
 a map(I,v, ) // Otherwise, map: (I is the current index)
 if(I==i-1, ) // If I == i-1,
 1, // Return 1,
 0 // Otherwise 0

Answer 5

APL (Dyalog Unicode), 10 bytes

⊢⍪ ̄1↓⍋∘.=⍋

Try it online!

Tacit function taking the list of coefficients on the right.

Explanation

⊢⍪ ̄1↓⍋∘.=⍋
 ⍋ ⍋ ⍝ Grade up to obtain a list of k distinct values
 ∘.= ⍝ Outer product with operation `equals` (identity matrix)
 ̄1↓ ⍝ Drop the last row
⊢⍪ ⍝ Prepend the list of coefficients

Answer 6

Python 2, 46 bytes

lambda l,k:[l]+zip(*[iter(([1]+[0]*k)*~-k)]*k)

Try it online!

Takes input as a tuple l and number of terms k, and outputs with both rows and columns reversed.

The idea is to use the zip/iter trick to create an identity-like matrix by splitting a repeating list into chunks. The is similar to my solution to construct the identity matrix but changed to have one fewer row by changing the inner multiplier k to k-1 (written ~-k).

• Jonathan Allan: Cool, a nice trick of which I was unaware!

Answer 7

Charcoal, 12 bytes

IEθ⎇κEθ=⊖κμθ

Try it online! Link is to verbose version of code. Produces the "reversed in both directions" output. Works by replacing the first row of a shifted identity matrix with the input. Explanation:

 Eθ Map over input list
 ⎇κ If this is not the first row then
 Eθ Map over input list
 =⊖κμ Generate a shifted identity matrix
 θ Otherwise replace the first row with the input
I Cast to string for implicit print

• Neil: @xash Actually I was thinking of a different permutation, but either way I've probably misunderstood the question. I'll rewrite it to use the reversed in both directions option.

Answer 8

R, 34 bytes

function(r,k)rbind(diag(k)[-1,],r)

Try it online!

Takes the length as well; the TIO link has a k=length(r) argument so you can just input the recurrence relation.

Answer 9

Python 3, ^{(削除) 60 (削除ここまで)} 58 bytes

-2 bytes thanks to @JonathanAllan

lambda a,k:[map(i.__eq__,range(k))for i in range(1,k)]+[a]

Try it online!

Takes the coefficients in reverse order

• ManfP: -1 byte: lambda a,k,r=range(k):[[i==j for j in r]for i in r[1:]]+[a]
• Jonathan Allan: @ManfP - that's invalid, k is not defined at the point it's being used by range (TIO).
• Jonathan Allan: lambda a,k:[map(i.__eq__,range(k))for i in range(1,k)]+[a] is 58. Returns a list of iterables, and False==0 and True==1.
• ManfP: @JonathanAllan oh sorry you are totally right, the perils of testing locally with shadowing variable names...

Answer 10

05AB1E, 7 bytes

āDδQ`\)

Outputs reversed in both dimensions.

Try it online or verify all test cases.

Explanation:

ā # Push a list in the range [1,length] (without popping the implicit input-list)
 D # Duplicate it
 δ # Apply double-vectorized:
 Q # Check if it's equal
 # (this results in an L by L matrix filled with 0s, with a top-left to
 # bottom-right diagonal of 1s; where `L` is the length of the input-list)
 ` # Pop and push all rows of this matrix separated to the stack
 \ # Discard the last row
 ) # And wrap all list on the stack into a list
 # (after which the matrix is output implicitly as result)

Answer 11

Jelly, 8 bytes

W;J=þṖ$$

A monadic Link accepting a list which yields a list of lists in the reversed rows & columns permutation.

Try it online!

How?

W;J=þṖ$$ - Link: list A e.g. [5,2,5,4]
W - wrap (A) in a list [[5,2,5,4]]
 $ - last two links as a monad - f(A):
 J - range of length (A) [1,2,3,4]
 $ - last two links as a monad - f(J):
 Ṗ - pop [1,2,3]
 þ - (J) outer product (that) with:
 = - equals? [[1,0,0,0],[0,1,0,0],[0,0,1,0]]
 ; - (W) concatenate (that) [[5,2,5,4],[1,0,0,0],[0,1,0,0],[0,0,1,0]]

Answer 12

C (gcc), ^{(削除) 90 (削除ここまで) (削除) 89 (削除ここまで)} 80 bytes

Saved 9 bytes thanks to ceilingcat!!!

i;j;f(a,k)int*a;{for(i=k;i--;puts(""))for(j=k;j--;)printf("%d ",i?i-1==j:a[j]);}

Try it online!

Inputs an array of coefficients (in forward order) along with its length.
Prints a matrix that represents the recurrence relation.

Answer 13

Google Sheets, 52

Closing Parens discounted.

• Input cells is Row 1, starting in column B.
• A2 - =COUNTA(1:1). Rules say that we can take this as input too, so I have discounted this as well. (Our "k")
• A3 - =ArrayFormula(IFERROR(0^MOD(SEQUENCE(A2-1,A2)-1,A2+1)))

The output matrix starts in B1.

How it works

1. Since this is a spreadsheet, the input cells give us free output too. As long is it's the first row and we end up with a square set of cells, we're good. If this didn't count, we'd have to do this with Column 1 instead to use TRANSPOSE() to copy the input. (Because it's smaller than ArrayFormula())
2. Cache the number of columns in A2
3. Generate a k-1 x k matrix using SEQUENCE. Values are MOD number of columns + 1. (Diagonals are 0, otherwise something else).
4. Since 0^0 is 1 in Sheets, that means this effectively is a Boolean NOT() converted to an integer.
5. IFERROR handles input size of 1. (Output a Blank)

Answer 14

Pari/GP, 29 bytes

a->matcompanion(x^#a-Pol(a))~

Try it online!