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.^[1]^[2] 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 $x$ is an $n \times 1$ vector of variables and $A$ and $B$ are $n \times 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

𝐱_{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 $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

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

where $I$ is the $n \times n$ identity matrix, and where it is assumed that $[I - A]$ 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 $[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:

\begin{matrix} 𝐲_{1} & = {𝐀 𝐲}_{0} \\ 𝐲_{2} & = {𝐀 𝐲}_{1} = 𝐀^{2} 𝐲_{0} \\ 𝐲_{3} & = {𝐀 𝐲}_{2} = 𝐀^{3} 𝐲_{0} \end{matrix}

and so forth, so that by mathematical induction the solution in terms of $t$ is

𝐲_{t} = 𝐀^{t} 𝐲_{0}

Further, if $A$ is diagonalizable, we can rewrite $A$ in terms of its eigenvalues and eigenvectors, giving the solution as

𝐲_{t} = {𝐏 𝐃}^{t} 𝐏^{- 1} 𝐲_{0},

where $P$ is an $n \times n$ matrix whose columns are the eigenvectors of $A$ (assuming the eigenvalues are all distinct) and $D$ is an $n \times 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$ :

λ^{n} - a_{1} λ^{n - 1} - a_{2} λ^{n - 2} - \dots - a_{n} λ^{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 (matrix of matrices). For example, suppose we have the second-order equation

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

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

[\begin{matrix} 𝐱_{t} \\ 𝐱_{t - 1} \end{matrix}] = [\begin{matrix} 𝐀 & 𝐁 \\ 𝐈 & 𝟎 \end{matrix}] [\begin{matrix} 𝐱_{t - 1} \\ 𝐱_{t - 2} \end{matrix}]

where $I$ is the $n \times n$ identity matrix and $0$ is the $n \times n$ zero matrix. Then denoting the $2 n \times 1$ stacked vector of current and once-lagged variables as $z t$ and the $2 n \times 2 n$ block matrix as $L$ , 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 $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 reverse evolution 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 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} = 𝐊 + 𝐀^{'} 𝐇_{t} 𝐀 - 𝐀^{'} 𝐇_{t} 𝐂 {[𝐂^{'} 𝐇_{t} 𝐂 + 𝐑]}^{- 1} 𝐂^{'} 𝐇_{t} 𝐀

where $H$ , $K$ , and $A$ are $n \times n$ , $C$ is $n \times k$ , $R$ is $k \times 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. See here for details.

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 has been shown^[3] that this Riccati equation can be solved analytically if $R = 0$ 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. See also Stochastic control § Discrete time.

A related Riccati equation^[5] is

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

in which the matrices $X, A, B, C, E$ are all $n \times n$ . This equation can be solved explicitly. Suppose $𝐗_{t} = 𝐍_{t} 𝐃_{t}^{- 1},$ which certainly holds for $t = 0$ with $N 0 = X 0$ and with $D 0 = I$ . Then using this in the difference equation yields

\begin{matrix} 𝐗_{t + 1} & = - [𝐄 + {𝐁 𝐍}_{t} 𝐃_{t}^{- 1}] 𝐃_{t} 𝐃_{t}^{- 1} {[𝐂 + {𝐀 𝐍}_{t} 𝐃_{t}^{- 1}]}^{- 1} \\ = - [{𝐄 𝐃}_{t} + {𝐁 𝐍}_{t}] {[[𝐂 + {𝐀 𝐍}_{t} 𝐃_{t}^{- 1}] 𝐃_{t}]}^{- 1} \\ = - [{𝐄 𝐃}_{t} + {𝐁 𝐍}_{t}] {[{𝐂 𝐃}_{t} + {𝐀 𝐍}_{t}]}^{- 1} \\ = 𝐍_{t + 1} 𝐃_{t + 1}^{- 1} \end{matrix}

so by induction the form $𝐗_{t} = 𝐍_{t} 𝐃_{t}^{- 1}$ holds for all $t$ . Then the evolution of $N$ and $D$ can be written as

[\begin{matrix} 𝐍_{t + 1} \\ 𝐃_{t + 1} \end{matrix}] = [\begin{matrix} - 𝐁 & - 𝐄 \\ 𝐀 & 𝐂 \end{matrix}] [\begin{matrix} 𝐍_{t} \\ 𝐃_{t} \end{matrix}] \equiv 𝐉 [\begin{matrix} 𝐍_{t} \\ 𝐃_{t} \end{matrix}]

Thus by induction

[\begin{matrix} 𝐍_{t} \\ 𝐃_{t} \end{matrix}] = 𝐉^{t} [\begin{matrix} 𝐍_{0} \\ 𝐃_{0} \end{matrix}]

References

^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).
^ Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).

[1] Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).

[2] Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).

[3] Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).

[4] Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).

[5] Lua error in Module:Citation/CS1/Configuration at line 2172: attempt to index field '?' (a nil value).

[1]

[2]

[3]

[4]

[5]

Matrix difference equation

Contents

Nonhomogeneous first-order case and the steady state

Stability of the first-order case

Solution of the first-order case

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

Solution and stability of higher-order cases

Nonlinear matrix difference equations: Riccati equations

See also

References

Navigation menu

Matrix difference equation

Nonhomogeneous first-order case and the steady state

Stability of the first-order case

Solution of the first-order case

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

Solution and stability of higher-order cases

Nonlinear matrix difference equations: Riccati equations

See also

References

Navigation menu

Search