Linear Algebra – Eigenvalues and eigenvectors – Discrete dynamical systems

A discrete dynamical system is given by \(\mathbf{x}_{k+1}=A\mathbf{x}_k\) for \(k=0,1,2,\ldots\), where \(A\) is a square matrix. Starting with an initial state \(\mathbf{x}_0\) multiplication by \(A\) leads to the next state \(\mathbf{x}_1=A\mathbf{x}_0\), \(A\mathbf{x}_2=A\mathbf{x}_1=A^2\mathbf{x}_0\), and so on. Note that this implies that \(\mathbf{x}_k=A^k\mathbf{x}_0\) for \(k=0,1,2,\ldots\).

If \(A\) is an \(n\times n\) matrix which is diagonalizable, then there exists a basis \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) of \(\mathbb{R}^n\) consisting of eigenvectors of \(A\) corresponding to the eigenvalues \(\lambda_1,\ldots,\lambda_n\) respectively. Then, every initial state \(\mathbf{x}_0\in\mathbb{R}^n\) can be written as a linear combination of these eigenvectors:

\[\mathbf{x}_0=c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n.\]

This implies that

\[\mathbf{x}_1=A\mathbf{x}_0=A\left(c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n\right)=c_1A\mathbf{v}_1+\cdots+c_nA\mathbf{v}_n =c_1\lambda_1\mathbf{v}_1+\cdots+c_n\lambda_n\mathbf{v}_n.\]

In general we have:

\[\mathbf{x}_k=c_1\lambda_1^k\mathbf{x}_1+\cdots+c_n\lambda_n^k\mathbf{v}_n,\quad k=0,1,2,\ldots.\]

Markov chains

A special case of a discrete dynamical system leads to a so-called Markov chain, that is a sequence of probability vectors \(\mathbf{x}_0\), \(\mathbf{x}_1\), \(\mathbf{x}_2\), \(\ldots\) given by a difference equation \(\mathbf{x}_{k+1}=M\mathbf{x}_k\) with \(k=0,1,2,\ldots\), where \(M\) is a stochastic (or Markov) matrix.

Definition: A vector with nonnegative entries that add up to \(1\) is called a probability vector. A stochastic matrix (or Markov matrix) is a square matrix whose columns are probability vectors.

Example: Consider the discrete dynamical system \(\mathbf{x}_{k+1}=A\mathbf{x}_k\) with \(k=0,1,2,\ldots\) and \(A=\begin{pmatrix}\frac{1}{2}&\frac{1}{4}\\\frac{1}{2}&\frac{3}{4}\end{pmatrix}\). Note that \(A\) is a stochastic (or Markov) matrix. Now we have:

\[\det(A-\lambda I)=\begin{vmatrix}\frac{1}{2}-\lambda&\frac{1}{4}\\\frac{1}{2}&\frac{3}{4}-\lambda\end{vmatrix} =\lambda^2-\tfrac{5}{4}\lambda+\tfrac{1}{4}=(\lambda-1)(\lambda-\tfrac{1}{4}).\]

So, the eigenvalues are \(\lambda_1=1\) and \(\lambda_2=\frac{1}{4}\). Further we have:

\[\lambda_1=1:\quad\begin{pmatrix}-\frac{1}{2}&\frac{1}{4}\\\frac{1}{2}&-\frac{1}{4}\end{pmatrix} \sim\begin{pmatrix}-2&1\\0&0\end{pmatrix}\quad\Longrightarrow\quad\mathbf{v}_1=\begin{pmatrix}1\\2\end{pmatrix}\]

and

\[\lambda_2=\tfrac{1}{4}:\quad\begin{pmatrix}\frac{1}{4}&\frac{1}{4}\\\frac{1}{2}&\frac{1}{2}\end{pmatrix} \sim\begin{pmatrix}1&1\\0&0\end{pmatrix}\quad\Longrightarrow\quad\mathbf{v}_2=\begin{pmatrix}1\\-1\end{pmatrix}.\]

We conclude that

\[\mathbf{x}_k=c_1\lambda_1^k\mathbf{v}_1+c_2\lambda_2^k\mathbf{v}_2=c_1\begin{pmatrix}1\\2\end{pmatrix} +c_2\left(\tfrac{1}{4}\right)^k\begin{pmatrix}1\\-1\end{pmatrix},\quad k=0,1,2,\ldots,\]

where \(c_1\) and \(c_2\) can be determined from the initial state: \(\mathbf{x}_0=c_1\mathbf{v}_1+c_2\mathbf{v}_2\). For instance, if \(\mathbf{x}_0=\begin{pmatrix}\frac{1}{2}\\\frac{1}{2}\end{pmatrix}\), then we have:

\[c_1\begin{pmatrix}1\\2\end{pmatrix}+c_2\begin{pmatrix}1\\-1\end{pmatrix}=\begin{pmatrix}\frac{1}{2}\\\frac{1}{2}\end{pmatrix}: \quad\left(\left.\begin{matrix}1&1\\2&-1\end{matrix}\,\right|\,\begin{matrix}\frac{1}{2}\\\frac{1}{2}\end{matrix}\right) \sim\left(\left.\begin{matrix}1&1\\0&-3\end{matrix}\,\right|\,\begin{matrix}\frac{1}{2}\\-\frac{1}{2}\end{matrix}\right) \sim\left(\left.\begin{matrix}3&0\\0&3\end{matrix}\,\right|\,\begin{matrix}1\\\frac{1}{2}\end{matrix}\right) \quad\Longrightarrow\quad\left\{\begin{array}{l}c_1=\frac{1}{3}\\[2.5mm]c_2=\frac{1}{6}.\end{array}\right.\]

Now we have: \(\lim\limits_{k\to\infty}\mathbf{x}_k=\frac{1}{3}\begin{pmatrix}1\\2\end{pmatrix}\). This is called a steady-state or equilibrium vector.

Theorem: Every stochastic (or Markov) matrix \(M\) has a steady-state or equilibrium vector \(\mathbf{q}\), which is a probability vector such that \(M\mathbf{q}=\mathbf{q}\).
So, \(\mathbf{q}\) is an eigenvector of \(M\) corresponding to the eigenvalue \(1\).

If \(M\) is a stochastic (or Markov) matrix, then the entries in every column add up to \(1\). This implies that \(\det(M-\lambda I)\) is equal to the determinant of the matrix that arise from \(M-\lambda I\) by adding all other rows to the first one (for instance). Then all entries in the first row are equal to \(1-\lambda\) which implies that \(1-\lambda\) is a factor of the characteristic polynomial \(\det(M-\lambda I)\). This implies that \(\lambda=1\) is an eigenvalue of \(M\). It is much more difficult to show that there exists a probability vector that is an eigenvector of \(M\) corresponding to this eigenvalue \(\lambda=1\).

Example: Earlier we considered an example of a car rental company with three locations (airport, city center and suburbs):

\[\mathbf{x}_{k+1}=A\mathbf{x}_k,\quad k=0,1,2,\ldots\quad\text{with}\quad A=\begin{pmatrix}0.85&0.15&0.15\\0.10&0.80&0.05\\0.05&0.05&0.80\end{pmatrix}.\]

Note that \(A\) is a stochastic (or Markov) matrix. Now we have:

\begin{align*} \det(A-\lambda I)&=\begin{vmatrix}0.85-\lambda&0.15&0.15\\0.10&0.80-\lambda&0.05\\0.05&0.05&0.80-\lambda\end{vmatrix} =\begin{vmatrix}1-\lambda&1-\lambda&1-\lambda\\0.10&0.80-\lambda&0.05\\0.05&0.05&0.80-\lambda\end{vmatrix} =\begin{vmatrix}1-\lambda&0&0\\0.10&0.70-\lambda&-0.05\\0.05&0&0.75-\lambda\end{vmatrix}\\[2.5mm] &=(1-\lambda)\begin{vmatrix}0.70-\lambda&-0.05\\0&0.75-\lambda\end{vmatrix}=(1-\lambda)(0.75-\lambda)(0.70-\lambda). \end{align*}

This implies that the eigenvalues are \(\lambda_1=1\), \(\lambda_2=0.75\) and \(\lambda_3=0.70\). Further we have:

\[\lambda_1=1:\quad\begin{pmatrix}-0.15&0.15&0.15\\0.10&-0.20&0.05\\0.05&0.05&-0.20\end{pmatrix} \sim\begin{pmatrix}1&-1&-1\\2&-4&1\\1&1&-4\end{pmatrix}\sim\begin{pmatrix}1&-1&-1\\0&-2&3\\0&2&-3\end{pmatrix} \sim\begin{pmatrix}2&0&-5\\0&2&-3\\0&0&0\end{pmatrix}\quad\Longrightarrow\quad\mathbf{v}_1=\begin{pmatrix}5\\3\\2\end{pmatrix},\] \[\lambda_2=0.75:\quad\begin{pmatrix}0.05&0.15&0.15\\0.10&0.05&0.05\\0.05&0.05&0.05\end{pmatrix} \sim\begin{pmatrix}1&3&3\\2&1&1\\1&1&1\end{pmatrix}\sim\begin{pmatrix}1&1&1\\0&1&1\\0&0&0\end{pmatrix} \sim\begin{pmatrix}1&0&0\\0&1&1\\0&0&0\end{pmatrix}\quad\Longrightarrow\quad\mathbf{v}_2=\begin{pmatrix}0\\1\\-1\end{pmatrix}\]

and

\[\lambda_3=0.70:\quad\begin{pmatrix}0.15&0.15&0.15\\0.10&0.10&0.05\\0.05&0.05&0.10\end{pmatrix} \sim\begin{pmatrix}1&1&1\\2&2&1\\1&1&2\end{pmatrix}\sim\begin{pmatrix}1&1&1\\0&0&1\\0&0&0\end{pmatrix} \sim\begin{pmatrix}1&1&0\\0&0&1\\0&0&0\end{pmatrix}\quad\Longrightarrow\quad\mathbf{v}_3=\begin{pmatrix}1\\-1\\0\end{pmatrix}.\]

Hence we have

\[\mathbf{x}_k=c_1\lambda_1^k\mathbf{v}_1+c_2\lambda_2^k\mathbf{v}_2+c_3\lambda_3^k\mathbf{v}_3=c_1\begin{pmatrix}5\\3\\2\end{pmatrix} +c_2\left(0.75\right)^k\begin{pmatrix}0\\1\\-1\end{pmatrix}+c_3\left(0.70\right)^k\begin{pmatrix}1\\-1\\0\end{pmatrix},\quad k=0,1,2,\ldots,\]

where \(c_1\), \(c_2\) and \(c_3\) can be determined from the initial state: \(\mathbf{x}_0=c_1\mathbf{v}_1+c_2\mathbf{v}_2+c_3\mathbf{v}_3\). For instance, if \(\mathbf{x}_0=\begin{pmatrix}0.40\\0.30\\0.30\end{pmatrix}\), then we have:

\[c_1\begin{pmatrix}5\\3\\2\end{pmatrix}+c_2\begin{pmatrix}0\\1\\-1\end{pmatrix}+c_3\begin{pmatrix}1\\-1\\0\end{pmatrix}=\begin{pmatrix}0.40\\0.30\\0.30\end{pmatrix} \quad\Longrightarrow\quad c_1=0.10,\quad c_2=-0.10\quad\text{and}\quad c_3=-0.10.\]

Since \(\mathbf{x}_0\) is a stochastic vector, this leads to a Markov chain. However, it is also possible to work with numbers of cars (for instance):

\[\mathbf{x}_0=\begin{pmatrix}40\\30\\30\end{pmatrix}\quad\Longrightarrow\quad\mathbf{x}_k=\begin{pmatrix}50\\30\\20\end{pmatrix} -(0.75)^k\begin{pmatrix}0\\10\\-10\end{pmatrix}-(0.70)^k\begin{pmatrix}10\\-10\\0\end{pmatrix},\quad k=0,1,2,\ldots.\]

Note that \(\lim\limits_{k\to\infty}\mathbf{x}_k=\begin{pmatrix}50\\30\\20\end{pmatrix}\), which means that the optimal division of the cars among the three locations is: \(50\) at the airport, \(30\) at the city center and \(20\) at the suburbs. However, since the eigenvalues are the same for each initial state \(\mathbf{x}_0\) every (reasonable) division of the cars will eventually stabilize to the steady-state or equilibrium vector \(\begin{pmatrix}50\\30\\20\end{pmatrix}\).

The solution of a discrete dynamical system \(\mathbf{x}_{k+1}=A\mathbf{x}_k\) with \(k=0,1,2,\ldots\) can be written as \(\mathbf{x}_k=A^k\mathbf{x}_0\) for \(k=0,1,2,\ldots\). If \(A\) is diagonizable, then we have: \(A=PDP^{-1}\) for some invertible matrix \(P\) and diagonal matrix \(D\). In that case we have: \(A^k=PD^kP^{-1}\).

Suppose that \(A\) is diagonizable and that \(A=PDP^{-1}\) for some invertible matrix \(P\) and diagonal matrix \(D\). Now set \(\mathbf{x}_k=P\mathbf{y}_k\) for \(k=0,1,2,\ldots\), then we have:

\[\mathbf{x}_{k+1}=A\mathbf{x}_k\quad\Longleftrightarrow\quad P\mathbf{y}_{k+1}=AP\mathbf{y}_k=PDP^{-1}P\mathbf{y}_k=PD\mathbf{y}_k,\quad k=0,1,2,\ldots.\]

Since \(P\) is invertible, we can (left) multiply by \(P^{-1}\) to obtain that

\[\mathbf{x}_{k+1}=A\mathbf{x}_k\quad\Longleftrightarrow\quad\mathbf{y}_{k+1}=D\mathbf{y}_k,\quad k=0,1,2,\ldots.\]

If \(D=\text{diag}(\lambda_1,\ldots,\lambda_n)\) this implies that \(\mathbf{y}_k=\begin{pmatrix}c_1\lambda_1^k\\\vdots\\c_n\lambda_n^k\end{pmatrix}\) for \(k=0,1,2,\ldots\). Let \(P=\Bigg(\mathbf{v}_1\;\ldots\;\mathbf{v}_n\Bigg)\), then we have:

\[\mathbf{x}_k=P\mathbf{y}_k=\Bigg(\mathbf{v}_1\;\ldots\;\mathbf{v}_n\Bigg)\begin{pmatrix}c_1\lambda_1^k\\\vdots\\c_n\lambda_n^k\end{pmatrix} =c_1\lambda_1^k\mathbf{v}_1+\cdots+c_n\lambda_n^k\mathbf{v}_n,\quad k=0,1,2,\ldots.\]

In the case of a \(2\times2\) matrix \(A\) we can plot the sequence of vectors \(\{\mathbf{x}_k\}_{k=0}^{\infty}\) that satisfy the discrete dynamical system \(\mathbf{x}_{k+1}=A\mathbf{x}_k\) for \(k=0,1,2\ldots\) in the plane \(\mathbb{R}^2\). The graph of \(\{\mathbf{x}_k\}_{k=0}^{\infty}\) is called a trajectory of the discrete dynamical system. Note that such a trajectory consists of 'single points' in \(\mathbb{R}^2\) which only depend on the initial state \(\mathbf{x}_0\).

Let \(A\) be diagonizable with eigenvectors \(\mathbf{v}_1\) and \(\mathbf{v}_2\) corresponding to the eigenvalues \(\lambda_1\) and \(\lambda_2\) respectively. Then the behaviour of the solutions \(\mathbf{x}_k=c_1\lambda_1^k\mathbf{v}_1+c_2\lambda_2^k\mathbf{v}_2\) with \(k=0,1,2,\ldots\) is determined by the eigenvalues.

If \(|\lambda_1| < 1\) and \(|\lambda_2| < 1\), then all solutions tend to the origin for \(k\to\infty\). In that case the origin is called an attractor of the dynamical system.

If \(|\lambda_1| > 1\) and \(|\lambda_2| > 1\), then all solutions tend to infinity (away from the origin) for \(k\to\infty\). In that case the origin is called a repeller of the dynamical system.

If \(|\lambda_1| > 1\) and \(|\lambda_2| < 1\), then the origin is called a saddle point of the dynamical system. Some trajectories tend towards the origin, while others move away from the origin and tend to infinity depending on the initial state \(\mathbf{x}_0\).

In the case of nonreal eigenvalues \(\lambda=\alpha\pm i\beta\) with \(\alpha,\beta\in\mathbb{R}\) and \(\beta\neq0\) the trajectories have the form of a spiral, which move toward the origin if \(|\lambda|=\sqrt{\alpha^2+\beta^2} < 1\) and tend to infinity (move away from the origin) if \(|\lambda|=\sqrt{\alpha^2+\beta^2} > 1\).

---

Last modified on April 5, 2021