Matrix difference equation

A matrix difference equation 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. The order of the equation is the maximum time gap between any two indicated values of the variable vector. For example,

${𝐱}_t={𝐀𝐱}_{t-1}+{𝐁𝐱}_{t-2}$

is an example of a second-order matrix difference equation, in which Template:Math is an Template:Math vector of variables and Template:Math and Template:Math are Template:Math 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

${𝐱}_{t+2}={𝐀𝐱}_{t+1}+{𝐁𝐱}_t$

or as

${𝐱}_n={𝐀𝐱}_{n-1}+{𝐁𝐱}_{n-2}$

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

Nonhomogeneous first-order case and the steady state

An example of a nonhomogeneous first-order matrix difference equation is

${𝐱}_t={𝐀𝐱}_{t-1}+𝐛$

with additive constant vector Template:Math. The steady state of this system is a value Template:Math of the vector Template:Math which, if reached, would not be deviated from subsequently. Template:Math is found by setting Template:Math in the difference equation and solving for Template:Math to obtain

${𝐱}^{*}=[𝐈-𝐀{]}^{-1}𝐛$

where Template:Math is the Template:Math identity matrix, and where it is assumed that Template:Math is invertible. Then the nonhomogeneous equation can be rewritten in homogeneous form in terms of deviations from the steady state:

$[{𝐱}_t-{𝐱}^{*}]=𝐀[{𝐱}_{t-1}-{𝐱}^{*}]$

Stability of the first-order case

The first-order matrix difference equation Template:Math is stable—that is, Template:Math converges asymptotically to the steady state Template:Math—if and only if all eigenvalues of the transition matrix Template:Math (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 Template:Math. Then we can iterate and substitute repeatedly from the initial condition Template:Math, which is the initial value of the vector Template:Math and which must be known in order to find the solution:

$\begin{array}{cc}{𝐲}_1& ={𝐀𝐲}_0\\ {𝐲}_2& ={𝐀𝐲}_1={𝐀}^2{𝐲}_0\\ {𝐲}_3& ={𝐀𝐲}_2={𝐀}^3{𝐲}_0\end{array}$

and so forth, so that by mathematical induction the solution in terms of Template:Mvar is

${𝐲}_t={𝐀}^t{𝐲}_0$

Further, if Template:Math is diagonalizable, we can rewrite Template:Math in terms of its eigenvalues and eigenvectors, giving the solution as

${𝐲}_t={𝐏𝐃}^t{𝐏}^{-1}{𝐲}_0,$

where Template:Math is an Template:Math matrix whose columns are the eigenvectors of Template:Math (assuming the eigenvalues are all distinct) and Template:Math is an Template:Math diagonal matrix whose diagonal elements are the eigenvalues of Template:Math. This solution motivates the above stability result: Template:Math shrinks to the zero matrix over time if and only if the eigenvalues of Template:Mvar 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 Template:Math-dimensional system Template:Math, we can extract the dynamics of one of the state variables, say Template:Math. The above solution equation for Template:Mvar shows that the solution for Template:Math is in terms of the Template:Mvar eigenvalues of Template:Math. Therefore the equation describing the evolution of Template:Math by itself must have a solution involving those same eigenvalues. This description intuitively motivates the equation of evolution of Template:Math, 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 Template:Mvar are from the characteristic equation of the matrix Template:Math:

${\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 Template:Mvar-dimensional first-order linear system evolves according to a univariate Template:Mvarth-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 (matrix of matrices). For example, suppose we have the second-order equation

${𝐱}_t={𝐀𝐱}_{t-1}+{𝐁𝐱}_{t-2}$

with the variable vector Template:Math being Template:Math and Template:Math and Template:Math being Template:Math. This can be stacked in the form

$\left[\begin{array}{c}{𝐱}_t\\ {𝐱}_{t-1}\end{array}\right]=\left[\begin{array}{cc}𝐀& 𝐁\\ 𝐈& \mathrm{𝟎}\end{array}\right]\left[\begin{array}{c}{𝐱}_{t-1}\\ {𝐱}_{t-2}\end{array}\right]$

where Template:Math is the Template:Math identity matrix and Template:Math is the Template:Math zero matrix. Then denoting the Template:Math stacked vector of current and once-lagged variables as Template:Math and the Template:Math block matrix as Template:Math, we have as before the solution

${𝐳}_t={𝐋}^t{𝐳}_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 Template:Math 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 reverse evolution of a current-and-future-cost matrix, denoted below as Template:Math. 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 controlled by manipulating an exogenous vector in order to optimize a quadratic cost function. This Riccati equation assumes the following, or a similar, form:

${𝐇}_{t-1}=𝐊+{𝐀}^{\prime }{𝐇}_t𝐀-{𝐀}^{\prime }{𝐇}_t𝐂{[{𝐂}^{\prime }{𝐇}_t𝐂+𝐑]}^{-1}{𝐂}^{\prime }{𝐇}_t𝐀$

where Template:Math, Template:Math, and Template:Math are Template:Math, Template:Math is Template:Math, Template:Math is Template:Math, Template:Math is the number of elements in the vector to be controlled, and Template:Math is the number of elements in the control vector. The parameter matrices Template:Math and Template:Math are from the linear equation, and the parameter matrices Template:Math and Template:Math are from the quadratic cost function. See here for details.

In general this equation cannot be solved analytically for Template:Math in terms of Template:Mvar; rather, the sequence of values for Template:Math is found by iterating the Riccati equation. However, it has been shown that this Riccati equation can be solved analytically if Template:Math and Template:Math, by reducing it to a scalar rational difference equation; moreover, for any Template:Mvar and Template:Mvar if the transition matrix Template:Math 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.

In most contexts the evolution of Template:Math backwards through time is stable, meaning that Template:Math converges to a particular fixed matrix Template:Math which may be irrational even if all the other matrices are rational. See also Template:Section link.

A related Riccati equation is

${𝐗}_{t+1}=-[𝐄+𝐁{𝐗}_t]{[𝐂+𝐀{𝐗}_t]}^{-1}$

in which the matrices Template:Math are all Template:Math. This equation can be solved explicitly. Suppose ${𝐗}_t={𝐍}_t{𝐃}_t^{-1},$ which certainly holds for Template:Math with Template:Math and with Template:Math. Then using this in the difference equation yields

$\begin{array}{cc}{𝐗}_{t+1}& =-[𝐄+{𝐁𝐍}_t{𝐃}_t^{-1}]{𝐃}_t{𝐃}_t^{-1}{[𝐂+{𝐀𝐍}_t{𝐃}_t^{-1}]}^{-1}\\ & =-[{𝐄𝐃}_t+{𝐁𝐍}_t]{\left[[𝐂+{𝐀𝐍}_t{𝐃}_t^{-1}]{𝐃}_t\right]}^{-1}\\ & =-[{𝐄𝐃}_t+{𝐁𝐍}_t]{[{𝐂𝐃}_t+{𝐀𝐍}_t]}^{-1}\\ & ={𝐍}_{t+1}{𝐃}_{t+1}^{-1}\end{array}$

so by induction the form ${𝐗}_t={𝐍}_t{𝐃}_t^{-1}$ holds for all Template:Mvar. Then the evolution of Template:Math and Template:Math can be written as

$\left[\begin{array}{c}{𝐍}_{t+1}\\ {𝐃}_{t+1}\end{array}\right]=\left[\begin{array}{cc}-𝐁& -𝐄\\ 𝐀& 𝐂\end{array}\right]\left[\begin{array}{c}{𝐍}_t\\ {𝐃}_t\end{array}\right]\equiv 𝐉\left[\begin{array}{c}{𝐍}_t\\ {𝐃}_t\end{array}\right]$

Thus by induction

$\left[\begin{array}{c}{𝐍}_t\\ {𝐃}_t\end{array}\right]={𝐉}^t\left[\begin{array}{c}{𝐍}_0\\ {𝐃}_0\end{array}\right]$

See also

• Matrix differential equation
• Difference equation
• Linear difference equation
• Dynamical system
• Algebraic Riccati equation