Matrix difference equation

From Wikipedia, the free encyclopedia

A matrix difference equation^[1]^[2] is a difference equation in which the value of a vector (or sometimes, a matrix) of variables at one point in time is related to its own value at one or more previous points in time, using matrices. Occasionally, the time-varying entity may itself be a matrix instead of a vector. The order of the equation is the maximum time gap between any two indicated values of the variable vector. For example,

$x_{t}=Ax_{{t-1}}+Bx_{{t-2}}$

is an example of a second-order matrix difference equation, in which x is an n × 1 vector of variables and A and B are n×n matrices. This equation is homogeneous because there is no vector constant term added to the end of the equation. The same equation might also be written as

$x_{{t+2}}=Ax_{{t+1}}+Bx_{{t}}$

or as

$x_{n}=Ax_{{n-1}}+Bx_{{n-2}}$ .

The most commonly encountered matrix difference equations are first-order.

Non-homogeneous first-order matrix difference equations and the steady state

An example of a non-homogeneous first-order matrix difference equation is

$x_{t}=Ax_{{t-1}}+b\,$

with additive constant vector b. The steady state of this system is a value x* of the vector x which, if reached, would not be deviated from subsequently. x* is found by setting $x_{t}=x_{{t-1}}=x*$ in the difference equation and solving for x* to obtain

$x^{{*}}=[I-A]^{{-1}}b\,$

where $I$ is the n×n identity matrix, and where it is assumed that $[I-A]$ is invertible. Then the non-homogeneous equation can be rewritten in homogeneous form in terms of deviations from the steady state:

$[x_{t}-x^{{*}}]=A[x_{{t-1}}-x^{{*}}].\,$

Stability of the first-order case

The first-order matrix difference equation [x_t - x*] = A[x_t-1-x*] is stable -- that is, $x_{t}$ converges asymptotically to the steady state x* -- if and only if all eigenvalues of the transition matrix A (whether real or complex) have an absolute value which is less than 1.

Solution of the first-order case

Assume that the equation has been put in the homogeneous form $y_{t}=Ay_{{t-1}}$ . Then we can iterate and substitute repeatedly from the initial condition $y_{0}$ , which is the initial value of the vector y and which must be known in order to find the solution:

$y_{1}=Ay_{0},$

$y_{2}=Ay_{1}=AAy_{0}=A^{{2}}y_{0},$

$y_{3}=Ay_{2}=AA^{{2}}y_{0}=A^{{3}}y_{0},$

and so forth. By induction, we obtain the solution in terms of t:

$y_{t}=A^{t}y_{0}=PD^{{t}}P^{{-1}}y_{0},$

where P is an n × n matrix whose columns are the eigenvectors of A (assuming the eigenvalues are all distinct) and D is an n × n diagonal matrix whose diagonal elements are the eigenvalues of A. This solution motivates the above stability result: $A^{t}$ shrinks to the zero matrix over time if and only if the eigenvalues of A are all less than unity in absolute value.

Extracting the dynamics of a single scalar variable from a first-order matrix system

Starting from the n-dimensional system $y_{t}=Ay_{{t-1}},$ we can extract the dynamics of one of the state variables, say $y_{1}.$ The above solution equation for $y_{t}$ shows that the solution for $y_{{1,t}}$ is in terms of the n eigenvalues of A. Therefore the equation describing the evolution of $y_{1}$ by itself must have a solution involving those same eigenvalues. This description intuitively motivates the equation of evolution of $y_{1},$ which is

$y_{{1,t}}=a_{1}y_{{1,t-1}}+a_{2}y_{{1,t-2}}+\dots +a_{n}y_{{1,t-n}}$

where the parameters $a_{i}$ are from the characteristic equation of the matrix A:

$\lambda ^{{n}}-a_{1}\lambda ^{{n-1}}-a_{2}\lambda ^{{n-2}}-\dots -a_{n}\lambda ^{{0}}=0.$

Thus each individual scalar variable of an n-dimensional first-order linear system evolves according to a univariate n^th degree difference equation, which has the same stability property (stable or unstable) as does the matrix difference equation.

Solution and stability of higher-order cases

Matrix difference equations of higher order—that is, with a time lag longer than one period—can be solved, and their stability analyzed, by converting them into first-order form using a block matrix. For example, suppose we have the second-order equation

$x_{t}=Ax_{{t-1}}+Bx_{{t-2}}$

with the variable vector x being n×1 and A and B being n×n. This can be stacked in the form

${\begin{pmatrix}x_{t}\\x_{{t-1}}\\\end{pmatrix}}={\begin{pmatrix}{\text{A}}&{\text{B}}\\{\text{I}}&0\\\end{pmatrix}}{\begin{pmatrix}x_{{t-1}}\\x_{{t-2}}\end{pmatrix}},$

where $I$ is the n×n identity matrix and 0 is the n×n zero matrix. Then denoting the 2n×1 stacked vector of current and once-lagged variables as $z_{t}$ and the 2n×2n block matrix as L, we have as before the solution

$z_{t}=L^{{t}}z_{0}.$

Also as before, this stacked equation and thus the original second-order equation are stable if and only if all eigenvalues of the matrix L are smaller than unity in absolute value.

Nonlinear matrix difference equations: Riccati equations

In linear-quadratic-Gaussian control, there arises a nonlinear matrix equation for the evolution backwards through time of a current-and-future-cost matrix, denoted below as H. This equation is called a discrete dynamic Riccati equation, and it arises when a variable vector evolving according to a linear matrix difference equation is to be controlled by manipulating an exogenous vector in order to optimize a quadratic cost function. This Riccati equation assumes the following form or a similar form:

$H_{{t-1}}=K+A'H_{t}A-A'H_{t}C(C'H_{t}C+R)^{{-1}}C'H_{t}A,\,$

where H, K, and A are n×n, C is n×k, R is k×k, n is the number of elements in the vector to be controlled, and k is the number of elements in the control vector. The parameter matrices A and C are from the linear equation, and the parameter matrices K and R are from the quadratic cost function.

In general this equation cannot be solved analytically for $H_{t}$ in terms of t ; rather, the sequence of values for $H_{t}$ is found by iterating the Riccati equation. However, it was shown in ^[3] that this Riccati equation can be solved analytically if R is the zero matrix and n=k+1, by reducing it to a scalar rational difference equation; moreover, for any k and n if the transition matrix A is nonsingular then the Riccati equation can be solved analytically in terms of the eigenvalues of a matrix, although these may need to be found numerically.^[4]

In most contexts the evolution of H backwards through time is stable, meaning that H converges to a particular fixed matrix H* which may be irrational even if all the other matrices are rational.

A related Riccati equation^[5] is

$X_{{t+1}}=-(E+BX_{t})(C+AX_{t})^{{-1}}$

in which the matrices X, A, B, C, and E are all n×n. This equation can be solved explicitly. Suppose $X_{t}=N_{t}D_{t}^{{-1}}$ , which certainly holds for t=0 with N₀ = X₀ and with D₀ equal to the identity matrix. Then using this in the difference equation yields

$X_{{t+1}}=-(E+BN_{t}D_{t}^{{-1}})D_{t}D_{t}^{{-1}}(C+AN_{t}D_{t}^{{-1}})^{{-1}}$

$=-(ED_{t}+BN_{t})[(C+AN_{t}D_{t}^{{-1}})D_{t}]^{{-1}}$

$=-(ED_{t}+BN_{t})[CD_{t}+AN_{t}]^{{-1}}$

$=N_{{t+1}}D_{{t+1}}^{{-1}},$

so by induction the form $X_{t}=N_{t}D_{t}^{{-1}}$ holds for all t. Then the evolution of N and D can be written as

${\begin{pmatrix}N_{{t+1}}\\D_{{t+1}}\end{pmatrix}}={\begin{pmatrix}-B&-E\\A&C\end{pmatrix}}{\begin{pmatrix}N_{t}\\D_{t}\end{pmatrix}}=J{\begin{pmatrix}N_{t}\\D_{t}\end{pmatrix}}.$

Thus

${\begin{pmatrix}N_{t}\\D_{t}\end{pmatrix}}=J^{{t}}{\begin{pmatrix}N_{0}\\D_{0}\end{pmatrix}}.$

References

↑ Cull, Paul; Flahive, Mary; and Robson, Robbie. Difference Equations: From Rabbits to Chaos, Springer, 2005, chapter 7; ISBN 0-387-23234-6.
↑ Chiang, Alpha C., Fundamental Methods of Mathematical Economics, third edition, McGraw-Hill, 1984: 608–612.
↑ Balvers, Ronald J., and Mitchell, Douglas W., "Reducing the dimensionality of linear quadratic control problems," Journal of Economic Dynamics and Control 31, 2007, 141–159.
↑ Vaughan, D. R., "A nonrecursive algebraic solution for the discrete Riccati equation," IEEE Transactions on Automatic Control 15, 1970, 597-599.
↑ Martin, C. F., and Ammar, G., "The geometry of the matrix Riccati equation and associated eigenvalue method," in Bittani, Laub, and Willems (eds.), The Riccati Equation, Springer-Verlag, 1991.