# Help me accelerate linear recurrence relation!

## 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

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 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.


# 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


# J, 10 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


# 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}$$

# 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


# 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


# 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).

• Cool, a nice trick of which I was unaware! – Jonathan Allan Jul 31 at 11:51

# Charcoal, 12 bytes

ＩＥθ⎇κＥθ⁼⊖κμθ


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:

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

• @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. – Neil Jul 30 at 12:48

# 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.

# 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

• -1 byte: lambda a,k,r=range(k):[[i==j for j in r]for i in r[1:]]+[a]  – ManfP Jul 30 at 19:05
• @ManfP - that's invalid, k is not defined at the point it's being used by range (TIO). – Jonathan Allan Jul 31 at 1:12
• 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. – Jonathan Allan Jul 31 at 1:25
• @JonathanAllan oh sorry you are totally right, the perils of testing locally with shadowing variable names... – ManfP Jul 31 at 10:08

# 05AB1E, 7 bytes

āDδQ\)


Outputs reversed in both dimensions.

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)


# 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]]


# 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.

# 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)