Blog

# The polar decomposition of the Fibonacci sequence

If we think about the matrix form of the Fibonacci recursion:

 f(n + 1) f(n + 2)

=

 0 1 1 1

 f(n) f(n + 1)

a natural question to ask is what the polar decomposition of the matrix

A

=

 0 1 1 1

tells us about the recursion and the sequence that it generates.

To get the polar decomposition of the matrix A we write it as

A = UP

where U is unitary and P is positive definite

Writing a matrix in its polar decomposition is much like writing a complex number as

z = r eiθ

where the positive definite part of the polar decomposition corresponds to the magnitude of the complex number and the unitary part of the polar decomposition corresponds to the rotational part of the complex number.

In the case of the Fibonacci recursion we find that

P=(1/√5)

 2 1 1 3

and

U=(1/√5)

 -1 2 2 1

so that

P2=

 1 1 1 2

P3=(1/√5)

 3 4 4 7

P4=

 2 3 3 5

etc., and that U2 = I.

In general, I'd guess that for a nth-order linear recursion, we'll always have that Un = I. That shouldn't be too hard to show.

As we saw before, A has eigenvalues

a = (1 + √5) / 2

and

b = (1 – √5) / 2

while in this case we find that P has eigenvalues a and –b while U has eigenvalues 1 and -1.

I'm not sure how useful this polar decomposition will be, but I feel fairly sure that I'll find a use for it some day.