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.
14 Answers 14
MATL, (削除) 8 (削除ここまで) 7 bytes
-1 byte thanks to @LuisMendo
Xy4LY)i
Takes the coefficients in reverse order
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.
,}:@=@/:
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)
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)))))
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↓⍋∘.=⍋
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)
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).
-
\$\begingroup\$ Cool, a nice trick of which I was unaware! \$\endgroup\$Jonathan Allan– Jonathan Allan2020年07月31日 11:51:38 +00:00Commented Jul 31, 2020 at 11:51
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
-
1\$\begingroup\$ @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 directionsoption. \$\endgroup\$Neil– Neil2020年07月30日 12:48:25 +00:00Commented Jul 30, 2020 at 12:48
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]
Takes the coefficients in reverse order
-
\$\begingroup\$ -1 byte:
lambda a,k,r=range(k):[[i==j for j in r]for i in r[1:]]+[a]\$\endgroup\$ManfP– ManfP2020年07月30日 19:05:00 +00:00Commented Jul 30, 2020 at 19:05 -
\$\begingroup\$ @ManfP - that's invalid,
kis not defined at the point it's being used byrange(TIO). \$\endgroup\$Jonathan Allan– Jonathan Allan2020年07月31日 01:12:28 +00:00Commented Jul 31, 2020 at 1:12 -
\$\begingroup\$
lambda a,k:[map(i.__eq__,range(k))for i in range(1,k)]+[a]is 58. Returns a list of iterables, andFalse==0andTrue==1. \$\endgroup\$Jonathan Allan– Jonathan Allan2020年07月31日 01:25:00 +00:00Commented Jul 31, 2020 at 1:25 -
\$\begingroup\$ @JonathanAllan oh sorry you are totally right, the perils of testing locally with shadowing variable names... \$\endgroup\$ManfP– ManfP2020年07月31日 10:08:46 +00:00Commented Jul 31, 2020 at 10:08
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)
Jelly, 8 bytes
W;J=þṖ$$
A monadic Link accepting a list which yields a list of lists in the reversed rows & columns permutation.
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]);}
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 columnB. 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
- 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 thanArrayFormula()) - Cache the number of columns in A2
- Generate a k-1 x k matrix using
SEQUENCE. Values areMODnumber of columns + 1. (Diagonals are 0, otherwise something else). - Since
0^0is1in Sheets, that means this effectively is a BooleanNOT()converted to an integer. IFERRORhandles input size of 1. (Output a Blank)