Vandermonde Matrices

Consider the following linear homogeneous recurrence relation with constant coefficients $a_1, a_2, ..., a_k$ of order $k$:

(1)

\begin{align} \quad f_n = a_1f_{n-1} + a_2f_{n-2} + ... + a_kf_{n-k} \end{align}

We will soon see that if the characteristic equation $x^k - a_1x^{k-1} - a_2x^{k-2} - ... - a_k = 0$ has precisely $k$ distinct roots $q_1, q_2, ..., q_k$ (i.e, $q_i \neq q_j$ for $i, j \in \{1, 2, ..., k \}$ and $i \neq j$) then in solving the linear homogeneous recurrence with constant coefficients above requires us to solve the following system of $k$ equations for the constants $c_1, c_2, ..., c_k$:

(2)

\begin{align} \left\{\begin{matrix} c_1 + c_2 + ... + c_k = f_0\\ c_1q_1 + c_2q_2 + ... + c_kq_k = f_1\\ \vdots\\ c_1q_1^{k-1} + c_2q_2^{k-1} + ... + c_kq_k^{k-1} = f_{k-1} \end{matrix}\right. \end{align}

Since this is a system of $k$ equations in $k$ unknowns, we know that a unique solution exists provided that the following matrix $V$ has a nonzero determinant:

(3)

\begin{align} V = \begin{bmatrix} 1 & 1 & \cdots & 1\\ q_1 & q_2 & \cdots & q_k\\ \vdots &\vdots & \ddots & \vdots \\ q_1^{k-1} & q_2^{k-1} & \cdots & q_k^{k-1} \end{bmatrix} \end{align}

Before we get too far ahead of ourselves, we will need to be able to obtain these matrices from linear homogeneous recurrence relations with constant coefficients. Matrices of the form above are given a special name which we define below.

Definition: For $q_1, q_2, ..., q_k$ as distinct roots to the characteristic equation $x^k - a_1x^{k-1} - a_2x^{k-2} - ... - a_k = 0$, the corresponding Vandermonde Matrix is the matrix $V$ given by $V = \begin{bmatrix} 1 & 1 & \cdots & 1\\ q_1 & q_2 & \cdots & q_k\\ \vdots &\vdots & \ddots & \vdots \\ q_1^{k-1} & q_2^{k-1} & \cdots & q_k^{k-1} \end{bmatrix}$.

For example, consider the following second order linear homogeneous recurrence relation with constant coefficients for $n \geq 2$

(4)

\begin{align} \quad f_n = 9f_{n-2} \end{align}

We can rewrite this as:

(5)

\begin{align} \quad f_n - 9f_{n-2} = 0 \end{align}

The corresponding characteristic equation is:

(6)

\begin{align} \quad x^2 - 9 = 0 \end{align}

The roots of the characteristic equation above are $q_1 = 3$ and $q_2 = -3$. Therefore the Vandermonde Matrix for this linear homogeneous recurrence relation with constant coefficients is:

(7)

\begin{align} \quad V = \begin{bmatrix} 1 & 1\\ 3 & -3 \end{bmatrix} \end{align}

For a more complicated example, consider the following third order linear homogeneous recurrence relation with constant coefficients:

(8)

\begin{align} \quad f_n = -7f_{n-1} - 14f_{n-2} - 8f_{n-3} \end{align}

This can be rewritten as:

(9)

\begin{align} \quad f_n + 7f_{n-1} + 14f_{n-2} + 8f_{n-3} = 0 \end{align}

The corresponding characteristic equation is:

(10)

\begin{align} \quad x^3 + 7x^2 + 14x + 8 = 0 \end{align}

The roots of this characteristic equation are $q_1 = -1$, $q_2 = -2$, and $q_3 = -4$, all of which are distinct. Therefore the Vandermonde matrix for this linear homogeneous recurrence relation with constant coefficients is:

(11)

\begin{align} \quad V = \begin{bmatrix} 1 & 1 & 1\\ -1 & -2 & -4\\ 1 & 4 & 16 \end{bmatrix} \end{align}