%\setcounter{chapter}{-1}
\appendix
\chapter{Math Review}
%\chapter*{Appendix: Math Review}
%\addcontentsline{toc}{chapter}{Appendix: Math Review}
\label{chp:m_review}
\begin{flushright}
\parbox{5.5in}{Kroemer’s Lemma of New Technology: ``The principal applications of any sufficiently new and innovative technology always have
been – and will continue to be – applications created by that technology.''

In other words: The principal applications have not been of the kind where one improves on something
that could already be done on an acceptable level; they have been applications that could previously
not been met at all – or were not even recognized.

As a rule, such applications have indeed arisen, although usually not immediately. The problem with
truly new applications is that they are extraordinarily hard to predict, and were historically rarely predicted.
Ultimately, progress in applications is not deterministic, but opportunistic, exploiting for new
applications whatever new science and technology happen to be coming along.---H. Kroemer~\cite[p.~958]{kroemer05}

\begin{center}
------------------------
\end{center}


``The last word, when all is heard: Fear God and keep his commandments, for this is man's all; because God will bring to judgment every work, with all its hidden qualities, whether good or bad.''\\{\em Ecclesiastes 12:13--14}}
\end{flushright}

\bigskip

The appendix reviews mathematical techniques that are used in the book. The appendix also serves as a glossary of symbols,\index{appendix!as a glossary of symbols} notation,\index{appendix!notation} and concepts employed in the text. For more information on the topics covered here, the reader should consult references supplied at the end of the appendix.

In an attempt to keep the presentation as clear as possible, we employ the theorem-proof style whenever appropriate. Major results of independent interest are encapsulated as theorems.\index{theorem!major result of independent interest} A lemma is used to denote an auxiliary result\index{lemma!an auxiliary result} that is used as a stepping stone towards a theorem. We use the term proposition as a way to announce a minor theorem.\index{proposition!a minor theorem} A corollary is a direct consequence of a theorem or proposition.\index{corollary!direct consequence of a theorem or proposition} A hypothesis\index{hypothesis} is a statement that is taken for further reasoning in a proof. For more information on the subject of writing for mathematical or technical sciences, we recommend a very clear and useful book by Higham~\cite{higham93}.

\section{Notation and Methods of Proof}
%\section*{Notation and Methods of Proof}
%\addcontentsline{toc}{section}{Notation and Methods of Proof}
We often use the term set.\index{set!collection of definite, distinguishable objects} The great German mathematician G.~Cantor~(1845--1918),\index{Cantor!creator of the theory of sets} the creator of the theory of sets, defines a set as any collection of definite, distinguishable objects of our thought, to be conceived as a whole.~\cite[page~1]{maddox88} The objects, in the definition, are the elements or members of the set. Usually, we use capital letters to denote sets and lower case letters to denote elements of the set. Thus, if $X$ is a set, then we write $x\in X$ to mean that $x$ is an element of $X$. When an object $x$ is not an element of a set $X$, we write $x \notin X$. Often, we use the curly bracket notation for sets. For example, $\{x:x<7\}$ denotes the set of all $x$ less than 7. The colon, :, following $x$ is read ``such that''. The following sets are used in the book:
\begin{center}
\begin{tabular}{l}
$\mb{\Bb N}=\{1,2,3,\ldots \}$, the set of all positive integers,\index{set!of all positive integers}\\
$\mb{\Bb Z}=\{0,1,-1,2,-2,\ldots \}$, the set of all integers,\index{set!of all integers}\\
$\mb{\Bb R}$, the set of all real numbers,\index{set!of all real numbers}\\
$\mb{\Bb C}$, the set of all complex numbers.\index{set!of all complex numbers}
\end{tabular}
\end{center}
Sometimes, we take a fixed set, and then carry out manipulations with reference to the fixed set. We call this fixed set the {\em universe of discourse\/},\index{universe of discourse!a fixed set} or just the {\em universe\/},\index{universe!a fixed set}\index{universe of discourse|see{universe}} for short.

Throughout the text, we work with statements that are combinations of individual statements. It is necessary to distinguish between sentences and the statements. A sentence is a part of a language.\index{sentence!a part of a language} Sentences are used to make different statements.\index{sentences!are used to make statements} In classical logic, statements are either true or false.\index{statements!are either true or false} Consider the following two statements:
\begin{itemize}
\item[$A$]: $x >7$;
\item[$B$]: $x^2 >49$.
\end{itemize}
We can combine the above two statements into one statement, called a {\em conditional\/},\index{conditional!combination of two statements into one statement} that has the form: ``IF $A$ THEN $B$''. Thus, a conditional is a compound statement obtained by placing the word ``IF'' before the first statement and inserting the word ``THEN'' before the second statement. We use the symbol ``$\Rightarrow$'' to represent the conditional ``IF $A$ THEN $B$'' as $A \Rightarrow B$. The statement $A \Rightarrow B$ also reads as ``$A$ implies $B$'', or ``$A$ only if $B$'', or ``$A$ is sufficient for $B$'', or ``$B$ is necessary for $A$''. Statements $A$ and $B$ may either be true or false. The relationship between the truth or falsity of $A$ and $B$ and the conditional $A \Rightarrow B$ can be illustrated by means of a diagram called a {\em truth table\/}\index{truth table} shown in Table~\ref{tab:trutabcon}. In the table, T stands for ``true'', and F stands for ``false''.
\begin{table}[h]
\caption{Truth table for conditional.}
\begin{center}
\begin{tabular}{ccc}\hline
$A$ & $B$ & $A \Rightarrow B$\\ \hline
F & F & T\\
F & T & T\\
T & F & F\\
T & T & T\\ \hline
\end{tabular}
\end{center}
\label{tab:trutabcon}
\end{table}
It is intuitively clear that if $A$ is true, then $B$ must also be true for the statement $A \Rightarrow B$ to be true. If $A$ is not true, then the sentence $A \Rightarrow B$ does not have an obvious meaning in everyday language. We can interpret $A \Rightarrow B$ to mean that we cannot have $A$ true and $B$ not true. One can check that the truth values of the statements $A \Rightarrow B$ and ``not ($A$ and not $B$)'' are the same. We can also check that the truth values of $A \Rightarrow B$ and ``not $B$ $\Rightarrow$ not $A$'' are the same. The above is the basis for three methods, inference processes, of proving statements of the form $A \Rightarrow B$. {\em Inference\/} is a process by which one statement is arrived at,\index{inference} using reasoning, on the basis of one or more other statements accepted as a starting point. {\em Reasoning\/}\index{reasoning} is a special kind of thinking in which inference takes place using the laws of thought. By a {\em proof\/}\index{proof} we mean the process of establishing the truth of a statement by arriving at it from other statements using principles of reasoning. Most of the time we are concerned with the statements of the form $A \Rightarrow B$. We use the following types of proofs of such statements:
\begin{itemize}
\item[(i)] the direct method;
\item[(ii)] the proof by contraposition;
\item[(iii)] the proof by contradiction.
\end{itemize}
In the first case, the direct method,\index{proof!direct} one starts with $A$, then tries to deduce $B$. In the proof by contraposition,\index{proof!by contraposition} one starts with ``not~$B$'', then deduces a chain of consequences to end with ``not~$A$''. This method of proving is based on the fact that the truth values of $A \Rightarrow B$ and ``not $B$ $\Rightarrow$ not $A$'' are the same. The proof by contradiction\index{proof!by contradiction} is based on the fact that the truth values of $A \Rightarrow B$ and  ``not ($A$ and not $B$)'' are the same. In this method, one starts with ``$A$ and not $B$'' and tries to arrive at a contradiction, which is a statement that is always false.

It is possible to combine two conditionals to form a {\em biconditional\/},\index{biconditional} which is a statement of the form ``$A$ if and only if $B$''. Occasionally, we use the symbol ``$\Leftrightarrow$'' to write $A \Leftrightarrow B$ to mean ``$A$ if and only if $B$''. Another way of expressing $A \Leftrightarrow B$ is ``$A$ is equivalent to $B$'', or ``$A$ is necessary and sufficient for $B$''.

\section{Vectors}\label{sec_app:vectors}
%\section*{Vectors}
%\addcontentsline{toc}{section}{Vectors}
We define an $n$-dimensional column vector\index{vector!column} to be an $n$-tuple of numbers
\begin{equation}
\left[\begin{array}{c}
x_1\\
x_2\\
\vdots\\
x_n
\end{array}\right],
\label{eq:n_tuple}
\end{equation}
where $n$ is a positive integer. Thus a vector can be viewed as an ordered set of scalars.\index{vector!an ordered set of scalars} We use lower-case bold letters, for example $\b x$, to denote such $n$-tuples.\index{vector!n-tuple} We call the numbers $x_1, x_2,\ldots,x_n$ the {\em coordinates}\index{coordinates!of the vector} or {\em components}\index{components!of the vector} of the vector $\b x$. The number of components of a vector is its dimension.\index{vector!dimension of} When referring to a particular component of a vector, we use its component, for example $x_i$, or the subscripted name of the vector, for example $(\b x)_i$ to denote $x_i$. The set of all $n$-tuples, that is $n$-vectors, with real coefficients will be denoted $\mb{\Bb R}^n$ and called the real $n$-space. The transpose of the vector\index{transpose!of the vector} $\b x$, denoted $\b x^{\top}$, is an $n$-dimensional row vector
\begin{equation}
\b x^{\top}=\left[\begin{array}{c}
x_1\\
x_2\\
\vdots\\
x_n
\end{array}\right]^{\top}=\left[\begin{array}{cccc}
x_1&x_2\cdots x_n
\end{array}\right].
\label{eq:tran_tuple}
\end{equation}

The sum of two $n$-vectors $\b x$ and $\b y$ is an $n$-vector,\index{sum!of two vectors} denoted $\b x+\b y$, whose $i$-th component is $x_i+y_i$.
The following rules are satisfied:
\begin{enumerate}
\item $(\b x+\b y)+\b z=\b x+(\b y+\b z)$, that is, vector addition is associative.\index{vector addition!associative}
\item $\b x+\b y=\b y+\b x$, which means that vector addition is commutative.\index{vector addition!commutative}
\item Let $\b 0=\left[\begin{array}{cccc}
0&0&\cdots&0
\end{array}\right]^{\top}$ denote the zero vector.\index{zero vector} Then,
\[
\b 0+\b x=\b x+\b 0=\b x.
\]
\item Let $\b x=\left[\begin{array}{cccc}
x_1&x_2&\cdots&x_n
\end{array}\right]^{\top}$ and let $-\b x=\left[\begin{array}{cccc}
-x_1&-x_2&\cdots&-x_n
\end{array}\right]^{\top}$. Then,
\[
\b x+(-\b x)=\b 0.
\]
\end{enumerate}


The product of an $n$-vector $\b x$ by a scalar $c$ is an $n$-th vector, denoted $c\b x$, whose $i$-th component is $cx_i$.


For two vectors $\b x$ and $\b y$ from $\mb{\Bb R}^n$, we define their {\em scalar product},\index{scalar product} also called the {\em inner product},\index{inner product|see{scalar product}} to be
\begin{equation}
\langle \b x,\b y \rangle=\b x^{\top}\b y=x_1y_1+x_2y_2+\cdots+x_ny_n.
\label{eq:scalar_prod}
\end{equation}
The scalar product is commutative,\index{scalar product!commutative}\index{commutative!scalar product}
\[
\langle\b x,\b y\rangle=\langle\b y,\b x\rangle,
\]
and distributivity over vector addition holds,\index{distributivity!over vector addition}
\[
\langle\b x,\b y+\b z\rangle=\langle\b x,\b y\rangle+\langle\b x,\b z\rangle.
\]
Two vectors $\b x$ and $\b y$ are said to be {\em orthogonal\/}\index{orthogonal!vectors} if $\langle \b x,\b y \rangle=0$.

A {\em vector norm\/},\index{vector norm} denoted $\|\cdot\|$, satisfies the following properties:
\begin{itemize}
\item[{\bf VN 1.}] $\|\b x\| > 0$ for any nonzero vector.
\item[{\bf VN 2.}] For any scalar $c$, $\|c \b x\|=|c|\|\b x\|$.
\item[{\bf VN 3.}] For any two vectors $\b x$ and $\b y$, $\|\b x + \b y\| \le \|\b x\|+\|\b y\|$---{\em the triangle inequality}.\index{triangle inequality}
\end{itemize}


The {\em Euclidean norm\/},\index{Euclidean norm} or the {\em 2-norm\/},\index{2-norm|see{Euclidean norm}} of a vector $\b x \in \mb{\Bb R}^n$, denoted $\|\b x\|_2$, is defined as
\begin{equation}
\|\b x\|_2=\sqrt{\langle \b x,\b x\rangle}=\sqrt{x_1^2+x_2^2+\cdots+x_n^2}.
\label{eq:norm_def}
\end{equation}
Note that $\|\b x\|_2^2=\langle \b x,\b x\rangle=\b x^{\top}\b x$. The Euclidean norm is a special class of norms called the {\em H\"{o}lder} or {\em p-norms}\index{H\"{o}lder norms}\index{H\"{o}lder norms|see{p-norms}}\index{p-norms} defined by
\begin{equation}
\|\b x\|_p=\left(|x_1|^p+\cdots+|x_n|^p \right)^{1/p},\quad p\ge 1.
\label{eq:defofpnorm}
\end{equation}
Other often used norms that are special cases of the above class of norms are the {\em 1-norm}\index{1-norm} and the {\em infinity norm}\index{infinity norm} defined respectively as
\begin{equation}
\|\b x\|_1=|x_1|+\cdots+|x_n|
\label{eq:defof1norm}
\end{equation}
and
\begin{equation}
\|\b x\|_{\infty}=\max_i |x_i|.
\label{eq:defofinfnorm}
\end{equation}


Most of the time, we use the Euclidean norm for vectors. So for the sake of brevity, we write $\|\b x\|$ to mean $\|\b x\|_2$.
\begin{thm}[Pythagoras]
If $\b x$ and $\b y$ are orthogonal, then\index{Pythagoras theorem}
\[
\|\b x+\b y\|^2=\|\b x\|^2+\|\b y\|^2.
\]
\label{thm:pythagoras}
\end{thm}
{\bf Proof}\quad We have,
\begin{eqnarray*}
\|\b x+\b y\|^2 &=& \left( \b x+\b y\right)^{\top}\left(\b x+\b y \right)\\
&=& \|\b x\|^2+2\langle \b x,\b y\rangle +\|\b y\|^2\\
&=& \|\b x\|^2+\|\b y\|^2,
\end{eqnarray*}
since by assumption $\langle \b x,\b y\rangle=0$. The proof of the theorem is complete.\\
\hspace*{5.5in}$\Box$

We now introduce the notion of {\em projection}.\index{projection} Let $\b x$, $\b y$ be two vectors, where $\b y \ne \b 0$. Let $\b z=c\b y$, $c\in \mb{\Bb R}$, be the vector such that the vector $\b x-\b z$ is orthogonal to $\b y$---see Figure~\ref{fig:projection_il} for an illustration of the above construction.
\begin{figure}
\vskip.2in
\setlength{\unitlength}{.07in}
\begin{center}
\begin{picture}(60,40)(0,0)
\thicklines
\put(10,10){\vector(4,1){40}}
\put(51,20){$\b y$}
\put(10,10){\vector(1,1){20.1}}
\put(27,29){$\b x$}
\put(10,10){\vector(4,1){24}}
\put(34,14){$\b z=c\b y$}
\put(34,16){\vector(-1,4){3.5}}
\put(8,9){$\b 0$}
\put(32,28){$\b x-\b z$}
\end{picture}
\end{center}
\caption{Computing the projection of $\b x$ along $\b y$.}
\label{fig:projection_il}
\end{figure}
Thus,
\begin{equation}
\left( \b x-\b z\right)^{\top}\b y=0.
\label{eq:vecs_xyzp}
\end{equation}
Substituting $\b z=c\b y$ into~(\ref{eq:vecs_xyzp}) yields
\begin{equation}
\left( \b x-\b z\right)^{\top}\b y=\left( \b x-c\b y\right)^{\top}\b y=0.
\label{eq:after_subssyzp}
\end{equation}
Hence,
\begin{equation}
c=\frac{\langle\b x,\b y \rangle}{\|\b y\|^2}.
\label{eq:project_coef}
\end{equation}
The number $c$ given by~(\ref{eq:project_coef}) is called the component of $\b x$ along $\b y$.\index{component!of $\b x$ along $\b y$} The projection of $\b x$ along $\b y$\index{projection!of $\b x$ along $\b y$} is the vector
\begin{equation}
\b z=c\b y=\frac{\langle\b x,\b y \rangle}{\|\b y\|^2}\b y.
\label{eq:pro_vec_al}
\end{equation}
\begin{thm}[Cauchy-Schwarz Inequality]
Let $\b x, \b y \in \mb{\Bb R}^n$. Then,\index{Cauchy-Schwarz inequality}
\begin{equation}
\left\arrowvert \langle \b x,\b y \rangle\right\arrowvert \le \|\b x\| \|\b y\|.
\label{eq:schwarz_ineq}
\end{equation}
\end{thm}
{\bf Proof}\quad If $\b y = \b 0$, then both sides of~(\ref{eq:schwarz_ineq}) are equal to 0, and the assertion holds. Suppose that $\b y\ne \b 0$, and let $c$ denote the component of $\b x$ along $\b y$. Hence, $c$ is given by~(\ref{eq:project_coef}). We then write
\begin{equation}
\b x=\b x-\b z+\b z=\b x-c\b y+c\b y.
\label{eq:aminusaz}
\end{equation}
For an illustration of~(\ref{eq:aminusaz}), consult Figure~\ref{fig:projection_il}. Applying the Pythagoras theorem\index{Pythagoras theorem} to~(\ref{eq:aminusaz}), we obtain
\begin{equation}
\|\b x\|^2=\|\b x-c\b y\|^2+\|c\b y\|^2=\|\b x-c\b y\|^2+c^2\|\b y\|^2.
\label{eq:after_pytag}
\end{equation}
Hence,
\begin{equation}
c^2\|\b y\|^2\le \|\b x\|^2.
\label{eq:pyta_less}
\end{equation}
On the other hand, by~(\ref{eq:project_coef}),
\begin{equation}
c^2\|\b y\|^2=\frac{\langle\b x,\b y \rangle^2}{\|\b y\|^4}\|\b y\|^2=\frac{\langle\b x,\b y \rangle^2}{\|\b y\|^2}.
\label{eq:on_the_other}
\end{equation}
Combining~(\ref{eq:pyta_less}) and~(\ref{eq:on_the_other}) yields
\begin{equation}
\frac{\langle\b x,\b y \rangle^2}{\|\b y\|^2}\le \|\b x\|^2.
\label{eq:com_and_done}
\end{equation}
Multiplying both sides of~(\ref{eq:com_and_done}) by $\|\b y\|^2$ and taking the square root, concludes the proof.\\
\hspace*{5.5in}$\Box$

\begin{thm}[Triangle inequality]
Let $\b x$, $\b y$ be two vectors in $\mb{\Bb R}^n$. Then,\index{triangle inequality}
\begin{equation}
\|\b x+\b y\|\le \|\b x\|+\|\b y\|.
\label{eq:triangle_in}
\end{equation}
\label{thm:triangle_in}
\end{thm}
{\bf Proof}\quad Both sides of~(\ref{eq:triangle_in}) are nonnegative. Hence, to prove that~(\ref{eq:triangle_in}) holds it suffices to show that the squares of the both sides satisfy the desired inequality,
\begin{equation}
\left(\b x+\b y \right)^{\top}\left(\b x+\b y \right)\le \left(\|\b x\|+\|\b y\| \right)^2.
\label{eq:triangle_sq}
\end{equation}
Expanding $\left(\b x+\b y \right)^{\top}\left(\b x+\b y \right)$ and applying the Cauchy-Schwarz inequality\index{Cauchy-Schwarz inequality} yields
\begin{eqnarray}
\left(\b x+\b y \right)^{\top}\left(\b x+\b y \right)&=&\|\b x\|^2+2\langle\b x,\b y \rangle +\|\b y\|^2\nonumber\\
&\le& |\b x\|^2+2\|\b x\|\|\b y \| +\|\b y\|^2\nonumber\\
&=& \left(\|\b x\|+\|\b y\| \right)^2,
\label{eq:triangle_sql}
\end{eqnarray}
which completes the proof of the theorem.\\
\hspace*{5.5in}$\Box$

\begin{thm}
Let $\b x$, $\b y$ be two vectors in $\mb{\Bb R}^n$. Then,
\[
\left\arrowvert\|\b x\|-\|\b y \|\right\arrowvert\le \|\b x-\b y\|.
\]
\label{thm:abs_twonmrm}
\end{thm}
{\bf Proof}\quad We have
\[
\|\b x\|=\|\left( \b x-\b y\right)+\b y\|\le \|\b x-\b y\|+\|\b y\|.
\]
Hence,
\begin{equation}
\|\b x\|-\|\b y\| \le \|\b x-\b y\|.
\label{eq:first_abs}
\end{equation}
The above implies that
\begin{equation}
\|\b x-\b y\|=\|\b y-\b x\|\ge \|\b y\|-\|\b x\|=-\left(\|\b x\|-\|\b y\| \right).
\label{eq:sec_abs}
\end{equation}
Combining~(\ref{eq:first_abs}) and~(\ref{eq:sec_abs}) yields
\[
\left|\|\b x\|-\|\b y \|\right|\le \|\b x-\b y\|,
\]
thus completing the proof.\\
\hspace*{5.5in}$\Box$


\section{Matrices and Determinants}
%\section*{Matrices and Determinants}
%\addcontentsline{toc}{section}{Matrices and Determinants}

Let $m$, $n$ be two integers such that $m, n \ge 1$. An array of numbers
\[
\left[\begin{array}{cccc}
a_{11} & a_{12} & \cdots & a_{1n}\\
a_{21} & a_{22} & \cdots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{m1} & a_{m2} & \cdots & a_{mn}
\end{array}\right]
\]
is called a {\em matrix}.\index{matrix!array of numbers} Thus a matrix is a set of scalars subject to two orderings.\index{matrix!a set of scalars subject to two orderings} We say that it is an $m$ by $n$ matrix, or $m\times n$ matrix. This matrix has $m$ rows and $n$ columns. If $m=n$, then we say that it is a square matrix.\index{square matrix} An $m\times n$ matrix $\b A$ whose elements are real numbers will be denoted as $\b A \in \mb{\Bb R}^{m\times n}$. If the elements of the matrix $\b A$ are complex numbers, then we write $\b A \in \mb{\Bb C}^{m\times n}$. We define the zero matrix,\index{zero matrix!denoted $\b O$} denoted $\b O$, to be the matrix such that $a_{ij}=0$ for all $i$, $j$. We define the $n\times n$ identity matrix,\index{identity matrix} denoted $\b I_n$, as the matrix having diagonal components all equal to 1 and all other components all equal to 0.

Given an $m\times n$ matrix $\b A$. The $n\times m$ matrix $\b B$ such that $b_{ji}=a_{ij}$ is called the transpose of $\b A$ and is denoted $\b A^{\top}$. Thus, the transpose of a matrix\index{transpose!of a matrix} is obtained by changing rows into columns and vice versa. A matrix $\b A$ which is equal to its transpose, that is, $\b A=\b A^{\top}$, is called symmetric.

We now define the sum of two matrices.\index{sum!of two matrices} Given two matrices $\b A$ and $\b B$ of the same size. We define $\b A+\b B$ to be the matrix whose elements are $a_{ij}+b_{ij}$, that is, we add matrices of the same size componentwise.

Let $c$ be a number and $\b A$ be a matrix. We define $c\b A$ to be the matrix whose components are $c a_{ij}$. Thus, to obtain $c\b A$, we multiply each component of $\b A$ by $c$.

We now define the product of two matrices.\index{product!of two matrices} Let $\b A$ be an $m\times n$ matrix and $\b B$ be an $n\times s$ matrix. Let $\b a_i^{\top}$ denote the $i$-th row of $\b A$, and $\b b_j$ the $j$-th column of $\b B$, Then, the product of $\b A\b B$ is an $m \times s$ matrix $\b C$ defined as
\begin{equation}
\b C=\b A\b B=\left[\begin{array}{cccc}
\b a_1^{\top}\b b_1 & \b a_1^{\top}\b b_2 & \cdots & \b a_1^{\top}\b b_s\\
\b a_2^{\top}\b b_1 & \b a_2^{\top}\b b_2 & \cdots & \b a_2^{\top}\b b_s\\
\vdots & \vdots & \ddots & \vdots\\
\b a_m^{\top}\b b_1 & \b a_m^{\top}\b b_2 & \cdots & \b a_m^{\top}\b b_s
\end{array}\right].
\label{eq:mat_product}
\end{equation}
It is not always true that $\b A\b B=\b B\b A$, that is, matrix multiplication is not necessarily commutative.\index{matrix multiplication!not necessarily commutative}

Let $\b A$, $\b B$, and $\b C$ be matrices such that $\b A$, $\b B$ can be multiplied, $\b B$, $\b C$ can be multiplied, and $\b B$, $\b C$ can be added. Then,
\begin {equation}
\b A(\b B+\b C)=\b A\b B+\b A\b C.
\label{eq:mat_distribute}
\end{equation}
The above property is called the distributive law.\index{distributive law} If $x$ is a number, then
\begin{equation}
\b A(x\b B)=x(\b A\b B).
\label{eq:mat_scalar}
\end{equation}
Furthermore, matrix multiplication is associative\index{matrix multiplication!is associative} because
\begin{equation}
(\b A\b B)\b C=\b A(\b B\b C).
\label{eq:mat_associate}
\end{equation}

Suppose now that $\b A$, $\b B$ can be multiplied. Then,
\begin{equation}
(\b A\b B)^{\top}=\b B^{\top}\b A^{\top}.
\label{eq:transpose_prod}
\end{equation}
Thus the transpose of a product\index{transpose!of a product of matrices} is the product of transposed matrices in reverse order.

Let $\b A$ be an $n\times n$ matrix. An inverse of $\b A$, if it exists, is an $n\times n$ matrix $\b B$ such that
\begin{equation}
\b A\b B=\b B\b A=\b I_n.
\label{eq:mat_inverse}
\end{equation}
If an inverse exists, then it is unique. A square matrix that is invertible\index{invertible matrix}\index{matrix!invertible} is said to be {\em nonsingular}.\index{nonsingular matrix}\index{matrix!nonsingular} We denote the inverse of $\b A$ by $\b A^{-1}$. Hence, we have
\[
\b A^{-1}\b A=\b A\b A^{-1}=\b I_n.
\]
The transpose of an inverse is the inverse of the transpose,
\begin{equation}
\left( \b A^{-1}\right)^{\top}=\left( \b A^{\top}\right)^{-1},
\label{eq:mat_trans_inverse}
\end{equation}
and we denote it $\b A^{-T}$.

We now present the Sherman-Morrison-Woodbury formula\index{Sherman-Morrison-Woodbury formula} for inverting a special kind of matrices.
\begin{lemma}
\label{lemma:smwformula}
If $\b A$, $\b D$, and $\b D^{-1}+\b C\b A^{-1}\b B$ are invertible, then
\[
\left( \b A+\b B\b D\b C\right)^{-1}=\b A^{-1}-\b A^{-1}\b B\left( \b D^{-1}+\b C\b A^{-1}\b B\right)^{-1}\b C\b A^{-1}.
\]
\end{lemma}
{\bf Proof}\quad We prove the Sherman-Morrison-Woodbury formula by verification. We have
\begin{eqnarray*}
&{}&\left( \b A+\b B\b D\b C\right)\left( \b A^{-1}-\b A^{-1}\b B\left( \b D^{-1}+\b C\b A^{-1}\b B\right)^{-1}\b C\b A^{-1}\right)\\
&{}&\quad= \left( \b A+\b B\b D\b C\right)\b A^{-1}\\
&{}&\qquad -\left( \b A+\b B\b D\b C\right)\b A^{-1}\b B\left(\b D^{-1}+\b C\b A^{-1}\b B \right)^{-1}\b C\b A^{-1}\\
&{}&\quad=\b I+\b B\b D\b C\b A^{-1}\\
&{}&\qquad -\left(\b B+\b B\b D\b C\b A^{-1}\b B \right)\left(\b D^{-1}+\b C\b A^{-1}\b B \right)^{-1}\b C\b A^{-1}\\
&{}&\quad=\b I+\b B\b D\b C\b A^{-1}\\
&{}&\qquad -\b B\b D\left(\b D^{-1}+\b C\b A^{-1}\b B \right)\left(\b D^{-1}+\b C\b A^{-1}\b B \right)^{-1}\b C\b A^{-1}\\
&{}&\quad=\b I+\b B\b D\b C\b A^{-1}-\b B\b D\b C\b A^{-1}\\
&{}&\quad=\b I,
\end{eqnarray*}
as desired.\\
\hspace*{5.5in}$\Box$

In the case when $\b D=\b I$, the Sherman-Morrison-Woodbury formula\index{Sherman-Morrison-Woodbury formula} takes the form
\begin{equation}
\left( \b A+\b B\b C\right)^{-1}=\b A^{-1}-\b A^{-1}\b B\left( \b I+\b C\b A^{-1}\b B\right)^{-1}\b C\b A^{-1}.
\label{eq:specialsmw}
\end{equation}
Formula~(\ref{eq:specialsmw}) is sometimes referred to as the {\em matrix inversion formula}.\index{matrix inversion formula}


A set of nonzero vectors $\{\b q_1,\b q_2,\ldots,\b q_r\}$ is said to be orthogonal if
\[
\langle \b q_i,\b q_j \rangle = 0,\quad\mb{for}\quad i \ne j.
\]
If each vector in an orthogonal set is of unity length, that is, $\|\b q_i\|=1$ for all $i=1,2\ldots,r$, then the set of vectors is also called {\em orthonormal}.\index{orthogonal!set of vectors}\index{orthonormal|see{orthogonal}} A square matrix with orthogonal columns is called an {\em orthogonal matrix}.\index{orthogonal matrix} Sometimes in the literature, an orthogonal matrix is called an {\em unitary matrix}.\index{unitary matrix|see{orthogonal matrix}} If $\b Q\in \mb{\Bb R}^{n \times n}$ is an orthogonal matrix, then
\begin{equation}
\b Q^{\top}\b Q=\b Q\b Q^{\top}=\b I_n.
\label{eq:orthogonal_mat}
\end{equation}

For a square, $n \times n$, matrix $\b A$, its trace,\index{trace!of a square matrix}\index{trace!sum of diagonal elements} denoted $\mb{trace}\b A$, is the sum of its diagonal elements,
\begin{equation}
\mb{trace} \b A=\sum_{i=1}^n a_{ii}.
\label{eq:mat_trace}
\end{equation}
If $\b B$ is also an $n \times n$ matrix, then
\begin{equation}
\mb{trace}(\b A\b B)=\mb{trace}(\b B\b A).
\label{eq:two_mat_trace}
\end{equation}

The {\em determinant\/} of a square matrix\index{determinant!of a square matrix} $\b A$, denoted $\mb{det}\b A$, can be evaluated using the Laplace expansion\index{Laplace expansion!to evaluate determinant} as follows. Let $c_{ij}$ denote the cofactor\index{cofactor!of a matrix} corresponding to the element $a_{ij}$ of an $n\times n$ matrix $\b A$. The cofactor $c_{ij}$ is $(-1)^{i+j}$ times the determinant of the $(n-1)\times (n-1)$ submatrix\index{submatrix} of $\b A$ that is obtained by deleting the $i$-th row and $j$-th column of $\b A$. Then, for any fixed $i$, $1\le i \le n$, we have
\begin{equation}
\det\b A=\sum_{j=1}^n a_{ij}c_{ij}.
\label{eq:mat_det}
\end{equation}
This is the expansion of the determinant along the $i$-th row.\index{expansion of the determinant!along the $i$-th row} In a similar fashion, we can expand the determinant along a column. The determinant has the following properties:\index{determinant!properties of}
\begin{itemize}
\item[{\bf D 1.}] $\det \b A = \det \b A^{\top}$
\item[{\bf D 2.}] Let $\b A$ and $\b B$ be square matrices of the same size, then $\det\left( \b A\b B\right)= \det\b A \det \b B = \det \left(\b B\b A \right)$
\item[{\bf D 3.}] $\det \b O = 0$
\item[{\bf D 4.}] $\det \b I_n = 1$.
\end{itemize}
We now list additional properties of determinants. Let $\b a_i$ denote the $i$-th column of $\b A$. Then, we write
\[
\det \b A=\det\left(\b a_1,\b a_2,\ldots,\b a_n\right).
\]
\begin{itemize}
\item[{\bf D 5.}] Suppose that the $i$-th column $\b a_i$ is written as a sum
\[
\b a_i=\b b+\b c.
\]
Then, we have
\begin{eqnarray*}
\det\left(\b a_1,\ldots,\b a_i,\ldots,\b a_n\right) &=& \det\left(\b a_1,\ldots,\b b+\b c,\ldots,\b a_n\right)\\
&=& \det\left(\b a_1,\ldots,\b b,\ldots,\b a_n\right)+\det\left(\b a_1,\ldots,\b c,\ldots,\b a_n\right).
\end{eqnarray*}
\item[{\bf D 6.}] If $x$ is a number, then
\[
\det\left(\b a_1,\ldots,x\,\b a_i,\ldots,\b a_n\right)=x\det\left(\b a_1,\ldots,\b a_i,\ldots,\b a_n\right).
\]
\item[{\bf D 7.}] If two columns of the matrix are equal, then the determinant is equal to zero.
\item[{\bf D 8.}] If we add a multiple of one column to another, then the value of the determinant does not change. In other words, if $x$ is a number, then
\[
\det\left(\b a_1,\ldots,\b a_i,\ldots,\b a_j,\ldots,\b a_n\right)=\det\left(\b a_1,\ldots,\b a_i+x\b a_j,\ldots,\b a_j,\ldots,\b a_n\right).
\]
\end{itemize}
Properties {\bf D 5}--{\bf D 8} hold also for rows instead of columns because $\det \b A=\det \b A^{\top}$.

Using the cofactors of $\b A$ and its determinant, we can give a formula for $\b A^{-1}$. First, we define the adjugate of $\b A$,\index{adjugate!transpose of the cofactor matrix} denoted $\mb{adj} \b A$ to be the matrix whose $(i,j)$-th entry is the cofactor $c_{ji}$, that is, $\mb{adj} \b A$ is the transpose of the cofactor matrix of $\b A$. Then,
\begin{equation}
\b A^{-1}=\left( \frac{1}{\det \b A}\right)\mb{adj} \b A=\frac{\mb{adj} \b A}{\det \b A}.
\label{eq:inverse_mat_f}
\end{equation}

If $\b A$ is $n \times n$ and $\b v$ is a nonzero $n \times 1$ vector such that for some scalar $\lambda$,
\begin{equation}
\b A\b v=\lambda \b v,
\label{eq:eigen_eigen}
\end{equation}
then $\b v$ is an {\em eigenvector\/}\index{eigenvector} corresponding to the {\em eigenvalue\/}\index{eigenvalue} $\lambda$. In order that $\lambda$ be an eigenvalue of $\b A$, it is necessary and sufficient for the matrix $\lambda \b I_n-\b A$ to be singular, that is, $\det\left(\lambda \b I_n - \b A \right)=0$. This leads to an $n$-th order polynomial equation in $\lambda$ of the form
\begin{equation}
\det\left(\lambda \b I_n - \b A \right)=\lambda^n+ a_{n-1}\lambda^{n-1}+\cdots+a_1\lambda+a_0=0.
\label{eq:character_eq}
\end{equation}
This equation, called the {\em characteristic polynomial equation\/}\index{characteristic polynomial equation}, must have $n$, possibly nondistinct, complex roots which are the eigenvalues of $\b A$. The {\em spectral radius\/} of $\b A$, denoted $\rho(\b A)$ is defined as
\[
\rho(\b A)=\max_{1\le i\le n}|\lambda_i(\b A)|,
\]
where $\lambda_i(\b A)$ denotes the $i$-th eigenvalue of $\b A$.

Any $m\times n$ matrix $\b A$ can be represented as
\begin{equation}
\b A=\b U\left[\begin{array}{ll}
\b S, & \b O
\end{array}\right]\b V^{\top},\quad\mb{if}\quad m\le n,
\label{eq:svddecompose}
\end{equation}
or
\begin{equation}
\b A=\b U\left[\begin{array}{l}
\b S\\
\b O
\end{array}\right]\b V^{\top},\quad\mb{if}\quad m > n,
\label{eq:svddectwo}
\end{equation}
where $\b U$ is an $m\times m$ orthogonal matrix, $\b V$ is an $n\times n$ orthogonal matrix,\index{orthogonal matrix} and $\b S$ is a diagonal matrix\index{diagonal matrix} of the form
\[
\b S=\mb{diag}(\sigma_1,\sigma_2,\ldots,\sigma_p),\quad\mb{where}\quad p=\min(m,n)\quad\mb{and} \quad\sigma_i\ge 0,\quad i=1,2,\ldots,p.
\]
The nonnegative numbers $\{\sigma_i\}$ are called the {\em singular values\/}\index{singular values} of $\b A$, and~(\ref{eq:svddecompose}), or~(\ref{eq:svddectwo}), is called the {\em singular value decomposition\/}~(SVD)\index{singular value decomposition (SVD)}\index{SVD|see{singular value decomposition}} of $\b A$. Following the convention, we write
\[
\sigma_1\ge \sigma_2\ge \cdots\ge \sigma_p,
\]
so that $\sigma_1=\sigma_1(\b A)$ denotes the largest singular value of $\b A$. The singular values of $\b A$ are the square roots of the eigenvalues of $\b A\b A^{\top}$ if $m\le n$ or of $\b A^{\top}\b A$ if $m > n$. If $\b A$ is symmetric, its singular values are the absolute values of its eigenvalues.

\section{Quadratic Forms}
%\section*{Quadratic Forms}
%\addcontentsline{toc}{section}{Quadratic Forms}
\label{sec:quadratform}

A real {\em quadratic form\/}\index{quadratic form!a real-valued function of $n$ variables} is a special type of a real-valued function of $n$ variables. It is the product $\b x^{\top}\b Q\b x$, where $\b Q$ is a specified $n\times n$ matrix with real coefficients and $\b x$ is an $n\times 1$ real, column, vector. Without loss of generality, the matrix $\b Q$ can be taken to be symmetric, that is, $\b Q=\b Q^{\top}$, for if $\b Q$ is not symmetric, we can always replace it with a symmetric matrix\index{symmetric matrix} without changing the quadratic form values. Indeed, because $z=\b x^{\top}\b Q\b x$ is a scalar, hence $z^{\top}=z$, and we have
\[
\left( \b x^{\top}\b Q\b x\right)^{\top}=\b x^{\top}\b Q^{\top}\b x=\b x^{\top}\b Q\b x.
\]
Therefore, we can write
\[
\b x^{\top}\b Q\b x=\b x^{\top}\left( \frac{1}{2}\b Q+\frac{1}{2}\b Q^{\top}\right)\b x=\b x^{\top}\left(\frac{\b Q+\b Q^{\top}}{2} \right)\b x,
\]
where $\frac{1}{2}\left(\b Q+\b Q^{\top} \right)$ is a symmetric matrix. Thus, the quadratic form values are unchanged if $\b Q$ is replaced with the symmetric matrix $\frac{1}{2}\left(\b Q+\b Q^{\top} \right)$. From now on, in our study of quadratic forms, we assume that $\b Q$ is symmetric.

A quadratic form $\b x^{\top}\b Q\b x$, or equivalently, the matrix $\b Q$, is called {\em positive semi-definite\/}\index{positive semi-definite} if $\b x^{\top}\b Q\b x \ge 0$ for all $\b x$. It is {\em positive definite\/}\index{positive definite} if $\b x^{\top}\b Q\b x > 0$ for all $\b x\ne \b 0$. If $\b Q$ is positive semi-definite, then we write $\b Q\ge 0$, if it is positive definite, we write $\b Q>0$. We write $\b Q_1 \ge \b Q_2$ to mean that $\b Q_1-\b Q_2 \ge 0$. We say that $\b Q$ is {\em negative semi-definite\/}\index{negative semi-definite} if $\b x^{\top}\b Q\b x \le 0$ for all $\b x$, it is {\em negative definite\/}\index{negative definite} if $\b x^{\top}\b Q\b x < 0$ for all $\b x \ne \b 0$. Note that $\b Q \le 0$ if and only if $-\b Q \ge 0$.

We next present tests for definiteness properties of symmetric matrices. We state these tests in terms of {\em principal minors\/}\index{principal minors} of a given real, symmetric, $n \times n$ matrix $\b Q$ with elements $q_{ij}$. We will also give tests for definiteness in terms of eigenvalues of $\b Q$. The principal minors of $\b Q$ are $\det \b Q$ itself and the determinants of submatrices of $\b Q$ obtained by removing successively an $i$-th row and $i$-th column. Specifically, for $p=1,2,\ldots,n$, the principal minors are
\[
\Delta_p\left(\begin{array}{cccc}
i_1, & i_2, &\ldots, & i_p\\
i_1, & i_2, &\ldots, & i_p
\end{array} \right)=\det\left[\begin{array}{cccc}
q_{i_1 i_1}&q_{i_1 i_2}&\cdots&q_{i_1 i_p}\\
q_{i_2 i_1}&q_{i_2 i_2}&\cdots&q_{i_2 i_p}\\
\vdots& \vdots & \ddots & \vdots\\
q_{i_p i_1}&q_{i_p i_2}&\cdots&q_{i_p i_p}
\end{array}\right]\quad 1 \le i_1 < i_2 < \cdots < i_p\le n.
\]
The above are called the principal minors of order $p$.\index{principal minors!of order $p$}

In the following, we use the fact that if $\b Q=\b Q^{\top}$, then its eigenvalues are all real.
\begin{thm}
\label{thm:testforpsd}
The following are equivalent:
\begin{itemize}
\item[(i)] The symmetric matrix $\b Q$ is positive semi-definite.
\item[(ii)] Principal minors of $\b Q$ are nonnegative, that is, for $p=1,2,\ldots,n$,
\[
\Delta_p\left(\begin{array}{cccc}
i_1, & i_2, &\ldots, & i_p\\
i_1, & i_2, &\ldots, & i_p
\end{array} \right) \ge 0, \quad 1 \le i_1 < i_2 < \cdots < i_p\le n.
\]
\item[(iii)] Eigenvalues of $\b Q$ are nonnegative,
\[
\lambda_i(\b Q) \ge 0,\quad i=1,2,\ldots,n.
\]
\end{itemize}
\end{thm}

We give two tests for $\b Q=\b Q^{\top}$ to be positive definite; one in terms of its leading principal minors, and the other in terms of its eigenvalues. The {\em leading principal minors\/}\index{leading principal minors} of $\b Q$ are
\begin{eqnarray*}
&{}&\Delta_1\left(\begin{array}{c}
1\\
1
\end{array} \right)=q_{11},\quad \Delta_2\left(\begin{array}{cc}
1, & 2\\
1, & 2
\end{array} \right)=\det\left[\begin{array}{cc}
q_{11} & q_{12}\\
q_{21} & q_{22}
\end{array}\right],\\
&{}&\Delta_3\left(\begin{array}{ccc}
1,&2,&3\\
1,&2,&3
\end{array} \right)=\det\left[\begin{array}{ccc}
q_{11} & q_{12}& q_{13}\\
q_{21} & q_{22}& q_{23}\\
q_{31} & q_{32}& q_{33}
\end{array}\right],\ldots, \Delta_n\left(\begin{array}{cccc}
1, & 2, &\ldots, & n\\
1, & 2, &\ldots, & n
\end{array} \right)=\det \b Q.
\end{eqnarray*}
\begin{thm}
\label{thm:psosdeftests}
The following are equivalent:
\begin{itemize}
\item[(i)] The symmetric matrix $\b Q$ is positive definite.
\item[(ii)] Leading principal minors of $\b Q$ are positive, that is,
\[
\Delta_p\left(\begin{array}{cccc}
1, & 2, &\ldots, & p\\
1, & 2, &\ldots, & p
\end{array} \right) > 0, \quad p=1,2,\ldots,n.
\]
\item[(iii)] Eigenvalues of $\b Q$ are positive,
\[
\lambda_i(\b Q) > 0,\quad i=1,2,\ldots,n.
\]
\end{itemize}
\end{thm}

If a given matrix $\b Q\in \mb{\Bb R}^{n\times n}$ is symmetric, then its eigenvalues are all real and there exists an orthogonal matrix\index{orthogonal matrix} $\b U$ such that
\begin{equation}
\b U^{\top}\b Q\b U=\left[\begin{array}{cccc}
\lambda_1 & 0 & \cdots &0\\
0 & \lambda_2 &\cdots & 0\\
\vdots&{}&\ddots& \vdots\\
0 & 0& \cdots& \lambda_n
\end{array}\right]=\b{\Lambda}.
\label{eq:diaofsymauutr}
\end{equation}
Recall that $\b U$ is orthogonal if $\b U^{\top}\b U=\b I_n$. Using the above, we show that a symmetric positive semi-definite matrix $\b Q$ has a positive semi-definite symmetric square root,\index{positive semi-definite!symmetric square root of matrix}\index{square root of matrix} denoted $\b Q^{1/2}$ or $\sqrt{\b Q}$, that satisfies
\begin{equation}
\b Q^{1/2}\b Q^{1/2}=\b Q.
\label{eq:squmatrpro}
\end{equation}
Indeed, it follows from Theorem~\ref{thm:testforpsd} that if $\b Q=\b Q^{\top} \ge 0$ then its eigenvalues are all nonnegative. Hence,
\begin{equation}
\b{\Lambda}^{1/2}=\left[\begin{array}{cccc}
\lambda_1^{1/2} & 0 & \cdots &0\\
0 & \lambda_2^{1/2} &\cdots & 0\\
\vdots&{}&\ddots& \vdots\\
0 & 0& \cdots& \lambda_n^{1/2}
\end{array}\right]
\label{eq:sqroooflam}
\end{equation}
is well defined. Using the fact that $\b U^{\top}\b U=\b I_n$, we define
\begin{equation}
\b Q^{1/2}=\b U\b{\Lambda}^{1/2}\b U^{\top},
\label{eq:deofsqroqpsd}
\end{equation}
which has the desired properties.

If $\b Q=\b Q^{\top}$ is positive semi-definite, and not positive definite, then some of its eigenvalues are equal to zero. Suppose that $\b Q$ has $r$ nonzero eigenvalues. Then, there is an orthogonal matrix, say $\b U$, such that
\begin{equation}
\b U^{\top}\b Q\b U=\left[\begin{array}{ccccccc}
\lambda_1 & 0 & \cdots&0&0 &\cdots&0\\
0 & \lambda_2 &\cdots&0&0 &\cdots& 0\\
\vdots&{}&\ddots& \vdots&{}&\ddots&\vdots\\
0 & 0& \cdots& \lambda_r&0&\cdots&0\\
0&0&\cdots&0&0&\cdots&0\\
\vdots&{}&{}&{}&{}&\ddots&\vdots\\
0&0&\cdots&0&0&\cdots&0
\end{array}\right].
\label{eq:diapsdmauum}
\end{equation}
Let $\b V\in \mb{\Bb R}^{n\times r}$ be a matrix that consists of the first $r$ columns of the matrix $\b U$, and let
\begin{equation}
\b C=\left[\begin{array}{cccc}
\lambda_1^{1/2} & 0 & \cdots &0\\
0 & \lambda_2^{1/2} &\cdots & 0\\
\vdots&{}&\ddots& \vdots\\
0 & 0& \cdots& \lambda_r^{1/2}
\end{array}\right]
\b V^{\top}.
\label{eq:srtmofpsd}
\end{equation}
Note that the matrix $\b C$ is of full rank. We have
\begin{equation}
\b Q=\b C^{\top}\b C.
\label{eq:furafaofq}
\end{equation}
We refer to~(\ref{eq:furafaofq}) as a full rank factorization\index{full rank factorization} of $\b Q$ because $\b C$ is of full rank. We can generalize the above, using~(\ref{eq:svddecompose}), to obtain a full rank factorization of a non-square matrix. Specifically, given an $m\times n$ matrix $\b A$ of rank $r$, we can represent it as
\[
\b A=\b B\b C,
\]
where $\b B$ is an $m\times r$ matrix and $\b C$ is a $r\times n$ matrix such that
\[
\mb{rank}(\b B)=\mb{rank}(\b C)=\mb{rank}(\b A)=r.
\]

\section{The Kronecker Product}
%\section*{The Kronecker Product}
%\addcontentsline{toc}{section}{The Kronecker Product}
\label{sec:kroneckerpro}

Let $\b A$ be an $m \times n$ and $\b B$ be a $p \times q$ matrices. The {\em Kronecker product\/}\index{Kronecker product} of $\b A$ and $\b B$, denoted $\b A \otimes \b B$, is an $mp \times nq$ matrix defined as
\begin{equation}
\b A \otimes \b B=\left[\begin{array}{cccc}
a_{11}\b B & a_{12} \b B&\cdots& a_{1n}\b B\\
a_{21}\b B & a_{22} \b B&\cdots& a_{2n}\b B\\
\vdots& \vdots & \ddots & \vdots\\
a_{m1}\b B & a_{m2} \b B&\cdots& a_{mn}\b B
\end{array}\right],
\label{eq:kronecker_def}
\end{equation}
where the symbol $\otimes$ reads ``otimes.'' Thus, the matrix $\b A \otimes \b B$ consists of $mn$ blocks. Using the definition of the Kronecker product, we can verify the following two properties:
\begin{eqnarray}
\left(\b A \otimes \b B\right)\left(\b C \otimes \b D \right) &=& \b A \b C \otimes \b B \b D,\\
\left(\b A \otimes \b B\right)^{\top} &=& \b A^{\top} \otimes \b B^{\top}.
\end{eqnarray}

Let
\[
\b X=\left[\begin{array}{cccc}
\b x_1,&\b x_2,&\ldots,&\b x_m
\end{array}\right]
\]
be a $n \times m$ matrix, where $\b x_i$, $i=1,2,\ldots,m$ are the columns of $\b X$. Each $\b x_i$ consists of $n$ elements. Then, the {\em vectorization operator\/}\index{vectorization operator} or {\em stacking operator\/}\index{stacking operator} is defined as
\begin{eqnarray*}
\mb{vec}(\b X) &=& \left[\begin{array}{cccc}
\b x^{\top}_1,&\b x^{\top}_2,&\ldots,&\b x^{\top}_m
\end{array}\right]^{\top}\\
&=&\left[\begin{array}{ccccccccccccc}
x_{11}&x_{21}&\cdots&x_{n1}&x_{12}&x_{22}&\cdots&x_{n2}&\cdots&x_{1m}&x_{2m}&\cdots &x_{nm}
\end{array}\right]^{\top}
\end{eqnarray*}
is the column $nm$-vector formed from the columns of $\b X$ taken in order. Let now $\b A$ be an $n\times n$, and $\b C$ and $\b X$ be $n\times m$ matrices. Then, the matrix equation
\begin{equation}
\b A \b X = \b C
\label{eq:axc_eq}
\end{equation}
can be written as
\begin{equation}
\left(\b I_m \otimes \b A \right) \mb{vec}(\b X)=\mb{vec}(\b C).
\end{equation}
Let $\b B$ be an $m \times m$ matrix, then the matrix equation
\begin{equation}
\b X \b B =\b C
\label{eq:xbc_eq}
\end{equation}
can be written as
\begin{equation}
\left(\b B^{\top} \otimes \b I_n \right) \mb{vec}(\b X)=\mb{vec}(\b C).
\end{equation}
Using the above two facts, we can verify that the Sylvester matrix equation,\index{Sylvester matrix equation}
\begin{equation}
\b A \b X + \b X \b B = \b C,
\label{eq:abc_eq}
\end{equation}
where $\b A$ is $n \times n$, $\b B$ is $m\times m$, and $\b C$ is $n\times m$, can be written as
\begin{equation}
\left( \b I_m \otimes \b A + \b B^{\top} \otimes \b I_n \right) \mb{vec}(\b X)=\mb{vec}(\b C).
\label{eq:abc_equieq}
\end{equation}

Let $\lambda_i$, $\b v_i$ be the eigenvalues and eigenvectors, respectively, of $\b A$, and $\mu_j$ and $\b w_j$ the eigenvalues and eigenvectors of $m\times m$ matrix $\b B$. Then,
\begin{eqnarray}
\left( \b A \otimes \b B \right) \left(\b v_i \otimes \b w_j \right) &=& \b A \b v_i \otimes \b B \b w_j\nonumber\\
&=& \lambda _i \b v_i \otimes \mu _j \b w_j\nonumber\\
&=& \lambda _i \mu _j \left( \b v_i \otimes \b w_j \right).
\end{eqnarray}
Thus, the eigenvalues of $\b A \otimes \b B$ are $\lambda _i \mu_j$, and their respective eigenvectors are $\b v_i \otimes \b w_j$ for $i=1,2,\ldots ,n$, $j=1,2,\ldots ,m$.

We use the above result to study the Sylvester equation,\index{Sylvester equation|see{Sylvester matrix equation}} given by~(\ref{eq:abc_eq}), that we represent as
\begin{equation}
\b M \,\mb{vec}(\b X)=\mb{vec}(\b C),
\label{eq:abc_asd}
\end{equation}
where
\begin{equation}
\b M = \b I_m \otimes \b A + \b B^{\top} \otimes \b I_n.
\end{equation}
The solution to~(\ref{eq:abc_asd}) is unique if, and only if, the $mn \times mn$ matrix $\b M$ is nonsingular. To find the condition for this to hold, consider the following matrix
\begin{equation}
\left(\b I_m + \varepsilon \b B^{\top} \right) \otimes \left( \b I_n + \varepsilon \b A \right)=\b I_m \otimes \b I_n + \varepsilon \b M + \varepsilon^2 \b B^{\top} \otimes \b A
\label{eq:long_matrix}
\end{equation}
whose eigenvalues are
\begin{equation}
\left(1+\varepsilon \mu_j\right) \left(1+\varepsilon \lambda_i \right) = 1+\varepsilon \left( \mu_j+\lambda_i \right) + \varepsilon^2 \mu_j \lambda_i
\label{eq:eigoflongm}
\end{equation}
because for a square matrix $\b Q$,
\[
\lambda_i \left(\b I_n + \varepsilon \b Q \right)=1+\varepsilon \lambda_i \left(\b Q \right).
\]
Comparing terms in $\varepsilon$ in~(\ref{eq:long_matrix}) and~(\ref{eq:eigoflongm}), we conclude that the eigenvalues of $\b M$ are $\lambda_i+\mu_j$, $i=1,2,\ldots ,n$, $j=1,2,\ldots ,m$. Hence, $\b M$ is nonsingular if and only if
\begin{equation}
\lambda_i+\mu_j \ne 0.
\end{equation}
The above is the necessary and sufficient condition for the solution $\b X$ of the matrix equation $\b A \b X + \b X \b B = \b C$ to be unique.

Another useful identity involving the Kronecker product\index{Kronecker product} is
\begin{equation}
\mb{vec}(\b A\b B\b C)=\left(\b C^{\top}\otimes \b A \right)\mb{vec}(\b B)
\label{eq:stack_three}
\end{equation}

For more information on the subject of the Kronecker product, we refer the reader to Brewer~\cite{brewer78}.

\section{Upper and Lower Bounds}
%\section*{Upper and Lower Bounds}
%\addcontentsline{toc}{section}{Upper and Lower Bounds}

Consider a set ${\cal S}$ of real numbers. A number $M$ is called an {\em upper bound\/}\index{upper bound} of the set ${\cal S}$ if
\[
x\le M\quad \mb{for all} \quad x\in {\cal S}.
\]
A set of real numbers that has an upper bound is said to be {\em bounded above}.\index{bounded above!a set of real numbers}

{\bf The Least Upper Bound Axiom}\index{Least Upper Bound Axiom} Every nonempty set $\cal S$ of real numbers that has an upper bound has a {\em least upper bound\/},\index{least upper bound!supremum} also called {\em supremum\/},\index{supremum!least upper bound} and is denoted
\[
\sup\{x:x\in {\cal S}\}.
\]
{\bf Examples}\\
{\bf 1.} \[
\sup\left\{\frac{1}{2},\frac{2}{3},\ldots,\frac{n}{n+1},\ldots \right\}=1;
\]
{\bf 2.} \[
\sup\left\{-\frac{1}{2},-\frac{1}{8},-\frac{1}{27},\ldots,-\frac{1}{n^3},\ldots\right\}=0;
\]
{\bf 3.} \[
\sup\left\{x:x^2<3\right\} = \sup\left\{x:-\sqrt{3}<x<\sqrt{3}\right\}=\sqrt{3}.
\]
\begin{thm}
\label{thm_lub}
If $M=\sup\{x:x\in {\cal S}\}$ and $\varepsilon >0$, then there is at least one number $x$ in $\cal S$ such that
\[
M-\varepsilon <x \le M.
\]
\end{thm}
{\bf Proof}\quad The condition $x\le M$ is satisfied by all numbers $x$ in $\cal S$ by virtue of the Least Upper Bound Axiom.\index{Least Upper Bound Axiom} We have to show that for an $\varepsilon >0$ there is a number $x\in{\cal S}$ such that
\[
M-\varepsilon<x.
\]
We prove the statement by contradiction.\index{proof!by contradiction} We suppose that there is no such number in $\cal S$. Then,
\[
x\le M-\varepsilon \quad \mb{for all} \quad x\in {\cal S}
\]
and hence $M-\varepsilon$ would be an upper bound of $\cal S$ that is less than $M$ which is the least upper bound. This contradicts the assumption, and thus the proof is complete.\\
\hspace*{5.5in}$\Box$

To illustrate the above theorem, we consider the following set of real numbers:
\[
{\cal S}=\left\{\frac{1}{2},\frac{2}{3},\frac{3}{4},\ldots,\frac{n}{n+1},\ldots\right\}.
\]
Note that
\[
\sup\{x:x\in{\cal S}\}=1.
\]
Let $\varepsilon=0.1$. Then, for example, the element of the set ${\cal S}$ that is equal to $99/100$ satisfies
\[
1-\varepsilon<\frac{99}{100}\le 1.
\]

A number $m$ is called a {\em lower bound}\index{lower bound} of $\cal S$ if
\[
m\le x\quad \mb{for all}\quad x\in {\cal S}.
\]
Sets that have lower bounds are said to be {\em bounded below}.\index{lower bounded}
\begin{thm}
\label{thm_glb}
Every nonempty set of real numbers that has a lower bound has a {\em greatest lower bound\/},\index{greatest lower bound!infimum} also called {\em infimum\/},\index{infimum!greatest lower bound} denoted as
\[
\inf\{x:x\in{\cal S}\}.
\]
\end{thm}
{\bf Proof}\quad By assumption $\cal S$ is nonempty and has a lower bound that we call $s$. Thus
\[
s\le x \quad \mb{for all} \quad x\in {\cal S}.
\]
Hence
\[
-x\le -s \quad \mb{for all} \quad x\in {\cal S},
\]
that is, the set $\{-x:x\in{\cal S}\}$ has an upper bound $-s$. From the Least Upper Bound Axiom,\index{Least Upper Bound Axiom} we conclude that the set $\{-x:x\in{\cal S}\}$ has a least upper bound, supremum. We call it $-s_0$. Because
\[
-x\le -s_0\quad \mb{for all} \quad x\in {\cal S},
\]
we have
\[
s_0\le x \quad \mb{for all} \quad x\in {\cal S},
\]
and thus $s_0$ is a lower bound for $\cal S$. We now prove, by contradiction, that $s_0$ is the greatest lower bound, infimum, of the set $\cal S$. Indeed, if there was a number $\tilde{x}$ satisfying
\[
s_0 < \tilde{x} \le x \quad \mb{for all} \quad x\in {\cal S},
\]
then we would have
\[
-x\le -\tilde{x}<-s_0 \quad \mb{for all} \quad x\in {\cal S},
\]
which contradicts the fact that $-s_0$ is the supremum of $\{-x:x\in {\cal S}\}$.\\
\hspace*{5.5in}$\Box$

Using arguments similar to those we used in the proof of Theorem~\ref{thm_glb}, we can prove the following theorem:
\begin{thm}
\label{thm_glb2}
If $m=\inf\{x:x\in{\cal S}\}$ and $\varepsilon >0$, then there is at least one number $x$ in $\cal S$ such that
\[
m\le x <m+\varepsilon.
\]
\end{thm}

\section{Sequences}
%\section*{Sequences}
%\addcontentsline{toc}{section}{Sequences}

A {\em sequence of real numbers}\index{sequence!of real numbers} is a function whose domain is the set of natural numbers $1,2,\ldots,n,\ldots$ and whose range is contained in $\mb{\Bb R}$. Thus, a sequence of real numbers can be viewed as a set of points $(1,a_1),(2,a_2),\ldots,(n,a_n),\ldots$. We denote a sequence of real numbers
\[
a_1,a_2,\ldots,a_n,\ldots
\]
as $\{a_n\}$.

A sequence $\{a_n\}$ is increasing if $a_1<a_2<\cdots<a_n\cdots$. In general, a sequence is increasing if\index{sequence!increasing}\index{increasing!sequence} $a_n<a_{n+1}$. If $a_n\le a_{n+1}$, then we say that the sequence is nondecreasing.\index{sequence!nondecreasing}\index{nondecreasing!sequence} Similarly, we can define decreasing\index{sequence!decreasing}\index{decreasing!sequence} and nonincreasing sequences.\index{sequence!nonincreasing}\index{nonincreasing!sequence} Nonincreasing or nondecreasing sequences are called monotone sequences.\index{sequence!monotone}\index{monotone!sequence}

A number $g$ is called the limit of the infinite sequence\index{limit!of infinite sequence}\index{sequence!limit of} $a_1,a_2,\ldots,a_n,\ldots$ if for any positive $\varepsilon$ there is a number $k=k(\varepsilon)$ such that for all $n>k$
\[
|a_n-g|<\varepsilon,
\]
that is, $a_n$ lies between $g-\varepsilon$ and $g+\varepsilon$ for all $n>k$. In other words, for any $\varepsilon>0$ we have $|a_n-g|<\varepsilon$ for sufficiently large $n$'s, see Figure~\ref{fig:limit}, and we write
\[
g=\lim_{n\to \infty}a_n,
\]
or
\[
a_n \to g.
\]
\begin{figure}
\centering
\includegraphics[scale=0.5]{limit.eps}
%\vspace{3in}
%\hskip1in\special{bmp:c:/mybook/limit.bmp x=4in y=3in}
\caption{An illustration of the notion of the limit of a sequence.}
\label{fig:limit}
\end{figure}
A sequence that has a limit is called a {\em convergent} sequence.\index{convergent sequence!sequence has a limit} A sequence that has no limit is called {\em divergent}.\index{divergent sequence!sequence has no limit}

The notion of the sequence can be extended to sequences with elements in $\mb{\Bb R}^p$. Specifically, a sequence in $\mb{\Bb R}^p$ is a function whose domain is the set of natural numbers $1,2,\ldots,n,\ldots$ and whose range is contained in $\mb{\Bb R}^p$.

Suppose that $\b a_1,\b a_2,\ldots,\b a_n,\ldots$, denoted $\{\b a_n\}$, is a sequence in $\mb{\Bb R}^p$. Then, $\b g \in \mb{\Bb R}^p$ is called the limit of this sequence if for each $\varepsilon >0$ there exists a natural number $k=k(\varepsilon)$ such that for all $n > k$
\[
\left\Arrowvert\b a_n - \b g\right\Arrowvert < \varepsilon,
\]
and we write
\[
\b g=\lim_{n \to \infty} \b a_n,
\]
or
\[
\b a_n \to \b g.
\]
\begin{thm}
If a limit of a sequence in $\mb{\Bb R}^p$ exists, then it is unique.
\end{thm}
{\bf Proof}\quad We prove this theorem by contradiction.\index{proof!by contradiction} Let us assume that a sequence $\{\b a_n\}$ has two different limits, say $\b g_1$ and $\b g_2$. Then, we have
\[
\left\Arrowvert\b g_1 - \b g_2\right\Arrowvert >0.
\]
Let
\[
\varepsilon=\frac{1}{2}\left\Arrowvert\b g_1 - \b g_2\right\Arrowvert.
\]
From the definition of a limit, there exist $k_1=k_1(\varepsilon)$ and $k_2=k_2(\varepsilon)$ such that for $n>k_1$ we have $\left\Arrowvert\b a_n - \b g_1\right\Arrowvert < \varepsilon$, and for $n>k_2$ we have $\left\Arrowvert\b a_n - \b g_2\right\Arrowvert < \varepsilon$. Let $m=\max\left( k_1,k_2\right)$. Then, if $n>m$, we have $\left\Arrowvert\b a_n - \b g_1\right\Arrowvert < \varepsilon$ and $\left\Arrowvert\b a_n - \b g_2\right\Arrowvert < \varepsilon$. Adding $\left\Arrowvert\b a_n - \b g_1\right\Arrowvert < \varepsilon$ and $\left\Arrowvert\b a_n - \b g_2\right\Arrowvert < \varepsilon$ yields
\begin{equation}
\left\Arrowvert\b a_n - \b g_1\right\Arrowvert + \left\Arrowvert\b a_n - \b g_2\right\Arrowvert < 2\varepsilon.
\label{eq:geonetep}
\end{equation}
It follows from the triangle inequality\index{triangle inequality} that
\[
\|\b a-\b b\| \le \|\b a\| + \|\b b\|.
\]
Using the above inequality, we obtain
\begin{eqnarray}
\left\Arrowvert-\b g_1+ \b g_2\right\Arrowvert &= &\left\Arrowvert\b a_n - \b g_1 -\b a_n +\b g_2\right\Arrowvert\nonumber\\
&=& \left\Arrowvert\left(\b a_n - \b g_1\right) -\left(\b a_n -\b g_2\right)\right\Arrowvert\nonumber\\
&\le& \left\Arrowvert\b a_n - \b g_1\right\Arrowvert +\left\Arrowvert\b a_n - \b g_2\right\Arrowvert.
\label{eq:migopgt}
\end{eqnarray}
Applying~(\ref{eq:geonetep}) to~(\ref{eq:migopgt}) yields
\[
\left\Arrowvert -\b g_1 + \b g_2\right\Arrowvert = \left\Arrowvert\b g_1 - \b g_2\right\Arrowvert < 2\varepsilon.
\]
However, the above contradicts the assumption that $\left\Arrowvert\b g_1 - \b g_2\right\Arrowvert= 2\varepsilon$, which completes the proof.\\
\hspace*{5.5in} $\Box$

A sequence in $\mb{\Bb R}^p$ is bounded\index{bounded!sequence}\index{sequence!bounded} if there exists a number $M \ge 0$ such that $\left\Arrowvert \b a_n \right\Arrowvert \le M$ for all $n=1,2,\ldots$. The set of all bounded sequences is sometimes denoted $l_{\infty}$.\index{set of all bounded sequences!denoted $l_{\infty}$}
\begin{thm}
Every convergent sequence is bounded.
\end{thm}
{\bf Proof}\quad Let
\[
\b g=\lim_{n \to \infty} \b a_n.
\]
Choose $\varepsilon =1$. Then, there exists a natural number $k=k(\varepsilon)$ such that
\[
\left\Arrowvert \b a_n - \b g\right\Arrowvert < 1 \quad \mb{for all}\quad n>k.
\]
By Theorem~\ref{thm:abs_twonmrm},
\[
\|\b a\|-\|\b b\| \le \|\b a-\b b\|.
\]
Using the above inequality, we get
\[
\left\Arrowvert \b a_n\right\Arrowvert - \left\Arrowvert \b g \right\Arrowvert \le \left\Arrowvert \b a_n - \b g \right\Arrowvert < 1 \quad \mb{for all}\quad n>k.
\]
Therefore,
\[
\left\Arrowvert \b a_n \right\Arrowvert < \left\Arrowvert \b g \right\Arrowvert + 1 \quad \mb{for all}\quad n>k.
\]
Let
\[
M=\max\left( \left\Arrowvert \b a_1\right\Arrowvert, \left\Arrowvert \b a_2\right\Arrowvert, \ldots,\left\Arrowvert \b a_k\right\Arrowvert, \left\Arrowvert \b g\right\Arrowvert+1\right),
\]
then we have
\[
M \ge \left\Arrowvert\b a_n \right\Arrowvert\quad\mb{for all}\quad n,
\]
which means that a convergent sequence is bounded,\index{convergent sequence!is bounded} and the proof is complete.\\
\hspace*{5.5in}$\Box$

Suppose we are given a sequence $\b a_1, \b a_2,\ldots$ in $\mb{\Bb R}^p$, and an increasing sequence of positive natural numbers
\[
m_1,m_2,\ldots, m_n,\ldots.
\]
The sequence
\[
\b a_{m_1},\b a_{m_2},\ldots,\b a_{m_n},\ldots
\]
is called a {\em subsequence} of the sequence\index{subsequence!of the sequence} $\b a_1, \b a_2,\ldots$ in $\mb{\Bb R}^p$.

We have
\[
m_n \ge n.
\]
Indeed, this is obvious for $n=1$, that is, $m_1\ge 1$ because $m_1$ is a positive integer. We now apply the principle of induction.\index{principle of induction} We assume that $m_n \ge n$ for a given $n$. Then, we have
\[
m_{n+1} > m_n \ge n.
\]
Hence,
\[
m_{n+1} \ge n+1.
\]
Thus, indeed $m_n \ge n$ for all $n$.

We can say that a subsequence is obtained from the given sequence by neglecting a number of elements in the sequence. We denote a subsequence $\b a_{m_1},\b a_{m_2},\ldots,\b a_{m_n},\ldots$ as
\[
\left\{ \b a_{m_n}\right\}.
\]
\begin{thm}
A subsequence of a convergent sequence\index{subsequence!of a convergent sequence} in $\mb{\Bb R}^p$ is convergent to the same limit, that is, if
\[
\lim_{n\to \infty} \b a_n=\b g,
\]
and if
\[
m_1 < m_2<\ldots<m_n<\ldots,
\]
then
\[
\lim_{n \to \infty}\b a_{m_n} =\b g.
\]
\end{thm}
{\bf Proof} \quad Let $\varepsilon > 0$ be given. Then, there exists a natural number $k=k(\varepsilon)$ such that $\left\Arrowvert \b a_n - \b g\right\Arrowvert< \varepsilon$ for any $n>k$. From the fact that $m_n \ge n$, it follows that
\[
m_n>n>k,
\]
and thus
\[
\left\Arrowvert \b a_{m_n} - \b g\right\Arrowvert< \varepsilon
\]
for any $m_n>n>k$, which means that
\[
\lim_{n \to \infty} \b a_{m_n}=\b g.
\]
The proof is complete.\\
\hspace*{5.5in} $\Box$

We now state, without a proof, an important result due to Bolzano and Weierstrass.\index{Bolzano-Weierstrass theorem}
\begin{thm}[Bolzano-Weierstrass]
\label{thm:bolzweierstr}
Every bounded sequence in $\mb{\Bb R}^p$ contains a convergent subsequence.
\end{thm}

\begin{thm}[Cauchy]
A sequence $\left\{ \b a_n\right\}$ in $\mb{\Bb R}^p$ is convergent if, and only if for every $\varepsilon >0$ there exists an $r=r(\varepsilon)$ such that\index{Cauchy theorem}
\[
\left\Arrowvert \b a_{n} - \b a_r\right\Arrowvert< \varepsilon
\]
holds for all $n>r$.
\end{thm}
{\bf Proof}\quad $\left( \Rightarrow \right)$ Let
\[
\lim_{n \to \infty}\b a_n = \b g,
\]
and let $\varepsilon > 0$ be given. Then, for some $l=l(\varepsilon)$, we have
\[
\left\Arrowvert \b a_{n} - \b g\right\Arrowvert< \frac{1}{2}\varepsilon \quad \mb{for all}\quad n>l.
\]
Let $r=l+1$, then
\[
\left\Arrowvert \b a_{r} - \b g\right\Arrowvert< \frac{1}{2}\varepsilon.
\]
Adding the above inequalities we obtain
\[
\left\Arrowvert \b a_{n} - \b g\right\Arrowvert +\left\Arrowvert \b a_{r} - \b g\right\Arrowvert< \varepsilon \quad \mb{for all}\quad n>r.
\]
On the other hand
\[
\left\Arrowvert \b a_{n} - \b a_r\right\Arrowvert\le \left\Arrowvert \b a_{n} - \b g \right\Arrowvert+\left\Arrowvert \b a_{r} - \b g \right\Arrowvert.
\]
Hence,
\[
\left\Arrowvert \b a_{n} - \b a_r \right\Arrowvert < \varepsilon \quad\mb{for all}\quad n>r.
\]
%This completes the proof of the necessity part.

$\left( \Leftarrow \right)$ We now assume that for every $\varepsilon > 0$ there exists an $r=r(\varepsilon)$ such that
\[
\left\Arrowvert \b a_{n} - \b a_r \right\Arrowvert < \varepsilon \quad\mb{for all}\quad n>r.
\]
We then show that the above condition implies
\[
\lim_{n \to \infty}\b a_n = \b g.
\]
First, we show that $\left\{ \b a_n\right\}$ is a bounded sequence. Let $\varepsilon = 1$. Then, an $r=r(\varepsilon)$ exists such that $\left\Arrowvert \b a_{n} - \b a_r \right\Arrowvert <1$ for all $n>r$. Hence,
\[
\left\Arrowvert \b a_{n} \right\Arrowvert-\left\Arrowvert \b a_r \right\Arrowvert \le \left\Arrowvert \b a_{n} - \b a_r \right\Arrowvert <1,
\]
which means that
\[
\left\Arrowvert \b a_{n}\right\Arrowvert <\left\Arrowvert \b a_r \right\Arrowvert +1.
\]
Let
\[
M=\max\left\{ \left\Arrowvert \b a_1 \right\Arrowvert, \left\Arrowvert \b a_2 \right\Arrowvert,\ldots,\left\Arrowvert \b a_{r-1} \right\Arrowvert,\left\Arrowvert \b a_r \right\Arrowvert +1\right\},
\]
then we have
\[
\left\Arrowvert \b a_{n}\right\Arrowvert \le M\quad\mb{for all}\quad n,
\]
which implies that the sequence $\left\{\b a_n\right\}$ is bounded. By the Bolzano-Weierstrass theorem\index{Bolzano-Weierstrass theorem} the sequence $\left\{\b a_n\right\}$ contains a convergent subsequence. Let
\[
\lim_{n \to \infty}\b a_{m_n}=\b g,\quad m_1<m_2<\ldots .
\]
We will show that
\[
\lim_{n\to \infty}\b a_n=\b g.
\]
From the hypothesis of the theorem it follows that for some $r=r\left( \varepsilon/3\right)$, we have
\begin{equation}
\left\Arrowvert \b a_{n}-\b a_r\right\Arrowvert< \frac{1}{3}\varepsilon \quad\mb{for all}\quad n>r.
\label{eq:nroneth}
\end{equation}
On the other hand, the assumption that the subsequence $\left\{\b a_{m_n}\right\}$ is convergent implies that for some $k=k\left( \varepsilon/3\right)$,
\begin{equation}
\left\Arrowvert \b a_{m_n}-\b g\right\Arrowvert < \frac{1}{3}\varepsilon \quad\mb{for all}\quad n>k.
\label{eq:mngonet}
\end{equation}
We can select $k$ so that $k>r$. In such a case, (\ref{eq:nroneth}) and (\ref{eq:mngonet}) are satisfied for all $n>k$. Since $m_n \ge n > r$, we have for all $n>k$,
\[
\left\Arrowvert \b a_{m_n}-\b a_r\right\Arrowvert < \frac{1}{3}\varepsilon ,
\]
or equivalently,
\begin{equation}
\left\Arrowvert \b a_{r}-\b a_{m_n}\right\Arrowvert < \frac{1}{3}\varepsilon.
\label{eq:rmnagain}
\end{equation}
Adding~(\ref{eq:nroneth}), (\ref{eq:mngonet}), and~(\ref{eq:rmnagain}) yields
\[
\left\Arrowvert \b a_{n}-\b a_r\right\Arrowvert +\left\Arrowvert \b a_{m_n}-\b g\right\Arrowvert+\left\Arrowvert \b a_{r}-\b a_{m_n}\right\Arrowvert < \varepsilon.
\]
Hence,
\begin{eqnarray*}
\left\Arrowvert \b a_{n}-\b g\right\Arrowvert&=&
\left\Arrowvert \left(\b a_{n}-\b a_r\right)+\left(\b a_r-\b a_{m_n}\right)+\left(\b a_{m_n}-\b g\right)\right\Arrowvert\\
&\le& \left\Arrowvert \b a_{n}-\b a_r\right\Arrowvert +\left\Arrowvert \b a_{m_n}-\b g\right\Arrowvert+\left\Arrowvert \b a_{r}-\b a_{m_n}\right\Arrowvert\\
&<& \varepsilon \quad\mb{for all}\quad n>k,
\end{eqnarray*}
which implies that
\[
\lim_{n \to \infty}\b a_n = \b g.
\]
The proof is complete.\\
\hspace*{5.5in} $\Box$

\begin{thm}
Every monotone bounded sequence in $\mb{\Bb R}$ is convergent.
\end{thm}
{\bf Proof} \quad We will prove the theorem for nondecreasing sequences.\index{monotone bounded sequence!is convergent} The proof for nonincreasing sequences is analogous.

We assume that we are given a sequence $\left\{ a_n \right\}$ in $\mb{\Bb R}$ that is bounded and nondecreasing. Let $Z$ be the set of numbers belonging to the sequence, and let $g$ be the least upper bound of $Z$. Hence
\[
g\ge a_n,\quad n=1,2,\ldots .
\]
From the properties of the least upper bound---see Theorem~\ref{thm_lub}, it follows that for any $\varepsilon > 0$ there exists a $k$ such that
\[
g-\varepsilon < a_k.
\]
Since the sequence $\left\{ a_n\right\}$ is nondecreasing, the inequality $n>k$ implies that
\[
a_k\le a_n,
\]
and thus
\[
g-\varepsilon < a_n.
\]
We then conclude that for any $\varepsilon > 0$, there exists a $k$ such that for $n>k$ we have
\[
g-\varepsilon < a_n <g+\varepsilon.
\]
Hence,
\[
\left\arrowvert a_n-g\right\arrowvert < \varepsilon,
\]
which means that
\[
\lim_{n \to \infty}a_n = g.
\]
Thus, a monotone bounded sequence in $\mb{\Bb R}$ is convergent. The proof is complete.\\
\hspace*{5.5in} $\Box$

Given a sequence $\{a_n\}$ of real numbers. Then the sequence $\{s_N\}$ defined by
\[
s_N=\sum_{n=1}^N a_n = a_1+a_2+\cdots + a_N
\]
is called the sequence of {\em partial sums\/} of the series\index{partial sums!of the series}
\begin{equation}
\sum_{n=1}^{\infty} a_n.
\label{eq:sernotoinf}
\end{equation}
If the sequence of the partial sums has a limit, that is, $s_N \to s$ as $N \to \infty$, then we say that the series converges to the sum $s$, and write
\[
s=\sum_{n=1}^{\infty}a_n.
\]
The above formula can only make sense when the series~(\ref{eq:sernotoinf}) converges.
\begin{thm}
\label{thm:anofseries}
If the series $\sum_{n=1}^{\infty} a_n$ converges, then
\[
a_n \to 0\quad\mb{as}\quad n\to \infty.
\]
\end{thm}
{\bf Proof}\quad Let $s$ be the sum of the series $\sum_{n=1}^{\infty} a_n$. Then,
\begin{equation}
s_N=\sum_{n=1}^N a_n \to s\quad\mb{as}\quad N\to \infty.
\label{eq:sngsts}
\end{equation}
We also have
\begin{equation}
s_{N-1} \to s\quad\mb{as}\quad N\to \infty.
\label{eq:snm1gsts}
\end{equation}
We have,
\begin{eqnarray*}
a_N&=& \left(a_1+a_2+\cdots+a_N \right)-\left(a_1+a_2+\cdots+a_{N-1} \right)\\
&=& s_N-s_{N-1}.
\end{eqnarray*}
Therefore, by~(\ref{eq:sngsts}) and~(\ref{eq:snm1gsts}),
\[
a_N\to (s-s)=0\quad\mb{as}\quad N\to \infty,
\]
and the proof is complete.\\
\hspace*{5.5in} $\Box$

The converse of Theorem~\ref{thm:anofseries} is false. The terms of the series
\[
\sum_{n=1}^{\infty} \frac{1}{n}
\]
tend to zero, but the series diverges.\index{series!diverges}\index{series!converges}

\section{Functions}
%\section*{Functions}
%\addcontentsline{toc}{section}{Functions}

We discuss functions\index{function!of one variable}\index{function!of several variables} of one and several variables and their basic properties. A function $f$ from a set ${\cal A}$ to a set ${\cal B}$, denoted
\[
f:{\cal A} \to {\cal B},
\]
is a rule that assigns to each $\b x \in {\cal A}$ a unique element $\b y \in {\cal B}$. The set ${\cal A}$ is the domain of $f$ and the range of $f$ is a subset of ${\cal B}$, not necessarily the whole of ${\cal B}$.

%If $f:{\cal A} \to {\cal B}$ and a set ${\cal S} \subset {\cal A}$, then %the function $g:{\cal S} \to {\cal B}$ defined by $g(z)=f(z)$, for $z\in %{\cal S}$, is called the {\em restriction\/} of $f$ to ${\cal S}$.

Let $f:{\cal S} \to \mb{\Bb R}$, where ${\cal S}$ is a subset of $\mb{\Bb R}$. Then, $f$ is said to be continuous\index{function!continuous at a point} at $z_0 \in {\cal S}$ if for every $\varepsilon >0$, there exists $\delta=\delta(\varepsilon,z_0)$ such that $z\in{\cal S}$, $|z-z_0|<\delta$ imply $|f(z)-f(z_0)|<\varepsilon$. This is also written as $f(z)\to f(z_0)$ as $z\to z_0$. If $f$ is continuous at every point of ${\cal S}$, then we say that $f$ is continuous on ${\cal S}$.\index{function!continuous}

We say that the function $f$ is bounded on a set ${\cal S}$ if there is $M\ge 0$ such that for any $\b z \in {\cal S}$ we have
\[
|f(\b z)| \le M.
\]

\begin{lemma}
\label{lemma:bounded}
If $f$ is continuous on $[a,b] \subset \mb{\Bb R}$, then $f$ is bounded on $[a,b]$.
\end{lemma}
{\bf Proof}\quad Consider the set
\[
\{x:x\in [a,b],\mb{ and {\em f} is bounded on } [a,x]\}.
\]
This set is nonempty and bounded above by $b$. Let
\[
c=\sup\{x: f \mb{ is bounded on } [a,x]\}.
\]
We will show that $c=b$. Suppose that $c<b$. From the continuity of $f$ at $c$ it follows that $f$ is bounded on $[c-\delta,c+\delta]$ for some sufficiently small $\delta > 0$. Being bounded on $[a,c-\delta]$ and on $[c-\delta,c+\delta]$, it is bounded on $[a,c+\delta]$. This contradicts our choice of $c$. We therefore conclude that $c=b$. This means that $f$ is bounded on $[a,x]$ for all $x<b$. From the continuity of $f$, we know that $f$ is bounded on some interval $[b-\delta,b]$. Hence, $f$ is bounded on $[a,b-\delta]$ and on $[b-\delta,b]$, which means that $f$ is bounded on $[a,b]$.\\
\hspace*{5.5in} $\Box$

With the help of the above lemma, we can now prove the maximum-minimum theorem of Weierstrass.\index{maximum-minimum theorem!of Weierstrass}\index{theorem of Weierstrass}
\begin{thm}[The Maximum-Minimum Theorem]
\label{thm:minmaxt}
If $f$ is continuous on an interval $[a,b]$, then it takes on both its supremum and infimum values on $[a,b]$.
\end{thm}
{\bf Proof}\quad By Lemma~\ref{lemma:bounded} above, the function $f$ is bounded on $[a,b]$. Let
\[
M=\sup\{f(x):x \in [a,b]\}.
\]
We show that there is a $c \in [a,b]$ such that $f(c)=M$. Let
\[
g(x)=\frac{1}{M-f(x)}.
\]
If $f$ does not take on the value of $M$, then $g$ is continuous on $[a,b]$, and by Lemma~\ref{lemma:bounded} the function $g$ is bounded on $[a,b]$. But $g$ cannot be bounded on $[a,b]$. Thus, the assumption that $f$ does not take on the value $M$ has led us to a contradiction. The other case that $f$ takes on its infimum value can be proved in a similar manner.\\
\hspace*{5.5in} $\Box$

A {\em sphere\/},\index{sphere!ball} ball, around $\b x$ in $\mb{\Bb R}^p$ is a set of the form $\{\b y:\|\b x-\b y\|<\varepsilon\}$ for some $\varepsilon >0$. A set $\Omega$ in $\mb{\Bb R}^p$ is said to be {\em open\/} if around every point $\b x$ in $\Omega$ there is a sphere that is contained in $\Omega$.\index{open set}

If $\b x\in \mb{\Bb R}^p$, then any set that contains an open set containing $\b x$ is called a {\em neighborhood\/}\index{neighborhood} of $\b x$. A sphere around $\b x$ is a neighborhood of $\b x$.

A point $\b x\in \mb{\Bb R}^p$ is called a {\em boundary point}\index{boundary point} of a set $\Omega \subseteq \mb{\Bb R}^p$ if every neighborhood of $\b x$ contains a point of $\Omega$ and a point that is not in $\Omega$. The set of all boundary points of $\Omega$ is called the {\em boundary\/} of $\Omega$.\index{boundary!of a set} A set is said to be {\em closed\/} if it contains its boundary. Equivalently, a set $\Omega$ is closed if $\b x_k \to \b g$ with $\b x_k \in \Omega$ implies $\b g \in \Omega$. A set is {\em bounded\/} if it is contained within some sphere of finite radius. A set is {\em compact\/}\index{compact set!closed and bounded} if it is both closed and bounded. Any finite set $\Omega=\left\{\b x_1,\b x_2,\ldots,\b x_k\right\}$ in $\mb{\Bb R}^p$ is compact.\index{finite set!is compact}

We now generalize Lemma~\ref{lemma:bounded} for real-valued functions of several variables.
\begin{lemma}
\label{lemma:many}
Let $f:\mb{\Bb R}^p \to \mb{\Bb R}$ be a continuous function on a compact set\index{continuous function!on a compact set} $\Omega \subset \mb{\Bb R}^p$. Then, $f$ is bounded on $\Omega$.
\end{lemma}
{\bf Proof}\quad We prove the lemma by contradiction. We assume that $f$ is continuous on a compact set $\Omega$, but $f$ is not bounded on $\Omega$. Without loss of generality, suppose that $f$ is unbounded above on $\Omega$. Since $f$ is unbounded above on $\Omega$, we can find a sequence $\{\b x_n\} \subset \Omega$ such that $f(\b x_n) > r(n)$, where $r(n) \to \infty$ as $n\to \infty$, that is, $f(\b x_n)\to \infty$ as $n \to \infty$. The sequence $\{ \b x_n\}$ must be bounded because, by assumption, the set $\Omega$ is compact. Therefore, by the Bolzano-Weierstrass theorem,\index{Bolzano-Weierstrass theorem} on page~\pageref{thm:bolzweierstr}, there is a convergent subsequence, say, $\{\b x_{n_k}\}$ that converges to a point $\b x^* \in \Omega$. The function is continuous on $\Omega$. Hence,
\begin{equation}
\lim_{k\to \infty}f(\b x_{n_k})=f\left(\lim_{k\to \infty}\b x_{n_k}\right)=f\left(\b x^* \right).
\label{eq:ledirifin}
\end{equation}
We arrived at a contradiction because by assumption, the left-hand side of~(\ref{eq:ledirifin}) is divergent, while $f\left( \b x^*\right) < \infty$ because $f$ is continuous on $\Omega$. Therefore, a continuous function on a compact set in $\mb{\Bb R}^p$ must be bounded.\\
\hspace*{5.5in} $\Box$

We next prove the theorem of Weierstrass for real-valued functions of several variables.\index{theorem of Weierstrass!for functions of several variables}
\begin{thm}[Weierstrass]
\label{thm:weierstrassgen}
If $f:\mb{\Bb R}^p \to \mb{\Bb R}$ is a continuous function on a compact set $\Omega \subset \mb{\Bb R}^p$, then $f$ achieves its supremum and infimum.
\label{thm:weierstrass}
\end{thm}
{\bf Proof}\quad The proof follows that of Theorem~\ref{thm:minmaxt} with the interval $[a,b]$ being replaced with the compact set $\Omega$, and by referring to Lemma~\ref{lemma:many} rather than to Lemma~\ref{lemma:bounded}.\\
\hspace*{5.5in} $\Box$

There is a special type of continuity that we will use later.
\begin{defn}[Uniform continuity]
Let $f:{\cal X} \to {\cal Y}$. Then, $f$ is called uniformly continuous on ${\cal X}$ if for every $\varepsilon>0$ there exists $\delta=\delta(\varepsilon)>0$, depending only on $\varepsilon$, such that $\left|x-x'\right|<\delta$ implies $\left|f(x)-f(x')\right|<\varepsilon$, where $x,x'$ are in ${\cal X}$
\label{defn:uni_con}
\end{defn}\markdefn

Every uniformly continuous function\index{uniformly continuous}\index{function!uniformly continuous} is continuous, but not necessarily conversely. Indeed, $f(x)=1/x$ is continuous on $(0,1)$ but not uniformly continuous.

Another type of continuous functions that we will be using later are absolutely continuous functions.
\begin{defn}[Absolutely continuous function]
Let $f$ be a function defined on the closed interval $[a,b]$. Then, the function $f$ is said to be absolutely continuous on $[a,b]$ if for every $\varepsilon>0$, there exists a $\delta>0$ such that
\begin{equation}
\sum_{k=1}^n\left(b_k-a_k \right)<\delta
\label{eq:abs_cont_d}
\end{equation}
for all numbers $a_1,b_1,\ldots,a_n,b_n$ such that $a_1<b_1\le a_2<b_2\le \cdots\le a_n<b_n$, we have
\begin{equation}
 \sum_{k=1}^n \left|f(b_k)-f(a_k) \right|<\varepsilon.
\label{eq:abs_cont_e}
\end{equation}
\label{defn:abs_con}
\end{defn}\markdefn

Note that every absolutely continuous function\index{absolutely continuous}\index{function!absolutely continuous} is continuous, because the case $n=1$ is not excluded in the above definition. A function $f$ that satisfies the Lipschitz condition,\index{Lipschitz condition}
\[
\left|f(x)-f(y) \right| \le L|x-y|,
\]
is absolutely continuous.

\section{Linear Operators}
%\section*{Linear Operators}
%\addcontentsline{toc}{section}{Linear Operators}

%A {\em mapping} is a generalization of a function. For the sake of brevity, %a mapping will be called a {\em map}. A map from a set ${\cal X}$ to a set %${\cal Y}$ is an association which to every element of ${\cal X}$ %associates an element of ${\cal Y}$. A function is a map from a set into a %set of numbers, for example into $\mb{\Bb R}$ or $\mb{\Bb C}$. If $F:{\cal %X} \to {\cal Y}$ is a map, and if $x\in {\cal X}$, then we denote by $F(x)$ %the element of ${\cal Y}$ associated to $x$ under $F$. We can write
%\[
%x \mapsto F(x),
%\]
%with a special arrow $\mapsto$ to denote that $x$ maps to $F(x)$. For %example, we can represent the map $F(x)=x^3$ as $x \mapsto x^3$.

A function
\[
F:\mb{\Bb R}^n \to \mb{\Bb R}^m
\]
is said to be {\em linear\/}\index{linear function}\index{function!linear} if it satisfies the following two properties:
\begin{itemize}
\item[{\bf LM 1.}] For any $\b x$, $\b y$ in $\mb{\Bb R}^n$, we have
\[
F(\b x+\b y)=F(\b x)+F(\b y),
\]
\item[{\bf LM 2.}] If $c$ is a number, then
\[
F(c\,\b x)=cF(\b x).
\]
\end{itemize}
Linear functions are sometimes referred to as {\em linear maps\/} or {\em linear operators\/}.\index{linear maps|see{linear functions}}\index{linear operators|see{linear functions}}

Linear functions from $\mb{\Bb R}^n$ into $\mb{\Bb R}^m$ can be identified with the $m\times n$ real matrices by
\[
\b F:\mb{\Bb R}^n \to \mb{\Bb R}^m\quad \mb{is linear if and only if}\quad \b F(\b x)=\b A\b x,
\]
where $\b A\in \mb{\Bb R}^{m\times n}$.

If $\b F:\mb{\Bb R}^n \to \mb{\Bb R}^m$ is linear, then there exists a constant $L \ge 0$ such that
\begin{equation}
\|\b F(\b x)\| \le L\|\b x\|
\label{eq:lin_bounded}
\end{equation}
for all $\b x \in \mb{\Bb R}^n$. The smallest such constant $L$ for which this is true is denoted $\|\b F\|$ and called the norm of the linear map\index{norm!of the linear map}\index{linear map!norm of} $\b F$. If $\b F$ is the linear map induced by the matrix $\b A$, then we define $\|\b A\|=\|\b F\|$. For any matrix $\b A$ and vector norm $\|\cdot\|$, we can compute the matrix norm\index{matrix norm} using the formula
\begin{equation}
\fbox{$\displaystyle \|\b A\|=\sup_{\b x\ne \b 0}\frac{\|\b A\b x\|}{\|\b x\|} $}
\label{eq:mat_norm_def}
\end{equation}
The matrix norm, that is, the norm of the linear map $\b F$ given by~(\ref{eq:mat_norm_def}) is equivalent to
\begin{equation}
\fbox{$\displaystyle \|\b A\|=\max_{\|\b x\|=1} \|\b A\b x\|$}
\label{eq:linnorm_gen}
\end{equation}
A matrix norm produced using~(\ref{eq:mat_norm_def}) or~(\ref{eq:linnorm_gen}) is called the {\em induced norm}.\index{induced norm} Note that
\[
\|\b A\b x-\b A\b y\|=\|\b A(\b x-\b y)\|\le \|\b A\|\|\b x-\b y\|,
\]
that is, the linear map, $\b F$, represented by the matrix $\b A$ is uniformly continuous.

A couple of comments on the notation used in~(\ref{eq:mat_norm_def}) and~(\ref{eq:linnorm_gen}) are needed to clarify the matter. First, the same symbol is used for the matrix norm as for the norm of a vector. Second, the norms appearing on the right side of~(\ref{eq:mat_norm_def}) and~(\ref{eq:linnorm_gen}) are the norms of the vectors $\b x \in \mb{\Bb R}^n$, and $\b A\b x \in \mb{\Bb R}^m$. Thus, if $\mb{\Bb R}^n$ is equipped with the vector norm $\|\cdot\|_s$ while $\mb{\Bb R}^m$ is equipped with the vector norm $\|\cdot\|_t$, then~(\ref{eq:linnorm_gen}) should be interpreted as
\[
\|\b A\|=\max_{\|\b x\|_s=1} \|\b A\b x\|_t.
\]
Vector norms and a matrix norm are said to be {\em compatible\/}, or {\em consistent\/},\index{matrix norm!compatible} if they satisfy,\index{matrix norm!consistent}\index{compatible matrix norm}\index{consistent matrix norm|see{compatible matrix norm}}
\begin{equation}
\|\b A\b x\|_t \le \|\b A\|\|\b x\|_s.
\label{eq:compconfn}
\end{equation}

We next show that~(\ref{eq:linnorm_gen}) is well defined. For this, we need the following lemma.
\begin{lemma}
A vector norm $\| \cdot\|:\mb{\Bb R}^p \to \mb{\Bb R}$ is an uniformly continuous function.\index{vector norm!uniformly continuous function}
\label{lemma:norm_cont}
\end{lemma}
{\bf Proof}\quad
By Theorem~\ref{thm:abs_twonmrm}, on page~\pageref{thm:abs_twonmrm},
\[
\left|\|\b x\|-\|\b y \|\right|\le \|\b x-\b y\|.
\]
Hence, for any $\varepsilon > 0$, if we take $\delta=\varepsilon$ then for any $\b x, \b y \in \mb{\Bb R}^p$, if $\|\b x-\b y\|<\delta$ then $\left|\|\b x-\b y \|\right|<\varepsilon$, as was to be shown.\\
\hspace*{5.5in} $\Box$

By the continuity of the vector norm and the theorem of Weierstrass,\index{theorem of Weierstrass}\index{Weierstrass!theorem of} on page~\pageref{thm:weierstrassgen}, a vector $\b x_0$ can be found such that $\|\b x_0\|=1$ and $\|\b A\|=\|\b A\b x_0\|=\max_{\|\b x\|=1} \|\b A\b x\|$. Thus, the expression~(\ref{eq:linnorm_gen}) is well defined.

We show that~(\ref{eq:linnorm_gen}) satisfies~(\ref{eq:compconfn}). Suppose that we are given  a vector $\b y\ne \b 0$. Then,
\[
\b x=\frac{1}{\|\b y\|}\b y
\]
satisfies the condition $\|\b x\|=1$. Hence,
\[
\|\b A\b y\|=\|\b A\left(\|\b y\|\b x \right)\|=\|\b y\|\|\b A\b x\|.
\]
Applying now~(\ref{eq:linnorm_gen}) to the right-hand side of the above yields
\[
\|\b A\b y\|\le \|\b y\|\|\b A\|.
\]
Hence, any matrix norm produced by~(\ref{eq:linnorm_gen}) is consistent.

Next, we prove that a matrix norm obtained using~(\ref{eq:linnorm_gen}) satisfies the following conditions:
\begin{itemize}
\item[{\bf MN 1.}] $\|\b A\| >0$ if $\b A \ne \b O$ and $\|\b O\| = 0$.
\item[{\bf MN 2.}] $\|c\b A\| = |c|\|\b A\|$, where $c$ is a constant.
\item[{\bf MN 3.}] $\|\b A+\b B\| \le \|\b A\|+\|\b B\|$.
\item[{\bf MN 4.}] $\|\b A\b B\| \le \|\b A\|\|\b B\|$.
\end{itemize}

{\bf Proof of MN 1.} Let $\b A \ne \b O$. Then a vector $\b x$, $\|\b x\|=1$, can be found such that $\b A\b x \ne \b 0$, and thus $\|\b A\b x\| \ne 0$. Hence, $\|\b A\|=\max_{\|\b x\|=1}\|\b A\b x\| \ne 0$. If, on the other hand, $\b A=\b O$, then $\|\b A\|=\max_{\|\b x\|=1}\|\b O\b x\|=0$.

{\bf Proof of MN 2.} By definition, $\|c\b A\|=\max_{\|\b x\|=1}\|c\b A\b x\|$. Using a property of the vector norm, we write $\|c\b A\b x\|=|c|\|\b A\b x\|$, and hence
\[
\|c\b A\|=\max_{\|\b x\|=1}|c|\|\b A\b x\|=|c|\max_{\|\b x\|=1}\|\b A\b x\|=|c|\|\b A\|.
\]

{\bf Proof of MN 3.} For the sum of two matrices $\b A+\b B$, there exists a vector $\b x_0$, $\|\b x_0\|=1$, such that
\[
\|\b A+\b B\|=\|(\b A+\b B)\b x_0\|.
\]
Then, using properties of the vector norm, we obtain
\[
\|\b A+\b B\|=\|\b A\b x_0+\b B\b x_0\|\le \|\b A\b x_0\|+\|\b B\b x_0\|.
\]
Using~(\ref{eq:linnorm_gen}) yields
\[
\|\b A+\b B\|\le \|\b A\|\|\b x_0\|+\|\b B\|\|\b x_0\| = \|\b A\|+\|\b B\|.
\]

{\bf Proof of MN 4.} For the product of two matrices $\b A\b B$, there exists a vector $\b x_0$, $\|\b x_0\|=1$, such that $\|\b A\b B\|=\|\b A\b B\b x_0\|$. Then, using~(\ref{eq:linnorm_gen}), we have
\[
\|\b A\b B\|=\|\b A(\b B\b x_0)\| \le \|\b A\|\|\b B\b x_0\|.
\]
Using~(\ref{eq:linnorm_gen}) again yields
\[
\|\b A\b B\|\le \|\b A\|\|\b B\|\|\b x_0\|=\|\b A\|\|\b B\|.
\]
\hspace*{5.5in} $\Box$

The most frequently used matrix norms are the $p$-norms\index{matrix p-norms}\index{p-norms!of matrix}
\[
\|\b A\|_p=\max_{\|\b x\|_p=1} \|\b A\b x\|_p.
\]
The induced matrix norms\index{induced matrix norms!p-norms} corresponding to the one-, two-, and infinity-norm for vectors are:
\begin{itemize}
\item $\|\b A\|_1=\max_j\|\b a_j\|_1$, that is, $\|\b A\|_1$ is the maximum of absolute column sum;\index{matrix 1-norm!maximum of absolute column sum}
\item $\|\b A\|_2=\sigma_1(\b A)$, which is the largest singular value of $\b A$;\index{matrix 2-norm!largest singular value}
\item $\|\b A\|_{\infty}=\max_i\|\b a_i^{\top}\|_1$, which is the maximum of absolute row sum.\index{matrix infinity-norm!maximum of absolute row sum}
\end{itemize}
A matrix norm that is not induced by a vector norm is the {\em Frobenius norm},\index{Frobenius norm} defined for an $m\times n$ matrix $\b A$ as
\begin{equation}
\|\b A\|_F=\left(\sum_{i=1}^m\sum_{j=1}^n a_{ij}^2 \right)^{1/2}.
\label{eq:frobenius_norm}
\end{equation}
The Frobenius norm satisfies the relation
\begin{equation}
\|\b A\|_F^2=\mb{trace}\left(\b A\b A^{\top} \right)=\mb{trace}\left(\b A^{\top}\b A \right).
\label{eq:frob_trace}
\end{equation}
The Frobenius norm is compatible with the Euclidean vector norm, that is,
\begin{equation}
\|\b A\b x\|_2 \le \|\b A\|_F\|\b x\|_2.
\label{eq:frobe_euclide}
\end{equation}


\section{Vector Spaces}
%\section*{Vector Spaces}
%\addcontentsline{toc}{section}{Vector Spaces}
\label{sec:vector_spaces}

A given set of vectors of the same dimension $\{\b x_1,\b x_2,\ldots,\b x_r \}$ is {\em linearly dependent}\index{linearly dependent!set of vectors}\index{set of vectors!linearly dependent} if the zero vector, $\b 0$, can be written as a non-trivial {\em linear combination} of the given vectors,\index{linear combination!of vectors}
\[
\alpha_1\b x_1+\alpha_2\b x_2+\cdots+\alpha_r\b x_r=\b 0,\quad\mb{with}\quad \alpha_i\ne 0\quad\mb{for at least one } i.
\]
In other words, the set of vectors $\{\b x_1,\b x_2,\ldots,\b x_r \}$ is {\em linearly independent\/}\index{linearly independent!set of vectors}\index{set of vectors!linearly independent} if
\[
\alpha_1\b x_1+\alpha_2\b x_2+\cdots+\alpha_r\b x_r=\b 0,\quad\mb{implies}\quad \alpha_1=\alpha_2=\cdots=\alpha_r=0.
\]
A set ${\cal S}$ containing vectors of dimension $p$ is a {\em subspace} of $\mb{\Bb R}^p$ if for any scalars $\alpha$ and $\beta$,
\begin{equation}
\b x, \b y \in {\cal S}\quad\mb{implies}\quad \alpha \b x+\beta \b y \in {\cal S}.
\label{eq:def_subspace}
\end{equation}
It follows from the above that a subspace must contain the zero vector, $\b 0$.\index{zero vector} The set containing only the zero vector is a subspace.\index{subspace} This set, $\{\b 0\}$, is called a {\em trivial} subspace.\index{trivial subspace}

A matrix-vector product\index{matrix-vector product}
\begin{equation}
\b A\b x=\left[\begin{array}{cccc}
\b a_1&\b a_2&\cdots&\b a_n
\end{array}\right]\left[\begin{array}{c}
x_1\\
x_2\\
\vdots\\
x_n
\end{array}\right]=x_1\b a_1+x_2\b a_2+\cdots +x_n\b a_n
\label{eq:mat_vec_prod}
\end{equation}
is a linear combination of the columns of the matrix. Thus, linear dependence of the columns\index{linear dependence of columns} of $\b A$ is equivalent to the condition
\begin{equation}
\b A\b z=\b 0\quad\mb{for some vector}\quad \b z \ne \b 0.
\label{eq:lin_dep_condm}
\end{equation}
Linear independence of the columns of $\b A$ is equivalent to the condition
\begin{equation}
\b A\b z=\b 0\quad\mb{implies}\quad \b z=\b 0.
\label{eq:lin_independm}
\end{equation}
The set of all vectors that are linear combinations of the columns of $\b A$ is called the {\em range\/},\index{range!of a matric} or {\em image\/},\index{image!of a matric} of $\b A$ and will be denoted $\mb{range}(\b A)$. Thus,
\begin{equation}
\mb{range} (\b A)=\{\b v:\b v=\b A\b x \quad\mb{for some}\quad \b x\}.
\label{eq:range_defn}
\end{equation}
For a given $m\times n$ matrix $\b A$ and an $m$-vector $\b b$, we have $\b b\in \mb{range}(\b A)$ if and only if there exists an $n$-vector $\b x$ such that $\b A\b x=\b b$. We say that a system of linear equations represented by $\b A\b x=\b b$ is compatible if $\b b \in \mb{range}(\b A)$.\index{compatible!system of linear equations}

The range of $\b A$ is a subspace of $\mb{\Bb R}^m$. Indeed, for any $\b b_1, \b b_2 \in \mb{range}(\b A)$, we have $\b b_1=\b A \b x_1$ and $\b b_2=\b A\b x_2$ for some $\b x_1$ and $\b x_2$. Using the fact that $\b A$ represents a linear map, for any scalars $\alpha_1$ and $\alpha_2$,
\begin{equation}
\alpha_1\b b_1+\alpha_2\b b_2=\alpha_1\b A\b x_1+\alpha_2\b A\b x_2=\b A\left( \alpha_1\b x_1+\alpha_2 \b x_2 \right).
\label{eq:range_sub}
\end{equation}
Hence, if $\b b_1, \b b_2 \in \mb{range}(\b A)$, then $\alpha_1\b b_1+\alpha_2 \b b_2 \in \mb{range}(\b A)$, which means that the range of $\b A$ is a subspace of $\mb{\Bb R}^m$.

Similarly, we define the range of $\b A^{\top}$ to be the set
\begin{equation}
\mb{range} (\b A^{\top})=\left\{\b y : \b y=\b A^{\top}\b z \quad\mb{for some}\quad \b z\right\}.
\label{eq:rangeatr}
\end{equation}

For a non-trivial subspace ${\cal S}$ there is a unique smallest positive integer called the {\em dimension\/} of the subspace ${\cal S}$\index{dimension!of a subspace} and denoted $\dim {\cal S}$. The dimension of the subspace is equal to the smallest number of linearly independent vectors of the subspace such that every vector of the subspace can be expressed as a linear combination of these vectors. Any such set of vectors is called a {\em basis\/} of the subspace.\index{basis!of a subspace} The vectors forming a basis are not unique.

The number of linearly independent columns of a matrix $\b A$\index{matrix rank!number of linearly independent columns} is called the {\em rank\/} of $\b A$\index{rank!of a mtrix}\index{matrix!rank of} and denoted $\mb{rank} (\b A)$. The rank of $\b A$ is also equal to the number of linearly independent rows of $\b A$.\index{matrix rank!number of linearly independent rows}

For the product of a $m\times n$ matrix $\b A$ and a $n \times p$ matrix $\b B$, we have {\em Sylvester's inequalities}:\index{Sylvester's inequalities}
\begin{equation}
\mb{rank} (\b A)+\mb{rank} (\b B)-n\le \mb{rank} (\b A\b B)\le \min \{\mb{rank} (\b A),\mb{rank} (\b B) \}.
\label{sylvesterineq}
\end{equation}

For an $m\times n$ matrix $\b A$, the set of all $n$-vectors orthogonal to the rows of $\b A$ is called the {\em kernel\/},\index{kernel|see{null space}} or {\em null space\/},\index{null space} of $\b A$ and denoted $\ker (\b A)$, that is,
\begin{equation}
\ker (\b A)=\left\{ \b x: \b A\b x=\b 0 \right\}.
\label{eq:kernel_def}
\end{equation}
The kernel of $\b A$ is a subspace of $\mb{\Bb R}^n$. Indeed, if $\b x_1, \b x_2 \in \ker (\b A)$, then $\b A\b x_1 =\b 0$ and $\b A\b x_2 = \b 0$. Hence, for any scalars $\alpha_1$ and $\alpha_2$, we have
\begin{equation}
\b A\left( \alpha_1\b x_1+\alpha_2\b x_2\right)=\alpha_1\b A\b x_1+\alpha_2 \b A\b x_2=\b 0.
\label{eq:kernelsubs}
\end{equation}
Thus, if $\b x_1, \b x_2 \in \ker (\b A)$, then $\alpha_1\b x_1+\alpha_2\b x_2 \in \ker (\b A)$, which means that $\ker (\b A)$ is a subspace of $\mb{\Bb R}^n$. Similarly, we define the kernel of $\b A^{\top}$ to be the set
\begin{equation}
\ker \left(\b A^{\top}\right)=\left\{ \b w: \b A^{\top}\b w = \b 0\right\}.
\label{eq:kerenlatrans}
\end{equation}
The intersection of $\mb{range} (\b A)$ and $\ker \left( \b A^{\top} \right)$ contains only the zero vector,\index{zero vector} that is,
\begin{equation}
\mb{range} (\b A) \cap \ker \left( \b A^{\top}\right)=\{\b 0\}.
\label{eq:interseckerandr}
\end{equation}

For a given subspace ${\cal S}$ of $\mb{\Bb R}^n$, the orthogonal complement\index{orthogonal complement} ${\cal S}^{\perp}$ of ${\cal S}$ is defined by
\begin{equation}
{\cal S}^{\perp}=\left\{\b x\in \mb{\Bb R}^n: \b x^{\top}\b y=0\quad\mb{for all}\quad \b y \in {\cal S} \right\}.
\label{eq:gencomplement}
\end{equation}

The vectors in $\ker \left( \b A^{\top}\right)$ are orthogonal to the vectors in $\mb{range}(\b A)$, and vice versa. We say that $\mb{range}(\b A)$ and $\ker \left(\b A^{\top} \right)$ are {\em orthogonal complements\/} of one another and write
\begin{equation}
\mb{range} (\b A)^{\perp}=\ker \left( \b A^{\top}\right),
\label{eq:complaatr}
\end{equation}
and
\begin{equation}
\ker \left(\b A^{\top} \right)^{\perp}=\mb{range} (\b A).
\label{eq:complatra}
\end{equation}
Similarly,
\begin{equation}
\mb{range} \left(\b A^{\top}\right)^{\perp}=\ker \left( \b A\right),
\label{eq:complatrpa}
\end{equation}
and
\begin{equation}
\ker \left(\b A\right)^{\perp}=\mb{range} \left(\b A^{\top}\right).
\label{eq:complkeraptra}
\end{equation}

If $\b A$ is an $m\times n$ matrix with linearly independent columns, which implies that $m \ge n$, then
\[
\mb{rank} (\b A)=n=\dim \mb{range} (\b A),
\]
and
\[
\dim \ker \left( \b A^{\top}\right)=m-n.
\]

We now define a normed space.\index{normed space!vector space with a norm}
\begin{defn}
A vector space with a norm is called a {\em normed space}.
\end{defn}\markdefn

By the normed vector space $\mb{\Bb R}^n$, we usually mean the Euclidean space, which is $\mb{\Bb R}^n$ with the norm $\|\b x\|_2=\sqrt{x_1^2+\cdots +x_n^2}$. The vector space $\mb{\Bb R}^n$ equipped with any of the $p$-norm forms a normed vector space. The absolute value is a norm in $\mb{\Bb R}$.

Let $\Omega$ be a compact subset\index{compact!subset} of $\mb{\Bb R}^n$ and let ${\cal C}(\Omega)$ denote the set of continuous functions $f:\mb{\Bb R}^n \to \mb{\Bb R}$ on $\Omega$. Thus, we view functions as vectors in the function space ${\cal C}(\Omega)$. Then, the function $\|\cdot\|:{\cal C}(\Omega) \to \mb{\Bb R}$ defined as
\begin{equation}
\|f\|=\max_{\b x \in \Omega}|f(\b x)|,
\label{eq:funnormma}
\end{equation}
satisfies the norm axioms. The function space ${\cal C}(\Omega)$, with scalars from $\mb{\Bb R}$ and with the norm~(\ref{eq:funnormma}) is a normed linear space.\index{normed linear space} In particular, the space of all real-valued functions, $f(x)$, continuous on some interval $[a,b]$ of the real line with the norm defined by
\begin{equation}
\|f\|=\max_{x\in[a,b]}|f(x)|,
\label{eq:rvfofone}
\end{equation}
is an example of a normed linear space. This space is denoted ${\cal C}([a,b])$.

We will also be interested in sequences of elements of ${\cal C}([a,b])$. Let $f_1,f_2,\ldots$ be a sequence of elements of ${\cal C}([a,b])$. Denote this sequence by $\{f_k\}$. In the following, $f_k(x)$, means the value of the function $f_k$ at $x$, while $f_k$ means the function itself. We say that the sequence $\{f_k\}$ converges (pointwise) on the interval $[a,b]$ if there exists a function $f$ such that for every $x\in[a,b]$, the sequence $\{f_k(x)\}$ converges to $f(x)$. In other words, the sequence $\{f_k\}$ converges (pointwise)\index{pointwise convergence} if there exists a function $f$ such that for a given $x\in[a,b]$ and a given $\varepsilon>0$, we can find $N=N(x,\varepsilon)$ such that
\begin{equation}
|f(x)-f_k(x)|<\varepsilon\quad\mb{for}\quad k>N.
\label{eq:ptconv}
\end{equation}
The sequence $\{f_k\}$ converges uniformly, on the interval $[a,b]$, if there is a function $f$ such that for any $\varepsilon >0$ there exists $N=N(\varepsilon)$, depending on $\varepsilon$ but not on $x$, such that~(\ref{eq:ptconv}) holds for every $x\in[a,b]$. The distinction between convergence and uniform convergence\index{uniform convergence} is that in the later case, the same $N$ can be used for any value of $x$ to show the convergence of the sequence $\{f_k(x)\}$. One can show that the limit of an uniformly convergent sequence of continuous functions is continuous. It can be verified that the norm~(\ref{eq:rvfofone}) defines the uniform convergence because $\{f_k\}$ converges uniformly to $f$ if and only if $\max_{x\in[a,b]}|f(x)-f_k(x)|\to 0$. This is the reason the norm~(\ref{eq:rvfofone}) is sometimes called the {\em norm of uniform convergence\/}.\index{norm of uniform convergence} It can be shown that there is no norm on ${\cal C}([a,b])$ that defines pointwise convergence\index{pointwise convergence} to an element in ${\cal C}([a,b])$---see Debnath and Mikusi\'{n}ski~\cite[p.~12]{debnath90}.
\begin{defn}[Banach Space]
A normed linear space is complete, if every Cauchy sequence\index{Cauchy sequence} with elements form the space converges to an element in the space. A complete normed linear space\index{complete normed linear space} is called a Banach space.\index{Banach space!complete normed linear space}
\label{defn:banachspa}
\end{defn}\markdefn

The Euclidean space, as well as ${\cal C}([a,b])$ with the norm~(\ref{eq:rvfofone}), are examples of Banach spaces.

\section{Least Squares}
%\section*{Least Squares}
%\addcontentsline{toc}{section}{Least Squares}
\label{sec:rls}

Consider the system of equations\index{system!of linear equations}
\begin{equation}
\mb{\bm$A$}\mb{\bm$x$}=\mb{\bm$b$},
\label{eq:abeqflse}
\end{equation}
where $\mb{\bm$A$}\in \mb{\Bb R}^{m\times n}$, $\mb{\bm$x$}\in \mb{\Bb R}^{n}$, and $\mb{\bm$b$}\in \mb{\Bb R}^{m}$. A necessary and sufficient condition for the system~(\ref{eq:abeqflse}) to have a solution is
\begin{equation}
\mb{rank}(\mb{\bm$A$})=\mb{rank}\left[\begin{array}{ccc}
\mb{\bm$A$} &\vdots & \mb{\bm$b$}
\end{array}\right].
\label{eq:krocappsoco}
\end{equation}
In particular, if the matrix $\mb{\bm$A$}$ is invertible, then there is a unique solution to~(\ref{eq:abeqflse}) given by
\[
\mb{\bm$x$}^*=\mb{\bm$A$}^{-1}\mb{\bm$b$}.
\]
Here, we analyze the case when $m>n$ and $\mb{rank}(\mb{\bm$A$})<\mb{rank}\left[\begin{array}{ccc}
\mb{\bm$A$} &\vdots & \mb{\bm$b$}
\end{array}\right]$, that is, $\mb{\bm$b$} \notin \mb{range}(\mb{\bm$A$})$, which means that the system~(\ref{eq:abeqflse}) does not have an exact solution. We modify~(\ref{eq:abeqflse}) by incorporating an error vector $\mb{\bm$e$}$ to obtain
\begin{equation}
\mb{\bm$A$}\mb{\bm$x$}+\mb{\bm$e$}=\mb{\bm$b$}.
\label{eq:axpeeb}
\end{equation}
This is illustrated in Figure~\ref{fig:axpebls}.
\begin{figure}
\centering
\includegraphics[scale=0.5]{axpebls.eps}
%\vspace{3in}
%\hskip.75in\special{bmp:c:/ee675/axpebls.bmp x=4in y=3in}
\caption{Geometrical interpretation of the least squares solution to a system of linear equations.}
\label{fig:axpebls}
\end{figure}
Because
\begin{equation}
\mb{\bm$e$}=\mb{\bm$b$}-\mb{\bm$A$}\mb{\bm$x$},
\label{eq:eroflse}
\end{equation}
we have
\begin{eqnarray}
\|\mb{\bm$e$}\|^2&=&\mb{\bm$e$}^{\top}\mb{\bm$e$}\nonumber\\
%&=& \sum_{i=1}^m e_i^2\nonumber\\
&=&\left(\mb{\bm$b$}-\mb{\bm$A$}\mb{\bm$x$}\right)^{\top}\left(\mb{\bm$b$}-\mb{\bm$A$}\mb{\bm$x$}\right)\nonumber\\
&=&\mb{\bm$x$}^{\top}\mb{\bm$A$}^{\top}\mb{\bm$A$}\mb{\bm$x$}-2\b x^{\top}\b A^{\top}\b b+\mb{\bm$b$}^{\top}\mb{\bm$b$}.
\label{eq:quaforlse}
\end{eqnarray}
The gradient of $\|\mb{\bm$e$}\|^2$ with respect to $\mb{\bm$x$}$ is
\begin{equation}
\nabla_{\mb{\bm$x$}} \|\mb{\bm$e$}\|^2=2 \mb{\bm$A$}^{\top}\mb{\bm$A$}\mb{\bm$x$}-2\mb{\bm$A$}^{\top}\mb{\bm$b$}.
\label{gralse}
\end{equation}
Solving
\[
\nabla_{\mb{\bm$x$}} \|\mb{\bm$e$}\|^2=\mb{\bm$0$}
\]
yields candidate minimizer\index{candidate minimizer}\index{minimizer} points of~(\ref{eq:quaforlse}). If the matrix $\mb{\bm$A$}$ has full column rank,\index{full column rank}\index{matrix!full column rank} then the matrix $\mb{\bm$A$}^{\top}\mb{\bm$A$}$ is invertible and the only critical point is
\begin{equation}
\fbox{$\displaystyle \mb{\bm$x$}^*=\left( \mb{\bm$A$}^{\top}\mb{\bm$A$}\right)^{-1}\mb{\bm$A$}^{\top}\mb{\bm$b$} $}
\label{eq:solsecri}
\end{equation}
The above point satisfies the second order sufficient condition to be the minimizer of~(\ref{eq:quaforlse}) because the Hessian of~(\ref{eq:quaforlse}) is
\[
2\mb{\bm$A$}^{\top}\mb{\bm$A$},
\]
which is positive definite. The solution given by~(\ref{eq:solsecri}) is called the least squares solution\index{least squares!solution} of the inconsistent linear system of equations, $\b A\b x=\b b$, because it minimizes the sum of squares $\|\mb{\bm$e$}\|^2=\mb{\bm$e$}^{\top}\mb{\bm$e$}
= \sum_{i=1}^m e_i^2$. For a graphical interpretation\index{least squares!graphical interpretation} of the least squares solution, we refer to Figure~\ref{fig:axpebls}.

Suppose now that we interpret the $i$-th row of the matrix $\mb{\bm$A$}$ and the $i$-th component of the vector $\mb{\bm$b$}$ as the $i$-th data pair. Thus, the $i$-th data pair has the form $\left(\mb{\bm$a$}_i^{\top};b_i\right)$. Suppose that the $k$ data pairs are represented by the pair $\left(\mb{\bm$A$};\mb{\bm$b$}\right)$. We know that the least squares solution to the system of equations represented by the data pair $\left(\mb{\bm$A$};\mb{\bm$b$}\right)$ is given by~(\ref{eq:solsecri}). If the new data pair, $\left(\mb{\bm$a$}_{k+1}^{\top};b_{k+1}\right)$, becomes available, then we could find the least squares solution to the system of equations
\begin{equation}
\left[\begin{array}{c}
\mb{\bm$A$}\\
\mb{\bm$a$}_{k+1}^{\top}
\end{array}\right]\mb{\bm$x$}=\left[\begin{array}{c}
\mb{\bm$b$}\\
b_{k+1}
\end{array}\right]
\label{eq:addnedatpair}
\end{equation}
by applying the formula~(\ref{eq:solsecri}) to~(\ref{eq:addnedatpair}). Let $\mb{\bm$x$}_{k+1}$ denote the least squares solution to the above problem. Then, we have
\begin{equation}
\mb{\bm$x$}_{k+1}=\left( \left[\begin{array}{c}
\mb{\bm$A$}\\
\mb{\bm$a$}_{k+1}^{\top}
\end{array}\right]^{\top}\left[\begin{array}{c}
\mb{\bm$A$}\\
\mb{\bm$a$}_{k+1}^{\top}
\end{array}\right]\right)^{-1}\left[\begin{array}{c}
\mb{\bm$A$}\\
\mb{\bm$a$}_{k+1}^{\top}
\end{array}\right]^{\top}\left[\begin{array}{c}
\mb{\bm$b$}\\
b_{k+1}
\end{array}\right].
\label{eq:heaonapplse}
\end{equation}
In the case of large $k$ the above method of recomputing the new least squares solution from scratch may be time consuming. We present a recursive method of computing least squares solutions\index{least squares solution!recursive method} as the data pairs become available. To proceed, let
\begin{equation}
\mb{\bm$P$}_k=\left(\mb{\bm$A$}^{\top}\mb{\bm$A$} \right)^{-1}.
\label{eq:nofopkrlse}
\end{equation}
In view of the above, we can write
\begin{eqnarray}
\mb{\bm$P$}_{k+1}^{-1} &=& \left[\begin{array}{c}
\mb{\bm$A$}\\
\mb{\bm$a$}_{k+1}^{\top}
\end{array}\right]^{\top}\left[\begin{array}{c}
\mb{\bm$A$}\\
\mb{\bm$a$}_{k+1}^{\top}
\end{array}\right]\nonumber\\
&=& \left[\begin{array}{cc}
\mb{\bm$A$}^{\top} &\mb{\bm$a$}_{k+1}
\end{array}\right]\left[\begin{array}{c}
\mb{\bm$A$}\\
\mb{\bm$a$}_{k+1}^{\top}
\end{array}\right]\nonumber\\
&=&\mb{\bm$A$}^{\top}\mb{\bm$A$}+\mb{\bm$a$}_{k+1}\mb{\bm$a$}_{k+1}^{\top}\nonumber\\
&=& \mb{\bm$P$}_k^{-1}+\mb{\bm$a$}_{k+1}\mb{\bm$a$}_{k+1}^{\top}.
\label{eq:pkponrlse}
\end{eqnarray}
Hence,
\[
\mb{\bm$P$}_{k+1}=\left( \mb{\bm$P$}_k^{-1}+\mb{\bm$a$}_{k+1}\mb{\bm$a$}_{k+1}^{\top} \right)^{-1}.
\]
Applying to the above the matrix inversion formula~(\ref{eq:specialsmw})\index{matrix inversion formula}, we obtain
\begin{equation}
\fbox{$\displaystyle \mb{\bm$P$}_{k+1}=\mb{\bm$P$}_{k}-\frac{\mb{\bm$P$}_{k}\mb{\bm$a$}_{k+1}\mb{\bm$a$}^{\top}_{k+1}\mb{\bm$P$}_{k}}{1+\mb{\bm$a$}^{\top}_{k+1}\mb{\bm$P$}_{k}\mb{\bm$a$}_{k+1}} $}
\label{eq:exfopkporlse}
\end{equation}
Using~(\ref{eq:nofopkrlse}), we write
\begin{eqnarray}
\mb{\bm$x$}_k &=& \left( \mb{\bm$A$}^{\top}\mb{\bm$A$}\right)^{-1}\mb{\bm$A$}^{\top}\mb{\bm$b$}\nonumber\\
&=&\mb{\bm$P$}_k\mb{\bm$A$}^{\top}\mb{\bm$b$}.
\label{eq:exfoxsta}
\end{eqnarray}
Using~(\ref{eq:pkponrlse}), we can write
\begin{eqnarray}
\mb{\bm$x$}_{k+1} &=& \left( \left[\begin{array}{c}
\mb{\bm$A$}\\
\mb{\bm$a$}_{k+1}^{\top}
\end{array}\right]^{\top}\left[\begin{array}{c}
\mb{\bm$A$}\\
\mb{\bm$a$}_{k+1}^{\top}
\end{array}\right]\right)^{-1}\left[\begin{array}{c}
\mb{\bm$A$}\\
\mb{\bm$a$}_{k+1}^{\top}
\end{array}\right]^{\top}\left[\begin{array}{c}
\mb{\bm$b$}\\
b_{k+1}
\end{array}\right]\nonumber\\
&=&\mb{\bm$P$}_{k+1}\left(\mb{\bm$A$}^{\top}\mb{\bm$b$}+\mb{\bm$a$}_{k+1}b_{k+1}\right).
\label{eq:exfoxpluone}
\end{eqnarray}
Computing $\mb{\bm$A$}^{\top}\mb{\bm$b$}$ from~(\ref{eq:exfoxsta}), we get
\begin{equation}
\mb{\bm$A$}^{\top}\mb{\bm$b$}=\mb{\bm$P$}_k^{-1}\mb{\bm$x$}_k.
\label{eq:atrab}
\end{equation}
Substituting the above into~(\ref{eq:exfoxpluone}) yields
\begin{equation}
\mb{\bm$x$}_{k+1} =\mb{\bm$P$}_{k+1}\left( \mb{\bm$P$}_k^{-1}\mb{\bm$x$}_k + \mb{\bm$a$}_{k+1}b_{k+1} \right).
\label{eq:sorlse}
\end{equation}
Computing $\mb{\bm$P$}_k^{-1}$ from~(\ref{eq:pkponrlse}) gives
\[
\mb{\bm$P$}_k^{-1}= \mb{\bm$P$}_{k+1}^{-1}-\mb{\bm$a$}_{k+1}\mb{\bm$a$}_{k+1}^{\top}
\]
Substituting the above into~(\ref{eq:sorlse}) we have
\begin{equation}
\mb{\bm$x$}_{k+1}=\mb{\bm$P$}_{k+1}\left( \left( \mb{\bm$P$}_{k+1}^{-1}-\mb{\bm$a$}_{k+1}\mb{\bm$a$}_{k+1}^{\top}\right)\mb{\bm$x$}_k + \mb{\bm$a$}_{k+1}b_{k+1} \right).
\label{eq:exfoxkpluon}
\end{equation}
Taking into account that $\b a^{\top}_{k+1}\b x_k$ is a scalar while performing simple manipulations, we obtain
\begin{equation}
\fbox{$\displaystyle \mb{\bm$x$}_{k+1}= \mb{\bm$x$}_k + \left(b_{k+1}-\mb{\bm$a$}^{\top}_{k+1}\mb{\bm$x$}_k \right)\b P_{k+1}\b a_{k+1} $}
\label{eq:fiexfoxkplon}
\end{equation}
The two equations~(\ref{eq:exfopkporlse}) and~(\ref{eq:fiexfoxkplon}) constitute the {\em recursive least squares\/}~(RLS) algorithm.\index{recursive least squares (RLS)}\index{RLS|see{recursive least squares}} To initialize the RLS, we can set
\[
\mb{\bm$P$}_0=\left(\mb{\bm$A$}_n^{\top}\mb{\bm$A$}_n\right)^{-1}\quad\mb{and}\quad \mb{\bm$x$}_0=\mb{\bm$P$}_n\mb{\bm$A$}_n^{\top}\mb{\bm$b$}_n,
\]
where the pair $\left( \mb{\bm$A$}_n;\mb{\bm$b$}_n\right)$ represents the first $n$ data pairs.

\section{Contraction Maps}
%\section*{Contraction Maps}
%\addcontentsline{toc}{section}{Contraction Maps}

An operator $\b F$ that maps Euclidean space $\mb{\Bb R}^p$ into itself is called a {\em contraction map}\index{contraction map} if for any two elements $\b x$ and $\b y$ of $\mb{\Bb R}^p$,
\begin{equation}
\left\Arrowvert \b F(\b x)-\b F(\b y) \right\Arrowvert \le L\|\b x-\b y\|,\quad 0<L<1.
\label{eq:deoconmawccl}
\end{equation}
A point $\b x^{*} \in \mb{\Bb R}^p$ is called a {\em fixed point}\index{fixed point} if
\begin{equation}
\b F(\b x^{*})=\b x^{*}.
\label{eq:deoffipo}
\end{equation}
The importance of the contraction operators\index{contraction operator!unique fixed point} lies in the fact that there is a unique fixed point.\index{unique fixed point} Furthermore, this point may be found by successive iterations as stated in the following theorem.
\begin{thm}
\label{thm:contramap}
Let $\b F:\mb{\Bb R}^p \to \mb{\Bb R}^p$ be a contraction map with the contraction constant $0<L<1$. Then $\b F$ has a unique fixed point, and the sequence
\[
\b x^{(1)},\b x^{(2)},\ldots
\]
generated by $\b x^{(n+1)}=\b F\left(\b x^{(n)}\right)$, $n=0,1,2,\ldots$, converges to $\b x^{*}$ for any initial choice of $\b x^{(0)} \in \mb{\Bb R}^p$.
\end{thm}
{\bf Proof}\quad To show the uniqueness of the fixed point $\b x^{*}$, suppose that there exist two distinct fixed points $\b x^{*}$ and $\b y^{*}$. We then have
\begin{eqnarray*}
\left\Arrowvert \b x^{*} - \b y^{*}\right\Arrowvert &=& \left\Arrowvert \b F(\b x^{*}) - \b F(\b y^{*}) \right\Arrowvert \\
&\le& L\left\Arrowvert \b x^{*} - \b y^{*}\right\Arrowvert.
\end{eqnarray*}
Thus,
\[
\left\Arrowvert \b x^{*} - \b y^{*}\right\Arrowvert \le L\left\Arrowvert \b x^{*} - \b y^{*}\right\Arrowvert,\quad 0<L<1,
\]
which is impossible unless $\left\Arrowvert \b x^{*} - \b y^{*}\right\Arrowvert=0$. Hence, $\b x^{*}=\b y^{*}$ which means that $\b F$ has at most one fixed point.

We next show that a fixed point exists, and that the sequence
\[
\b x^{(1)},\b x^{(2)},\ldots
\]
generated by $\b x^{(n+1)}=\b F\left(\b x^{(n)}\right)$, $n=0,1,2,\ldots$, converges to $\b x^{*}$ for any initial choice of $\b x^{(0)} \in \mb{\Bb R}^p$. If $\b F\left(\b x^{(0)}\right)=\b x^{(0)}$, then the theorem is proved. In general $\b F\left(\b x^{(0)}\right)\ne\b x^{(0)}$. For any $n$, $m$ with $m>n$, we have
\begin{eqnarray}
\left\Arrowvert\b x^{(m)} - \b x^{(n)}\right\Arrowvert &=& \left\Arrowvert \b F^m\left(\b x^{(0)}\right) - \b F^n\left(\b x^{(0)}\right)\right\Arrowvert\nonumber\\
&=& \left\Arrowvert \b F\left(\b F^{m-1}\left(\b x^{(0)}\right)\right) - \b F\left(\b F^{n-1}\left(\b x^{(0)}\right)\right)\right\Arrowvert\nonumber\\
&\le& L\left\Arrowvert \b F^{m-1}\left(\b x^{(0)}\right) - \b F^{n-1}\left(\b x^{(0)}\right)\right\Arrowvert\nonumber\\
&\vdots&{}\nonumber\\
&\le&L^n\left\Arrowvert\b x^{(m-n)}-\b x^{(0)}\right\Arrowvert\nonumber\\
&=& L^n\left\Arrowvert\b x^{(0)}-\b x^{(m-n)}\right\Arrowvert.
\label{eq:xmmixnmgen}
\end{eqnarray}
We write
\begin{eqnarray}
\left\Arrowvert\b x^{(0)}-\b x^{(m-n)}\right\Arrowvert&=&\left\Arrowvert\b x^{(0)}-\b x^{(1)}+\b x^{(1)}-\b x^{(2)}+\b x^{(2)}-\right.\nonumber\\
&{}&\qquad \left.\cdots-\b x^{(m-n-1)}+\b x^{(m-n-1)}-\b x^{(m-n)}\right\Arrowvert.
\label{eq:xzemixmmin}
\end{eqnarray}
Substituting~(\ref{eq:xzemixmmin}) into~(\ref{eq:xmmixnmgen}) and then applying the triangle inequality yields
\begin{equation}
\left\Arrowvert\b x^{(m)}-\b x^{(n)}\right\Arrowvert\le L^n\left(\left\Arrowvert\b x^{(0)}-\b x^{(1)}\right\Arrowvert+\left\Arrowvert\b x^{(1)}-\b x^{(2)}\right\Arrowvert+\cdots+\left\Arrowvert\b x^{(m-n-1)}-\b x^{(m-n)}\right\Arrowvert \right).
\label{eq:xmmixnlesu}
\end{equation}
Observe that
\begin{eqnarray}
\left\Arrowvert\b x^{(j)}-\b x^{(j+1)}\right\Arrowvert&=&\left\Arrowvert\b F\left(\b x^{(j-1)}\right)-\b F\left(\b x^{(j)}\right)\right\Arrowvert\nonumber\\
&\le& L\left\Arrowvert\b x^{(j-1)}-\b x^{(j)}\right\Arrowvert\nonumber\\
&\vdots&{}\nonumber\\
&\le& L^j\left\Arrowvert\b x^{(0)}-\b x^{(1)}\right\Arrowvert,
\label{eq:xjmixjpole}
\end{eqnarray}
We use the above to further evaluate the right hand side of~(\ref{eq:xmmixnlesu}) to obtain
\begin{eqnarray*}
\left\Arrowvert\b x^{(m)}-\b x^{(n)}\right\Arrowvert &\le& L^n\left\Arrowvert\b x^{(0)}-\b x^{(1)}\right\Arrowvert\left( 1+L+\cdots+L^{m-n-1}\right)\\
&\le& L^n\left\Arrowvert\b x^{(0)}-\b x^{(1)}\right\Arrowvert\left( 1+L+\cdots+L^{m-n-1}+L^{m-n}+\cdots\right)\\
&=&\frac{L^n}{1-L}\left\Arrowvert\b x^{(0)}-\b x^{(1)}\right\Arrowvert
\end{eqnarray*}
because $0<L<1$. Recall that a sequence $\b x^{(0)},\b x^{(1)},\ldots $ is a Cauchy sequence if for each $\varepsilon>0$ there exists a positive integer $n=n(\varepsilon)$ such that $\left\Arrowvert\b x^{(m)}-\b x^{(n)}\right\Arrowvert<\varepsilon$ for all $m>n$. Given an $\varepsilon>0$, let $n$ be such that
\[
L^n < \frac{\varepsilon(1-L)}{\left\Arrowvert\b x^{(0)}-\b x^{(1)}\right\Arrowvert}.
\]
Then,
\begin{equation}
\left\Arrowvert\b x^{(m)}-\b x^{(n)}\right\Arrowvert \le \frac{L^n}{1-L}\left\Arrowvert\b x^{(0)}-\b x^{(1)}\right\Arrowvert <\varepsilon,\quad \mb{for all}\quad m>n.
\label{eq:mnlelnetc}
\end{equation}
Therefore, the sequence $\b x^{(0)},\b x^{(1)},\ldots$ is a Cauchy sequence,\index{Cauchy sequence} and we show that the limit $\b g$ of this sequence is the fixed point $\b x^{*}$ of the map $\b F$. Note that $\b F$ is uniformly continuous. Indeed, for each $\varepsilon >0$ there exists a $\delta=\delta(\varepsilon)$ such that if $\|\b x-\b y\| < \delta$, then $\left\Arrowvert\b F(\b x)-\b F(\b y)\right\Arrowvert <\varepsilon$. Since $\left\Arrowvert\b F(\b x)-\b F(\b y)\right\Arrowvert \le L\|\b x -\b y\|$, given an $\varepsilon>0$, we can choose $\delta=\varepsilon/L$. Because $F$ is continuous,
\[
\lim_{n\to \infty}\b F\left(\b x^{(n)}\right) = \b F\left( \lim_{n\to \infty}\b x^{(n)}\right)= \b F(\b g).
\]
However, $\b x^{(n+1)}=\b F\left(\b x^{(n)}\right)$. Therefore,
\begin{eqnarray*}
\b g &=& \lim_{n\to \infty}\b x^{(n+1)}\\
&=& \lim_{n \to \infty}\b F\left(\b x^{(n)}\right)\\
&=& \b F\left(\lim_{n\to \infty}\b x^{(n)} \right)\\
&=& \b F(\b g).
\end{eqnarray*}
Hence, $\b g=\b x^{*}$ is a fixed point of $\b F$, and the proof is complete.\\
\hspace*{5.5in}$\Box$

Using the above proof we can give an estimate of the norm\index{estimate of the norm}\index{norm!estimate of} of $\left\Arrowvert\b x^{(n)}-\b x^{*}\right\Arrowvert$. Indeed, if we fix $n$ in~(\ref{eq:mnlelnetc}) and allow $m\to \infty$, then
\begin{equation}
\left\Arrowvert\b x^{(n)}-\b x^{*}\right\Arrowvert\le \frac{L^n}{1-L}\left\Arrowvert\b x^{(0)}-\b F\left(\b x^{(0)}\right)\right\Arrowvert.
\label{eq:estiofnoer}
\end{equation}


\section{First-Order Differential Equation}
%\section*{First-Order Differential Equation}
%\addcontentsline{toc}{section}{First-Order Differential Equation}

Let $\mb{\Bb R}$ denote the set of real numbers and let $D\subseteq \mb{\Bb R}^2$ be a domain, that is, an open connected nonempty subset of $\mb{\Bb R}^2$. Let $f$ be a real valued function defined and continuous on $D$. Let $\dot{x}=dx/dt$ denote the derivative of $x$ with respect to $t$. We call
\begin{equation}
\dot{x}=f(t,x)
\label{eq:gefoode}
\end{equation}
an {\em ordinary differential equation of the first order}.\index{ordinary differential equation!of the first order} By a {\em solution\/} of the differential equation~(\ref{eq:gefoode})\index{differential equation!solution of}\index{solution of!differential equation} on an open interval $I=\{t\in \mb{\Bb R}:t_1<t<t_2\}$, we mean a real valued continuously differentiable function $\phi$ defined on $I$ such that $(t,\phi(t))\in D$ for all $t \in I$ and
\[
\dot{\phi}(t)=f(t,\phi(t))\quad\mb{for all}\quad t\in I.
\]
\begin{defn}
Given $(t_0,x_0)\in D$, the {\em initial value problem\/}\index{initial value problem} for~(\ref{eq:gefoode}) is
\begin{equation}
\dot{x}=f(t,x),\quad x(t_0)=x_0.
\label{eq:invaprofsto}
\end{equation}
\end{defn}\markdefn

A function $\phi$ is a solution to~(\ref{eq:invaprofsto}) if $\phi$ is a solution of the differential equation~(\ref{eq:gefoode}) on some interval $I$ containing $t_0$ and $x(t_0)=x_0$.

We can represent the initial value problem~(\ref{eq:invaprofsto}) equivalently by an integral equation,\index{integral equation}
\begin{equation}
\phi(t)=x_0+\int_{t_0}^{t} f(s,\phi(s)) ds.
\label{eq:eqreofinvpr}
\end{equation}
To prove this equivalence, let $\phi$ be a solution of the initial value problem~(\ref{eq:invaprofsto}).\index{initial value problem!solution of}\index{solution of!initial value problem} Then $x(t_0)=x_0$ and
\[
\dot{\phi}(t)=f(t,\phi(t))\quad\mb{for all}\quad t\in I.
\]
Integrating the above from $t_0$ to $t$, we obtain
\[
\int_{t_0}^{t} \dot{\phi}(s)ds = \int_{t_0}^{t} f(s,\phi(s)) ds.
\]
Hence,
\[
\phi(t)-x_0=\int_{t_0}^{t} f(s,\phi(s)) ds.
\]
Therefore, $\phi$ is a solution of the integral equation~(\ref{eq:eqreofinvpr}).

Conversely, let $\phi$ be a solution of the integral equation~(\ref{eq:eqreofinvpr}). Then $\phi(t_0)=x_0$, and differentiating both sides of~(\ref{eq:eqreofinvpr}) with respect to $t$ gives $\dot{\phi}(t)=f(t,\phi(t))$. Therefore, $\phi$ is also a solution of the initial value problem~(\ref{eq:invaprofsto}).


The general {\em ordinary differential linear equation of the first order\/}\index{ordinary differential linear equation!of the first order} has the form
\begin{equation}
\dot{x}(t)=a(t)x(t)+b(t), \qquad t \in (t_1,\; t_2),
\label{eq:first_ode}
\end{equation}
where $a(t)$ and $b(t)$ are assumed to be continuous on the interval $(t_1,\; t_2)$. We associate with equation~(\ref{eq:first_ode}) the initial condition\index{initial condition}
\[
x(t_0)=x_0, \qquad x_0 \in \mb{\Bb R}.
\]
To find the solution to~(\ref{eq:first_ode}), we write it in the form
\begin{equation}
\dot{x}(t)-a(t)x(t)=b(t).
\label{eq:first_next}
\end{equation}
We then multiply~(\ref{eq:first_next}) by the ``integrating factor''\index{integrating factor}
\begin{equation}
e^{-\int_{t_0}^{t}a(s)ds}
\label{eq:integrating_f}
\end{equation}
to get
\begin{equation}
\dot{x}(t)e^{-\int_{t_0}^{t}a(s)ds}-a(t)x(t)e^{-\int_{t_0}^{t}a(s)ds}=e^{-\int_{t_0}^{t}a(s)ds}b(t).
\label{eq:integrate_multi}
\end{equation}
The above equation can be represented in an equivalent form as
\begin{equation}
\frac{d}{dt}\left \{ x(t)e^{-\int_{t_0}^{t}a(s)ds}\right \}=e^{-\int_{t_0}^{t}a(s)ds}b(t).
\label{eq:first_equi}
\end{equation}
Integrating both sides of~(\ref{eq:first_equi}) yields
\begin{equation}
x(t)e^{-\int_{t_0}^{t}a(s)ds}-x_0=\int_{t_0}^{t}e^{-\int_{t_0}^{\tau}a(s)ds}b(\tau )d\tau .
\end{equation}
Hence,
\begin{equation}
x(t)=e^{\int_{t_0}^{t}a(s)ds}\left [x_0+\int_{t_0}^{t}e^{-\int_{t_0}^{\tau}a(s)ds}b(\tau )d\tau \right ],
\end{equation}
or in an equivalent form
\begin{equation}
\fbox{$\displaystyle x(t)=e^{\int_{t_0}^{t}a(s)ds}x_0+\int_{t_0}^{t}e^{\int_{\tau }^{t}a(s)ds}b(\tau )d\tau $}
\label{eq:first_soln}
\end{equation}


\section{Integral and Differential Inequalities}
%\section*{Integral and Differential Inequalities}
%\addcontentsline{toc}{section}{Integral and Differential Inequalities}
\subsection{The Bellman-Gronwall Lemma}
%\subsection*{The Bellman-Gronwall Lemma}
%\addcontentsline{toc}{subsection}{The Bellman-Gronwall Lemma}

\begin{lemma}
\label{lem:bellgron}
Let $v(t)$ and $w(t)$ be continuous real functions of $t$. Let $w(t) \ge 0$, and $c$ be a real constant. If
\begin{equation}
v(t) \le c+\int_{0}^{t}w(s)v(s)ds,
\label{eq:v_func_l}
\end{equation}
then\index{Bellman-Gronwall lemma}
\begin{equation}
v(t) \le ce^{\int_{0}^{t}w(s)ds}.
\end{equation}
\end{lemma}
{\bf Proof}\quad Denote the right-hand side of~(\ref{eq:v_func_l}) by $x(t)$, that is, let
\begin{equation}
x(t)=c+\int_{0}^{t}w(s)v(s)ds,
\label{eq:x_defnit}
\end{equation}
and let
\begin{equation}
z(t)=x(t)-v(t).
\label{eq:z_defn}
\end{equation}
Note that $z(t) \ge 0$, and $x(t)$ is differentiable. Differentiating both sides of~(\ref{eq:x_defnit}) and using~(\ref{eq:z_defn}) yields
\begin{eqnarray}
\dot{x}(t)&=&w(t)v(t)\nonumber\\
&=&w(t)x(t)-w(t)z(t).
\label{eq:xwvz}
\end{eqnarray}
We use~(\ref{eq:first_soln}) to represent~(\ref{eq:xwvz}) in the equivalent integral form\index{equivalent integral form} as
\begin{equation}
x(t)=e^{\int_{0}^{t}w(s)ds}x_0-\int_{0}^{t}e^{\int_{\tau }^{t}w(s)ds}w(\tau )z(\tau )d\tau .
\label{eq:xwvz_equi}
\end{equation}
Since $z(t) \ge 0$ and $w(t) \ge 0$, we have
\begin{equation}
x(t) \le e^{\int_{0}^{t}w(s)ds}x_0.
\end{equation}
From the definition of $x(t)$ given by~(\ref{eq:x_defnit}), we have $x(0)=c$. Since
\begin{equation}
v(t)=x(t)-z(t) \le x(t),
\end{equation}
because $z(t) \ge 0$, hence,
\[
v(t) \le ce^{\int_{0}^{t}w(s)ds},
\]
and the proof is completed.\\
\hspace*{5.5in} $\Box$

The generalized Bellman-Gronwall lemma\index{Bellman-Gronwall lemma} allows us to convert the investigation of integral equations\index{integral equations} into integral inequalities.\index{integral inequalities}

\subsection{A Comparison Theorem}
%\subsection*{A Comparison Theorem}
%\addcontentsline{toc}{subsection}{A Comparison Theorem}
\label{subsec:comparison}

We state and prove a theorem that allows one to reduce the study of some problems involving differential equations to the study of corresponding problems using differential inequalities instead.

We consider the differential inequality,\index{differential inequality}
\[
\dot{x}(t) \le \omega(t,x(t)),\qquad x(t_0)=x_0,
\]
where $\omega : \mb{\Bb R}^2 \to \mb{\Bb R}$ is a continuous function in a domain $\Delta \subset \mb{\Bb R}^2$. We assume that in $\Delta$, the function $\omega$ satisfies the Lipschitz condition,\index{Lipschitz condition}
\[
|\omega (t,x) - \omega (t,y)| \le L|x-y|,
\]
where $L\ge 0$ is a Lipschitz constant.\index{Lipschitz constant} Consider an associated differential equation
\[
\dot{\tilde{x}}(t) = \omega(t,\tilde{x}(t)),\qquad \tilde{x}(t_0)=\tilde{x}_0.
\]
We refer to the above equation as the {\em equation of comparison}.\index{equation of comparison} Denote the solution to the equation of comparison by
\[
\tilde{x}(t)=\tilde{x}(t;t_0,\tilde{x}_0).
\]
The following theorem, that can be found, for example, in Corduneanu~\cite[page 49]{corduneanu71}, relates the solutions of the differential inequality and the associated differential equation.
\begin{thm}
\label{thm:comparison}
If $x(t)$ is a differentiable solution to the differential inequality and $\tilde{x}(t)$ is the solution to the associated differential equation with the corresponding initial conditions such that
\[
x_0 \le \tilde{x}_0,
\]
then
\[
x(t) \le \tilde{x}(t)
\]
for all $t \ge t_0$.
\end{thm}
{\bf Proof}\quad We prove the theorem by contradiction. We suppose that $x_0 \le \tilde{x}_0$ but $x(t) \le \tilde{x}(t)$ does not hold. Thus, there exists $t_1 > t_0$ such that
\[
x(t_1) > \tilde{x}(t_1).
\]
Let
\[
y(t)=x(t)-\tilde{x}(t).
\]
Note that $y(t_0)=x(t_0)-\tilde{x}(t_0) \le 0$, and $y(t_1)=x(t_1)-\tilde{x}(t_1) > 0$. Denote by $\tau$ the largest $t \in \left[ t_0, \, t_1 \right]$ such that $y(\tau) = 0$. Such a value of $t$ exists by virtue of the continuity of $y$. Thus,
\[
y(t) > 0 \quad \mbox{for all} \quad t \in \left( \tau, t_1 \right].
\]
On the other hand, for $t \in \left[ \tau, t_1 \right]$, we have
\begin{eqnarray*}
\dot{y}(t) &=& \dot{x}(t)-\dot{\tilde{x}}(t)\\
&\le& \omega (t,x(t)) - \omega (t, \tilde{x}(t))\\
&\le& |\omega (t,x(t)) - \omega (t, \tilde{x}(t))|\\
&\le& L|x(t)-\tilde{x}(t)|.
\end{eqnarray*}
In the interval $\left[ \tau, t_1 \right]$, we have
\[
y(t)=x(t)-\tilde{x}(t) \ge 0.
\]
Hence,
\begin{eqnarray*}
\dot{y}(t) &\le& L|x(t)-\tilde{x}(t)|\\
&=& L(x(t)-\tilde{x}(t))\\
&=& Ly(t).
\end{eqnarray*}
Therefore, in the interval $\left[ \tau, t_1 \right]$, the function $y$ satisfies
\[
y(t) \le y( \tau )e^{L(t - \tau )} = 0
\]
since $y(\tau) = 0$. But this is a contradiction to the previous conclusion that $y(t) > 0$ for all $t \in \left( \tau, t_1 \right]$, which completes the proof.\\
\hspace*{5.5in} $\Box$

\section{The Laplace Transform}
%\section*{The Laplace Transform}
%\addcontentsline{toc}{section}{The Laplace Transform}
\label{sec:laplace_t}

%\section{Definition}
The Laplace transform\index{Laplace transform} is an operator that transforms a function of time, $f(t)$, into a new function of complex variable, $F(s)$, where $s=\sigma+j\omega$, as illustrated in Figure~\ref{fig:l_tans}. The operator ${\cal L}$ denotes that the time function $f(t)$ has been transformed to its Laplace transform, denoted $F(s)$.
\begin{figure}[h]
\setlength{\unitlength}{.1in}
\begin{center}
\begin{picture}(60,20)
\thicklines
\put(14,9){\vector(1,0){8}}
\put(16,10){$f(t)$}
\put(22,5){\framebox(10,8){$\cal{L}$}}
\put(32,9){\vector(1,0){12}}
\put(33,10){$F(s)={\cal L}(f(t))$}
\end{picture}
\end{center}
\caption{Schematic representation of the Laplace transform operator.}
\label{fig:l_tans}
\end{figure}
The Laplace transform is very useful in solving linear differential equations\index{Laplace transform!solving linear differential equations} and hence in analyzing control systems.

To obtain the Laplace transform of the given function of time, $f(t)$,
\begin{enumerate}
\item multiply $f(t)$ by a converging factor\index{converging factor} $e^{-st}$. This is a factor that decreases to zero as time increases to infinity;
\item Integrate $f(t)e^{-st}$ with respect to time between the limits $0^{-}$ and $\infty$ to obtain the Laplace transform of $f(t)$,
\[
\fbox{$\displaystyle F(s)={\cal L}(f(t))=\int_{0^{-}}^{\infty}f(t)e^{-st}dt $}
\]
\end{enumerate}
The lower limit of integration is $0^{-}$, rather than $0$, to account for the effect of ``instantaneous energy transfer,'' for example, in electric circuits that contain inductors or capacitors.\index{instantaneous energy transfer}


The above definition of the Laplace transform is also referred to as the {\em one-sided} or {\em unilateral} Laplace transform.\index{Laplace transform!unilateral}\index{Laplace transform!one-sided} In the two-sided, or bilateral, Laplace transform,\index{Laplace transform!bilateral}\index{Laplace transform!two-sided} the lower limit is $-\infty$. For our purposes the one-sided Laplace transform is sufficient.

If we wish to reverse the operation and take the inverse transform, back to the time domain, we write
\[
{\cal L}^{-1}(F(s))=f(t).
\]
Taking the inverse Laplace transform\index{inverse Laplace transform} is illustrated in Figure~\ref{fig:invl_tans}.
\begin{figure}
\setlength{\unitlength}{.1in}
\begin{center}
\begin{picture}(60,20)
\thicklines
\put(14,9){\vector(1,0){8}}
\put(16,10){$F(s)$}
\put(22,5){\framebox(10,8){${\cal{L}}^{-1}$}}
\put(32,9){\vector(1,0){12}}
\put(33,10){$f(t)={\cal L}^{-1}(F(s))$}
\end{picture}
\end{center}
\caption{Schematic representation of the inverse Laplace transform operation.}
\label{fig:invl_tans}
\end{figure}

Because we are using the one-sided Laplace transform, we define all functions, whose Laplace transforms we compute, to be zero for $t<0^{-}$. To proceed, we recall the definition of the unit step function denoted $1(t)$,\index{unit step function!denoted $1(t)$}
\[
1(t)=\left\{\begin{array}{ccc}
1&\mb{if}& t\ge0\\
0&\mb{if}& t<0.
\end{array}  \right.
\]
The unit step function is also called the Heaviside function.\index{Heaviside function|see{unit step function}}
\begin{example}\rm
Find the Laplace transform of
\[
f(t)=e^{-at}1(t),
\]
where $a$ is a real constant. A graph of $f(t)$ for $a=3$ is shown in Figure~\ref{fig:expzero}.
\begin{figure}
\centering
\includegraphics[scale=0.5]{expzero.eps}
%\vspace{3.5in}
%\centerbmp{4.67in}{3.5in}{c:/ee202/expzero.bmp}
%\hskip1in\special{bmp:c:/ee202/expzero.bmp x=4.67  y=3.5in}
\caption{A plot of $e^{-3t}1(t)$.}
\label{fig:expzero}
\end{figure}
We have
\[
{\cal L}(e^{-at}1(t))=\int_{0^{-}}^{\infty}e^{-at}e^{-st}1(t)dt = \int_{0^{-}}^{\infty}e^{-(a+s)t}dt.
\]
The above integral exists if
\[
\Re(a+s)>0.
\]
The region of the $s$-plane for which the Laplace transform exists is called the {\em Region of Convergence}\index{Region of Convergence (ROC)} and abbreviated ROC.\index{ROC|see{Region of Convergence}} Since $s=\sigma+j\omega$, the ROC, in our example, is the region in the $s$-plane where
\[
0<\Re(a+s)=\Re(a+\sigma+j\omega)=a+\sigma,
\]
that is, the region where $\sigma>-a$. Proceeding with the integration, we obtain
\begin{eqnarray*}
{\cal L}(e^{-at}1(t))&=& \left. \left( -\frac{1}{a+s}e^{-(a+s)t}\right)\right\arrowvert_{0^{-}}^{\infty}\\
&=& \left( -\frac{1}{a+s}e^{-(a+s)\infty}\right)-\left( -\frac{1}{a+s}e^{-(a+s)0^{-}}\right).
\end{eqnarray*}
For $s$ in the ROC, the first term tends to zero. Hence,
\[
\fbox{$\displaystyle {\cal L}(e^{-at}1(t))=\frac{1}{s+a}$}
\]
\end{example}
\markex
Using the Laplace transform of the exponential function,\index{Laplace transform!of the exponential function} we can easily find the Laplace transform of the unit step.\index{Laplace transform!of the unit step} Indeed, if $a=0$, then $f(t)=e^{-at}1(t)=1(t)$. Hence,
\begin{equation}
\fbox{$\displaystyle {\cal L}(1(t))=\frac{1}{s}$}
\label{eq:latrast}
\end{equation}


\subsection{Linearity Property of the Laplace Transform}
%\subsection*{Linearity Property of the Laplace Transform}
%\addcontentsline{toc}{subsection}{Linearity Property of the Laplace Transform}



The Laplace transform of the sum, or difference, of two functions of time is equal to the sum, or difference, of the transforms of each function, that is,
\begin{equation}
{\cal L}\left( f_1(t)\pm f_2(t)\right)={\cal L}\left( f_1(t)\right)\pm {\cal L}\left(f_2(t)\right)
\label{eq:sumoflapltr}
\end{equation}
Indeed,
\begin{eqnarray*}
{\cal L}\left( f_1(t)\pm f_2(t)\right)&=&\int_{0^{-}}^{\infty}\left( f_1(t)\pm f_2(t)\right)e^{-st}dt\\
&=& \int_{0^{-}}^{\infty} f_1(t)e^{-st}dt\pm \int_{0^{-}}^{\infty} f_2(t)e^{-st}dt\\
&=& {\cal L}\left( f_1(t)\right)\pm{\cal L}\left( f_2(t)\right).
\end{eqnarray*}
The Laplace transform of the product of a real or complex constant $K$ and a time function $f(t)$ is equal to the product of the constant and the transform of the time function, that is,
\begin{equation}
{\cal L}\left( Kf(t)\right)=K{\cal L}\left( f(t)\right).
\label{eq:proconslap}
\end{equation}
Indeed,
\[
{\cal L}\left( Kf(t)\right)= \int_{0^{-}}^{\infty}K f(t)e^{-st}dt
= K\int_{0^{-}}^{\infty} f(t)e^{-st}dt
= K{\cal L}\left( f(t)\right).
\]
The above two properties can be represented in the form
\[
\fbox{$\displaystyle {\cal L}\left(K f_1(t)\pm f_2(t)\right)=K{\cal L}\left( f_1(t)\right)\pm {\cal L}\left(f_2(t)\right) $}
\]
Thus the Laplace transform is a linear operator.\index{Laplace transform!linear operator}
\begin{example}\rm
To find the Laplace transform of
\[
f(t)=K1(t),
\]
where $K$ is a constant, we can use~(\ref{eq:proconslap}) and the Laplace transform of the unit step, given by~(\ref{eq:latrast}), to obtain
\[
{\cal L}\left(K1(t) \right)=K{\cal L}\left(1(t) \right)=\frac{K}{s}.
\]
\end{example}\markex
\begin{example}\rm
We use the linear property of the Laplace transform to find the Laplace transform of
\[
f(t)=\sin \omega t.
\]
First, recall the Euler formula,\index{Euler formula}
\[
e^{j\omega t}=\cos \omega t+ j\sin \omega t.
\]
Hence,
\[
e^{-j \omega t}=\cos \omega t- j\sin \omega t.
\]
Subtracting the second of the above expressions from the first one and dividing the result by $2j$ gives
\[
\sin \omega t=\frac{e^{j\omega t}-e^{-j \omega t}}{2j} .
\]
Therefore,
\[
{\cal L}\left( \sin \omega t\right)= {\cal L}\left( \frac{e^{j\omega t}-e^{-j \omega t}}{2j} \right)
= {\cal L}\left( \frac{1}{2j}\left(e^{j\omega t}-e^{-j \omega t}\right) \right).
\]
Applying to the above~(\ref{eq:proconslap}) yields
\[
{\cal L}\left( \sin \omega t\right)=\frac{1}{2j}{\cal L}\left( e^{j\omega t}-e^{-j \omega t}\right).
\]
Applying now~(\ref{eq:sumoflapltr}), we obtain
\[
{\cal L}\left( \sin \omega t\right)=\frac{1}{2j}\left({\cal L}\left( e^{j\omega t}\right)-{\cal L}\left(e^{-j \omega t}\right)\right).
\]
We then use twice the formula for the Laplace transform of the exponential to get
\[
{\cal L}\left( \sin \omega t\right)=\frac{1}{2j}\left(\frac{1}{s-j\omega}-\frac{1}{s+j \omega} \right).
\]
Performing algebraic manipulations gives
\[
\fbox{$ \displaystyle {\cal L}\left( \sin \omega t\right)= \frac{\omega}{s^2+\omega^2} $}
\]
\end{example}
\markex
Similarly, we obtain
\[
{\cal L}\left( \cos \omega t\right)= {\cal L}\left( \frac{e^{j\omega t}+e^{-j \omega t}}{2} \right).
\]
Hence,
\[
\fbox{$ \displaystyle {\cal L}\left( \cos \omega t\right)= \frac{s}{s^2+\omega^2} $}
\]


\subsection{Laplace Transforms of Derivatives}
%\subsection*{Laplace Transforms of Derivatives}
%\addcontentsline{toc}{subsection}{Laplace Transforms of Derivatives}


We will now show that
\[
\fbox{$ \displaystyle {\cal L}\left( \frac{df(t)}{dt}\right)= sF(s)-f\left( 0^{-}\right) $}
\]
where $F(s)={\cal L}(f(t))$ and $f\left( 0^{-}\right)$ is the initial value of $f$, that is, the value of $f$ at $0^{-}$.\index{Laplace transform!of derivatives} Thus, differentiating in the time domain corresponds to multiplying $F(s)$ by $s$ and then subtracting the initial value of $f(t)$. To derive the above formula, we apply the definition of the Laplace transform,
\begin{equation}
{\cal L}\left( \frac{df(t)}{dt}\right)=\int_{0^{-}}^{\infty} \frac{df(t)}{dt}e^{-st}dt,
\label{laptotider}
\end{equation}
and then evaluate the integral by integrating by parts.\index{integrating by parts} Recall that the formula for integrating by parts can easily be derived from the formula for the derivative of the product of two functions. We use the notation,
\[
u'=\frac{du(t)}{dt}.
\]
Then, we have
\[
\left( uv\right)'=u'v+uv'.
\]
Integrating the above and rearranging gives
\begin{equation}
\int u'v=uv-\int uv'.
\label{eq:forfintbpar}
\end{equation}
We let
\[
u'=\frac{df}{dt}\quad\mb{and}\quad v=e^{-st}.
\]
Then applying~(\ref{eq:forfintbpar}) to~(\ref{laptotider}), we obtain
\[
{\cal L}\left( \frac{df(t)}{dt}\right)=\left.e^{-st}f(t)\right\arrowvert_{0^{-}}^{\infty}-\int_{0^{-}}^{\infty}f(t)\left(-se^{-st}\right)dt.
\]
Assuming that $f(t)$ is Laplace transformable,\index{Laplace transformable!function}\index{function!Laplace transformable} the value of $e^{-st}f(t)$ at $t=\infty$ is zero. Hence, the right-hand side of the above reduces to
\[
{\cal L}\left( \frac{df(t)}{dt}\right)=-f\left( 0^{-}\right)+s\int_{0^{-}}^{\infty}f(t)e^{-st}dt=sF(s)-f\left( 0^{-}\right).
\]
Thus, we showed that differentiation in the time domain corresponds to an algebraic operation in the $s$ domain.

Using the Laplace transform of the first derivative\index{Laplace transform!of higher-order derivatives} of a time function, we can easily determine the Laplace transform of higher-order derivatives. Indeed, to find the Laplace transform of $\frac{d^2f(t)}{dt^2}$, we let
\[
g(t)=\frac{df(t)}{dt}.
\]
Then,
\begin{equation}
{\cal L}(g(t))=G(s)={\cal L}\left( \frac{df(t)}{dt}\right)=sF(s)-f\left( 0^{-}\right).
\label{eq:laptraofinvag}
\end{equation}
Note that
\[
\frac{d^2f(t)}{dt^2}=\frac{dg(t)}{dt}.
\]
Hence,
\[
{\cal L}\left( \frac{df^2(t)}{dt^2}\right)= {\cal L}\left( \frac{dg(t)}{dt}\right) = sG(s)-g\left( 0^{-}\right).
\]
Substituting into the above~(\ref{eq:laptraofinvag}) gives
\[
{\cal L}\left( \frac{df^2(t)}{dt^2}\right)=s\left( sF(s)-f\left( 0^{-}\right)\right)-g\left( 0^{-}\right).
\]
Observing that $g\left( 0^{-}\right)=\frac{df\left(0^{-} \right)}{dt}$, we get
\[
\fbox{$\displaystyle {\cal L}\left( \frac{df^2(t)}{dt^2}\right)=s^2F(s)-sf\left( 0^{-}\right)-\frac{df\left(0^{-} \right)}{dt} $}
\]
Successively applying the above arguments, we can obtain the Laplace transform of the $n$-th time derivative,
\[
\fbox{$\displaystyle {\cal L}\left( \frac{df^n(t)}{dt^n}\right)=s^nF(s)-s^{n-1}f\left( 0^{-}\right)-s^{n-2}\frac{df\left(0^{-} \right)}{dt}-\cdots -s\frac{d^{n-2}f\left(0^{-} \right)}{dt^{n-2}}-\frac{d^{n-1}f\left(0^{-} \right)}{dt^{n-1}} $}
\]

\subsection{Solving Differential Equations Using Laplace Transform}
%\subsection*{Solving Differential Equations Using Laplace Transform}
%\addcontentsline{toc}{subsection}{Solving Differential Equations Using Laplace Transform}


We now illustrate how to use the Laplace transform and inverse Laplace transform to solve linear ordinary differential equations.\index{Laplace transform!to solve linear ordinary differential equations} After taking the Laplace transform of both sides of a differential equation and performing required manipulations in the $s$ domain, we need to reconstruct the solution in the time domain. This is achieved using the inverse Laplace transform.
\begin{example}\rm
We will solve the following differential equation using the Laplace transform,
\[
2\frac{d^2x(t)}{dt^2}+7\frac{dx(t)}{dt}+5x(t)=10\times 1(t),
\]
subject to the initial conditions
\[
\frac{dx\left(0^{-} \right)}{dt}=1, \quad x\left( 0^{-}\right)=-2,
\]
where $1(t)$ is the unit step function.

We take the Laplace transform of both sides of the differential equation to get
\[
2{\cal L}\left( \frac{d^2x(t)}{dt^2}\right)+7{\cal L}\left( \frac{dx(t)}{dt}\right)+5{\cal L}\left( x(t)\right)=10{\cal L}\left( 1(t)\right).
\]
Using Laplace transforms of time derivatives\index{Laplace transform!of time derivatives} of a function of time and the Laplace transform of the unit step function, we obtain
\[
2\left(s^2X(s)-sx\left(0^{-} \right)-\frac{dx\left(0^{-} \right)}{dt}\right)+7\left( sX(s)-x\left(0^{-} \right)\right)+5X(s)=\frac{10}{s}.
\]
Substituting into the above the initial conditions and rearranging gives
\[
\left(2s^2+7s+5 \right)X(s)=\frac{10}{s}-4s-12=\frac{10-4s^2-12s}{s}.
\]
Hence,
\begin{equation}
X(s)=\frac{-4s^2-12s+10}{s\left( 2s^2+7s+5\right)}=\frac{-2s^2-6s+5}{s\left( s^2+3.5s+2.5\right)}=\frac{-2s^2-6s+5}{s\left( s+2.5\right)\left(s+1 \right)}.
\label{eq:xinsdooode}
\end{equation}
We now need to reconstruct the solution of the differential equation in the time domain. In other words, given $X(s)$ we wish to obtain $x(t)$ in which $x(t)$ is zero for $t<0$ such that $X(s)={\cal L}(x(t))$. Thus,
\[
x(t)={\cal L}^{-1}\left( X(s)\right).
\]
To proceed, note that $X(s)$ as given by~(\ref{eq:xinsdooode}) is a rational function\index{rational function!strictly proper} of $s$, that is, $X(s)$ is a ratio of two polynomials in $s$, in which the degree of the numerator\index{degree!of numerator} with respect to $s$ is smaller than the degree of the denominator.\index{degree!of denominator} Such a rational function is called strictly proper and can be expanded into a sum of partial fractions by writing a term or a series of terms for each zero of the denominator. We obtain
\begin{equation}
X(s)=\frac{K_1}{s}+\frac{K_2}{s+2.5}+\frac{K_3}{s+1}.
\label{eq:xoswikis}
\end{equation}
We next compute the constants $K_i$'s. We can do so by representing the right-hand side of the above as a rational function and then comparing the resulting numerator with the numerator of~(\ref{eq:xinsdooode}). We represent~(\ref{eq:xoswikis}) as
\begin{eqnarray}
X(s)&=&\frac{K_1\left( s+2.5\right)\left(s+1 \right)+K_2 s\left(s+1\right)+K_3 s\left(s+2.5\right)}{s\left( s+2.5\right)\left(s+1 \right)}\nonumber\\
&=& \frac{\left( K_1+K_2+K_3\right)s^2+\left( 3.5K_1+K_2+2.5K_3\right)s+ 2.5K_1 }{s\left( s+2.5\right)\left(s+1 \right)}
\label{eq:lcdwitks}
\end{eqnarray}
Comparing coefficients of like powers of the numerators of~(\ref{eq:xinsdooode}) and~(\ref{eq:lcdwitks}) gives three algebraic equations in three unknowns,
\[
\left.\begin{array}{rcl}
K_1+K_2+K_3&=&-2\\
3.5K_1+K_2+2.5 K_3 &=& -6\\
5&=& 2.5K_1
\end{array}\right\}
\]
Solving the above system of equations gives
\[
K_1=2,\quad K_2=2,\quad K_3=-6.
\]
Substituting the above into~(\ref{eq:xoswikis}) yields
\[
X(s)=\frac{2}{s}+\frac{2}{s+2.5}-\frac{6}{s+1}.
\]
Applying the inverse Laplace transform to the above, we obtain
\begin{eqnarray*}
x(t)&=&{\cal L}\left( \frac{2}{s}+\frac{2}{s+2.5}-\frac{6}{s+1}\right)\\
&=&{\cal L}\left( \frac{2}{s}\right)+{\cal L}\left(\frac{2}{s+2.5}\right)-{\cal L}\left(\frac{6}{s+1}\right)\\
&=&\left(2+2e^{-2.5t}-6e^{-t} \right)1(t).
\end{eqnarray*}
\end{example}
\markex
%As in the above simple example, we will often need to find the inverse %Laplace transform of a rational function,
%\[
%F(s)=\frac{N(s)}{D(s)}=
%\]


\subsection{Laplace Transforms of Integrals}
%\subsection*{Laplace Transforms of Integrals}
%\addcontentsline{toc}{subsection}{Laplace Transforms of Integrals}


We first consider taking the Laplace transform\index{Laplace transform!of integrals} of
\begin{equation}
\int_{0^{-}}^{t} f(x)dx.
\label{eq:intomtin}
\end{equation}
Let $F(s)$ denote the Laplace transform of $f(t)$, that is, $F(s)={\cal L}(f(t))$. We find the Laplace transform of~(\ref{eq:intomtin}) using integration by parts to obtain
\begin{equation}
{\cal L}\left( \int_{0^{-}}^{t} f(x)dx\right)=\int_{0^{-}}^{\infty} \left( \int_{0^{-}}^{t} f(x)dx\right)e^{-st}dt.
\label{eq:firsltoint}
\end{equation}
Recall the formula for integration by parts,
\[
\int u'v=uv-\int uv'.
\]
Let
\[
u=-\frac{1}{s}e^{-st}\quad\mb{and}\quad v=\int_{0^{-}}^{t} f(x)dx.
\]
Note that
\[
\frac{dv}{dt}=\frac{d}{dt}\int_{0^{-}}^{t} f(x)dx=f(t).
\]
Integrating~(\ref{eq:firsltoint}) by parts gives
\[
{\cal L}\left( \int_{0^{-}}^{t} f(x)dx\right)=\left.-\frac{1}{s}e^{-st}\int_{0^{-}}^{t} f(x)dx \right\arrowvert_{0^{-}}^{\infty}+\frac{1}{s}\int_{0^{-}}^{\infty}e^{-st}f(t)dt.
\]
The first term on the right-hand side is zero at both the lower and upper limits. The value at the lower limit, $t=0^{-}$, is clearly zero. The value at the upper limit, $t=\infty$, is zero because we assumed that $f(t)$ is Laplace transformable.\index{Laplace transformable} Hence,
\begin{equation}
\fbox{$\displaystyle {\cal L}\left( \int_{0^{-}}^{t} f(x)dx\right)=\frac{F(s)}{s} $}
\label{eq:laptranofom}
\end{equation}

We next find the Laplace transform of
\begin{equation}
\int_{-\infty}^{t} f(x)dx.
\label{eq:intmintot}
\end{equation}
Applying the definition and using the fact that the Laplace transform is linear\index{Laplace transform!is linear} yields
\[
{\cal L}\left( \int_{-\infty}^{t} f(x)dx\right) = {\cal L}\left( \int_{-\infty}^{0^{-}} f(x)dx\right)+{\cal L}\left( \int_{0^{-}}^{t} f(x)dx\right)
= F_1(s)+F_2(s).
\]
The limits of the first integral are constant, therefore the integral will be a constant. Hence,
\[
F_1(s)=\frac{\int_{-\infty}^{0^{-}} f(x)dx}{s},
\]
while by~(\ref{eq:laptranofom}),
\[
F_2(s)=\frac{F(s)}{s}.
\]
Therefore,
\begin{equation}
\fbox{$\displaystyle {\cal L}\left( \int_{-\infty}^{t} f(x)dx\right)= \frac{F(s)}{s}+\frac{\int_{-\infty}^{0^{-}} f(x)dx}{s}$}
\label{eq:tolaintra}
\end{equation}
\begin{example}\rm
We find the Laplace transform of the voltage,\index{Laplace transform!of voltage across a capacitor} $v_C(t)$, across a capacitor $C$. We have
\[
v_C(t)=\frac{1}{C}\int_{-\infty}^{t} i(x)dx.
\]
Using~(\ref{eq:tolaintra}) gives
\[
{\cal L}\left( v_C(t)\right)= \frac{1}{C}\frac{I(s)}{s}+\frac{\frac{1}{C}\int_{-\infty}^{0^{-}} i(x)dx}{s}.
\]
Since $\int_{-\infty}^{0^{-}} i(x)dx$ is the charge, $q$, on the capacitor\index{charge!on the capacitor} at $t=0^{-}$ and $v=q/C$, we obtain
\[
\fbox{$\displaystyle {\cal L}\left( v_C(t)\right)= \frac{1}{C}\frac{I(s)}{s}+\frac{v_C\left( 0^{-}\right)}{s} $}
\]
\end{example}
\markex


\subsection*{More Properties of the Laplace Transform}
%\subsection*{More Properties of the Laplace Transform}
%\addcontentsline{toc}{subsection}{More Properties of the Laplace Transform}




We will now show that translation in the time domain\index{translation!in the time domain} corresponds to multiplication by an exponential in the $s$ domain,\index{multiplication by an exponential!in the $s$ domain} that is,
\[
\fbox{$\displaystyle {\cal L}\left( f(t-a)1(t-a)\right)=e^{-sa}F(s),\qquad a > 0 $}
\]
where $F(s)={\cal L}(f(t))$. We have
\begin{equation}
{\cal L}\left( f(t-a)1(t-a)\right)= \int_{0^{-}}^{\infty}f(t-a)1(t-a)e^{-st}dt \nonumber
= \int_{a^{-}}^{\infty} f(t-a)e^{-st}dt,
\label{eq:ltrotish}
\end{equation}
because $1(t-a)=0$ for $t<a$. Next, we change the variable of integration. We let
\[
x=t-a.
\]
Then, $x=0^{-}$ when $t=a^{-}$, $x=\infty$ when $t=\infty$, and $dx=dt$. Substituting the above into~(\ref{eq:ltrotish}) yields
\[
{\cal L}\left( f(t-a)1(t-a)\right)=\int_{0^{-}}^{\infty}f(x)e^{-s(x+a)}dx
= e^{-sa}\int_{0^{-}}^{\infty}f(x)e^{-sx}dx
= e^{-as}F(s),
\]
which is the desired result.\\\markex

Next, we prove the time/frequency scaling property,\index{time/frequency scaling property}
\[
\fbox{$\displaystyle{\cal L}(f(at))=\frac{1}{a}F\left( \frac{s}{a}\right),\quad a>0 $}
\]
Indeed, applying the Laplace transform yields
\begin{equation}
{\cal L}(f(at))=\int_{0^{-}}^{\infty} f(at)e^{-st}dt.
\label{eq:latrftscal}
\end{equation}
Let $x=at$. Then, $dt=\frac{1}{a}dx$. Substituting the above into~(\ref{eq:latrftscal}) gives
\[
{\cal L}(f(at))=\frac{1}{a}\int_{0^{-}}^{\infty} f(x)e^{-\left(\frac{s}{a}\right) x}dx
= \frac{1}{a}F\left( \frac{s}{a}\right).
\]



%\section{The Impulse Function and Its Properties}
%
%The impulse function, denoted $\delta(t)$, also called the Dirac function, is a signal of infinite amplitude, zero duration, and unity area. We can construct an impulse function as the limit of pulse functions
%\[
%p_{\varepsilon_i}(t)=\frac{1}{\varepsilon_i}\left(1(t)-1(t-\varepsilon_i) \right)
%\]
%as $\varepsilon_i \to 0$. This is illustrated in Figure~\ref{fig:u_d_ma}. Note that the pulse functions have the following features as $\varepsilon_i \to 0$:
%\begin{enumerate}
%\item the amplitude approaches infinity,
%\item the duration of the pulses approaches zero,
%\item the area under each pulse is constant; in our example the area equals unity.
%\end{enumerate}
%\begin{figure}
%\centering
%\includegraphics[scale=0.5]{u_d_ma.jpg}
%%\vspace{3in}
%%\centerbmp{3.33in}{2.5in}{c:/ee202/u_d_ma.bmp}
%%\hskip1.5in\special{bmp:c:/ee202/u_d_ma.bmp x=4  y=3in}
%\caption{Generating the unit impulse function as the limit of the pulse functions.}
%\label{fig:u_d_ma}
%\end{figure}
%The unit impulse function is defined as
%\[
%\int_{-\infty}^{\infty}\delta(t) dt=1\quad\mb{and} \quad \delta(t)=0\;\;\mb{for}\;\; t\ne 0.
%\]
%The above definition states that the area under the impulse function is constant. The area represents the strength of the impulse function. The impulse function of strength $K$ is denoted $K\delta(t)$. Its graphical representation is depicted in Figure~\ref{fig:u_del_s}. The strength of the impulse is shown next to the arrow's head. The shifted impulse function of strength $K$ is also shown in Figure~\ref{fig:u_del_s}.
%\begin{figure}
%\centering
%\includegraphics[scale=0.5]{u_del_s.jpg}
%%\vspace{3in}
%%\centerbmp{3.33in}{2.5in}{c:/ee202/u_del_s.bmp}
%%\hskip1.5in\special{bmp:c:/ee202/u_del_s.bmp x=4  y=3in}
%\caption{A graphical representation of the impulse $K\delta(t)$ and $K\delta(t-a)$.}
%\label{fig:u_del_s}
%\end{figure}
%The unit impulse function can be thought of as a derivative of the unit step function, that is,
%\[
%\delta(t)=\frac{du(t)}{dt}.
%\]
%The function shown in Figure~\ref{fig:usubeps} approaches the unit step function as $\varepsilon \to 0$.
%\begin{figure}
%\centering
%\includegraphics[scale=0.5]{usubeps.jpg}
%%\vspace{3in}
%%\centerbmp{3.33in}{2.5in}{c:/ee202/usubeps.bmp}
%%\hskip1.5in\special{bmp:c:/ee202/usubeps.bmp x=4  y=3in}
%\caption{The function $1_{\epsilon}$ approaches the unit step as $\varepsilon \to 0$.}
%\label{fig:usubeps}
%\end{figure}
%The function shown in Figure~\ref{fig:u_delt}, which is the derivative of the function from Figure~\ref{fig:usubeps}, approaches the unit impulse function as $\varepsilon \to 0$.
%\begin{figure}
%\centering
%\includegraphics[scale=0.5]{u_delt.jpg}
%%\vspace{3in}
%%\centerbmp{3.33in}{2.5in}{c:/ee202/u_delt.bmp}
%%\hskip1.5in\special{bmp:c:/ee202/u_delt.bmp x=4  y=3in}
%\caption{The derivative of $1_{\varepsilon}(t)$ shown in Figure~\ref{fig:usubeps}. As $\varepsilon \to 0$, $\delta_{\varepsilon}(t)$ approches $\delta(t)$.}
%\label{fig:u_delt}
%\end{figure}
%
%The impulse function has the {\em sifting property},
%\[
%\fbox{$\displaystyle \int_{-\infty}^{\infty}f(t)\delta(t-a) dt = f(a) $}
%\]
%where $f(t)$ is a continuous function of time. It follows from the above that the impulse function sifts out everything except the value of $f$ at $t=a$---hence the name of the property. To verify the validity of the sifting property, we note that $\delta(t-a)$ is zero everywhere except at $t=a$. Hence, we can write,
%\[
%\int_{-\infty}^{\infty}f(t)\delta(t-a) dt=\int_{a-\varepsilon}^{a+\varepsilon}f(t)\delta(t-a) dt.
%\]
%By assumption, $f$ is continuous at $a$. Therefore, it must take the value of $f(a)$ as $t\to a$. Thus,
%\[
%\int_{a-\varepsilon}^{a+\varepsilon}f(t)\delta(t-a) dt=f(a)\int_{a-\varepsilon}^{a+\varepsilon}\delta(t-a) dt=f(a),
%\]
%which was to be demonstrated.

Using the sifting property, given by~\eqref{eq:sift_delta} on page~\pageref{eq:sift_delta}, we show that
\[
\fbox{$ \displaystyle {\cal L}(\delta (t))=1 $}
\]
Indeed, applying the definition of the Laplace transform and using the sifting property~\eqref{eq:sift_delta}, we obtain
\[
{\cal L}(\delta (t))=\int_{0^{-}}^{\infty}\delta (t) e^{-st} dt=e^0\int_{0^{-}}^{0^{+}}\delta (t) dt=1.
\]

%We now discuss another important property of the impulse function---the sampling property. Since $\delta(t-a)=0$ for $t\ne a$,
%\[
%f(t)\delta(t-a)=0\quad\mb{for}\quad t\ne a
%\]
%as is
%\[
%f(a)\delta(t-a)=0\quad\mb{for}\quad t\ne a.
%\]
%However, when $t=a$, we have
%\[
%f(t)\delta(t-a)=f(a)\delta(t-a)\quad\mb{for}\quad t= a
%\]
%provided that $f(a)$ exists. Therefore,
%\[
%\fbox{$\displaystyle  f(t)\delta(t-a)=f(a)\delta(t-a)\quad\mb{for all $t$}
% $}
%\]
%The above property is called the sampling property of the impulse function.\\
%{\bf Examples}\begin{itemize}
%\item[(i)] $(\cos 3t)\delta (t-\pi)=(\cos 3\pi)\delta(t-\pi)=-\delta(t-\pi)$;
%\item[(ii)] $e^{-2t}\delta(t)=e^{-2(0)}\delta(t)=\delta(t)$;
%\item[(iii)] $\left( 1-e^{-4t} \right)\delta(t)=\left( 1-e^0\right)\delta(t)=0 \delta(t)= 0$.
%\end{itemize}

%\section*{Solving the State Equations}\addcontentsline{toc}{section}{Solving the State Equations}
%\subsection*{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
%\[
%\fbox{$\displaystyle \b x(t)=e^{\b A t}\b x_0 $}
%\]
%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
%\]
%Observe 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$. There are many methods for calculating the state transition matrix. For an overview of some of them, we refer the reader to the classic paper on the subject by Moler and Van Loan~\cite{moler78}. 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.
%
%\subsection*{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{The ${\cal Z}$-Transform}
%\section*{The $z$-Transform}
%\addcontentsline{toc}{section}{The $z$-Transform}
\label{sec:z_transform}
\subsection{Definition and Simple Examples}
%\subsection*{Definition and Simple Examples}
%\addcontentsline{toc}{subsection}{Definition and Simple Examples}

The ${\cal Z}$-transform\index{Z-transform} is an operator denoted ${\cal Z}(\cdot)$  that, when applied to a sequence of numbers produces a function of a variable $z$.
\begin{defn}
For a given sequence of numbers\index{sequence of numbers}
\[
y(0), y(1),\ldots , y(k), \ldots
\]
its ${\cal Z}$-transform is the series\index{Z-transform!is a series} defined as
\[
Y(z)={\cal Z}(y(k))=\sum_{k=0}^{\infty} \frac{y(k)}{z^k} .
\]
\end{defn}\markdefn

\begin{figure}[h]
\setlength{\unitlength}{.1in}
\begin{center}
\begin{picture}(60,20)
\thicklines
\put(14,9){\vector(1,0){8}}
\put(16,10){$f(kT)$}
\put(22,5){\framebox(10,8){${\cal Z}(\cdot)$}}
\put(32,9){\vector(1,0){9}}
\put(34,10){$F(z)$}
\end{picture}
\end{center}
\caption{The ${\cal Z}$-transform is an operator acting on a sequence of numbers resulting in a function of the variable $z$.}
\label{fig:z-transform}
\end{figure}

\begin{example}\rm\label{ex:unit_s_z_tr}
We find the ${\cal Z}$-transform of the sampled unit step,\index{Z-transform!of the sampled unit step} $f(kT)=1$. The ${\cal Z}$-transform of this sequence is
\begin{eqnarray*}
F(z)&=& \sum_{k=0}^{\infty} f(kT)z^{-k}\\
&=& 1 + \frac{1}{z} + \frac{1}{z^2} + \cdots
\end{eqnarray*}
If $z$ is a complex variable such that $|z| > 1$, then the above sequence converges and we have
\begin{eqnarray*}
F(z)&=& \frac{1}{1-1/z}\\
&=& \frac{z}{z-1}.
\end{eqnarray*}
\end{example}
\markex

\begin{example}\rm\label{ex:ramp_z_tr}
We find the ${\cal Z}$-transform of the sampled unit ramp,\index{Z-transform!of the sampled unit ramp} $f(kT)=kT$. The ${\cal Z}$-transform of this sequence is
\begin{eqnarray}
F(z)&=& \sum_{k=0}^{\infty} kT z^{-k}\nonumber\\
&=& T\left( z^{-1} + 2 z^{-2} + 3 z^{-3} + \cdots \right)
\label{eq:defn_ramp_z}
\end{eqnarray}
Multiplying both sides of the above by $z$ gives
\begin{equation}
z F(z)=T\left( 1 + 2 z^{-1} + 3 z^{-2} + \cdots \right)
\label{eq:ztimesF}
\end{equation}
Subtracting~\eqref{eq:defn_ramp_z} from~\eqref{eq:ztimesF} yields
\begin{eqnarray}
z F(z) - F(z) &=& (z-1) F(z)\nonumber\\
&=& T\left(1 + z^{-1} + z^{-2} + \cdots \right)\nonumber\\
&=& \frac{1}{1-z^{-1}}\nonumber\\
&=& \frac{z}{z-1}.
\label{eq:aftersubing}
\end{eqnarray}
Hence, the ${\cal Z}$-transform of $f(k T) = kT$ is
\begin{equation}
\fbox{$\displaystyle {\cal Z}(kT) = T \frac{z}{(z-1)^2} $}
\label{eq:z_tr_u_ram}
\end{equation}
\end{example}
\markex

\begin{example}\rm\label{ex:geo_s_z_tr}
We now find the ${\cal Z}$-transform of the geometric sequence\index{Z-transform!of the geometric sequence}
\begin{equation}
f(k) = a^{k T}.
\label{eq:geo_seq_w_T}
\end{equation}
We obtain
\begin{equation}
\fbox{$\displaystyle {\cal Z}(a^{k T}) = \sum_{k=0}^{\infty} \frac{a^{k T}}{z^k} = \frac{z}{z-a^T} $}
\label{eq:z_tr_geo_seq}
\end{equation}
for $|z| > \left|a^T  \right|$.
\end{example}
\markex


\subsection{Some Properties of the ${\cal Z}$-Transform }
%\subsection*{Some Properties of the ${\cal Z}$-Transform }
%\addcontentsline{toc}{subsection}{Some Properties of the ${\cal Z}$-Transform}

We analyze now three basic properties that are especially useful when computing transforms of more complicated sequences.

{\bf Linearity property:} The ${\cal Z}$-transform is a linear operator,\index{Z-transform!a linear operator} that is,
\begin{itemize}
\item[(i)] if $F_1(z)={\cal Z}(f_1(kT))$ and $F_2(z)={\cal Z}(f_2(kT))$ then
    \[
    {\cal Z}(f_1(kT)+f_2(kT))=F_1(z) + F_2(z); \mb{ and}
    \]
\item[(ii)] if $F(z)={\cal Z}(f(kT))$ then
\[
{\cal Z}(cf(kT)) = cF(z),
\]
where $c$ is a real or complex number.
\end{itemize}
We represent the above two properties as: if $F_1(z)={\cal Z}(f_1(kT))$ and $F_2(z)={\cal Z}(f_2(kT))$, and $c$ is a real or complex number, then
\[
{\cal Z}(f_1(kT)+cf_2(kT))=F_1(z) + cF_2(z).
\]

{\bf ${\cal Z}$-transform of a delayed sequence:}\index{Z-transform!of a delayed sequence} If the sequence $f(kT)$ has the ${\cal Z}$-transform $F(z)$, then the unit delayed sequence
\[
g(kT)=\left\{\begin{array}{lll}
f((k-1)T) &{}& k\ge 1\\
0 &{}& k=0
\end{array}  \right.
\]
has the ${\cal Z}$-transform
\begin{equation}
G(z)=z^{-1} F(z).
\label{eq:del_seq_z_tr}
\end{equation}
We use the definition of the ${\cal Z}$-transform to prove the above property;
\begin{eqnarray*}
G(z) &=& \sum_{k=0}^{\infty} z^{-k} g(k T)\\
&=& \sum_{k=1}^{\infty} z^{-k} f((k-1)T)\\
&=& z^{-1}\sum_{k=1}^{\infty} z^{-(k-1)} f((k-1)T)\\
&=& z^{-1}\sum_{j=0}^{\infty} z^{-j} f(j T)\\
&=& z^{-1} F(z).
\end{eqnarray*}
{\bf ${\cal Z}$-transform of an advanced sequence:}\index{Z-transform!of an advanced sequence} If the sequence $f(kT)$ has the ${\cal Z}$-transform $F(z)$, then the unit advanced sequence $h(kT)=f((k+1)T)$, $k\ge 0$, has the transform
\begin{equation}
{\cal Z}(f((k+1)T)) = z F(z) - z f(0).
\label{eq:z_tr_adva_seq}
\end{equation}
To prove the above, we apply the definition of the ${\cal Z}$-transform to obtain,
\begin{eqnarray*}
H(z) &=& \sum_{k=0}^{\infty} z^{-k} h(k T) \\
&=& \sum_{k=0}^{\infty} z^{-k} f((k + 1) T) \\
&=& z\sum_{k=0}^{\infty} z^{- k - 1} f((k + 1) T)\\
&=& z \sum_{j=1}^{\infty} z^{-j} f(j T)\\
&=& z \sum_{j=0}^{\infty} z^{-j} f(j T) - z f(0)\\
&=& z F(z) - z f(0).
\end{eqnarray*}

\begin{example}\rm\label{ex:del_geo_ser}
We find the ${\cal Z}$-transform of the delayed geometric sequence,\index{Z-transform!of the delayed geometric sequence}
\begin{equation}
f(kT) = \left\{\begin{array}{lll}
0 &\mb{for}& k=0\\
a^{(k-1)T} &\mb{for}& k>0 .
\end{array}  \right.
\label{eq:del_geo_ser}
\end{equation}
Applying~\eqref{eq:del_seq_z_tr} to the geometric sequence~\eqref{eq:geo_seq_w_T} yields
\begin{equation}
\fbox{$\displaystyle {\cal Z}(f(kT)=\frac{1}{z-a^T} $}
\label{eq:z_tr_dely_geo_s}
\end{equation}
\end{example}
\markex


\subsection*{Solving Difference Equations Using the ${\cal Z}$-Transform }
%\subsection*{Solving Difference Equations Using the ${\cal Z}$-Transform }
%\addcontentsline{toc}{subsection}{Solving Difference Equations Using the ${\cal Z}$-Transform}

The ${\cal Z}$-transform is a very effective tool for solving linear, constant-coefficients difference equations.\index{Z-transform!solving linear constant-coefficients difference equations} The basis for the method is the ${\cal Z}$-transform of an advanced sequence given by~\eqref{eq:z_tr_adva_seq}. Repeated application of this property gives
\begin{equation}
{\cal Z}(f((k+2)T)) = z^2 F(z) - z^2 f(0) - z f(T).
\label{eq:advanc_twice}
\end{equation}
Applying again~\eqref{eq:z_tr_adva_seq} to~\eqref{eq:advanc_twice} gives
\begin{equation}
{\cal Z}(f((k+3)T)) = z^3 F(z) - z^3 f(0) - z^2 f(T) - z f(2T)
\label{eq:advanc_thrice}
\end{equation}
and so on.
\begin{example}\rm\label{ex:simp_differe_eq}
We solve the difference equation\index{difference equation solving!using Z-transform}
\[
x[k+1] + 3 x[k]= 2^k,\quad k=0, 1, \ldots ,
\]
where $x(0)=0$. Applying the ${\cal Z}$-transform to both sides of the above difference equation gives
\[
z X(z) - z x(0) + 3 X(z)=\frac{z}{z-2}.
\]
Hence,
\[
X(z)=\frac{z}{(z+3)(z-2)},
\]
which is a strictly proper rational function\index{rational function!strictly proper} of $z$. We represent $X(z)$ in partial fraction form as
\[
X(z)=\frac{A}{z+3} + \frac{B}{z-2},
\]
where
\[
A=\left. (z+3)X(z) \right\arrowvert_{z=-3}=\frac{3}{5}\quad\mb{and}\quad B=\left. (z-2)X(z) \right\arrowvert_{z=2}=\frac{2}{5}.
\]
Therefore,
\[
X(z)=\frac{3/5}{z+3} + \frac{2/5}{z-2}.
\]
We use~\eqref{eq:z_tr_dely_geo_s} when applying the inverse ${\cal Z}$-transform\index{Z-transfrom!inverse}\index{inverse Z-transform} to the above,
\[
x[k]=\left\{\begin{array}{lll}
0 &\mb{for}& k=0\\
\frac{3}{5}(-3)^{k-1}   + \frac{2}{5} 2^{k-1} &\mb{for}& k \ge 1
\end{array}
\right.
\]
\end{example}
\markex

\begin{example}\rm\label{ex:nonz_ic_differe_eq}
We solve the difference equation
\[
x[k+1] + 3 x[k]= 2^k,\quad k=0, 1, \ldots ,
\]
where $x(0)=5$. Applying the ${\cal Z}$-transform to both sides of the above difference equation gives
\[
z X(z) - z x(0) + 3 X(z)=\frac{z}{z-2}.
\]
Hence,
\[
X(z)=\frac{5z^2 - 9z}{(z+3)(z-2)}=\frac{z(5z-9)}{(z+3)(z-2)}.
\]
The above rational function is not strictly proper so we use a different approach than in Example~\ref{ex:simp_differe_eq}. In this example $z$ is a factor of the numerator so we can represent the above as
\[
\frac{X(z)}{z}=\frac{5z-9}{(z+3)(z-2)}
\]
and express the right hand side in partial fraction format as
\[
\frac{X(z)}{z}=\frac{24/5}{z+3} + \frac{1/5}{z-2}.
\]
Thus
\[
X(z)=\frac{24}{5}\frac{z}{z+3} + \frac{1}{5}\frac{z}{z-2} .
\]
Taking into account~\eqref{eq:z_tr_geo_seq} when applying the inverse ${\cal Z}$-transform yields
\[
x[k]=\frac{24}{5}(-3)^{k} + \frac{1}{5} 2^{k},\quad k \ge 0
\]
\end{example}

\markex

\section{Curves and Surfaces}
%\section*{Curves and Surfaces}
%\addcontentsline{toc}{section}{Curves and Surfaces}

In the following, we review selected results from calculus of several variables concerning curves, surfaces, vector fields, and curve integrals.

Consider a point moving along a curve in $n$-dimensional space.\index{curve!in $n$-dimensional space} The position of the point at time $t$ can be described as,
\begin{equation}
\b x(t)=\left[\begin{array}{c}
x_1(t)\\
x_2(t)\\
\vdots\\
x_n(t)
\end{array}\right].
\label{eq:abbrev_n}
\end{equation}
For example, if the point is moving along a straight line passing through fixed points\index{straight line!passing through fixed points} $\b y$ and $\b z$ in $\mb{\Bb R}^n$, then
\begin{equation}
\b x(t)=\b y+t\b z.
\end{equation}
As another example, consider
\begin{equation}
\b x(t)=\left[\begin{array}{c}
x_1(t)\\
x_2(t)
\end{array}\right]=\left[\begin{array}{c}
\cos t\\
\sin t
\end{array}\right] \in \mb{\Bb R}^2.
\end{equation}
Then, the point moves around a circle\index{point!moving around a circle} of radius 1 in counterclockwise direction\index{counterclockwise direction} as shown in Figure~\ref{fig:bug_two}.
\begin{figure}
\centering
\includegraphics[scale=0.5]{bug_2.eps}
%\vskip3in
%\hskip1in\special{bmp:c:/mybook/bug_2.bmp x=4in y=3in}
\caption{An example of a curve in two-dimensional space.}
\label{fig:bug_two}
\end{figure}
We used $t$ as the variable corresponding to the angle corresponding to the position of the point on the circle. We are now ready for a formal definition of a curve.
\begin{defn}
Let $I \in \mb{\Bb R}$ be an interval. A parameterized curve\index{parameterized curve}\index{curve!parameterized} defined on the interval $I$ is an association which to each point of $I$ associates a vector, where $\b x(t)$ denotes the vector associated to $t \in I$ by $\b x$. We write the association $t \mapsto \b x(t)$ as
\[
\b x :I \to \mb{\Bb R}^n.
\]
We also call this association the parameterization of a curve.\index{parameterization!of a curve}\index{curve!parameterization of} We call $\b x(t)$, the position vector at time $t$.
\end{defn}\markdefn

The position vector\index{position vector} can be represented in terms of its coordinates as in~(\ref{eq:abbrev_n}), where each component $x_i(t)$ is a function of time $t$. We say that this curve is differentiable if each function $x_i(t)$ is a differentiable function of time $t$. We define the derivative $d\b x(t)/dt$ to be
\[
\dot{\b x}(t)=\frac{d \b x(t)}{dt}=\left[\begin{array}{c}
\frac{d x_1(t)}{dt}\\
\frac{d x_2(t)}{dt}\\
\vdots\\
\frac{d x_n(t)}{dt}
\end{array}\right],
\]
and call it the velocity vector of the curve\index{velocity vector!of the curve} at time $t$. The velocity vector is located at the origin. However, when we translate it to the point $\b x(t)$, as in Figure~\ref{fig:velocity}, then we visualize it as tangent to the curve\index{tangent!to the curve} $\b x(t)$.
\begin{figure}
\centering
\includegraphics[scale=0.5]{veloc.eps}
%\vskip3in
%\hskip1in\special{bmp:c:/mybook/veloc.bmp x=4in y=3in}
\caption{Velocity vector of a curve at time $t$ is parallel to a tangent vector at time $t$.}
\label{fig:velocity}
\end{figure}

We define the tangent line to a curve $\b x$ at time $t$ to be the line passing through $\b x(t)$ in the direction of $\dot{\b x}(t)$, provided $\dot{\b x}(t) \ne \b 0$. If $\dot{\b x}(t) = \b 0$, we do not define a tangent line.
The speed of the curve\index{speed!of the curve} $\b x(t)$, denoted $v(t)$, is
\[
v(t)=\left\Arrowvert \dot{\b x}(t) \right\Arrowvert.
\]
To illustrate the above, we consider the point moving on the circle. The point position at time $t$ is
\[
\b x(t)=\left[\begin{array}{cc}
\cos t & \sin t
\end{array}\right]^{\top}.
\]
The velocity vector of the curve at time t is
\[
\dot{\b x}(t)=\left[\begin{array}{cc}
-\sin t & \cos t
\end{array}\right]^{\top},
\]
and the speed of the curve $\b x(t)$ at time $t$ is
\[
v(t)=\left\Arrowvert \dot{\b x}(t) \right\Arrowvert=\sqrt{(-\sin t)^2 + \cos ^2 t}=1.
\]

The set of points in $\mb{\Bb R}^3$ such that for some $F:\mb{\Bb R}^3 \to \mb{\Bb R}$, we have
\[
F(\b x)=F(x_1,x_2,x_3)=0,
\]
and
\[
D F(x_1,x_2,x_3)=\nabla F(x_1,x_2,x_3)^{\top} =\left[\begin{array}{ccc}
\frac{\partial F}{\partial x_1}&\frac{\partial F}{\partial x_2}&
\frac{\partial F}{\partial x_3}
\end{array}\right]\ne \b 0^{\top},
\]
is called a surface in $\mb{\Bb R}^3$, where $\nabla\: F= \mb{grad}\: F$. For example, let
\[
F(x_1,x_2,x_3)=x_1^2+x_2^2+x_3^2-1,
\]
then, the surface is the sphere of radius 1, centered at the origin of $\mb{\Bb R}^3$.

%An alternative way to represent a surface in $\mb{\Bb R}^3$ is via the %equation
%\[
%x_3=f(x_1,x_2),
%\]
%or in parametric fashion as follows
%\begin{eqnarray*}
%x_1 &=& p(u,v)\\
%x_2 &=& q(u,v)\\
%x_3 &=& r(u,v),
%\end{eqnarray*}
%where the Jacobian matrix,
%\[
%\frac{\partial (x_1,x_2,x_3)}{\partial (u,v)}= \left[\begin{array}{cc}
%\frac{\partial p}{\partial u}&\frac{\partial p}{\partial v}\\
%\frac{\partial q}{\partial u}&\frac{\partial q}{\partial v}\\
%\frac{\partial r}{\partial u}&\frac{\partial r}{\partial v}
%\end{array}\right]
%\]
%is of rank 2.
%
%In general case, for $\mb{\Bb R}^n$, a surface can be described in three %equivalent ways as follows:
%\begin{itemize}
%\item[(a)] \begin{eqnarray*}
%F_1(x_1,x_2,\ldots,x_n) &=& 0\\
%{}&\vdots&{}\\
%F_m(x_1,x_2,\ldots,x_n) &=& 0,
%\end{eqnarray*}
%where $m<n$, or using abbreviated notation as
%\[
%\b F(\b x)=\b 0,
%\]
%where $\b F:\mb{\Bb R}^n \to \mb{\Bb R}^m$.
%\item[(b)] \begin{eqnarray*}
%x_{n-m+1} &=& f_{n-m+1}(x_1,x_2,\ldots,x_{n-m})\\
%{}&\vdots&{}\\
%x_{n} &=& f_{n}(x_1,x_2,\ldots,x_{n-m}),
%\end{eqnarray*}
%\item[(c)] \begin{eqnarray*}
%x_1 &=& g_1(u_1,u_2,\ldots,u_{n-m})\\
%{}&\vdots&{}\\
%x_n &=& g_n(u_1,u_2,\ldots,u_{n-m}).
%\end{eqnarray*}
%\end{itemize}

Let
\[
\b C(t)=\left[\begin{array}{cccc}
x_1(t) & x_2(t) & \cdots & x_n(t)
\end{array}\right]^{\top}
\]
be a differentiable curve.\index{differentiable curve} We say that the curve lies on the surface described by
\[
\left.\begin{array}{ccc}
F_1(x_1,x_2,\ldots,x_n) &=& 0\\
{}&\vdots&{}\\
F_m(x_1,x_2,\ldots,x_n) &=& 0,
\end{array}\right\}
\]
if, for all $t$, we have
\[
\left.\begin{array}{ccc}
F_1(x_1(t),x_2(t),\ldots,x_n(t)) &=& 0\\
{}&\vdots&{}\\
F_m(x_1(t),x_2(t),\ldots,x_n(t)) &=& 0.
\end{array}\right\}
\]
Differentiating the above equations, using the chain rule,\index{chain rule} we obtain
\[
D F_i\left( \b C(t)\right)\dot{\b C}(t)=\nabla F_i\left( \b C(t)\right)^{\top}\dot{\b C}(t)=0,\quad i=1,2,\ldots,m.
\]
Let $\b x_0$ be a point of the surface, and let $\b C(t)$ be a curve on the surface passing through $\b x_0$, that is, for some $t_0$ we have
\[
\b C(t_0)=\b x_0.
\]
For this $t_0$ we have
\[
\nabla F_i\left( \b x_0\right)^{\top}\dot{\b C}(t_0)=0,\quad i=1,2,\ldots,m,
\]
where we assumed that $\dot{\b C}(t_0)\ne \b 0$. Thus, the gradients $\nabla F_i$ at $\b x_0$ are orthogonal\index{gradients!orthogonal to} to the tangent vector of the curve\index{tangent vector!of the curve} at the point $\b x_0$. This is true for every differentiable curve on the surface passing through $\b x_0$. For an illustration of the above properties in three-dimensional space, we refer to Figure~\ref{fig:tangent}.
\begin{figure}
\centering
\includegraphics[scale=0.5]{tangent.eps}
%\vskip3in
%\hskip1in\special{bmp:c:/mybook/tangent.bmp x=4in y=3in}
\caption{Tangent space to a surface is the set of vectors orthogonal to the gradients of the functions defining the surface.}
\label{fig:tangent}
\end{figure}
\begin{defn}
The tangent space to the surface\index{tangent space!to the surface} $\left\{ \b x:\b F(\b x)=\b 0\right\}$ at the point $\b x_0$ is the set of vectors at $\b x_0$ that are tangent to differentiable curves on the surface passing through $\b x_0$.
\end{defn}\markdefn


\section*{Vector Fields and Curve Integrals}
%\section*{Vector Fields and Curve Integrals}
%\addcontentsline{toc}{section}{Vector Fields and Curve Integrals}

\begin{defn}
Let ${\cal U}$ be an open subset of $\mb{\Bb R}^n$. By a vector field on ${\cal U}$ we mean an association
\[
\b F:{\cal U} \to \mb{\Bb R}^n
\]
which to every point of ${\cal U}$ associates a vector of the same dimension.
\end{defn}\markdefn

We can interpret a vector field as a field of forces.\index{vector field!as a field of forces} We can visualize a vector field as a field of arrows, which to each point associates an arrow as shown in Figure~\ref{fig:field}.
\begin{figure}
\centering
\includegraphics[scale=0.5]{field.eps}
%\vskip3in
%\hskip1in\special{bmp:c:/mybook/field.bmp x=4in y=3in}
\caption{A vector field.}
\label{fig:field}
\end{figure}
If $f:{\cal U} \to \mb{\Bb R}$ is a function, then
\[
\b F=\nabla f
\]
is a vector field, and we have
\[
\b F(\b x)=\nabla f(\b x)
\]
for all $\b x \in {\cal U}$. We now consider an inverse problem: When is a given vector field in $\mb{\Bb R}^n$ a gradient?
\begin{defn}
Let $\b F$ be a vector field on an open set ${\cal U}$. If $f$ is a differentiable function on ${\cal U}$ such that
\[
\b F=\nabla f,
\]
then we say that $f$ is a potential function\index{potential function} for $\b F$.
\end{defn}\markdefn

We then can ask the question if the potential functions exist. To answer the question, we recast the problem into the one that involves solving $n$ first order partial differential equations:
\[
\frac{\partial f}{\partial x_i}=F_i(\b x),\quad i=1,2,\ldots,n,
\]
with the initial condition
\[
\b F(\b x_0)=\b F_0.
\]
To answer the above question we need one more definition.
\begin{defn}
An open set ${\cal U}$ is said to be connected\index{open set!connected}\index{connected!open set} if, given two points in ${\cal U}$, there is a differentiable curve in ${\cal U}$ that joins the two points.
\end{defn}\markdefn

If ${\cal U}=\mb{\Bb R}^n$, then any two points can be joined by a straight line. Of course, it is not always the case that two points of an open set can be joined by a straight line, as it is illustrated in Figure~\ref{fig:connect}. We say that the function $\b F=\left[\begin{array}{cccc}
F_1 & F_2 & \cdots & F_n
\end{array}\right]^{\top}$ is a ${\cal C}^1$ function if all partial derivatives of all functions $F_i$ exist and are continuous.
\begin{figure}
\centering
\includegraphics[scale=0.5]{connect.eps}
%\vskip3in
%\hskip1in\special{bmp:c:/mybook/connect.bmp x=4in y=3in}
\caption{A connected open set in which there are points that cannot be joined by a straight line.}
\label{fig:connect}
\end{figure}
\begin{thm}
\label{thm:nascfopofu}
Let $\b F(\b x)$ be ${\cal C}^1$ function defined on an open connected region\index{open!connected region}\index{region!open connected} ${\cal U}$ of $\mb{\Bb R}^n$. Then, there is a solution to the differential equation
\[
\nabla f(\b x)=\b F(\b x),\quad \b F(\b x_0)=\b F_0,
\]
if and only if
\[
\frac{\partial F_i}{\partial x_j}=\frac{\partial F_j}{\partial x_i},
\]
that is, the Jacobian matrix\index{Jacobian matrix} of $\b F$ is symmetric.
\label{thm:sym_jacob}
\end{thm}
{\bf Proof}\quad We prove the theorem for $n=2$, where the connected region ${\cal U}$ is a rectangle.\index{connected region!a rectangle} We select a point $\b x_0=\left[\begin{array}{cc}
x_{10} & x_{20}
\end{array}\right]^{\top}$ in the rectangle. We assume that $\b F=\left[\begin{array}{cc}
F_1 & F_2
\end{array}\right]^{\top}$ and that
\[
D_2F_1=D_1F_2,\quad\mb{that is,}\quad \frac{\partial F_1}{\partial x_2}=\frac{\partial F_2}{\partial x_1}.
\]
Our goal is to find a potential function $f(x_1,x_2)$. We assume that the potential function has the form
\[
f(x_1,x_2)=\int_{x_{10}}^{x_1}F_1(s,x_2)ds + u(x_2),
\]
where $u(x_2)$ is a function of $x_2$ only and is determined later in the proof. We illustrate the integration path in Figure~\ref{fig_intpath}.
\begin{figure}
\centering
\includegraphics[scale=0.5]{intpath.eps}
%\vspace{3in}
%\hskip1in\special{bmp:c:/mybook/intpath.bmp x=4in y=3in}
\caption{Integration path used in the proof of Theorem~\ref{thm:sym_jacob}.}
\label{fig_intpath}
\end{figure}
Applying the fundamental theorem of calculus,\index{fundamental theorem of calculus}\index{calculus!fundamental theorem of} we obtain
\begin{eqnarray*}
\frac{\partial f}{\partial x_1} &=& \frac{\partial}{\partial x_1}\int_{x_{10}}^{x_1}F_1(s,x_2)ds + \frac{\partial u(x_2)}{\partial x_1}\\
&=& F_1(x_1,x_2)
\end{eqnarray*}
because
\[
\frac{\partial u(x_2)}{\partial x_1}=0.
\]
Hence,
\[
D_1f(x_1,x_2)=F_1(x_1,x_2)
\]
as required. We now differentiate $f(x_1,x_2)$ with respect to $x_2$ to get
\begin{eqnarray*}
\frac{\partial f}{\partial x_2} &=& \int_{x_{10}}^{x_1}\frac{\partial F_1(s,x_2)}{\partial x_2}ds+\frac{\partial u(x_2)}{\partial x_2}\\
&=& \int_{x_{10}}^{x_1}\frac{\partial F_2(s,x_2)}{\partial x_1}ds+\frac{\partial u(x_2)}{\partial x_2}
\end{eqnarray*}
because, by assumption, $D_2 F=D_1 F$. Therefore,
\begin{eqnarray*}
\frac{\partial f}{\partial x_2} &=& \left. F_2(s,x_2)\right\arrowvert_{x_{10}}^{x_1}+\frac{\partial u(x_2)}{\partial x_2}\\
&=& F_2(x_1,x_2)-F_2(x_{10},x_2)+\frac{\partial u(x_2)}{\partial x_2}.
\end{eqnarray*}
Let
\[
-F_2(x_{10},x_2)+\frac{\partial u(x_2)}{\partial x_2}=0,
\]
that is, $\frac{\partial u(x_2)}{\partial x_2}=F_2(x_{10},x_2)$.
Then, $D_2f=F_2$ as wanted. To conclude the proof, we let
\[
u(x_2)=\int_{x_{20}}^{x_2} F_2(x_{10},x_2)dx_2,
\]
which yields
\begin{equation}
\fbox{$\displaystyle f(x_1,x_2)=\int_{x_{10}}^{x_1}F_1(s,x_2)ds+\int_{x_{20}}^{x_2}F_2(x_{10},t)dt $}
\label{eq:expfopofunt}
\end{equation}
The proof is complete for $n=2$.\\
\hspace*{5.5in} $\Box$

We note that if the connected region ${\cal U}$ is an arbitrary open set, then the above proof may not work. This is because we needed to integrate over intervals that were contained in the region ${\cal U}$.


Suppose we are given a vector field $\b F$ on an open set $U$ in the plane. We can interpret $\b F$ as a field of forces. We wish to calculate the work done when moving a particle from a point $\b C(t_1)$ to a point $\b C(t_2)$ along the curve $\b C(t)$ in $U$, as illustrated in Figure~\ref{fig_curveint}.
\begin{figure}
\centering
\includegraphics[scale=0.5]{curveint.eps}
%\vspace{3in}
%\hskip1in\special{bmp:c:/mybook/curveint.bmp x=4in y=3in}
\caption{A particle moving along a curve in vector field.}
\label{fig_curveint}
\end{figure}
Let
\[
\b F(\b x)=\left[\begin{array}{cc}
F_1(x_1,x_2) & F_2(x_1,x_2)
\end{array}\right]^{\top}.
\]
We assume that each component of $\b F$ is differentiable, that is, $\b F$ is a differentiable vector field. We next assume that the curve $\b C(t)$ is defined on a closed interval $[t_1,t_2]$ with $t_1<t_2$. For each $t \in [t_1,t_2]$ the value $\b C(t)$ is a point in $\mb{\Bb R}^2$. The curve $\b C$ lies in $U$ if $\b C(t)$ is a point in $U$ for all $t \in [t_1,t_2]$. We further assume that the curve $\b C$ is continuously differentiable and its derivative $\dot{\b C}(t)=\frac{d\b C(t)}{dt}$ exists and is continuous, that is, we assume that $\b C \in {\cal C}^1$.

We define the integral of $\b F$ along $\b C$ to be
\begin{eqnarray*}
\int_{\b C}\b F &=& \int_{t_1}^{t_2}\b F(\b C(t))^{\top}\frac{d \b C}{dt}dt\\
&=& \int_{t_1}^{t_2}\b F(\b C(t))^{\top} d\b C,
\end{eqnarray*}
which is the work done against the force field\index{work!done against the force field} $\b F$ along the curve $\b C$. Let
\[
\b C(t)=\left[\begin{array}{cc}
x_1(t) & x_2(t)
\end{array}\right]^{\top}.
\]
Then, we can write
\begin{equation}
\int_{\b C}\b F =\int_{\b C}F_1dx_1+F_2dx_2.
\label{eq:woragforfioc}
\end{equation}
\begin{thm}[Green]
Let the vector field $\b F$ be  given on a region $A$ that is the interior of a closed path $\b C$ parameterized counterclockwise. Then,\index{Green's thereom}\index{thereom of Green}
\[
\int_{\b C}F_1dx_1+F_2\,dx_2=\int\!\!\!\int_{A}\left( \frac{\partial F_2}{\partial x_1}-\frac{\partial F_1}{\partial x_2}\right)dx_1dx_2.
\]
\label{thm:green}
\end{thm}


\section{Matrix Calculus Formulas}
%\section*{Matrix Calculus Formulas}
%\addcontentsline{toc}{section}{Matrix Calculus Formulas}

Below, we list useful formulas from matrix calculus that involve computing the gradient\index{computing the gradient} (with respect to $\mb{\bm$x$}$). Recall that in our convention the gradient is a column vector.\index{gradient!a column vector} We have:
\begin{equation}
\nabla \left( \mb{\bm$x$}^{\top}\mb{\bm$y$}\right)=\nabla \left( \mb{\bm$y$}^{\top}\mb{\bm$x$}\right)=\mb{\bm$y$},
\label{eq:gralifo}
\end{equation}
\begin{equation}
\nabla \left( \mb{\bm$x$}^{\top}\mb{\bm$x$}\right)=2\mb{\bm$x$},
\label{eq:xtrax}
\end{equation}
\begin{equation}
\nabla \left( \mb{\bm$x$}^{\top}\mb{\bm$A$}\mb{\bm$y$}\right)=\mb{\bm$A$}\mb{\bm$y$},
\label{eq:xtay}
\end{equation}
\begin{equation}
\nabla \left( \mb{\bm$y$}^{\top}\mb{\bm$A$}\mb{\bm$x$}\right)=\mb{\bm$A$}^{\top}\mb{\bm$y$},
\label{eq:ytax}
\end{equation}
\begin{equation}
\nabla \left( \mb{\bm$x$}^{\top}\mb{\bm$A$}\mb{\bm$x$}\right)=\left(\mb{\bm$A$}+\mb{\bm$A$}^{\top}\right)\mb{\bm$x$}.
\label{eq:xtaxgrad}
\end{equation}
Let $\mb{\bm$f$}:\mb{\Bb R}^n \to \mb{\Bb R}^n$ and $\mb{\bm$g$}:\mb{\Bb R}^n \to \mb{\Bb R}^n$ be two maps, and let $\frac{\partial \mb{\bm$f$}}{\partial \mb{\bm$x$}}$ and $\frac{\partial \mb{\bm$g$}}{\partial \mb{\bm$x$}}$ be the Jacobian matrices\index{Jacobian matrices} of $\mb{\bm$f$}$ and $\mb{\bm$g$}$, respectively. Then,
\begin{equation}
\nabla \left( \b f(\b x)^{\top}\b g(\b x)\right)=\nabla \left( \b g(\b x)^{\top}\b f(\b x)\right)=\left( \frac{\partial \mb{\bm$f$}}{\partial \mb{\bm$x$}}\right)^{\top}\mb{\bm$g$}+\left( \frac{\partial \mb{\bm$g$}}{\partial \mb{\bm$x$}}\right)^{\top}\mb{\bm$f$}.
\label{eq:ftgxpr}
\end{equation}
For an $n\times n$ symmetric matrix $\mb{\bm$Q$}$,
\begin{equation}
\nabla \left( \mb{\bm$f$}(\mb{\bm$x$})^{\top}\mb{\bm$Q$}\mb{\bm$f$}(\mb{\bm$x$})\right)=2\left( \frac{\partial \mb{\bm$f$}}{\partial \mb{\bm$x$}}\right)^{\top}\mb{\bm$Q$}\mb{\bm$f$}.
\label{eq:ftqgprgr}
\end{equation}


\section{Notes}
%\section*{Notes}
%\addcontentsline{toc}{section}{Notes}

For other proof techniques, we refer to Velleman~\cite{velleman94}. For further reading on linear algebra, and in particular matrix theory, we recommend classical texts of Gelfand~\cite{gelfand61} and Gantmacher~\cite{gantmacher59v1}. Analyses of numerical methods for matrix computations can be found in Faddeeva~\cite{faddeeva59}, Householder~\cite{householder75}, Golub and Van~Loan~\cite{golub83}, as well as in Gill, Murray, and Wright~\cite{gill91}. Lang~\cite{lang87} and Seeley~\cite{seeley70} are recommended for a review of calculus of several variables. A straightforward approach to mathematical analysis is presented in Binmore~\cite{binmore82}. Principles of real analysis can be found in Natanson~\cite{natanson55}, Bartle~\cite{bartle76}, and Rudin~\cite{rudin76}. Some facts from basic functional analysis  that we touched upon in this chapter, are discussed, for example, by Maddox~\cite{maddox88}, and Debnath and Mikusi\'{n}ski~\cite{debnath90}. Lucid expositions of differential equations are in Driver~\cite{driver77}, Miller and Michel~\cite{miller82}, and in Boyce and DiPrima~\cite{boyce97}.

The famous mathematician, G.~H.~Hardy~(1877--1947) argues in~\cite[page~113]{hardy92} that in truly great theorems and their proofs, ``there is a very high degree of {\em unexpectedness\/}, combined with {\em inevitability\/} and {\em economy\/}. The arguments take so odd and surprising a form; the weapons used seem so childishly simple when compared with the far-reaching results; but there is no escape from the conclusions.'' He further states that ``A mathematical proof should resemble a simple and clear-cut constellation, not a scattered cluster in the Milky Way.''

\section{Exercises}
%\section*{Exercises}
%\addcontentsline{toc}{section}{Exercises}
\begin{exercise}\rm
The open unit disc\index{open unit disc}\index{disc!open unit} with respect to the norm $\|\cdot\|_p$, is the set
\[
\Delta_p=\{\b x\in\mb{\Bb R}^2:\|\b x\|_p < 1\}.
\]
The unit discs are quite different for different choices of the norm $\|\cdot\|_p$. Sketch
$\Delta_1$, $\Delta_2$, $\Delta_3$, and $\Delta_{\infty}$.
\end{exercise}
\begin{exercise}\rm
Let $v_1,v_2,\ldots,v_n$ be non-zero, mutually orthogonal elements of the space $V$ and let $v$ be an arbitrary element of $V$.
\begin{itemize}
\item[(i)] Find the component of $v$ along $v_j$.
\item[(ii)] Let $c_j$ denote the component of $v$ along $v_j$. Show that the element
\[
v-c_1v_1-\cdots c_nv_n
\]
is orthogonal to $v_1,v_2,\ldots, v_n$.
\item[(iii)] Verify the Bessel inequality,\index{Bessel inequality}
\[
\sum_{i=1}^n c_i^2\le \|v\|^2.
\]
\end{itemize}
\end{exercise}
\begin{exercise}[M.C.M. Teixeira] \rm
Given a linear combination of matrices,\index{linear combination!of matrices}
\begin{equation}
\b M=\alpha_1\b M_1+\cdots+\alpha_r\b M_r,
\label{ex:lincomat}
\end{equation}
where for $i=1,\ldots,r$, $\alpha_i\in \mb{\Bb R}$, and $\b M_i\in\mb{\Bb R}^{n\times n}$. Let $\b m_i^j$ be the $j$-th row of the matrix $\b M_i$. Thus,
\[
\b M_i=\left[\begin{array}{c}
\b m_i^1\\
\b m_i^2\\
\vdots\\
\b m_i^n
\end{array}\right].
\]
Show that
\begin{equation}
\det \b M=\sum_{s_1=1}^r\cdots\sum_{s_n=1}^r \alpha_{s_1}\cdots\alpha_{s_n}\det\left[\begin{array}{c}
\b m_{s_1}^1\\
\vdots\\
\b m_{s_n}^n
\end{array} \right].
\label{ex:doflincm}
\end{equation}
\end{exercise}

\begin{exercise}\rm
Let $\b X\in \mb{\Bb R}^{n\times m}$ and $\b Y\in \mb{\Bb R}^{m\times n}$. Show that
\[
\det\left(\b I_n+\b X\b Y \right)=\det\left(\b I_m+\b Y\b X \right).
\]
\label{ex:detxyyx}
\end{exercise}

\begin{exercise}\rm
Let $\lambda_i(\b A)$ denote the $i$-th eigenvalue of a matrix $\b A\in \mb{\Bb R}^{n\times n}$ and let $\alpha$ be a scalar. Show that
\begin{itemize}
\item[(i)] $\lambda_i(\alpha \b A)=\alpha \lambda_i(\b A)$;
\item[(ii)] $\lambda_i(\b I_n\pm \alpha \b A)=1\pm \alpha \lambda_i(\b A)$.
\end{itemize}
\end{exercise}

\begin{exercise}\rm
Show that the formulas~(\ref{eq:mat_norm_def}) and~(\ref{eq:linnorm_gen}) for matrix norms are equivalent.
\end{exercise}

\begin{exercise}\rm
Show that for any square matrix $\b A \in \mb{\Bb R}^{n\times n}$,
\begin{equation}
\|\b A\|\ge \max_{1\le i \le n}\left| \lambda_i(\b A)\right|.
\label{ex:nbierte}
\end{equation}
\end{exercise}

\begin{exercise}\rm
Show that if $\b P\in \mb{\Bb R}^{n\times n}$ is symmetric, then
\[
\lambda_{\min}(\b P) \|\b x\|_2^2\le \b x^{\top}\b P\b x\le \lambda_{\max}(\b P)\|\b x\|_2^2.
\]
\end{exercise}

\begin{exercise}\rm
Show that a sufficient condition for
\[
\lim_{k \to \infty}\b A^k \to \b O.
\]
is
\[
\|\b A\|<1.
\]
\end{exercise}

\begin{exercise}\rm
Let $\b A\in \mb{\Bb R}^{n \times n}$. Show that a necessary and sufficient condition for
\[
\lim_{k \to \infty}\b A^k \to \b O.
\]
is
\[
\left|\lambda_i(\b A) \right|<1,\quad i=1,2,\ldots,n
\]
\end{exercise}

\begin{exercise}\rm
Let $\mb{eig}(\b M)$ denote the set of eigenvalues of the square matrix $\b M$ and let $\Delta$ be the open unit disk in the complex plane. Prove that if $\mb{eig}(\b M) \subset \Delta \cup \{1\}$, then $\lim_{k\to \infty}\b M^k$ exists if and only if the dimension of the eigenspace\index{dimension of the eigenspace}\index{eigenspace!dimension of} corresponding to the eigenvalue 1 is equal to the multiplicity of the eigenvalue 1, that is, the geometric multiplicity\index{geometric multiplicity!of an eigenvalue} of the eigenvalue 1 is equal to its algebraic multiplicity.\index{algebraic multiplicity!of an eigenvalue}
\label{ex:ch1eigdisc}
\end{exercise}

\begin{exercise}\rm
\begin{itemize}
\item[(a)] Show that the series
\[
\sum_{n=1}^{\infty}\frac{1}{n}
\]
diverges to $+\infty$.
\item[(a)] Show that if $\alpha$ is a rational number such that $\alpha>1$, then the series
\[
\sum_{n=1}^{\infty}\frac{1}{n^{\alpha}}
\]
converges.
\item[(c)] Use MATLAB's Symbolic Math Toolbox\index{MATLAB's Symbolic Math Toolbox} to compute
\[
\sum_{n=1}^{\infty}\frac{1}{n^2}.
\]
\end{itemize}
\end{exercise}

\begin{exercise}\rm
\begin{itemize}
\item[(a)] Let $0<x<1$. Show that
\[
\ln(1-x)\le -x.
\]
\item[(b)] Let $0<x\le 1/2$. Show that
\[
\ln(1-x)\ge -2x.
\]
\end{itemize}
\label{ex:ch1lngemx}
\end{exercise}

\begin{exercise}\rm
Let $0<a_k<1$ for $k\ge 0$. Use a proof by contraposition, Theorem~\ref{thm:anofseries}, and Exercise~\ref{ex:ch1lngemx} to show that
\[
\prod_{k=0}^\infty (1-a_k)=0,\quad\mb{if and only if}\quad \sum_{k=0}^{\infty} a_k =\infty.
\]
\label{ex:ch1sumprod}
\end{exercise}
\begin{exercise}\rm
Prove Sylvester's inequalities~(\ref{sylvesterineq}).\index{Sylvester's inequalities}
\label{ex:sylvesters}
\end{exercise}
\begin{exercise}\rm
Compute $e^{\b A t}$ for
\[
\mb{(a)   }\b A=\left[\begin{array}{ccc}
0 & -3 & 0\\
3 & 0 & 0\\
0 & 0 & -1
\end{array}\right], \quad\mb{(b)   }\b A=\left[\begin{array}{ccc}
0 & 1 & 0\\
0 & 0 & 1\\
0 & -2 & -3
\end{array}\right].
\]
\end{exercise}
\begin{exercise}\rm
Find $\b x(t)$ for the dynamical system model,
\[
\dot{\b x}(t)=\left[\begin{array}{cc}
0 & 1\\
0 & 0
\end{array}\right]\b x(t)+\left[\begin{array}{c}
0\\
1
\end{array}\right]u(t),\quad \b x(0)=\left[\begin{array}{c}
0\\
1
\end{array}\right],
\]
where $u(t)$ is the unit step function,\index{unit step function} that is, $u(t)=1$ for $t\ge 0$ and $u(t)=0$ for $t<0$.

\end{exercise}
\begin{exercise}\rm
For
\[
\b A=\left[\begin{array}{cc}
-2 & -6\\
2 & -10
\end{array}\right],
\]
find constants $M>0$ and $\alpha>0$ such that
\[
\left\Arrowvert e^{\b A t} \right\Arrowvert_2 \le Me^{-\alpha t},\quad t\ge 0.
\]
\end{exercise}
\begin{exercise}\rm
Show that the function space ${\cal C}([a,b])$ of real-valued functions, $f:\mb{\Bb R} \to \mb{\Bb R}$, with the norm defined by~(\ref{eq:rvfofone}) is a normed linear space.\index{normed linear space} Show that this space is a Banach space.\index{Banach space}
\end{exercise}
\begin{exercise}\rm
Derive a sufficient condition for the convergence of the iteration process
\[
\b x^{(k+1)}=\b A\b x^{(k)}+\b b,\quad k=0,1,\ldots ,
\]
for any initial $\b x(0)$, where $\b A\in \mb{\Bb R}^{n\times n}$ and $\b b\in \mb{\Bb R}^n$.
\end{exercise} 