⏱ 4 minutes read

Generating Function and Eigenvalue¶

Generating Function $\leftrightarrow$ Matrix Eigenvalues: Correct. The poles (singularities) of the generating function directly correspond to the eigenvalues of the transition matrix.
Fourier Series Orthogonality $\leftrightarrow$ Fibonacci Matrix: Not directly applicable. Although the Fourier transform is based on orthogonal/unitary matrices ($U^T = U^{-1}$), the Fibonacci transition matrix (Q-matrix) is not orthogonal or unitary, so the property that "transpose equals inverse" cannot be directly exploited to simplify computation.

1. The Essential Connection Between Generating Functions and Eigenvalues¶

The generating function method and the matrix eigenvalue method are essentially two different expressions of the same mathematical structure.

Mathematical Correspondence¶

For the Fibonacci sequence $F_n = F_{n-1} + F_{n-2}$:

Generating Function Perspective: The generating function is $G(x) = \frac{x}{1-x-x^2}$. The roots of its denominator (i.e., the poles) are found by solving $1-x-x^2=0$: $$x_1 = \frac{1}{\phi}, \quad x_2 = \frac{1}{\psi}$$ where $\phi = \frac{1+\sqrt{5}}{2}, \psi = \frac{1-\sqrt{5}}{2}$.
Matrix Eigenvalue Perspective: The transition matrix is $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. Its characteristic equation is $\det(M-\lambda I) = \lambda^2 - \lambda - 1 = 0$. The eigenvalues are: $$\lambda_1 = \phi, \quad \lambda_2 = \psi$$

Core Conclusion¶

Reciprocal of generating function poles = Matrix eigenvalues. $$ \lambda_i = \frac{1}{x_i} $$ * Reason: The radius of convergence of the generating function $G(x) = \sum F_n x^n$ is determined by the pole closest to the origin, while the growth rate of the sequence $F_n \sim C \cdot \lambda^n$ is determined by the largest eigenvalue. Both describe the same asymptotic behavior. * Application: Performing a contour integral on the generating function using the Residue Theorem is, in essence, performing Spectral Decomposition, and the result is completely consistent with matrix diagonalization $M = PDP^{-1}$.

2. Misconceptions About "Orthogonal Matrices" and "Fourier Series"¶

"Fourier series correspond to the property that the transpose equals the inverse for orthogonal matrices in the real domain, and unitary matrices in the complex domain" — this is correct for the Fourier transform itself, but it cannot be directly applied to the Fibonacci matrix.

Why Is the Fibonacci Matrix Not Orthogonal/Unitary?¶

The Fibonacci transition matrix $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. * Testing Orthogonality: For $M$ to be orthogonal, it must satisfy $M^T M = I$. $$ M^T M = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 1 \ 1 & 1 \end{pmatrix} \neq I $$ * Eigenvalue Properties: * The eigenvalues of an orthogonal/unitary matrix must have modulus 1 ($|\lambda|=1$), meaning the system conserves energy, neither diverging nor decaying (e.g., a rotation matrix). * The Fibonacci matrix has eigenvalues $\phi \approx 1.618$ and $\psi \approx -0.618$. Since $|\phi| > 1$, the sequence grows exponentially.

Conclusion: The Fibonacci matrix cannot be diagonalized by an orthogonal matrix. Its eigenvectors are not orthogonal. $$ v_1 \cdot v_2 \neq 0 $$ Therefore, you cannot simply use $P^{-1} = P^T$ to simplify the matrix diagonalization process. $P^{-1}$ must be computed explicitly.

3. When Can Fourier Methods Be Used for Recurrence Sequences?¶

Although the Fibonacci matrix itself is not orthogonal, Fourier methods (FFT) are extremely powerful for handling specific types of recurrences or generating functions, but this typically occurs in the following scenarios:

Cyclic Convolution and Polynomial Multiplication: If the recurrence relation involves convolution (e.g., $c_n = \sum a_k b_{n-k}$), using the generating function $C(x) = A(x)B(x)$, the coefficient computation can be completed in $O(n \log n)$ time via FFT (based on the orthogonal Discrete Fourier Transform). This exploits the diagonalization property of circulant matrices, not the Fibonacci matrix.
Root of Unity Filtering: Using the orthogonality of Fourier series ($\sum \omega^{kj} = 0$), specific terms can be extracted from a generating function (e.g., extracting all even-indexed terms $F_{2n}$). This exploits the unitary property of the Discrete Fourier Transform (DFT) matrix, but it acts on the coefficient extraction process, rather than directly diagonalizing the Fibonacci matrix.

Summary Comparison Table¶

Concept	Generating Function Method	Matrix Eigenvalue Method	Fourier/Orthogonal Matrix Method
Core Object	$G(x) = \frac{P(x)}{Q(x)}$	$M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$	$F_N$ (DFT matrix)
Key Quantity	Poles (roots of denominator)	Eigenvalues ($\lambda$)	Roots of Unity ($e^{i 2\pi/N}$)
Relationship	Reciprocal of poles = Eigenvalues	Eigenvalues determine growth rate	Orthogonal basis used for expansion/convolution
Inverse Matrix	Partial Fraction Decomposition	$P^{-1}$ (needs explicit computation)	$U^{-1} = U^H$ (conjugate transpose)
Applicability	All linear recurrences	All linear recurrences	Only cyclic convolution or specific extraction
Applicable to Fibonacci?	Yes (perfect match)	Yes (perfect match)	No (matrix is not orthogonal)

Concept	Generating Function Method	Matrix Eigenvalue Method	Fourier/Orthogonal Matrix Method
Core Object	\(G(x) = \frac{P(x)}{Q(x)}\)	\(M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\)	\(F_N\) (DFT matrix)
Key Quantity	Poles (roots of denominator)	Eigenvalues (\(\lambda\))	Roots of Unity (\(e^{i 2\pi/N}\))
Relationship	Reciprocal of poles = Eigenvalues	Eigenvalues determine growth rate	Orthogonal basis used for expansion/convolution
Inverse Matrix	Partial Fraction Decomposition	\(P^{-1}\) (needs explicit computation)	\(U^{-1} = U^H\) (conjugate transpose)
Applicability	All linear recurrences	All linear recurrences	Only cyclic convolution or specific extraction
Applicable to Fibonacci?	Yes (perfect match)	Yes (perfect match)	No (matrix is not orthogonal)