\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}
\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 State Equation Solution}\\
by\\
{\large Stanislaw H. \.{Z}ak}
\end{center}
\begin{center}
September 14, 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}

Linear systems can be modeled using convolutions and in the case of lumped systems, we can use state-space equations. Analytical computation of convolutions can be quite involved. An efficient method of obtaining a solution to a model of a lumped system is to convert the transfer function  into a state-space model and then solve the state equation. We begin with a time-invariant case and then proceed with the time-varying case.


%\section*{Solving the State Equations}\addcontentsline{toc}{section}{Solving the State Equations}
\section{State Equation Solution of Uncontrolled System}
%\addcontentsline{toc}{subsection}{Solution of Uncontrolled System}
Given a dynamical system's time-invariant model of the form
\begin{equation}
\dot{\b x}(t)=\b A \b x(t)
\label{eq:xdobaxeq}
\end{equation}
subject to an initial condition
\begin{equation}
\b x(0)=\b x_0,
\label{eq:inicoax}
\end{equation}
where $\b A \in \mb{\Bb R}^{n \times n}$. The solution to~(\ref{eq:xdobaxeq}) subject to~(\ref{eq:inicoax}) is
\begin{equation}
\fbox{$\displaystyle \b x(t)=e^{\b A t}\b x_0 $}
\label{eqn:sol_uncon_sys_ti}
\end{equation}
The above is a generalization of the situation when $\b A$ is a scalar. The exponential matrix $e^{\b A t}$ is defined as
\[
e^{\b At}=\b I_n + t\b A + \frac{t^2}{2!}\b A^2+\frac{t^3}{3!}\b A^3+\cdots
\]
To verify that~\eqref{eqn:sol_uncon_sys_ti} solves~\eqref{eq:xdobaxeq} subject to~\eqref{eq:inicoax}, we use the fact that
\[
\frac{d}{dt}e^{\b At} = \b Ae^{\b At}= e^{\b At} \b A.
\]

Suppose now that the initial condition $\b x(0)=\b x_0$ is replaced with a more general condition
\[
\b x(t_0)=\b x_0,
\]
where $t_0$ is a given initial time instant. Then, the solution to $\dot{\b x}(t)=\b A \b x(t)$ subject to $\b x(t_0)=\b x_0$ is
\[
\fbox{$\displaystyle\b x(t)=e^{\b A\left(t-t_0\right)}\b x_0 $}
\]
The matrix $e^{\b A\left(t-t_0\right)}$ is often written as
\[
e^{\b A\left(t-t_0\right)}=\b \Phi \left(t,t_0\right)
\]
and is called the {\em state transition matrix\/}, because it relates the state at any instant of time $t_0$ to the state at any other time $t$.


\section{Computing State Transition Matrix of LTI Systems}

For an overview of methods to calculate the state transition matrix for a linear, time-invariant~(LTI) system, we refer the reader to the classic paper on the subject by Moler and Van Loan~\cite{moler78}, where the numerical issues related to the computation of the matrix exponential are discussed. In what follows, we present a few simple methods to compute the matrix exponential.

\subsection{The Inverse Laplace Transform Method}
In the case when the matrix $\b A$ is of low dimensions, we can use the formula that results from applying the Laplace transform to the time-invariant system $\dot{\b x}=\b A \b x,\quad \b x(0)=\b x_0$. The Laplace transform of the above matrix differential equation is
\[
s\b X(s)-\b x_0= \b A\b X(s).
\]
Hence
\[
\b X(s)=\left(s\b I_n-\b A\right)^{-1}\b x_0,
\]
and the inverse transform yields
\begin{equation}
\fbox{$\displaystyle e^{\b At}={\cal L}^{-1}\left\{\left(s\b I_n-\b A\right)^{-1}\right\} $}
\label{eq:inlatrofunco}
\end{equation}
where ${\cal L}^{-1}$ denotes the inverse Laplace transform operator.
\begin{example}\label{exam:iLtr}\rm
We use the inverse Laplace method to compute $e^{\b A t}$ for
\[
\b A=\left[\begin{array}{cc}
0 & 3\\
2 & 1
\end{array}\right].
\]
We have
\begin{eqnarray}
e^{\b A t} &=& {\cal L}^{-1}\left(\left[ s\b I_2 - \b A  \right]^{-1}  \right)\nonumber\\
&=& {\cal L}^{-1}\left(\left[\begin{array}{cc}
s & -3\\
-2 & s-1
\end{array}\right]^{-1}\right)\nonumber\\
&=& {\cal L}^{-1}\left(\frac{1}{(s-3)(s+2)}\left[\begin{array}{cc}
s-1 & 3\\
2 & s
\end{array}\right]
\right)\nonumber\\
&=& \left[\begin{array}{cc}
0.4 e^{3t} + 0.6 e^{-2t} & 0.6 \left( e^{3t} - e^{-2t} \right)\\
0.4 \left( e^{3t} - e^{-2t} \right) & 0.6 e^{3t} + 0.4 e^{-2t}
\end{array}\right].
\label{eq:iLmex}
\end{eqnarray}
\end{example}
\markex

\subsection{Diagonalization Method}

A convenient way to calculate $e^{\b A t}$ is when the matrix $\b A$ has distinct eigenvalues. In such a case the $n$-by-$n$ matrix $\b A$ has $n$ linearly independent eigenvectors as per the following theorem.
\begin{thm}\label{thm:dist_eigenval}
Suppose the characteristic equation $\Delta (\lambda)=0$ has $n$ distinct roots, $\lambda_1, \lambda_2, \ldots , \lambda_n$. Then, there exist $n$ linearly independent vectors $\b v_1, \b v_2, \ldots , \b v_n$ such that
\[
\b A\b v_i = \lambda_i \b v_i, \quad i=1,2,\ldots , n.
\]
\end{thm}
{\bf Proof}\quad See Exercise~\ref{ex:dist_eigenval_pf}.\\
\hspace*{5.5in} $\Box$

Let
\[
\b T=\left[\begin{array}{cccc}
\b v_1 & \b v_2 & \cdots & \b v_n
\end{array}\right].
\]
The matrix $\b T$ is invertible because the eigenvectors $\b v_i$, $i=1,2,\ldots, n$ are linearly independent. Then, because $\b T^{-1}\b T = \b I_n$, we have
\begin{eqnarray}
\b T^{-1}\b A\b T &=& \b T^{-1}\b A \left[\begin{array}{cccc}
\b v_1 & \b v_2 & \cdots & \b v_n
\end{array}\right]\nonumber\\
&=& \b T^{-1} \left[\begin{array}{cccc}
\b A\b v_1 & \b A\b v_2 & \cdots & \b A\b v_n
\end{array}\right]\nonumber\\
&=& \b T^{-1} \left[\begin{array}{cccc}
\lambda_1\b v_1 & \lambda_2\b v_2 & \cdots & \lambda_n\b v_n
\end{array}\right]\nonumber\\
&=& \b T^{-1}\b T\left[\begin{array}{ccccc}
\lambda_1 & 0 & 0 & \cdots & 0\\
0 & \lambda_2 & 0 & \cdots & 0\\
\vdots & \vdots & {} & \ddots & \vdots\\
0 & 0 & 0 & \cdots & \lambda_n
\end{array}\right]\nonumber\\
&=& \b{\Lambda}.
\label{eq:diag_lambda}
\end{eqnarray}
We use the above result to compute the transition matrix $e^{\b A t}$. Recall that
\[
e^{\b At} = \b I_n + \b A t + \frac{\b A^2 t^2}{2!}  + \frac{\b A^3 t^3}{3!} + \cdots
\]
Note that
\[
\b{\Lambda}^k = \left[\begin{array}{ccccc}
\lambda_1^k & 0 & 0 & \cdots & 0\\
0 & \lambda_2^k & 0 & \cdots & 0\\
\vdots & \vdots & {} & \ddots & \vdots\\
0 & 0 & 0 & \cdots & \lambda_n^k
\end{array}\right],\quad k\ge 1
\]
Hence
\[
e^{\b{\Lambda} t} = \left[\begin{array}{ccccc}
e^{\lambda_1 t} & 0 & 0 & \cdots & 0\\
0 & e^{\lambda_2 t} & 0 & \cdots & 0\\
\vdots & \vdots & {} & \ddots & \vdots\\
0 & 0 & 0 & \cdots & e^{\lambda_n t}
\end{array}\right].
\]
From~\eqref{eq:diag_lambda}, we obtain
\[
\b A=\b T\b{\Lambda}\b T^{-1}.
\]
Therefore,
\begin{eqnarray*}
\b A^k &=& \left( \b T\b{\Lambda}\b T^{-1} \right)^k\\
&=&\left( \b T\b{\Lambda}\b T^{-1} \right)\left( \b T\b{\Lambda}\b T^{-1} \right)\times \cdots \times \left( \b T\b{\Lambda}\b T^{-1} \right)\\
&=& \b T \b{\Lambda}^k \b T^{-1},
\end{eqnarray*}
and hence
\begin{eqnarray}
e^{\b A t} &=& e^{\b T\b{\Lambda}\b T^{-1}}\nonumber\\
&=& \b I_n + \b T\b{\Lambda}\b T^{-1} t + \frac{\left( \b T\b{\Lambda}\b T^{-1} \right)^2 t^2}{2!} + \frac{\left( \b T\b{\Lambda}\b T^{-1} \right)^3 t^3}{3!} + \cdots \nonumber\\
&=& \b T\left( \b I_n + \b{\Lambda} t + \frac{\b{\Lambda}^2 t^2}{2!} + \frac{\b{\Lambda}^3 t^3}{3!}\right) \b T^{-1} \nonumber\\
&=& \b T e^{\b{\Lambda} t}\b T^{-1}.
\label{eq:diag_m_for}
\end{eqnarray}
\begin{example}\label{exam:diag_met}\rm
We use the diagonalization method to compute $e^{\b A t}$ for
\[
\b A=\left[\begin{array}{cc}
0 & 3\\
2 & 1
\end{array}\right].
\]
Note that this is the same matrix $\b A$ as in Example~\ref{exam:iLtr}. The eigenvalues of $\b A$ are distinct so the diagonalization method is applicable here. We first compute an eigenvector, $\b v_1$, corresponding to the eigenvalue $\lambda_1=3$ by solving the eigenvalue-eigenvector equation,
\[
\left(\b A- \lambda_1 \b I_2  \right)\b v_1 = \b 0.
\]
That is,
\[
\left(\b A- \lambda_1 \b I_2  \right)\b v_1 =\left[\begin{array}{cc}
-3 & 3\\
2 & -2
\end{array}\right]\left[\begin{array}{c}
v_{11}\\
v_{21}
\end{array}\right]= \left[\begin{array}{c}
0\\
0
\end{array}\right].
\]
We take
\[
\b v_1=\left[\begin{array}{c}
1\\
1
\end{array}\right].
\]
We next compute an eigenvector corresponding to the eigenvalue $\lambda_2=-2$ by solving the equation
\[
\left(\b A- \lambda_2 \b I_2  \right)\b v_2 =\left[\begin{array}{cc}
2 & 3\\
2 & 3
\end{array}\right]\left[\begin{array}{c}
v_{12}\\
v_{22}
\end{array}\right]= \left[\begin{array}{c}
0\\
0
\end{array}\right].
\]
We take
\[
\b v_2=\left[\begin{array}{c}
-3\\
2
\end{array}\right].
\]
We use the above eigenvectors to form the transformation matrix
\[
\b T=\left[\begin{array}{cc}
\b v_1 & \b v_2
\end{array}\right] = \left[\begin{array}{cc}
1 & -3\\
1 & 2
\end{array}\right].
\]
Its inverse is
\[
\b T^{-1}=\frac{1}{5}\left[\begin{array}{cc}
2 & 3\\
-1 & 1
\end{array}\right].
\]
We are now ready to compute $e^{\b A t}$ using~\eqref{eq:diag_m_for},
\begin{eqnarray*}
e^{\b At} &=& \b Te^{\Lambda t} \b T^{-1}\\
&=& \frac{1}{5}\left[\begin{array}{cc}
1 & -3\\
1 & 2
\end{array}\right]\left[\begin{array}{cc}
e^{3 t} & 0\\
0 & e^{-2 t}
\end{array}\right]\left[\begin{array}{cc}
2 & 3\\
-1 & 1
\end{array}\right]\\
&=&\frac{1}{5}\left[\begin{array}{cc}
2e^{3 t} + 3 e^{-2 t} & 3\left( e^{3 t}- e^{-2 t} \right)\\
2\left( e^{3 t}- e^{-2 t} \right) & 3e^{3 t} + 2 e^{-2 t}
\end{array}\right].
\end{eqnarray*}
The result is the same as when we used the inverse Laplace transform method.
\end{example}
\markex

The above example illustrates that the transformation $\b T$ producing the diagonal form of $\b A$ is a powerful computational tool. The existence of a diagonalizing $\b T$ is not always guaranteed. The inability to transform $\b A$ to diagonal form is connected with the existence of repeated eigenvalues that we discuss next.

\section{Computing Functions of a Square Matrix}

In this section, we discuss methods of computing functions of a square matrix that is not necessarily diagonalizable. The methods discussed allow us to easily compute the matrix exponential and hence the state transition matrix of LTI systems. A major tool used by the methods discussed is the so called Jordan canonical form that we discuss next.

\subsection{The Jordan Canonical Form}

If a square $n$-by-$n$ matrix $\b A$ has repeated eigenvalues, then it may not be diagonalizable. Although some matrices possessing repeated eigenvalues can be transformed into diagonal form, in many cases it is only possible to obtain the so-called ``Jordan canonical form'' or just the ``Jordan from,'' for short. To illustrate the point, we consider the case when the characteristic equation, $\Delta (\lambda)=(\lambda-\lambda_1)^n$, that is, the matrix $\b A$ has just one eigenvalue with multiplicity $n$. For simplicity, we analyze the case when $n=4$ and suppose that
\[
\mb{rank} \left[\begin{array}{c}
\b A - \lambda_1 \b I_4
\end{array}\right] = 3.
\]
That is, the nullity of the matrix $\left[\begin{array}{c}
\b A - \lambda_1 \b I_4
\end{array}\right]$ is one, which means that there is only one eigenvector corresponding to the eigenvalue $\lambda_1$. Thus such a matrix $\b A$ cannot be diagonalized. We need three more linearly independent vectors to represent $\b A$ in a new basis, where it has a particularly simple form that is as close as possible to being diagonal.

To proceed, we need a notion of a generalized eigenvector that we define now.
\begin{defn}\label{defn:gene_eigenvec}
A vector $\b v$ is called a generalized eigenvector of grade $k$ if
\[
\left(\b A - \lambda \b I_n \right)^k \b v = \b 0
\]
and
\[
\left( \b A - \lambda \b I_n \right)^{k-1} \b v \ne \b 0.
\]
\end{defn}
\markdefn

For $k=1$, we have
\[
\left( \b A-\lambda \b I_n \right) \b v = \b 0,
\]
which means that $\b v$ is an ordinary eigenvector corresponding to the eigenvalue $\lambda$.

Suppose now that $\b A\in \mb{\Bb R}^{4 \times 4}$ and $\b v$ is a generalized eigenvector of grade $n=4$ corresponding to the repeated eigenvalue $\lambda_1$ whose multiplicity is also $4$. Then by Definition~\ref{defn:gene_eigenvec},
\[
\left(\b A - \lambda_1 \b I_4 \right)^4 \b v = \b 0\quad\mb{but}\quad \left(\b A - \lambda_1 \b I_4 \right)^3 \b v \ne \b 0.
\]
Let
\[
\b v_1=\left(\b A - \lambda_1 \b I_4 \right)^3 \b v.
\]
Then,
\begin{eqnarray*}
\left(\b A - \lambda_1 \b I_4 \right) \b v_1 &=& \left(\b A - \lambda_1 \b I_4 \right)^4 \b v\\
&=& \b 0.
\end{eqnarray*}
Hence
\begin{equation}
\b A\b v_1 = \lambda_1 \b v_1.
\label{eq:first_in_chain}
\end{equation}
We also have to have
\[
\left(\b A - \lambda_1 \b I_4 \right)^2 \b v \ne \b 0,
\]
otherwise we would have $\left(\b A - \lambda_1 \b I_4 \right)^3 \b v=\b 0$ as well, which would mean that $\b v$ is not a generalized eigenvector of grade 4.

Let
\[
\b v_2=\left(\b A - \lambda_1 \b I_4 \right)^2 \b v.
\]
Note that
\begin{eqnarray*}
\left(\b A - \lambda_1 \b I_4 \right) \b v_2 &=& \left(\b A - \lambda_1 \b I_4 \right)^3 \b v\\
&=& \b v_1.
\end{eqnarray*}
Therefore,
\begin{equation}
\b A\b v_2 = \b v_1 + \lambda_1 \b v_2.
\label{eq:second_in_chain}
\end{equation}

We proceed in a similar way by letting
\[
\b v_3=\left( \b A - \lambda_1 \b I_4 \right) \b v.
\]
We observer that
\begin{eqnarray*}
\left(\b A - \lambda_1 \b I_4 \right) \b v_3 &=& \left(\b A - \lambda_1 \b I_4 \right)^2 \b v\\
&=& \b v_2.
\end{eqnarray*}
Hence,
\begin{equation}
\b A\b v_3 = \b v_2 + \lambda_1 \b v_3.
\label{eq:third_in_chain}
\end{equation}
Finally, we let
\[
\b v_4=\b v
\]
and we note that
\begin{eqnarray*}
\left(\b A - \lambda_1 \b I_4 \right) \b v_4 &=& \left(\b A - \lambda_1 \b I_4 \right) \b v\\
&=& \b v_3.
\end{eqnarray*}
Therefore,
\begin{equation}
\b A\b v_4 = \b v_3 + \lambda_1 \b v_4.
\label{eq:fourth_in_chain}
\end{equation}
Combining now~\eqref{eq:first_in_chain}--\eqref{eq:fourth_in_chain}, we obtain
\begin{eqnarray}
\b A\left[\begin{array}{cccc}
\b v_1 & \b v_2 & \b v_3 & \b v_4
\end{array}\right] &=& \left[\begin{array}{cccc}
\lambda_1\b v_1 & \b v_1 + \lambda_1\b v_2 & \b v_2 + \lambda_1\b v_3 & \b v_3 + \lambda_1\b v_4
\end{array}\right]\nonumber\\
&=& \left[\begin{array}{cccc}
\b v_1 & \b v_2 & \b v_3 & \b v_4
\end{array}\right]\left[\begin{array}{cccc}
\lambda_1 & 1 & 0 & 0\\
0 & \lambda_1 & 1 & 0\\
0 & 0 & \lambda_1 & 1\\
0 & 0 & 0 & \lambda_1
\end{array}\right].
\label{eq:pre_simtoJ}
\end{eqnarray}
Let
\[
\b T=\left[\begin{array}{cccc}
\b v_1 & \b v_2 & \b v_3 & \b v_4
\end{array}\right].
\]
The matrix $\b T$ is invertible by construction, that is, the set of vectors $\left\{ \b v_1, \b v_2, \b v_3, \b v_4 \right\}$ forms a basis for $\mb{\Bb R}^4$. Therefore we can represent~\eqref{eq:pre_simtoJ} as
\begin{eqnarray}
\b T^{-1}\b A\b T &=& \left[\begin{array}{cccc}
\lambda_1 & 1 & 0 & 0\\
0 & \lambda_1 & 1 & 0\\
0 & 0 & \lambda_1 & 1\\
0 & 0 & 0 & \lambda_1
\end{array}\right]\nonumber\\
&=& \b J.
\label{eq:sim_to_J}
\end{eqnarray}
The representation  of $\b A$ in the basis $\left\{ \b v_1, \b v_2, \b v_3, \b v_4 \right\}$ has the form of a Jordan block of order 4.

\begin{example}\label{exam:Jord_formthre_by_three}\rm
Consider the matrix
\[
\b A=\left[\begin{array}{ccc}
5 & 2 & 4\\
0 & 5 & 3\\
0 & 0 & 5
\end{array}\right].
\]
The characteristic polynomial is $\Delta (\lambda)=(\lambda - 5)^3$ and
\[
\mb{rank} \left.\left[\begin{array}{c}
\b A - \lambda\b I_3
\end{array}\right]\right\arrowvert_{\lambda=5} = 2,
\]
that is, the nullity of the characteristic matrix is 1. We proceed to find $\b v_1$ such that
\begin{eqnarray*}
\left.\left[ \b A-\lambda \b I_3 \right]\right\arrowvert_{\lambda=5} \b v_1 &=&  \left[\begin{array}{ccc}
0 & 2 & 4\\
0 & 0 & 3\\
0 & 0 & 0
\end{array}\right]\left[\begin{array}{c}
v_{11}\\
v_{21}\\
v_{31}
\end{array}\right]\\
&=& \b 0.
\end{eqnarray*}
We take
\[
\b v_1=\left[\begin{array}{c}
1\\
0\\
0
\end{array}\right].
\]
Then we proceed to find $\b v_2$ such that
\[
\left.\left[ \b A-\lambda \b I_3 \right]\right\arrowvert_{\lambda=5} \b v_2=\b v_1,
\]
that is, we solve for $\b v_2$ satisfying
\[
\left[\begin{array}{ccc}
0 & 2 & 4\\
0 & 0 & 3\\
0 & 0 & 0
\end{array}\right]\left[\begin{array}{c}
v_{12}\\
v_{22}\\
v_{32}
\end{array}\right]=\left[\begin{array}{c}
1\\
0\\
0
\end{array}\right].
\]
We can take
\[
\b v_2=\left[\begin{array}{c}
0\\
1/2\\
0
\end{array}\right].
\]
Finally we find $\b v_3$ such that
\[
\left.\left[ \b A-\lambda \b I_3 \right]\right\arrowvert_{\lambda=5} \b v_3=\b v_2,
\]
that is, we solve for $\b v_3$ satisfying
\[
\left[\begin{array}{ccc}
0 & 2 & 4\\
0 & 0 & 3\\
0 & 0 & 0
\end{array}\right]\left[\begin{array}{c}
v_{13}\\
v_{23}\\
v_{33}
\end{array}\right]=\left[\begin{array}{c}
0\\
1/2\\
0
\end{array}\right].
\]
We can take
\[
\b v_3=\left[\begin{array}{c}
0\\
-2/6\\
1/6
\end{array}\right].
\]
The transformation matrix $\b T$ has the form
\[
\b T=\left[\begin{array}{ccc}
\b v_1 & \b v_2 & \b v_3
\end{array}\right]=\left[\begin{array}{ccc}
1 & 0 & 0\\
0 & 1/2 & -2/6\\
0 & 0 & 1/6
\end{array}\right],
\]
and
\[
\b T^{-1}=\left[\begin{array}{ccc}
1 & 0 & 0\\
0 & 2 & 4\\
0 & 0 & 6
\end{array}\right].
\]
The matrix $\b A$ in the new basis has the form
\begin{eqnarray*}
\b T^{-1}\b A\b T &=& \left[\begin{array}{ccc}
1 & 0 & 0\\
0 & 2 & 4\\
0 & 0 & 6
\end{array}\right] \left[\begin{array}{ccc}
5 & 2 & 4\\
0 & 5 & 3\\
0 & 0 & 5
\end{array}\right]\left[\begin{array}{ccc}
1 & 0 & 0\\
0 & 1/2 & -2/6\\
0 & 0 & 1/6
\end{array}\right]\\
&=& \left[\begin{array}{ccc}
5 & 1 & 0\\
0 & 5 & 1\\
0 & 0 & 5
\end{array}\right],
\end{eqnarray*}
which is a third order Jordan block.
\end{example}
\markex


If the rank of the characteristic matrix evaluated at  $\lambda_1$ is $n-2$, then the equation
\[
\left[ \b A-\lambda_1 \b I_n \right] \b v=\b 0,
\]
has two linearly independent solutions. Therefore, $\b A$ has two linearly independent eigenvectors. Let $\b u_1$ and $\b v_1$ be linearly independent eigenvectors associated with the eigenvalue $\lambda_i$. In order to transform $\b A$ into its Jordan form, we need to find $n-2$ generalized eigenvectors. In  this case we have two chains of generalized eigenvectors, $\{\b u_1, \b u_2,\ldots , \b u_k  \}$ and $\{\b v_1, \b u_2,\ldots , \b v_l \}$, where $k+l=n$. In the basis
\[
\{\b u_1, \b u_2,\ldots , \b u_k, \b v_1, \b u_2,\ldots , \b v_l \}
\]
the matrix $\b A$ will have a block diagonal form
\[
\b T^{-1}\b A\b T=\left[\begin{array}{cc}
\b J_1 & \b O\\
\b O & \b J_2
\end{array}\right],
\]
where $\b J_1$ is a Jordan block of order $k$ and $\b J_2$ is a Jordan block of order $l$.
\begin{example}\label{exam:two_blks_Jord_form}\rm
Let
\[
\b A=\left[\begin{array}{ccc}
3 & 1 & -1\\
0 & 6 & -3\\
0 & 3 & 0
\end{array}\right].
\]
The characteristic polynomial
\[
\Delta (\lambda)=(\lambda-3)^3
\]
and
\begin{eqnarray*}
\mb{rank}\left.\left[ \b A-\lambda \b I_3 \right]\right\arrowvert_{\lambda=3} &=& \left[\begin{array}{ccc}
0 & 1 & -1\\
0 & 3 & -3\\
0 & 3 & -3
\end{array}\right]\\
&=& 1
\end{eqnarray*}
As two linearly independent solutions to
\[
\left.\left[ \b A-\lambda \b I_3 \right]\right\arrowvert_{\lambda=3}\b v=\b 0,
\]
we can take
\[
\b u_1=\left[\begin{array}{c}
1\\
3\\
3
\end{array}\right]\quad\mb{and}\quad \b v_1=\left[\begin{array}{c}
0\\
1\\
1
\end{array}\right].
\]
Now we have to find one generalized eigenvector that together with $\b u_1$ and $\b v_1$ would form a basis for $\mb{\Bb R}^3$ and enable us to construct a transformation that brings $\b A$ into its Jordan form. We try first $\b u_1$ to construct $\b u_2$ such that
\[
\left.\left[ \b A-\lambda \b I_3 \right]\right\arrowvert_{\lambda=3} \b u_2=\b u_1,
\]
that is, we solve for $\b u_2$ satisfying
\[
\left[\begin{array}{ccc}
0 & 1 & -1\\
0 & 3 & -3\\
0 & 3 & -3
\end{array}\right]\left[\begin{array}{c}
u_{12}\\
u_{22}\\
u_{32}
\end{array}\right]=\left[\begin{array}{c}
1\\
3\\
3
\end{array}\right].
\]
We can take
\[
\b u_2=\left[\begin{array}{c}
1\\
1\\
0
\end{array}\right].
\]
We form the transformation matrix
\[
\b T=\left[\begin{array}{ccc}
\b u_1 & \b u_2 & \b v_1
\end{array}\right]=\left[\begin{array}{ccc}
1 & 1 & 0\\
3 & 1 & 1\\
3 & 0 & 1
\end{array}\right].
\]
Its inverse is
\[
\b T^{-1}=\left[\begin{array}{ccc}
1 & -1 & 1\\
0 & 1 & -1\\
-3 & 3 & -2
\end{array}\right].
\]
It is then easy to check that
\[
\b T^{-1}\b A\b T=\left[\begin{array}{cc}
\b J_1 & \b O\\
\b O & \b J_2
\end{array}\right]=\left[\begin{array}{ccc}
3 & 1 & 0\\
0 & 3 & 0\\
0 & 0 & 3
\end{array}\right],
\]
where
\[
\b J_1=\left[\begin{array}{cc}
3 & 1\\
0 & 3
\end{array}\right]\quad\mb{and}\quad \b J_2=3.
\]
\end{example}
\markex



In general, the Jordan canonical form is a block diagonal matrix, where each diagonal block is a Jordan block corresponding to a possibly different eigenvalue, that is,
\begin{eqnarray}
\b T^{-1}\b A\b T &=& \left[\begin{array}{ccccccccccc}
\lambda_1 & 1 & 0 & \cdots & 0 & {} & {} & {} & {} &{} &{} \\
0 & \lambda_1 & 1 & \cdots & 0 & {} & {} & {} & {} &{} &{} \\
0 & 0 & \lambda_1 & \cdots & 0 & {} & {} & {} & {} &{} &{} \\
\vdots &\vdots &\vdots & \ddots & \vdots &{} &{}& {}& {} & {} & {}\\
0 & 0 & 0 & \cdots & \lambda_1 & {} & {} & {} & {} &{} &{} \\
%{} & {} & {} & {} &{} &{} & {} & {} & {} & {} &{} \\
{} & {} & {} & {} &{} &\ddots & {} & {} & {} & {} &{} \\
{} & {} & {} & {} &{} &{} &\lambda_r & 1 & 0 & \cdots & 0\\
{} & {} & {} & {} &{} &{} &0 & \lambda_r & 1 & \cdots & 0\\
{} & {} & {} & {} &{} &{} &0 & 0 & \lambda_r & \cdots & 0\\
{} &{}& {}& {} & {} & {} &\vdots &\vdots &\vdots & \ddots & \vdots\\
{} & {} & {} & {} &{} &{} &0 & 0 & 0 & \cdots & \lambda_r
\end{array}\right]\nonumber\\
&=& \left[\begin{array}{cccc}
\b J_1 & \b O & \cdots &\b O\\
\b O & \b J_2 & {} &\b O\\
\vdots & {} & \ddots & \vdots\\
\b O & \b O& \cdots & \b J_q
\end{array}\right],
\label{eq:gen_Jord_can_form}
\end{eqnarray}
where each $r_i\times r_i$ Jordan block has the form $\b J_i=\lambda_i$ if $r_i=1$, or, for $r_i>1$ the corresponding Jordan block has a non-diagonal structure. Note that
\[
n=r_1 + r_2 + \cdots + r_q
\]
and
\[
q \ge r,
\]
which means that there may be more than one Jordan blocks associated with one eigenvalue as was the case in Example~\ref{exam:two_blks_Jord_form}.
\begin{example}\label{exam:two_eig_Jord_form}\rm
To illustrate the general case depicted in~\eqref{eq:gen_Jord_can_form}, we consider, as in Chen~\cite[p.~60]{ctchen99}, a $5$-by-$5$ matrix $\b A$ with repeated eigenvalue $\lambda_1$ of multiplicity 4 and a simple eigenvalue $\lambda_2$, that is, the characteristic polynomial of $\b A$ is
\[
\Delta(\lambda)=(\lambda-\lambda_1)^4(\lambda-\lambda_2).
\]
Depending on the nullity of the matrix $[\b A-\lambda_1\b I_5]$, the Jordan form of the matrix $\b A$ make take one of the following forms:
\begin{itemize}
\item If the nullity of $[\b A-\lambda_1\b I_5]$ is 1, then there is only one eigenvector, say $\b u_1$ associated with $\lambda_1$ and we need to compute three generalized eigenvectors to form a basis $\{\b u_1, \b u_2, \b u_3, \b u_4, \b v_1\}$, where $\b v_1$ is an eigenvector associated with $\lambda_2$. The matrix $\b A$ in this basis will have the form:
    \[
    \hat{\b A}_1=\b T_1^{-1}\b A\b T_1 = \left[\begin{array}{cccccc}
\lambda_1 & 1 & 0 & 0 & \vdots & 0\\
0 & \lambda_1 & 1 & 0 &  \vdots & 0\\
0 & 0 & \lambda_1 & 1 &   \vdots & 0\\
0 & 0 & 0 &\lambda_1 &    \vdots & 0\\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots\\
0 & 0 & 0 & 0 & \vdots & \lambda_2
\end{array}\right].
    \]
Note that we can re-order the basis vectors as $\{\b v_1, \b u_1, \b u_1, \b u_3, \b u_4\}$. In this basis the matrix $\b A$ representation has the form
\[
\hat{\b A}_2=\b T_2^{-1}\b A\b T_2 = \left[\begin{array}{cccccc}
\lambda_2 & \vdots & 0 & 0 & 0 & 0\\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots\\
0 & \vdots & \lambda_1 & 1 & 0 &   0\\
0 & \vdots & 0 & \lambda_1 & 1  & 0 \\
0 & \vdots & 0 & 0 & \lambda_1 &  1\\
0 & \vdots & 0 & 0 & 0 & \lambda_1
\end{array}\right].
\]
    \item If the nullity of $[\b A-\lambda_1\b I_5]$ is 2, then there are two eigenvectors associated with $\lambda_1$, that is, there are two Jordan blocks associated with $\lambda_1$. The matrix $\b A$ may take one of the following forms:
\[
\hat{\b A}_3=\b T_3^{-1}\b A\b T_3 = \left[\begin{array}{ccccccc}
\lambda_1 & 1 & 0 & \vdots & 0 &{}&  0 \\
0 & \lambda_1 & 1 & \vdots & 0 &{} & 0 \\
0 & 0 & \lambda_1 & \vdots & 0  & {} &0 \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots &{} \\
0 & 0 & 0 & \vdots & \lambda_1 &  \vdots &0\\
{} & {} & {} &  \cdots  & \cdots & \cdots & \cdots\\
0  & 0 & 0 & {}  &0& \vdots &\lambda_2
\end{array}\right]
\]
or
\[
\hat{\b A}_4=\b T_4^{-1}\b A\b T_4 = \left[\begin{array}{ccccccc}
\lambda_1 & 1 & \vdots & 0  & 0 &{}&  0 \\
0 & \lambda_1 & \vdots & 0  & 0 &{} & 0 \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots &{} \\
0 & 0 & \vdots & \lambda_1 & 1 & \vdots & 0 \\
0 & 0 &  \vdots & 0 & \lambda_1 &  \vdots &0\\
{} & {} & \cdots &  \cdots  & \cdots & \cdots & \cdots\\
0  & 0 & {} & 0  &0& \vdots &\lambda_2
\end{array}\right].
\]
    \item If the nullity of $[\b A-\lambda_1\b I_5]$ is 3, then there are three eigenvectors associated with $\lambda_1$, that is, there are three Jordan blocks associated with $\lambda_1$. The matrix $\b A$ may take the following form:
        \[
\hat{\b A}_5=\b T_5^{-1}\b A\b T_5 = \left[\begin{array}{cccccccc}
\lambda_1 & 1 & \vdots & 0  & {} & 0 &{}&  0 \\
0 & \lambda_1 & \vdots & 0  & {} & 0 &{} & 0 \\
\cdots & \cdots & \cdots & \cdots & \cdots & {} &{} & {}\\
0 & 0  & \vdots & \lambda_1 &  \vdots & 0 &{} &0\\
{} & {} & \cdots & \cdots & \cdots & \cdots &\cdots \\
0 & 0 &  {} & 0&  \vdots & \lambda_1 &  \vdots  & 0\\
{} & {} & {} & {}  & \cdots & \cdots & \cdots&\cdots\\
0  & 0 & {}& 0 & {}  &0& \vdots &\lambda_2
\end{array}\right].
\]
\item Finally, if the nullity of $[\b A-\lambda_1\b I_5]$ is 4, then there are four eigenvectors associated with $\lambda_1$, that is, there are four Jordan blocks associated with $\lambda_1$. The Jordan form of the matrix matrix $\b A$ is a diagonal matrix,
    \[
  \hat{\b A}_6=\b T_6^{-1}\b A\b T_6 = \left[\begin{array}{cccccc}
\lambda_1 & 0 & 0 & 0 & 0 \\
0 & \lambda_1 & 0 & 0 &  0 \\
0 & 0 & \lambda_1 & 0 &   0 \\
0 & 0 & 0 &\lambda_1 &    0 \\
0 & 0 & 0 & 0 &  \lambda_2
\end{array}\right].
    \]
\end{itemize}
\end{example}
\markex

To summarize our discussion, we need the following definitions.
\begin{defn}
For a given eigenvalue $\lambda_i$ of an $n$-by-$n$ matrix $\b A$, its algebraic multiplicity is the multiplicity of it in the characteristics polynomial $\Delta (\lambda)$, that is, the algebraic multiplicity of $\lambda_i$ is the sum of orders of all Jordan blocks associated with $\lambda_i$.
\end{defn}\markdefn
\begin{defn}
For a given eigenvalue $\lambda_i$ of an $n$-by-$n$ matrix $\b A$, its geometric multiplicity is the nullity of the associated characteristic matrix $\left[\begin{array}{c}
\b A - \lambda_i\b I_n
\end{array}\right]$, that is, the geometric multiplicity of $\lambda_i$ equals the number of Jordan blocks associated with it.
\end{defn}\markdefn

Then we have the following theorem:
\begin{thm}
A given $n$-by-$n$ matrix $\b A$ is diagonalizable if and only if geometric multiplicities of its eigenvalues are the same as their algebraic multiplicities, that is, if and only if $\b A$ has $n$ linearly independent eigenvectors.
\end{thm}

We close our discussion on the Jordan canonical form with an observation by Owens~\cite[p.~34]{owens81} that in almost all situations of practical relevance, the matrix $\b A$ has distinct eigenvalues. So in a sense the cases described in this section can be considered ``pathological'' from the applications point of view. In the literature, see for example~\cite[p.~61]{ctchen99}, if $\b A$ cannot be diagonalized then it is called to be defective. Calculation of the Jordan canonical is numerically ill conditioned. One can try MATLAB's function \verb!jordan!. However, the matrix $\b A$ must be known exactly, which in MATLAB's language means that its elements must be integers or ratios of small integers. Finally, to diagonalize a square matrix using MATLAB, one can call the function \verb!eig!. If, however, $\b A$ is not diagonalizable, then the function \verb!eig! will give incorrect solution.


\subsection{Computing Polynomial Functions of a Square Matrix}

If $\b A$ is an $n$-by-$n$ square matrix then its $k$-th power is
\[
\b A^k=\underbrace{\b A\b A \times \cdots \times \b A}_{\mb{$k$ times}},
\]
where
\[
\b A^0=\b I_n.
\]
Suppose now that we have a polynomial
\[
f(\lambda)=\lambda^n + \alpha_{n-1}\lambda^{n-1} +\cdots + \alpha_1 \lambda + \alpha_0.
\]
Then we define $f(\b A)$ as
\[
f(\b A)=\b A^n +\alpha_{n-1}\b A^{n-1} + \cdots + \alpha_1 \b A + \alpha_0 \b I_n.
\]
For example, if
\[
f(\lambda)=\lambda^2 + 2\lambda -3=(\lambda +3)(\lambda -1),
\]
then
\[
f(\b A)=\b A^2 + 2\b A - 3\b I_n= (\b A + 3\b I_n)(\b A-\b I_n).
\]
Now if the matrix $\b A$ is block diagonal, for example, such as
\[
\b A=\left[\begin{array}{ccc}
\b A_1 & \b O & \b O\\
\b O & \b A_2 & \b O\\
\b O & \b O & \b A_3
\end{array}\right],
\]
where $\b A_i$ are square matrices and $\b O$ denotes a matrix of zeros of appropriate dimensions, then we have
\[
\b A^k=\left[\begin{array}{ccc}
\b A_1^k & \b O & \b O\\
\b O & \b A_2^k & \b O\\
\b O & \b O & \b A_3^k
\end{array}\right]
\]
and
\[
f(\b A)=\left[\begin{array}{ccc}
f(\b A_1) & \b O & \b O\\
\b O & f(\b A_2) & \b O\\
\b O & \b O & f(\b A_3)
\end{array}\right].
\]
Consider a similar matrix $\hat{\b A}$ of the given matrix $\b A$, that is,
\[
\hat{\b A}=\b T^{-1}\b A \b T,
\]
where $\b T\in \mb{\Bb R}^{n\times n}$ is an invertible matrix. The above can be re-written as
\[
\b A=\b T\hat{\b A}\b T^{-1},
\]
and we have
\begin{eqnarray*}
\b A^k &=& \left( \b T\hat{\b A}\b T^{-1} \right)\left( \b T\hat{\b A}\b T^{-1} \right)\times \cdots \times \left( \b T\hat{\b A}\b T^{-1} \right)\\
&=& \b T\hat{\b A}^k\b T^{-1},
\end{eqnarray*}
or
\begin{eqnarray*}
\hat{\b A}^k &=& \left( \b T^{-1}\b A\b T \right)\left( \b T^{-1}\b A\b T \right)\times \cdots \times \left( \b T^{-1}\b A\b T \right)\\
&=& \b T^{-1}\b A^k\b T.
\end{eqnarray*}
Thus, we have
\begin{equation}
f\left(\b A\right)= \b Tf( \hat{\b A})\b T^{-1}
\label{eq:ahatAtinv}
\end{equation}
or
\begin{equation}
f(\hat{\b A})= \b T^{-1} f\left(\b A\right)\b T.
\label{eq:tinvaAt}
\end{equation}


Now let $\lambda_i$ be the $i$-th eigenvalue of $\b A$ and suppose that the algebraic multiplicity of $\lambda_i$ is $n_i$. Then the characteristic polynomial of $\b A$ can be written as,
\begin{equation}
\Delta(\lambda)=\det (\lambda\b I_n - \b A)= \prod_{i=1}^r \left(\lambda - \lambda_i \right)^{n_i}.
\label{eq:char_poly_of_A}
\end{equation}

We now discuss a very useful property of Jordan blocks that we will utilize in the proof of the very imporatnt theorem of linear algebra, the theorem of Cayley and Hamilton. Suppose that we have a fourth order Jordan block,
\[
\b J=\left[\begin{array}{cccc}
\lambda_i & 1 & 0 & 0\\
0 & \lambda_i & 1 & 0\\
0 & 0 & \lambda_i & 1\\
0 & 0 & 0 & \lambda_i
\end{array}\right].
\]
Then we have
\[
(\b J-\lambda_i \b I)=\left[\begin{array}{cccc}
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 0 & 0
\end{array}\right].
\]
Let us now compute successive powers of $(\b J-\lambda \b I)$. We obtain
\[
(\b J-\lambda_i \b I)^2=\left[\begin{array}{cccc}
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0
\end{array}\right],\quad
(\b J-\lambda_i \b I)^3=\left[\begin{array}{cccc}
0 & 0 & 0 & 1\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0
\end{array}\right],
\]
and
\[
(\b J-\lambda_i \b I)^k=\b O\quad\mb{for}\quad k\ge 4.
\]
A matrix with above property is called a {\it nilpotent} matrix.

In general, if we have a Jordan block of order $r_i$ then
\begin{equation}
(\b J-\lambda_i \b I)^k=\b O\quad\mb{for}\quad k\ge r_i.
\label{eq:nilpotentJ}
\end{equation}

We have all we need to state and prove the theorem of Cayley and Hamilton.
\begin{thm}\label{thm:CHthm}(Cayley-Hamilton theorem)
A square matrix satisfies its characteristic polynomial equation, that is,
\[
\Delta(\b A)=\b O.
\]
\end{thm}
{\bf Proof}\quad Suppose that $\hat{\b A}$ is the Jordan canonical form of $\b A$. Thus there exists a non-singular matrix $\b T$ such that
\[
\hat{\b A}=\b T^{-1}\b A\b T=\left[\begin{array}{cccc}
\b J_1 & \b O & \cdots &\b O\\
\b O & \b J_2 & {} &\b O\\
\vdots & {} & \ddots & \vdots\\
\b O & \b O& \cdots & \b J_q
\end{array}\right].
\]
Let us now consider the matrix polynomial $\Delta(\b A)$. We use~\eqref{eq:ahatAtinv} to obtain
\begin{eqnarray*}
\Delta(\b A) &=& \b T \Delta( \hat{\b A})\b T^{-1}\\
&=&\b T\prod_{i=1}^r \left(\hat{\b A}- \lambda_i\b I_n \right)^{n_i} \b T^{-1}\\
%&=& \b T\left(\hat{\b A}- \lambda_1\b I_n \right)^{n_1}\times \left(\hat{\b A}- \lambda_2\b I_n \right)^{n_2}\times \cdots \times \left(\hat{\b A}- \lambda_r\b I_n \right)^{n_r}\b T^{-1}\\
&=& \b T \prod_{i=1}^r\left[\begin{array}{cccc}
\b J_1-\lambda_i\b I_{r_1} & \b O & \cdots &\b O\\
\b O & \b J_2-\lambda_i\b I_{r_2} & {} &\b O\\
\vdots & {} & \ddots & \vdots\\
\b O & \b O& \cdots & \b J_q-\lambda_i\b I_{r_q}
\end{array}\right]^{n_i}\b T^{-1}\\
&=& \b T \prod_{i=1}^r\left[\begin{array}{cccc}
(\b J_1-\lambda_i\b I_{r_1})^{n_i} & \b O & \cdots &\b O\\
\b O & (\b J_2-\lambda_i\b I_{r_2})^{n_i} & {} &\b O\\
\vdots & {} & \ddots & \vdots\\
\b O & \b O& \cdots & (\b J_q-\lambda_i\b I_{r_q})^{n_i}
\end{array}\right]\b T^{-1}.
\end{eqnarray*}
The order of any Jordan block associated with $\lambda_i$ cannot exceed the corresponding algebraic multiplicity. Taking into account the nilpotent property given by~\eqref{eq:nilpotentJ}, we obtain
\begin{eqnarray}
\Delta(\b A) &=&\b T \left[\begin{array}{cccc}
\b O & \b O & \cdots &\b O\\
\b O & (\b J_2-\lambda_1\b I_{r_2})^{n_1} & {} &\b O\\
\vdots & {} & \ddots & \vdots\\
\b O & \b O& \cdots & (\b J_q-\lambda_1\b I_{r_q})^{n_1}
\end{array}\right]\times \nonumber\\
{}&{}&\quad \cdots \times \left[\begin{array}{cccc}
(\b J_1-\lambda_r\b I_{r_1})^{n_r} & \b O & \cdots &\b O\\
\b O & (\b J_2-\lambda_r\b I_{r_2})^{n_r} & {} &\b O\\
\vdots & {} & \ddots & \vdots\\
\b O & \b O& \cdots & \b O
\end{array}\right]\b T^{-1}\nonumber\\
&=& \b T \left[\begin{array}{cccc}
\b O & \b O & \cdots &\b O\\
\b O & \b O & {} &\b O\\
\vdots & {} & \ddots & \vdots\\
\b O & \b O& \cdots & \b O
\end{array}\right]\b T^{-1}\nonumber\\
&=&\b O,
\label{eq:C_H_thm_pf_end}
\end{eqnarray}
which completes the proof of the theorem.\\
\hspace*{5.5in} $\Box$

It follows from the Cayley-Hamilton theorem that
\[
\Delta(\b A)=\b A^n +\alpha_{n-1}\b A^{n-1} + \cdots + \alpha_1 \b A + \alpha_0 \b I_n=\b O,
\]
that is,
\begin{equation}
\b A^n=-\alpha_{n-1}\b A^{n-1} - \cdots - \alpha_1 \b A - \alpha_0 \b I_n.
\label{eq:Aton-alin_combo}
\end{equation}
Thus $\b A^n$ can be expressed as a linear combination of the matrices
\[
\{\b I_n, \b A, \ldots, \b A^{n-1}  \}.
\]
If we multiply both sides of~\eqref{eq:Aton-alin_combo} by $\b A$, then we obtain
\begin{equation}
\b A^{n+1}=-\alpha_{n-1}\b A^{n} - \cdots - \alpha_1 \b A^2 - \alpha_0 \b A.
\label{eq:Atonplusone}
\end{equation}
Thus, $\b A^{n+1}$ can be expressed as a linear combination of
\[
\{\b A, \b A^2, \ldots, \b A^{n}  \}.
\]
Using~\eqref{eq:Aton-alin_combo}, we conclude that $\b A^{n+1}$ can be expressed as a linear combination of $\{\b I_n, \b A, \ldots, \b A^{n-1}  \}$. Using the same argument, we conclude that any $\b A^k$, $k\ge 0$, can be expressed as a linear combination of $\{\b I_n, \b A, \ldots, \b A^{n-1}  \}$. Therefore, any matrix polynomial $f(\b A)$ can also be expressed as
\[
f(\b A)=\beta_0\b I_n + \beta_1\b A +\cdots + \beta_{n-1}\b A^{n-1}
\]
for some $\beta_i$, $i=0,1,\ldots, n-1$. The above property is used to efficiently compute matrix polynomials of $\b A$, which can then be used to compute the matrix exponential $e^{\b At}$ as well as the state transition matrix for discrete-time systems. In what follows, we present such a method and illustrate it with examples. We follow the presentation of Chen~\cite[pp.~63--67]{ctchen99}.


Suppose we are given a polynomial $f(\lambda)$ and we are interested in calculating $f(\b A)$. We begin with dividing $f(\lambda)$ by $\Delta (\lambda)$ to obtain
\begin{equation}
f(\lambda)=q(\lambda)\Delta(\lambda) + h(\lambda),
\label{eq:didefbydelat}
\end{equation}
where $q(\lambda)$ is the quotient, $h(\lambda)$ is the remainder, and
\[
\deg_{\lambda} h(\lambda) < n.
\]
We now evaluate $f(\b A)$ using~\eqref{eq:didefbydelat} and the Cayley-Hamilton theorem to obtain
\begin{eqnarray*}
f(\b A)&=&q(\b A)\Delta(\b A) + h(\b A)\\
&=& q(\b A)\b O + h(\b A)\\
&=& h(\b A).
\end{eqnarray*}
Thus instead of evaluating the matrix polynomial $f(\b A)$ that may contain very high powers of $\b A$, we can find $f(\b A)$ by computing $h(\b A)$, where the highest power of $\b A$ is less than $n$. In addition, rather than performing the division~\eqref{eq:didefbydelat}, we can find $h(\lambda)$ by assuming that it has the form
\[
h(\lambda)=\beta_0 + \beta_1 \lambda + \cdots + \beta_{n-1}\lambda^{n-1}
\]
and then solve $n$ equations for $\beta_i$, $i=0,1,\ldots,n-1$. Consider first the case when $\b A$ has distinct eigenvalues. To obtain equations involving the coefficients $\beta_i$, we note that
\[
f(\lambda_i)=q(\lambda_i)\Delta(\lambda_i) + h(\lambda_i) = h(\lambda_i),\quad i=1,2,\ldots, n.
\]
\begin{example}\label{ex:dist_eig_eqna_for_beta}\rm
For a given
\[
f(\lambda)=\lambda^{7},
\]
we compute
\[
f(\b A)=\b A^{7},
\]
where
\begin{equation}
\b A=\left[\begin{array}{cc}
0 & 2\\
1 & 1
\end{array}\right].
\label{eq:simpleA}
\end{equation}
The characteristic polynomial of $\b A$ is
\[
\Delta (\lambda)=\lambda^2-\lambda-2=(\lambda+1)(\lambda-2).
\]
Let
\[
h(\lambda)=\beta_0 + \beta_1\lambda.
\]
Then we have two equations:
\[
f(\lambda_i)=h(\lambda_i),\quad i=1,2,
\]
that is,
\[
f(-1)=(-1)^{7}=-1=\beta_0 -\beta_1
\]
and
\[
f(2)=2^{7}=128=\beta_0+2\beta_1 .
\]
We represent the above linear equations for $\beta_0$ and $\beta_1$ in the matrix format as
\[
\left[\begin{array}{cc}
1 & -1\\
1 & 2
\end{array}\right]\left[\begin{array}{c}
\beta_0\\
\beta_1
\end{array}\right]=\left[\begin{array}{c}
-1\\
128
\end{array}\right].
\]
Solving, we obtain $\beta_0=42$ and $\beta_1=43$. Hence
\[
f(\b A)=\b A^7=42\b I_2 + 43\b A=\left[\begin{array}{cc}
42 & 86\\
43 & 85
\end{array}\right].
\]
\end{example}
\markex
\begin{example}\label{ex:mat_exp_with_h}\rm
We can use the above method to evaluate $e^{\b At}$, where $\b A$ is given by~\eqref{eq:simpleA}. In other words, let $f(\lambda)=e^{\lambda t}$; we wish to find
\[
f(\b A)=e^{\b At}.
\]
Let $h(\lambda)=h(\lambda)=\beta_0 + \beta_1\lambda$. Then
\[
f(-1)=h(-1)
\]
yields
\[
e^{-t}=\beta_0-\beta_1,
\]
and
\[
f(2)=h(2)
\]
yields
\[
e^{2t}=\beta_0+2\beta_1.
\]
We thus have two equations for $\beta_0$ and $\beta_1$,
\[
\left[\begin{array}{cc}
1 & -1\\
1 & 2
\end{array}\right]\left[\begin{array}{c}
\beta_0\\
\beta_1
\end{array}\right]=\left[\begin{array}{c}
e^{-t}\\
e^{2t}
\end{array}\right].
\]
Solving the above gives
\[
\left[\begin{array}{c}
\beta_0\\
\beta_1
\end{array}\right]=\frac{1}{3}\left[\begin{array}{cc}
2 & 1\\
-1 & 1
\end{array}\right]\left[\begin{array}{c}
e^{-t}\\
e^{2t}
\end{array}\right]=\frac{1}{3}\left[\begin{array}{c}
2e^{-t}+e^{2t}\\
-e^{-t}+e^{2t}
\end{array}\right].
\]
Hence
\[
e^{\b At}=\beta_0\b I_2 + \beta_1\b A=\frac{1}{3}\left[\begin{array}{cc}
2e^{-t}+e^{2t} & -2e^{-t}+2e^{2t}\\
-e^{-t}+e^{2t} &  e^{-t}+2e^{2t}
\end{array}\right].
\]
\end{example}
\markex

When the characteristic polynomial has repeated zeros, we use the derivatives of $f(\lambda)$ and $h(\lambda)$ to obtain additional equations to determine the coefficients of $h(\lambda)$ as per the following theorem.
\begin{thm} Chen~\cite[p.~64]{ctchen99}\label{thm:handfon sepecofA}
We are given $f(\lambda)$ and an $n\times n$ matrix $\b A$ with characteristic polynomial
\[
\Delta (\lambda) = \prod_{i=1}^m (\lambda-\lambda_i)^{n_i},
\]
where $n=\sum_{i=1}^m n_i$. Let
\[
h(\lambda) = \beta_0 + \beta_1\lambda + \cdots + \beta_{n-1}\lambda^{n-1}.
\]
It is a polynomial of degree $n-1$ with $n$ unknown coefficients. These $n$ unknowns are to be solved from the following set of $n$ equations:
\[
f^{(l)}(\lambda_i)=h^{(l)}(\lambda_i)\quad\mb{for}\quad l=0,1,\ldots , n_i-1 \quad\mb{and}\quad i=1,2,\ldots , m
\]
where
\[
f^{(l)}(\lambda_i)=\left.\frac{d^l f(\lambda)}{d \lambda^l}\right.\arrowvert_{\lambda = \lambda_i}
\]
and $h^{(l)}(\lambda_i)$ is similarly defined. Then we have
\[
f(\b A)=h(\b A)
\]
and $h(\lambda)$ is said to be equal $f(\lambda)$ on the spectrum of $\b A$.
\end{thm}
\begin{example}\label{ex:mat_exp_sim_multi_ex}\rm
We compute $e^{\b A t}$ for
\[
\b A=\left[\begin{array}{ccc}
3 & 0 & 1\\
-1 & 1 & 2\\
-2 & 0 & 0
\end{array}\right].
\]
The characteristic polynomial is
\[
\Delta (\lambda)=(\lambda -1)^2(\lambda-2).
\]
Let $f(\lambda)=e^{\lambda t}$ and let $h(\lambda)=\beta_0 + \beta_1 \lambda + \beta_2 \lambda^2$. Then using Theorem~\ref{thm:handfon sepecofA}, we obtain
\begin{eqnarray*}
f(1)&=& h(1),\quad e^t = \beta_0 + \beta_1 + \beta_2,\\
f'(1)&=& h'(1), \quad te^t = \beta_1 + 2\beta_2,\\
f(2)&=& h(2),\quad e^{2t} = \beta_0 + 2\beta_1 + 4\beta_2.
\end{eqnarray*}
Thus we have a set of equations
\[
\left[\begin{array}{ccc}
1 & 1 & 1\\
0 & 1 & 2\\
1 & 2 & 4
\end{array}\right]\left[\begin{array}{c}
\beta_0\\
\beta_1\\
\beta_2
\end{array}\right]=\left[\begin{array}{c}
e^t\\
te^t\\
e^{2t}
\end{array}\right].
\]
Solving the above gives
\[
\left[\begin{array}{c}
\beta_0\\
\beta_1\\
\beta_2
\end{array}\right]=\left[\begin{array}{ccc}
0 & -2 & 1\\
2 & 3 & -2\\
-1 & -1 & 1
\end{array}\right]\left[\begin{array}{c}
e^t\\
te^t\\
e^{2t}
\end{array}\right]=\left[\begin{array}{c}
-2te^t + e^{2t}\\
2e^t + 3te^t -2 e^{2t}\\
-e^t - t e^t + e^{2t}
\end{array}\right].
\]
Hence
\begin{eqnarray*}
e^{\b A t} &=& h(\b A)\\
&=& \beta_0 \b I_3 + \beta_1\b A + \beta_2 \b A^2\\
&=& \left(-2te^t + e^{2t} \right)\left[\begin{array}{ccc}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{array}\right]+ \left(2e^t + 3te^t -2 e^{2t} \right)\left[\begin{array}{ccc}
3 & 0 & 1\\
-1 & 1 & 2\\
-2 & 0 & 0
\end{array}\right]\\
&{}& + \left(-e^t - t e^t + e^{2t} \right)\left[\begin{array}{ccc}
7 & 0 & 3\\
-8 & 1 & 1\\
-6 & 0 & -2
\end{array}\right]\\
&=& \left[\begin{array}{ccc}
-e^t+ 2e^{2t} & 0 & -e^t+ e^{2t}\\
6e^t+5te^t - 6e^{2t} & e^t & 3e^t+5te^t- 3e^{2t}\\
2e^t-2e^{2t} & 0 & 2e^t - e^{2t}
\end{array}\right].
\end{eqnarray*}
\end{example}
\markex
\begin{example}\label{ex:mat_exp_Jord_block}\rm
Suppose we are given the Jordan block of order $n_i$,
\[
\b J = \left[\begin{array}{cccccc}
\lambda_i & 1 & 0 &  \cdots & 0 & 0\\
0 & \lambda_i & 1 &  \cdots & 0 & 0\\
0 & 0 & \lambda_i &  \cdots & 0 & 0\\
\vdots & \vdots & {} & \ddots & {}& \vdots\\
0 & 0 & 0 & \cdots & \lambda_i & 1\\
0 & 0 & 0 & \cdots & 0 & \lambda_i
\end{array}\right].
\]
The characteristic polynomial of $\b J$ is $\Delta (\lambda)=(\lambda - \lambda_i)^{n_i}$. For computational simplicity we select the $(n_i-1)$-st order polynomial $h(\lambda)$ of the form
\[
h(\lambda)=\beta_0 + \beta_1(\lambda-\lambda_i) + \beta_2(\lambda - \lambda_i)^2 + \cdots + \beta_{n_i - 1} (\lambda - \lambda_i)^{n_i-1}.
\]
The condition $f(\lambda)=h(\lambda)$ on the spectrum of $\b J$ yields
\[
\beta_0 = f(\lambda_i),\quad \beta_1 = f'(\lambda_i),\quad \beta_2 = \frac{f''(\lambda_i)}{2!},\ldots , \beta_{n_i - 1}= \frac{f^{(n_i-1)}(\lambda_i)}{(n_i-1)!}.
\]
Hence
\begin{eqnarray*}
f(\b J)&=&f(\lambda_i) \b I_{n_i} + \frac{f'(\lambda_i)}{1!}(\b J-\lambda_i\b I_{n_i}) + \frac{f''(\lambda_i)}{2!}(\b J-\lambda_i\b I_{n_i})^2 + \cdots\\
 {}&{}&\quad \cdots + \frac{f^{(n_i-1)}(\lambda_i)}{(n_i-1)!}(\b J-\lambda_i\b I_{n_i})^{n_i-1}.
\end{eqnarray*}
Using the nilpotent property of the matrix $(\b J-\lambda_i\b I_{n_i})$, we obtain
\[
f(\b J)=\left[\begin{array}{ccccc}
f(\lambda_i) & f'(\lambda_i)/1! & f''(\lambda_i)/2! & \cdots &  f^{(n_i-1)}(\lambda_i)/(n_i-1)!\\
0 & f(\lambda_i) & f'(\lambda_i)/1! &\cdots & f^{(n_i-2)}(\lambda_i)/(n_i-2)! \\
0 & 0 & f(\lambda_i) &   \cdots & f^{(n_i-3)}(\lambda_i)/(n_i-3)! \\
%0 & 0 & 0 & f(\lambda_i) & \cdots  & 0\\
\vdots & \vdots & \vdots &  {} &  \vdots\\
0 & 0 & 0 & \ddots &  f'(\lambda_i)/1!\\
0 & 0 & 0 & \cdots  & f(\lambda_i)
\end{array}\right].
\]
In particular, if $f(\lambda)=e^{\lambda t}$, then we have
\[
e^{\b J t}=\left[\begin{array}{ccccc}
e^{\lambda_i t} & te^{\lambda_i t} & t^2e^{\lambda_i t}/2! & \cdots &  t^{n_i - 1}e^{\lambda_i t}/(n_i - 1)!\\
0 & e^{\lambda_i t} & te^{\lambda_i t} &\cdots & t^{n_i - 2}e^{\lambda_i t}/(n_i - 2)! \\
0 & 0 & e^{\lambda_i t} &   \cdots & t^{n_i - 3}e^{\lambda_i t}/(n_i - 3)! \\
%0 & 0 & 0 & f(\lambda_i) & \cdots  & 0\\
\vdots & \vdots & \vdots &  {} &  \vdots\\
0 & 0 & 0 & \ddots &  te^{\lambda_i t}\\
0 & 0 & 0 & \cdots  & e^{\lambda_i t}
\end{array}\right].
\]
\end{example}
\markex

\section{State Equation Solution of Controlled System}
%\addcontentsline{toc}{subsection}{Solution of Controlled System}

Consider a model of a controlled dynamic system,
\begin{equation}
\dot{\b x}(t)=\b A\b x(t) + \b B\b u(t)
\label{eq:cosymoli}
\end{equation}
subject to a given initial condition $\b x(0)=\b x_0$, where $\b B$ is an $n \times m$ matrix, and $m<n$ as is usually in practice. Premultiplying both sides of~(\ref{eq:cosymoli}) by the integrating factor, $e^{-\b At}$, yields
\[
e^{-\b At}\dot{\b x}(t)=e^{-\b At}\b A \b x(t) + e^{-\b At} \b B\b u(t).
\]
We then rearrange the above equation as
\begin{equation}
e^{-\b At}\dot{\b x}(t)-e^{-\b At}\b A \b x(t) = e^{-\b At} \b B\b u(t).
\label{eq:xdaxburear}
\end{equation}
Noting that
\[
\frac{d}{dt}\left( e^{-\b At}\b x(t) \right)=-\b Ae^{-\b At}\b x(t)+e^{-\b At}\dot{\b x}(t),
\]
we can represent~(\ref{eq:xdaxburear}) in the form
\[
\frac{d}{dt}\left(e^{-\b At}\b x(t)\right)=e^{-\b At}\b B\b u(t).
\]
Integrating both sides of the resulting equation gives
\[
e^{-\b At}\b x(t)-\b x(0)=\int_{0}^{t}e^{-\b A \tau}\b B\b u(\tau)d\tau.
\]
Hence
\[
\b x(t)=e^{\b At}\b x(0)+\int_{0}^{t}e^{\b A(t-\tau)}\b B\b u(\tau)d\tau.
\]
If the initial condition is $\b x(t_0)=\b x_0$, then integration from $t_0$ to $t$ yields
\begin{equation}
\fbox{$\displaystyle \b x(t)=e^{\b A(t-t_0)}\b x(t_0)+\int_{t_0}^{t}e^{\b A(t-\tau)}\b B\b u(\tau)d\tau $}
\label{eq:coreofcotrls}
\end{equation}

As in the case of the uncontrolled system, we can also use the Laplace transform technique to obtain the solution to~(\ref{eq:cosymoli}) subject to the initial condition $\b x(0)=\b x_0$. Indeed, taking the Laplace transform of~(\ref{eq:cosymoli}) and performing some manipulations yields
\[
\b X(s)=\left(sI_n-\b A\right)^{-1}\b x(0)+\left(sI_n-\b A\right)^{-1}\b B\b U(s).
\]
Hence
\[
\b x(t)={\cal L}^{-1}\left\{\left(sI_n-\b A\right)^{-1}\b x(0)\right\}+{\cal L}^{-1}\left\{\left(sI_n-\b A\right)^{-1}\b B\b U(s)\right\}.
\]
If $\b x_0=\b x(t_0)$, then
\[
\b x(t)={\cal L}^{-1}\left\{e^{-t_0s}\left(sI_n-\b A\right)^{-1}\b x(t_0)\right\}+{\cal L}^{-1}\left\{e^{-t_0s}\left(sI_n-\b A\right)^{-1}\b B\b U(s)\right\}.
\]


\section{From Continuous to Discrete Models}
Our objective here is to present a method for constructing linear discrete-time models from given linear continuous-time models.
%The obtained discrete models will be used to perform computations to generate control commands.

We use a sample-and-hold device that transforms a continuous signal, $f(t)$, into the staircase signal,
\[
f(kh),\quad kh\le t< (k+1)h,
\]
where $h$ is the sampling period. The sample and zero-order hold~(ZOH) operation is illustrated in Figure~\ref{fig:sample_hold}.
\begin{figure}[h]
\centering \epsfig{file=sample_zoh_2009.eps,width=12cm}
\caption{Sample and zero-order hold~(ZOH) element operating on a continuous function.}
\label{fig:sample_hold}
\end{figure}

Suppose that we are given a continuous-time model,
\begin{eqnarray}
\dot{\b x}(t) &=& \b A\b x(t) + \b B\b u(t),\quad \b x_0=\b x(t_0)\label{eq:state_eqn_forc2d}\\
\b y(t) &=& \b C\b x(t).
\label{eqn:out_eqn_for_c2d}
\end{eqnarray}
The solution to the state equation is
\begin{equation}
\b x(t)=e^{\b A(t-t_0)} \b x(t_0) +\int_{t_0}^t e^{\b A(t-\tau)} \b B \b u(\tau) d \tau.
\label{eq:contin_model}
\end{equation}
We assume that the input to the system is generated by a sample and zero-order device and has the form,
\[
\b u(t)=\b u(k), \quad kh\le t< (k+1)h.
\]
Let $t_0=kh$ and $t=(k+1)h$ and let us use shorthand notation,
\[
\b x[k] = \b x(kh)
\]
Then taking into account that $\b u(t)$ is constant on the interval $[kh, (k+1)h)$ we represent~(\ref{eq:contin_model}) as
\begin{eqnarray}
\b x[k+1] &=& e^{\b Ah}\b x[k]+\int_{kh}^{(k+1)h} e^{\b A(kh+h-\tau)}\b B\b u[k] d\tau\nonumber\\
&=& e^{\b Ah}\b x[k]+\int_{kh}^{(k+1)h} e^{\b A(kh+h-\tau)}\b B d\tau\, \b u[k].
\label{eq:pre_chang_lim}
\end{eqnarray}
Consider now the second term on the right-hand side of the above equation. Let
\[
\eta=kh+h-\tau.
\]
Then we can represent~(\ref{eq:pre_chang_lim}) as
\begin{eqnarray}
\b x[k+1] &=& e^{\b Ah}\b x[k]+\int_{kh}^{(k+1)h} e^{\b A(kh+h-\tau)}\b B d\tau\, \b u[k]\nonumber\\
&=& e^{\b Ah}\b x[k]+\int_{0}^{h} e^{\b A\eta}\b B d\eta\, \b u[k]\nonumber\\
&=& \b A_d \b x[k] +\b B_d\b u[k],
\label{eq:final_d_time}
\end{eqnarray}
where
\[
\b A_d=e^{\b Ah}\quad\mb{and}\quad \b B_d= \int_{0}^{h} e^{\b A\eta}\b B d\eta.
\]
The discrete output equation has the form
\[
\b y[k] = \b C\b x[k].
\]

We point out that the above discrete model, employing the zero-order hold, is exact in the sense that the state, input, and output of this model are exactly the same at the sampling times as the state, input, and output of the underlying continuous-time model.


\begin{example}\label{ex:c2d}\rm
We construct an exact linear discrete state-space model for the continuous system model,
\begin{eqnarray*}
\dot{\b x}(t) &=& \left[\begin{array}{cc}
0 & 1\\
0 & 0
\end{array}\right]\b x(k) + \left[\begin{array}{c}
2\\
1
\end{array}\right]u(t)\\
y(t) &=& \left[\begin{array}{cc}
1 & 0
\end{array}\right]\b x(t).
\end{eqnarray*}
The sampling period is $h=1$~sec.

We first evaluate $\b A_d=e^{\b Ah}$. Note that
$\b A^2=\b O$. Hence
\begin{eqnarray*}
\b A_d &=& \b I_2+\b Ah\\
&=& \left[\begin{array}{cc}
1 & 1\\
0 & 1
\end{array}\right].
\end{eqnarray*}
Next, we evaluate
\[
\b B_d=\int_0^h e^{\b A \tau}\b B d\tau.
\]
We obtain
\begin{eqnarray*}
\b B_d&=&\int_0^h e^{\b A \tau}\b B d\tau\\
&=&\int_0^h \left[\begin{array}{cc}
1 & \tau\\
0 & 1
\end{array}\right]\left[\begin{array}{c}
2\\
1
\end{array}\right]d\tau\\
&=& \int_0^1 \left[\begin{array}{c}
2+\tau\\
1
\end{array}\right]d\tau\\
&=& \left. \left[\begin{array}{c}
2\tau+\frac{1}{2}\tau^2\\
\tau
\end{array}\right] \right\arrowvert_0^1\\
&=& \left[\begin{array}{c}
2.5\\
1
\end{array}\right].
\end{eqnarray*}
The discrete model then has the form
\begin{eqnarray*}
\b x[k+1] &=& \left[\begin{array}{cc}
1 & 1\\
0 & 1
\end{array}\right]\b x[k] + \left[\begin{array}{c}
2.5\\
1
\end{array}\right]\\
y[k] &=& \left[\begin{array}{cc}
1 & 0
\end{array}\right]\b x[k].
\end{eqnarray*}
\end{example}

\section{Summary and Notes}



\section{Exercises}
\begin{exercise}\label{ex:anima_double_pend}\rm Write a MATLAB program that animates the motion of the double pendulum system discussed in class. Obtain a plot of the motion of the pendulum tip versus time on the time interval $[0,\; 5~\mb{sec}]$. Use the initial condition,
\[
\left[\begin{array}{cccc}
\theta_1(0)& \dot{\theta}_1(0) & \theta_2(0)& \dot{\theta}_2(0)
\end{array}\right]=\left[\begin{array}{cccc}
135^{\circ} & 0 & 180^{\circ} & 0
\end{array}\right].
\]
Recommended step-size for solving differential equations is $dt=0.0025$.
\end{exercise}

\begin{exercise}\label{ex:lin_algebra_test1_09}\rm
Suppose that $\b x=\left[\begin{array}{ccc}
1 & 2 & 3
\end{array}\right]^{\top}$ is the representation of the given vector in the natural basis $\{\b e_1, \b e_2, \b e_3\}$. Find the representation of this vector in the basis $\{\b e_1', \b e_2', \b e_3'\}$, where
\begin{eqnarray*}
\b e_1' &=& \b e_1 + \b e_3\\
\b e_2' &=& \b e_2-\b e_3\\
\b e_3' &=& \b e_3.
\end{eqnarray*}
\end{exercise}

\begin{exercise}\label{ex:dist_eigenval_pf}\rm Prove Theorem~\ref{thm:dist_eigenval}.
\end{exercise}

\begin{exercise}\label{ex:trans_mat to_get_J}\rm Find a similarity transformation that transforms
\[
\b A=\left[\begin{array}{cccc}
\lambda & 0 & 0 & 0\\
0 & \lambda & 0 & 1\\
1 & 0 & \lambda & 0\\
0 & 0 & 1 & \lambda
\end{array}\right]
\]
into its Jordan form. Do not fix $\lambda$; construct a transformation that works for any $\lambda$. Verify your calculations using MATLAB's Symbolic Toolbox.
\end{exercise}

\begin{exercise}\label{ex:complex_eig_in_A}\rm Calculate the solution for the system,
\[
\dot{\b x}=\left[\begin{array}{cc}
0 & -1\\
1 & -1
\end{array}\right]\b x + \left[\begin{array}{c}
1\\
0
\end{array}\right]u,\quad \b x(0)=\left[\begin{array}{c}
x_1(0)\\
x_2(0)
\end{array}\right],
\]
where $u(t)$ is the unit step, that is, $u(t)=1(t)$. Plot the system trajectories on the time interval $[0,\; 2]$ for $\b x(0)=\b 0$.
\end{exercise}


\begin{exercise}\label{ex:discretize_with_ZOH}\rm
Construct an exact linear discrete state-space model for the system,
\begin{eqnarray*}
\dot{\b x} &=& \left[\begin{array}{cc}
0 & -1\\
1 & -1
\end{array}\right]\b x + \left[\begin{array}{c}
1\\
0
\end{array}\right]u\\
y &=& \left[\begin{array}{cc}
0 & 1
\end{array}\right]\b x
\end{eqnarray*}
The sampling period is $h=0.2$~sec. Verify you calculations using MATLAB's function \verb!c2d!. Find the transfer function of the discrete systems and its step response. Plot the step response of the discrete system on the time interval $[0,\; 2~\mb{sec}]$.
\end{exercise}

\begin{exercise}\label{ex:sylvester's eqn_ex}\rm
Use the Kronecker product to solve the following Sylvester's equation,
\[
\b A\b X+\b X\b B=\b C,
\]
where
\[
\b A=\left[\begin{array}{ccc}
2.7694  &  0.7254 &  -0.2050\\
-1.3499  & -0.0631 &  -0.1241\\
3.0349 &   0.7147  &  1.4897
\end{array}\right], \;\;\;\b B=\left[\begin{array}{cccc}
1.4090  &  0.7172  &  0.7269  &  0.8884\\
1.4172  &  1.6302 &  -0.3034 &  -1.1471\\
0.6715  &  0.4889  &  0.2939  & -1.0689\\
-1.2075 &   1.0347 &  -0.7873 &  -0.8095
\end{array}\right],
\]
and
\[
\b C=\left[\begin{array}{cccc}
-2.9443 &  -0.7549 &  -0.1022  &  0.3129\\
1.4384  &  1.3703 &  -0.2414 &  -0.8649\\
0.3252 &  -1.7115  &  0.3192 &  -0.0301
\end{array}\right].
\]
Verify your solution using MATLAB's function \verb!lyap!.
\end{exercise}

\begin{exercise}\label{ex:simple_q_forms}\rm
\begin{itemize}
\item[{\bf (i)}] Does the rank of the matrix
\[
\b Q=\left[\begin{array}{ccc}
\alpha^4 & \alpha^3 & \alpha^2\\
\alpha^3 & \alpha^2 & \alpha\\
\alpha^2 & \alpha & 1
\end{array}\right], \quad \alpha \in \mb{\Bb R},
\]
depend on the value of $\alpha?$ Is $\b Q$ positive definite, positive semidefinite, negative definite,
negative semidefinite, or indefinite? Justify your answer.
\item[{\bf (ii)}] Find the range of the parameter $\gamma$ for which
the following quadratic form is positive definite;
\[
f(x_1,x_2)=\gamma x_1^2+x_2^2+4x_1x_2.
\]
\item[{\bf (iii)}] Find the range of values of the parameter $\xi$
for which the function
\[
f(x_1,x_2,x_3)=2x_1x_3 - x_1^2-x_2^2-5x_3^2-2\xi x_1x_2 -4x_2x_3,
\]
is negative semi-definite.
\end{itemize}
\end{exercise}
%\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} 