\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage{graphicx}
\usepackage[hypertex]{hyperref}
\usepackage{epsfig}
\usepackage{subfigure}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{mathrsfs}
\usepackage{cases}
\usepackage{array}
\renewcommand{\baselinestretch}{1.27}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}
%\input setbmp
%\input{psfig.sty}
\usepackage{epsfig}
\newtheorem{defn}{Definition}
\newtheorem{thm}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{example}{Example}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{algorithm}{Algorithm}
\newtheorem{exercise}{Exercise}
%\usepackage[centertags]{amsmath}
\newcommand{\markex}{\nopagebreak\begin{center}\rule{5in}{.01in}\end{center}}
\newcommand{\markdefn}{\nopagebreak\hfill$\Diamond$}
\newcommand{\mb}{\mbox}
\newcommand{\bm}{\boldmath}
\def\b#1{\mb{\bm$#1$}}
\newfont{\Bb}{msbm10 scaled\magstep1}
\newfont{\Fr}{eufm10 scaled\magstep1}
\newfont{\Sc}{eusm10 scaled\magstep1}
%\pagestyle{empty}
\begin{document}
\noindent{\large ECE 602}\hfill{\Large Fall 2010}
\begin{center}
{\Large \bf Stability in the sense of Lyapunov}\\
by\\
{\large Stanislaw H. \.{Z}ak}
\end{center}
\begin{center}
October 13, 2010
\end{center}
\medskip
%\bigskip
\begin{flushright}
%\parbox{5in}{Early amplifiers were made of crude materials that tended to disintegrate over use, causing the amp to ``run away.'' Not only would an aging relay amplify the phone signal, it would mistakenly compound any tiny deviation from the range it expected until the mushrooming error filled and killed the system. What was needed was Heron's {\it regula}, a counter signal to rein in the chief signal, to dampen the effect of the perpetual recycling. Black came up with a {\it negative} feedback loop, which was designated negative in contrast to the snowballing positive loop of the amplifier. Conceptually, the electrical negative feedback loop is a toilet flusher or thermostat. This braking circuit keeps the amplifier honed in on a steady amplification in the same way a thermostat hones in on a steady temperature. But instead of metallic levers, a weak train of electrons talks to itself.~\cite[page~116]{kelly94}}
\end{flushright}

\section{An Informal Introduction to Stability}
In general, it can be difficult to obtain an explicit solution of nonlinear differential equations modeling a dynamic system. However, often we do not need to know the explicit solution of the modeling equations. Instead, we are interested in the behavior of the solution as time tends to infinity. Furthermore, in many models of physical systems a ``small'' change in the initial conditions results in a ``small'' change in the solution. Specifically, if a system is perturbed from its rest, or equilibrium position, then it starts to move. We can roughly say that the equilibrium position is stable if the system does not go far from this position for small initial perturbations. This concept may be illustrated, as in Willems~\cite{willems70}, Brogan~\cite{brogan91}, or in Barnett~\cite{barnett75}, by means of a ball resting in equilibrium on a sheet of metal bent into various shapes with cross-sections depicted in Figure~\ref{fig:eq-pts}. This figure illustrates four possible scenarios. If we neglect frictional forces, a small perturbation from the equilibrium leads to:
\begin{itemize}
\item[(1)] oscillatory motion about equilibrium irrespective of the magnitude of the initial perturbation. In this case the equilibrium position is globally stable,
\item[(2)] the new position is also an equilibrium and the ball will remain in it. Here the equilibrium position is stable,
\item[(3)] the ball moving away without returning to the equilibrium. This equilibrium position is unstable,
\item[(4)] oscillatory motion about the equilibrium, unless the initial perturbation is so large that the ball is forced to oscillate about the new equilibrium position. This equilibrium position is locally stable.
\end{itemize}
If friction is taken into account, then the oscillatory motion steadily decreases until the ball returns to the equilibrium positions as in items~(1) and (4) above. We refer to such equilibrium positions as being asymptotically stable.
\begin{figure}
\centering
\includegraphics[scale=0.55]{eq-pts.eps}
%\vspace{3in}
%\centerbmp{4in}{3in}{c:/mybook/eq-pts.bmp}
%\hskip1.4in\special{bmp:c:/mybook/eq-pts.bmp x=4in y=3in}
\caption{Illustration of stable and unstable equilibrium positions.}
\label{fig:eq-pts}
\end{figure}
In our discussion of stability concepts, we implicitly assume, as in item~(4), that there is some ``small'' region for allowed initial perturbations for which subsequent motions converge to the equilibrium position. If however, as in item~(1), any initial perturbation yields a motion that converges to the equilibrium position, then we have global asymptotic stability, which is also referred to as asymptotic stability in the large.

\section{Stability of Continuous-Time LTI Systems}
It follows from the discussion in the previous sections that a linear time-invariant dynamic system modeled by the equation
\begin{equation}
\dot{\b x}={\b A\b x}, \quad {\b x}(t_0)={\b x}_0
\label{eq:simlinsysfls}
\end{equation}
is asymptotically stable if and only if, the solution to equation~(\ref{eq:simlinsysfls}) decays to zero as $t \to \infty$ for any initial state ${\b x}_0$. We can view the vector $\b x(t)\in \mb{\Bb R}^n$ as defining the coordinates of a point moving in an $n$-dimensional state space $\mb{\Bb R}^n$. In an asymptotically stable system modeled by equation~(\ref{eq:simlinsysfls}), this point converges to the origin of $\mb{\Bb R}^n$. We can argue that if a trajectory is converging to the origin of the state space, then it should be possible to find a family of nested surfaces described by $V(x_1,x_2, \ldots,x_n)=c$, $c\ge0$, such that monotonically decreasing values of $c$ give surfaces progressively shrinking in on the origin with the limiting surface $V(x_1,x_2, \ldots,x_n)=0$ being the origin $\b x=\b 0$. Furthermore, along every trajectory of~(\ref{eq:simlinsysfls}), the parameter $c$ should steadily decrease. We now introduce some notation and definitions that we use in the ensuing discussion.

Let $V({\b x})=V(x_1,x_2, \ldots,x_n):\mb{\Bb R}^n \to \mb{\Bb R}$ be a real-valued function and let ${\cal S} \subseteq \mb{\Bb R}^n$ be a compact region containing the origin ${\b x=\b 0}$ in its interior.
\begin{defn}
We say that the function $V=V({\b x})$ is {\em positive semi-definite} (p.s.d.) in ${\cal S}$, with respect to $\b x=\b 0$, if
\begin{enumerate}
\item  $V$ is continuously differentiable, that is, $V \in {\cal C}^1$,
\item $V({\b 0})=0$,
\item $V({\b x}) \ge 0$ for all ${\b x} \in {\cal S}$.
\end{enumerate}
\end{defn}
\begin{defn}
We say that the function $V=V({\b x})$ is {\em positive definite} (p.d.) in ${\cal S}$, with respect to $\b x=\b 0$, if
\begin{enumerate}
\item $V \in {\cal C}^1$,
\item $V({\b 0})=0$,
\item \label{it:stmin} $V({\b x}) > 0$ for all ${\b x} \in {\cal S} \setminus \{ {\b 0} \}$.
\end{enumerate}
\end{defn}
The symbol ${\cal S} \setminus \{ {\b 0} \}$ in item~\ref{it:stmin} above denotes the set $\{ {\b x} : {\b x} \in {\cal S}, {\b x \ne \b 0} \}$.

{\em Negative semi-definite} (n.s.d.) and {\em negative definite} (n.d.) functions are defined in a similar fashion by reversing inequality signs in item~\ref{it:stmin} in both definitions above.

There are many functions that satisfy the above definitions. In the stability analysis of dynamic systems one class is particularly useful. This is the positive definite quadratic form, a label attached to a nested family of ellipses and their extensions to higher dimensional spaces---ellipsoids for $n = 3$, and hyper-ellipsoids for $n \ge 4$. We consider the following quadratic form,
\[
V({\b x})={\b x}^{\top}{\b P\b x},
\]
where ${\b P}$ is a real symmetric $n \times n$ matrix.
The time derivative of $V({\b x}(t))$ evaluated on a solution of $\dot{\b x}={\b A\b x}$ is
\begin{eqnarray*}
\frac{dV({\b x}(t))}{dt} &=& \dot{V}(t) \\
&=& \dot{\b x}(t)^{\top} \b P \b x(t) + \b x(t)^{\top}{\b P} \dot{\b x}(t).
\end{eqnarray*}
Substituting $\dot{\b x}={\b A\b x}$ and $\dot{\b x}^{\top}=\b x^{\top} \b A^{\top}$ into the above equation yields
\begin{eqnarray*}
\dot{V} &=& {\b x}^{\top}{\b A}^{\top}{\b P\b x}+{\b x}^{\top}{\b P\b A\b x} \\
&=&{\b x}^{\top}({\b A}^{\top}{\b P}+{\b P\b A}){\b x}.
\end{eqnarray*}
Let
\[
{\b Q}=-({\b A}^{\top}{\b P+\b P\b A}).
\]
Then,
\begin{equation}
\dot{V}=-{\b x}^{\top}{\b Q\b x}.
\label{eq:derofq}
\end{equation}

We are now ready to state and prove the following theorem concerning the stability of the system $\dot{\b x}={\b A\b x}$, or equivalently, the matrix ${\b A} \in \mb{\Bb R}^n$.
\begin{thm}[A. M. Lyapunov, 1892]
\label{Lyapunov}
The system $\dot{\b x}={\b A\b x}$, ${\b x}(t_0)={\b x}_0$,  is asymptotically stable if and only if for any given real symmetric positive definite (r.s.p.d.) matrix ${\b Q}$ the solution ${\b P}$ to the continuous Lyapunov matrix equation,
\begin{equation}
{\b A}^{\top}\b P+\b P\b A=-\b Q
\label{eq:layamateqn}
\end{equation}
is also (real symmetric) positive definite.
\end{thm}
{\bf Proof} \quad($\Rightarrow$)\quad We prove necessity, for asymptotic stability, by contradiction. We have $-{\b x}^{\top}{\b Q\b x}<0$ for all ${\b x \neq \b 0}$. We assume that ${\b A}$ is an asymptotically stable matrix and that for some nonzero ${\b x}_0$ we have ${\b x}_0^{\top}{\b P \b x}_0 \le 0$. From the discussion before the theorem, and in particular from~(\ref{eq:derofq}), it follows that
\[
\frac{d}{dt}\left({\b x}(t)^{\top}{\b P\b x}(t)\right)=-{\b x}(t)^{\top}{\b Q\b x}(t) < 0.
\]
The above means that $V({\b x}(t))={\b x}(t)^{\top}{\b P\b x}(t)$ decreases on the trajectories of the system $\dot{\b x}(t)=\b A\b x(t)$ as $t \to \infty$. On the other hand, because ${\b A}$ is asymptotically stable, we have
\[
\lim_{t \rightarrow \infty}{\b x}(t)={\b 0}.
\]
Hence,
\[
\lim_{t \to \infty}{\b x}(t)^{\top}{\b P\b x}(t)=\lim_{{\b x}(t) \to {\b 0}}{\b x}(t)^{\top}{\b P\b x}(t) = 0.
\]
Thus, we arrived at a contradiction. This completes the proof of the first part of the theorem that states that asymptotic stability of ${\b A}$ implies that for any r.s.p.d matrix ${\b Q}$ the solution ${\b P}$ to the equation ${\b A}^{\top}{\b P+\b P\b A=-\b Q}$ is r.s.p.d..

($\Leftarrow$)\quad We prove sufficiency, also by contradiction. We assume that
\[
\b x^{\top}\b P\b x>0\quad\mb{and}\quad -\b x^{\top}\b Q\b x<0\quad \mb{for all}\quad \b x \ne \b 0,
\]
and that the matrix ${\b A}$ is not asymptotically stable. This means that the solution to $\dot{\b x}(t)={\b A\b x}(t)$, ${\b x}_0 \ne {\b 0}$, which has the form ${\b x}(t)=e^{{\b A}(t-t_0)}{\b x}_0$, is bounded away from the origin ${\b x=\b 0}$. Thus, there is a constant $b > 0$ such that
\[
{\b x}(t)^{\top}{\b Q\b x}(t)>b>0 \quad \mbox{for all }t>t_0.
\]
Integrating $\frac{d}{dt}\left({\b x}(t)^{\top}{\b P\b x}(t)\right)=-{\b x}(t)^{\top}{\b Q\b x}(t)$ yields
\[
{\b x}(t)^{\top}{\b P\b x}(t)={\b x}(t_0)^{\top}{\b P\b x}(t_0)+\int_{t_0}^{t}(-{\b x}(s)^{\top}{\b Q\b x}(s))ds.
\]
Taking into account that $-{\b x}(t)^{\top}{\b Q\b x}(t)<-b<0 \quad \mbox{for all }t>t_0$, we obtain for $t>t_0$,
\begin{eqnarray*}
{\b x}(t)^{\top}{\b P\b x}(t)&=&{\b x}(t_0)^{\top}{\b P\b x}(t_0)+\int_{t_0}^{t}(-{\b x}(s)^{\top}{\b Q\b x}(s))ds \\
&<&{\b x}(t_0)^{\top}{\b P\b x}(t_0)-b(t-t_0).
\end{eqnarray*}
The above implies that for a sufficiently large $t$ we would have ${\b x}(t)^{\top}{\b P\b x}(t)<0$, which contradicts the assumption that ${\b x}(t)^{\top}{\b P\b x}(t)>0$. This means that ${\b A}$ must be asymptotically stable, and the proof is complete.\\
\hspace*{5.5in} $\Box$
\begin{example} \rm
Let
\[
{\b A}=\left[\begin{array}{cc}
0 & 1\\
-1 & -2
\end{array}\right],
\]
and $\b Q=\b I_2$. We solve the Lyapunov equation $\b A^{\top}\b P+\b P\b A=-\b Q$ for $\b P$. Assume $\b P$ to have the form,
\[
{\b P}=\left[ \begin{array}{cc}
p_1 & p_2\\
p_2 & p_3
\end{array}
\right]= \b P^{\top}.
\]
Then, we have
\begin{eqnarray*}
\b A^{\top}\b P+\b P\b A &=&\left[ \begin{array}{cc}
0 & -1\\
1 & -2
\end{array}
\right]\left[ \begin{array}{cc}
p_1 & p_2\\
p_2 & p_3
\end{array}
\right]+\left[ \begin{array}{cc}
p_1 & p_2\\
p_2 & p_3
\end{array}
\right]\left[ \begin{array}{cc}
0 & 1\\
-1 & -2
\end{array}
\right]\\
&=& \left[ \begin{array}{cc}
-2p_2 & -p_3+p_1-2p_2\\
-p_3+p_1-2p_2 & 2p_2-4p_3
\end{array}
\right]\\
&=&-\b Q=\left[ \begin{array}{cc}
-1 & 0\\
0 & -1
\end{array}
\right].
\end{eqnarray*}
Solving the corresponding linear equations yields
\[
\b P=\left[ \begin{array}{cc}
3/2 & 1/2\\
1/2 & 1/2
\end{array}
\right].
\]
The solution matrix $\b P$ is positive definite. Hence, the matrix $\b A$ must have its eigenvalues in the open left-half plane. Indeed, the eigenvalues of $\b A$ are both located at $-1$.
\end{example}\markex
\begin{defn}
A positive definite function $V({\b x})$ whose time derivative evaluated on the solutions of the system $\dot{\b x}={\b A\b x}$ is negative definite (or negative semi-definite) is called a Lyapunov function for this system.
\end{defn}

Lyapunov's theorem gives us a necessary and sufficient condition for asymptotic stability of linear time-invariant dynamic systems. To check if a given matrix ${\b A}$ is asymptotically stable or not, it is enough to take an arbitrary r.s.p.d. matrix ${\b Q}$, solve the equation ${\b A}^{\top}{\b P+\b P\b A=-\b Q}$ for real symmetric ${\b P}$ and check if the obtained ${\b P}$ is positive definite, or not. If ${\b P} > 0$, then ${\b A}$ is asymptotically stable. If ${\b P}$ is not positive definite, then ${\b A}$ cannot be asymptotically stable. Because ${\b Q}$ can be an arbitrary r.s.p.d. matrix, ${\b Q = \b I}_n$, the $n \times n$ identity matrix, is a good choice. It is important to note that there would be no use, as the following example shows, in first choosing a matrix ${\b P}$ and then calculating ${\b Q}$ from the equation ${\b A}^{\top}{\b P+\b P\b A=-\b Q}$.
\begin{example} \rm
Let
\[
{\b A}=\left[ \begin{array}{cc}
-1 & 3\\
0 & -1
\end{array}
\right],
\]
which is asymptotically stable.
Let
\[
{\b P}=\left[ \begin{array}{cc}
1 & 0 \\
0 & 1
\end{array}
\right]
={\b I}_2 > 0.
\]
Then,
\[
{\b Q}=-({\b A}^{\top}{\b P+\b P\b A})=\left[ \begin{array}{cc}
2 & -3 \\
-3 & 2
\end{array}
\right]
\]
which is indefinite. Thus, unless ${\b Q}$ turns out to be definite, nothing can be inferred about asymptotic stability from the Lyapunov theorem if we start with ${\b P}$ and then calculate ${\b Q}$.
\end{example}\markex
We now give a geometric interpretation of the Lyapunov theorem. First, note that the function
\[
\dot{V}=\frac{dV({\b x}(t))}{dt}
\]
can be expressed, using the chain rule, as
\[
\dot{V}=\nabla V^{\top} \dot{\b x}=\| \nabla V \|\, \| \dot{\b x} \| \cos \theta,
\]
where $\theta$ is the angle between the vectors $\nabla V$ and $\dot{\b x}$. If $\| \dot{\b x} \|=1$, then $\nabla V^{\top} \dot{\b x}$ can be viewed as the rate of increase of $V$ at $\b x$ in the direction $\dot{\b x}$. Thus, $\dot{V}<0$ if and only if, $90 \deg < \theta < 270 \deg$. In such a case the velocity vector $\dot{\b x}(t)$ points in the direction of decreasing $V$. We illustrate the above discussion in Figure~\ref{fig:geolyap}.
\begin{figure}
\centering
\includegraphics[scale=0.55]{geolyap.eps}
%\vspace{3.5in}
%\centerbmp{4in}{3in}{c:/mybook/geolyap.bmp}
%\hskip.8in\special{bmp:c:/mybook/geolyap.bmp x=4.66in y=3.5in}
\caption{Geometric interpretation of the Lyapunov theorem.}
\label{fig:geolyap}
\end{figure}

We now prove a variant of Theorem~\ref{Lyapunov}, which is very useful in numerical verification of stability.
\begin{thm}
\label{thm:ver_lyap}
A matrix $\b A$ is asymptotically stable if and only if for any ${\b Q=\b C^{\top}\b C}$, $\b C\in \mb{\Bb R}^{p\times n}$, such that the pair $(\b A, \b C)$ is observable, the solution ${\b P}$ to the Lyapunov matrix equation ${\b A}^{\top}\b P+\b P\b A=-\b C^{\top}\b C$ is positive definite.
\end{thm}
{\bf Proof}\quad We first prove the necessity condition $(\Rightarrow )$ for asymptotic stability. If $\b A$ is asymptotically stable, that is, $\Re\lambda_i(\b A) <0$, then we will show that
\begin{equation}
\b P=\int_0^{\infty}e^{\b A^{\top}t}\b C^{\top}\b Ce^{\b At}dt
\label{eq:integsotl}
\end{equation}
is the symmetric positive definite solution to the Lyapunov equation. Indeed, the integrand of~(\ref{eq:integsotl}) is a sum of terms of the form
\[
t^ke^{\lambda_it},
\]
where $\lambda_i$ is the $i$-th eigenvalue of $\b A$. Since $\Re\lambda_i(\b A)<0$, the integral in~(\ref{eq:integsotl}) exists because the terms in $\b P$ do not diverge when $t \to \infty$. Indeed, let $-\alpha_i=\Re\lambda_i$, where $\alpha_i>0$, then
\[
\lim_{t\to \infty}t^ke^{-\alpha_i t}=\lim_{t \to \infty}\frac{t^k}{e^{\alpha_it}},
\]
We differentiate the numerator and denominator of the above $k$ times and use L'Hospital's rule to get
\begin{eqnarray}
\lim_{t \to \infty}\frac{t^k}{e^{\alpha_it}} &=& \lim_{t\to \infty}\frac{kt^{k-1}}{\alpha_ie^{\alpha_i t}}\nonumber\\
&=& \lim_{t\to \infty}\frac{k(k-1)t^{k-2}}{\alpha^2_ie^{\alpha_i t}}\nonumber\\
&\vdots& {}\nonumber\\
&=& \lim_{t\to \infty}\frac{k!}{\alpha^k_i e^{\alpha_i t}}\nonumber\\
&=&0.
\label{eq:lhospitwne}
\end{eqnarray}
Thus, by~(\ref{eq:lhospitwne}), the formula for $\b P$ given by~(\ref{eq:integsotl}) is well defined. Next, note that $\b P=\b P^{\top}$. The matrix $\b P$ is also positive definite because the pair $(\b A,\b C)$ is observable. Substituting the expression for $\b P$ into the Lyapunov equation and performing manipulations yields
\begin{eqnarray*}
\b A^{\top}\b P+\b P\b A &=&\int_0^{\infty}\b A^{\top}e^{\b A^{\top}t}\b C^{\top}\b Ce^{\b At}dt +\int_0^{\infty}e^{\b A^{\top}t}\b C^{\top}\b Ce^{\b At}\b A dt\\
&=& \int_0^{\infty}\frac{d}{dt}\left(e^{\b A^{\top}t}\b C^{\top}\b Ce^{\b At}\right)dt\\
&=& \left.e^{\b A^{\top}t}\b C^{\top}\b Ce^{\b At}\right\arrowvert^{\infty}_0\\
&=& -\b C^{\top}\b C.
\end{eqnarray*}

The sufficiency part $(\Leftarrow )$ can be proven using the arguments of the proof of the sufficiency part of the Lyapunov theorem and noting that the observability of the pair $(\b A,\b C)$ implies that $\b x(t)^{\top}\b C^{\top}\b C\b x(t)$ is not identically zero along any nonzero solution of $\dot{\b x}(t)=\b A\b x(t)$.\\
\hspace*{5.5in}$\Box$

We now show that if $\b A$ is asymptotically stable, then the Lyapunov equation~(\ref{eq:layamateqn}) has a unique solution for every $\b Q$. Uniqueness can be proven in many ways. We use the Kronecker product in our proof. We represent the Lyapunov equation~(\ref{eq:layamateqn}) as
\begin{equation}
\left(\b I_n\otimes \b A^{\top}+\b A^{\top}\otimes \b I_n \right)\mb{vec}(\b P)=-\mb{vec}(\b Q).
\label{eq:lyapinkron}
\end{equation}
The condition for a solution $\mb{vec}(\b P)$ of the above equation to be unique is
\[
\lambda_i(\b A^{\top})+\lambda_j(\b A) \ne 0,\quad i,j=1,2,\ldots,n.
\]
Because $\lambda_i(\b A^{\top})=\lambda_i(\b A)$, and $\b A$ is asymptotically stable by assumption, the condition $\lambda_i(\b A^{\top})+\lambda_j(\b A) \ne 0$ is met, and hence the Lyapunov equation has a unique solution.

\section{Discrete-Time Lyapunov Equation}
We will now use the Lyapunov approach to the stability analysis of the discrete-time linear time-invariant systems modeled by
\begin{equation}
\b x(k+1)=\b A\b x(k),\quad \b x(k_0)=\b x_0.
\label{eq:disclitisy}
\end{equation}
By analogy with the continuous-time case, consider a quadratic positive definite form,
\[
V(\b x(k))=\b x(k)^{\top}\b P\b x(k).
\]
We evaluate the first difference of $V$, defined $\Delta V=V(\b x(k+1))-V(\b x(k))$, on the trajectories of~(\ref{eq:disclitisy}) to obtain
\begin{eqnarray}
\Delta V(\b x(k)) &=& V(\b x(k+1))-V(\b x(k))\nonumber\\
&=&\b x(k+1)^{\top}\b P\b x(k+1)-\b x(k)^{\top}\b P\b x(k)\nonumber\\
&=& \b x(k)^{\top}\b A^{\top}\b P\b A\b x(k)-\b x(k)^{\top}\b P\b x(k)\nonumber\\
&=& \b x(k)^{\top}\left(\b A^{\top}\b P\b A-\b P\right)\b x(k),
\label{eq:frstdiofv}
\end{eqnarray}
where we replaced $\b x(k+1)$ in the above with $\b A\b x(k)$. For the solutions of~(\ref{eq:disclitisy}) to decrease the ``energy function'' $V$, at each $k>k_0$, it is necessary and sufficient that $\Delta V(\b x(k))<0$, or equivalently, that for some positive definite $\b Q$,
\begin{equation}
\Delta V(\b x(k))=-\b x(k)^{\top}\b Q\b x(k).
\label{eq:delvwqpsd}
\end{equation}
Combining~(\ref{eq:disclitisy}) and~(\ref{eq:delvwqpsd}), we obtain the so called {\em discrete-time Lyapunov equation},
\begin{equation}
\fbox{$\displaystyle \b A^{\top}\b P\b A-\b P=-\b Q $}
\label{eq:dtlyaeqfltis}
\end{equation}
\begin{thm}\label{thm:dlme}
The matrix $\b A$ has its eigenvalues in the open unit disk if and only if for any positive definite $\b Q$ the solution $\b P$ to~(\ref{eq:dtlyaeqfltis}) is positive definite.
\end{thm}
{\bf Proof}\quad $(\Rightarrow )$ We use the Kronecker product to represent the discrete-time Lyapunov equation as
\begin{equation}
\left(\b I_{n^2}-\b A^{\top}\otimes \b A^{\top} \right)\mb{vec}(\b P)=\mb{vec}(\b Q),
\label{eq:dtleuskpro}
\end{equation}
where $\otimes$ denotes the Kronecker product and $\b s(\cdot)$ is the stacking operator. It is easy to see that the above equation has a unique solution if and only if
\[
1-\lambda_i \lambda_j \ne 0,\quad\mb{for all}\quad i,j=1,2,\ldots,n,
\]
where $\{\lambda_i\}$ is the set of eigenvalues of $\b A$. By assumption, $|\lambda_i|<1$, which is a sufficient condition for~(\ref{eq:dtleuskpro}) and hence~(\ref{eq:dtlyaeqfltis}) to have a unique solution. The solution $\b P$ can be expressed as
\begin{equation}
\b P=\sum_{k=0}^{\infty}\left(\b A^{\top} \right)^k\b Q\b A^k.
\label{eq:solslme}
\end{equation}
The above expression is well defined because all eigenvalues of $\b A$ have magnitude (strictly) less than unity. Substituting~(\ref{eq:solslme}) into~(\ref{eq:dtlyaeqfltis}) gives
\begin{eqnarray*}
\b A^{\top}\b P\b A-\b P&=&\b A^{\top}\left(\sum_{k=0}^{\infty}\left(\b A^{\top} \right)^{k}\b Q\b A^{k}\right)\b A-\sum_{k=0}^{\infty}\left(\b A^{\top} \right)^k\b Q\b A^k\\
&=& \sum_{k=1}^{\infty}\left(\b A^{\top} \right)^k\b Q\b A^k-\sum_{k=1}^{\infty}\left(\b A^{\top} \right)^k\b Q\b A^k-\b Q\\
&=&-\b Q.
\end{eqnarray*}
Thus, indeed~(\ref{eq:solslme}) satisfies the discrete-time Lyapunov equation. Note that if $\b Q$ is symmetric so is $\b P$. If $\b Q$ is positive definite, so is $\b P$.

$(\Leftarrow )$ Let $\lambda_i$ be an eigenvalue of $\b A$ and $\b v_i$ be a corresponding eigenvector, that is, $\b A\b v_i=\lambda_i \b v_i$. Observe that $\lambda_i$ and $\b v_i$ may be complex. We denote by $\b v^*_i$ the complex conjugate transpose of $\b v_i$. Note that $\b v_i^*\b P\b v_i$ is a scalar. We will show that its complex conjugate equals itself, which means that $\b v_i^*\b P\b v_i$ is real. Indeed,
\[
\overline{\b v_i^*\b P\b v_i}= \b v_i^*\b P^*\b v_i=\b v_i^*\b P^{\top}\b v_i=\b v_i^*\b P\b v_i,
\]
where we used the fact that the complex conjugate transpose of a real matrix reduces to its transpose. Thus, $\b v_i^*\b P\b v_i$ is real for any complex $\b v_i$.

Premultiplying now~(\ref{eq:dtlyaeqfltis}) by $\b v^*_i$ and postmultiplying by $\b v_i$ gives
\begin{equation}
\b v_i^*\left(\b A^{\top}\b P\b A-\b P\right)\b v_i = -\b v_i^*\b Q\b v_i.
\label{eq:aftermuldle}
\end{equation}
The left-hand side of the above equality evaluates to
\begin{eqnarray*}
\b v_i^*\b A^{\top}\b P\b A\b v_i - \b v_i^*\b P\b v_i&=& \bar{\lambda}_i\b v_i^* \b P\b v_i\lambda_i-\b v_i^*\b P\b v_i\\
&=& \left(|\lambda_i|^2-1 \right)\b v_i^*\b P\b v_i.
\end{eqnarray*}
Comparing the above with the right-hand side of~(\ref{eq:aftermuldle}) yields
\[
\left(1-|\lambda_i|^2\right)\b v_i^*\b P\b v_i=\b v_i^*\b Q\b v_i>0
\]
because $\b Q$ is positive definite. Since $\b P$ is positive definite, we have to have $|\lambda_i|<1$. The proof is complete.\\
\hspace*{5.5in}$\Box$

%\section{Summary and Notes}



%\section{Exercises}

%\begin{exercise}\label{ex:toiletsysex}\rm
%An example of a closed-loop feedback system is a toilet flushing device connected to a water tank. A toilet system is shown in Figure~\ref{fig:toiletd}. The control objective is to maintain the level of water in the tank at a constant level. Draw a block diagram of the system.
%\begin{figure}[h]
%\centering
%\includegraphics[scale=0.6]{TOILETD.eps}
%%\vspace{3.5in}
%%\hskip1in\special{bmp:c:/mybook/toiletd.bmp x=4.67in y=3.5in}
%\caption{Toilet-flushing system for Exercise~\ref{ex:toiletsysex}.}
%\label{fig:toiletd}
%\end{figure}
%\end{exercise}



\bibliography{root2}
\bibliographystyle{plain}
\end{document} 