# Fibonacci Calculation using a larger matrix

So the formula to generate the fibonacci sequence in matrix form is: $$\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \\ \end{pmatrix}$$

So, is there a way to generalize it to a larger matrix, a 4x4 for example?

-
Why do you want to do this? You could fit the same matrix in a 4x4 twice... or just once and make the upper (or lower) corner an identity matrix. I doubt you'd get a computational advantage out of making it larger. It's an interesting generalization but without something more specific I don't think there's a good answer. – nayrb Jun 28 '14 at 0:25

An attempt at a direct generalization gives the cubes of the Fibonacci numbers:

$\pmatrix{ 3&6&-3&-1\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0 }^n\pmatrix{ 2197&512&125&27\\ 512&125&27&8\\ 125&27&8&1\\ 27&8&1&1 }=\pmatrix{ F_{n+7}^3&F_{n+6}^3&F_{n+5}^3&F_{n+4}^3\\ F_{n+6}^3&F_{n+5}^3&F_{n+4}^3&F_{n+3}^3\\ F_{n+5}^3&F_{n+4}^3&F_{n+3}^3&F_{n+2}^3\\ F_{n+4}^3&F_{n+3}^3&F_{n+2}^3&F_{n+1}^3\\ }$

It's not as clean as the original because there's an "accident" in the original where the coefficients of the recurrence relation are also the first two terms in the series. No such luck here.

-

Try looking at:

$$\begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{pmatrix}^n \begin{pmatrix} 2 \\ 1 \\ 1\\ 0 \\ \end{pmatrix}$$

-
What is it? I honestly can't tell – John Fernley Jun 28 '14 at 0:48
Let me wolfram alpha that for you – Nate Jun 28 '14 at 0:50
And are those Fibonacci numbers? – John Fernley Jun 28 '14 at 0:54

I suppose a natural generalization would be $$\begin{pmatrix} 1&1&0&0 \\ 1&0&1&0 \\ 0&0&0&1 \\ 0&0&0&0\end{pmatrix}^n$$ This adds the first two columns and then shifts everything over to the right, just as in the $2\times 2$ case. It is not hard to see how this would extend to a $k\times k$ matrix.

On the other hand, this is a little "lame"; the bottom row is never even used.

-

$$\begin{pmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 2 & 1 \\ 0 & 0 & 1 & 1 \\ \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n & 0 & 0 \\ F_n & F_{n-1} & 0 & 0 \\ 0 & 0 & F_{2n+1} & F_{2n} \\ 0 & 0 & F_{2n} & F_{2n-1} \\ \end{pmatrix}$$

The point is you're asking for something very arbitrary

-
I suppose the idea was to fit more Fibonacci numbers in the matrix... but okay... – Dane Bouchie Jun 28 '14 at 0:29
@DaneBouchie I did that now, if this is more what you wanted? – John Fernley Jun 28 '14 at 0:30