\documentstyle[12pt]{article}
\renewcommand{\baselinestretch}{1.5}
\setlength{\topmargin}{-.25in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\newtheorem{thm}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{algorithm}{Algorithm}
\newcommand{\mb}{\mbox}
\newcommand{\bm}{\boldmath}
\def\b#1{\mb{\bm$#1$}}
\newfont{\Bb}{msbm10 scaled\magstep1}
\begin{document}

\begin{thm}[Bolzano-Weierstrass]
\label{thm:bolzweierstr}
Every bounded sequence in $\mb{\Bb R}^p$ contains a convergent subsequence.
\end{thm}
{\bf Proof}\quad We prove this theorem only for sequences in $\mb{\Bb R}$, that is, for the case when $p=1$. Let a sequence $a_1,a_2,\ldots,a_n,\ldots$, denoted $\left\{ a_n \right\}$, be bounded. Let $Z$ be the set of all numbers $x$ such that $x \le a_n$ for infinitely many $n$. The set $Z$ is non-empty. Indeed, the number $-M$ belongs to the set $Z$, where $|a_n|\le M$, that is, the inequality $-M \le a_n$ holds for all $n$. The set $Z$ is bounded above, for if $x \in Z$, then $x\le M$ because if $x>M$, then the inequality $x\le a_n$ would not be satisfied by any $a_n$. Since the set $Z$ is non-empty and bounded above, it has a least upper bound. Denote this bound by $g$. Thus
\[
g=\sup\left\{ x:x\le a_n\right\}.
\]
We now show that $g$ is the limit of a certain subsequence of the sequence $\left\{ a_n\right\}$. This means that we have to define a sequence of positive integers $m_1<m_2<\ldots<m_n<\ldots$ such that
\[
\lim_{n \to \infty}a_{m_n}=g.
\]
By Theorem~\ref{thm_lub}, it follows that for any $\varepsilon>0$ there exists infinitely many $a_n$'s such that
\[
g-\varepsilon < a_n < g+\varepsilon.
\]
Let $\varepsilon=1$ in $g-\varepsilon < a_n < g+\varepsilon$. Then,
\[
g-1 < a_n < g+1.
\]
We choose one of $n$'s for which the above relation is satisfied and denote it by $m_1$. We thus have
\[
g-1<a_{m_1}<g+1.
\]
Now let $\varepsilon=1/2$. Then, there exist infinitely many $a_n$'s such that
\[
g-\frac{1}{2}<a_n<g+\frac{1}{2}.
\]
We choose one $a_n$ for which the above relation hold and denote it by $a_{m_2}$, where $m_1<m_2$. In general, if $m_n$ is defined, we choose $m_{n+1}$ in such a way that
\[
g-\frac{1}{n+1} < a_{m_{n+1}} < g + \frac{1}{n+1}.
\]
Since $\lim_{n \to \infty} \frac{1}{n}=0$, we have
\[
\lim_{n \to \infty}\left( g-\frac{1}{n}\right)=g= \lim_{n \to \infty}\left(g+\frac{1}{n}\right).
\]
The above two relations imply
\[
\lim_{n \to \infty}a_{m_n}=g.
\]
The inequality $m_n < m_{n+1}$, on the other hand, implies that the sequence $\left\{ a_{m_n}\right\}$ is a subsequence of the sequence $\left\{ a_n\right\}$. Thus, a bounded sequence contains a convergent subsequence, and the proof is complete.\\
\hspace*{5.5in} $\Box$

\section{The Inverse Function Theorem}
\label{sec:invfunt}
Let ${\cal S}$ be an open set in $\mb{\Bb R}^n$ and let $\b f:{\cal S} \to \mb{\Bb R}^n$ be a map, where
\[
\b f(\b x)=\left[\begin{array}{cccc}
f_1(\b x) & f_2(\b x) & \cdots & f_n(\b x)
\end{array}\right]^T.
\]
Recall that if all partial derivatives of all functions $f_i$ exist and are continuous in ${\cal S}$, then we say that $\b f$ is a ${\cal C}^1$ map in ${\cal S}$. We say that $\b f$ is a ${\cal C}^p$ map in ${\cal S}$ if each component $f_i$ is continuous and has continuous partial derivatives in ${\cal S}$ for all $k=1,2,\ldots,p$.

Let $\b f:\mb{\Bb R}^n \to \mb{\Bb R}^n$ be a ${\cal C}^p$-map, $p>0$, on an open subset ${\cal S}$ of $\mb{\Bb R}^n$, and let $\b a$ be a point of ${\cal S}$. We say that $\b f$ is locally ${\cal C}^p$-invertible at $\b a$ if there is an open set ${\cal U} \subset {\cal S}$ containing $\b a$ and an open set ${\cal V}$ containing $\b f(\b a)$ such that $\b f:{\cal U} \to {\cal V}$ has a ${\cal C}^p$ inverse $\b h:{\cal V} \to {\cal U}$ so that for all $\b x \in {\cal U}$,
\[
\b h( \b f(\b x))=\b x.
\]
Figure~\ref{fig:inverse} illustrates the sets ${\cal U}$ and ${\cal V}$ for one variable case.
\begin{figure}
\vspace{3in}
\hskip1in\special{bmp:c:/mybook/inverse.bmp x=4in y=3in}
\caption{An illustration of the sets ${\cal U}$ and ${\cal V}$ that appear in the inverse function theorem.}
\label{fig:inverse}
\end{figure}

The Jacobian matrix of $\b f:\mb{\Bb R}^n \to \mb{\Bb R}^n$, denoted $\b J(\b x)$, is defined as
\[
\b J(\b x)=D\b f(\b x)=\left[\begin{array}{c}
\nabla^T f_1(\b x)\\
\nabla^T f_2(\b x)\\
\vdots\\
\nabla^T f_n(\b x)
\end{array}\right]=\left[\begin{array}{c}
D f_1(\b x)\\
D f_2(\b x)\\
\vdots\\
D f_n(\b x)
\end{array}\right].
\]

A set ${\cal S}$ in $\mb{\Bb R}^n$ is {\em convex\/} if for every $\b x$ and $\b y$ in ${\cal S}$, the line segment joining $\b x$ and $\b y$ is in ${\cal S}$. The line segment joining $\b x$ and $\b y$, denoted $[\b x,\b y]$, can be described as
\begin{equation}
[\b x,\b y]=\{\lambda \b x +(1-\lambda )\b y : 0\le \lambda \le 1\}.
\label{eq:linseginrn}
\end{equation}
Therefore, a set ${\cal S}$ in $\mb{\Bb R}^n$ is convex, if for every $\b x$ and $\b y$ in ${\cal S}$ and every $\lambda \in [0,1]$,
\[
\lambda \b x +(1-\lambda )\b y \in {\cal S}.
\]

In the proof of the Inverse Function Theorem, we will use the following Mean Value Theorem for maps.
\begin{thm}
\label{thm:meavalthfmap}
Let ${\cal S}\subseteq \mb{\Bb R}^n$ be an open set and let $\b f:{\cal S} \to \mb{\Bb R}^q$. Suppose that ${\cal S}$ contains the points $\b x$, $\b y$ and the line segment $[\b x,\b y]$, and that $\b f$ is differentiable at every point of $[\b x,\b y]$. Then, there exists a point $\b \xi$ on $[\b x,\b y]$ such that
\begin{equation}
\fbox{$\displaystyle\left\Arrowvert \b f(\b y)-\b f(\b x)\right\Arrowvert \le \left\Arrowvert D\b f(\b \xi)(\b y-\b x)\right\Arrowvert $}
\label{eq:meanvalfmin}
\end{equation}
\end{thm}
{\bf Proof}\quad If $\b f(\b y)-\b f(\b x)=\b 0$ in $\mb{\Bb R}^q$, then~(\ref{eq:meanvalfmin}) holds and we are done. Suppose that $\b f(\b y)-\b f(\b x)\ne \b 0$. Let
\[
\b z=\left(\b f(\b y)-\b f(\b x)\right)/\left\Arrowvert \b f(\b y)-\b f(\b x)\right\Arrowvert .
\]
Note that $\|\b z\|=1$. Define
\begin{equation}
g(\b x)=\b f^T(\b x)\b z.
\label{eq:auxfunfmvtmv}
\end{equation}
We have
\begin{equation}
g(\b y)-g(\b x)=\left(\b f(\b y)-\b f(\b x)\right)^T\b z=\left\Arrowvert \b f(\b y)-\b f(\b x)\right\Arrowvert .
\label{eq:verfgmvtmv}
\end{equation}
Using the Mean Value Theorem for real-valued functions, we obtain
\begin{equation}
g(\b y)-g(\b x)=D g(\b \xi)\left(\b y-\b x\right)
\label{eq:mvtrvg}
\end{equation}
for some $\b \xi \in [\b x,\b y]$, where
\begin{equation}
Dg(\b \xi)=\b z^T D\b f(\b \xi).
\label{eq:derofgaxi}
\end{equation}
Substituting~(\ref{eq:derofgaxi}) and~(\ref{eq:verfgmvtmv}) into~(\ref{eq:mvtrvg}) yields
\begin{equation}
\left\Arrowvert \b f(\b y)-\b f(\b x)\right\Arrowvert=\b z^T D\b f(\b \xi)\left(\b y-\b x\right).
\label{eq:comtmvtfmv}
\end{equation}
Using Schwarz's Inequality and the fact that $\|\b z\|=1$ gives
\[
\left\Arrowvert \b f(\b y)-\b f(\b x)\right\Arrowvert \le \left\Arrowvert\b z^T\right\Arrowvert \left\Arrowvert D\b f(\b \xi)\left(\b y-\b x\right)\right\Arrowvert \le \left\Arrowvert D\b f(\b \xi)\left(\b y-\b x\right)\right\Arrowvert ,
\]
which completes the proof of the theorem.\\
\hspace*{5.5in} $\Box$

We now state and prove the Inverse Function Theorem for maps. 
\begin{thm}
\label{invfuntgen}
Let $\b f:\mb{\Bb R}^n \to \mb{\Bb R}^n$ be a ${\cal C}^p$-map, $p>0$, on an open subset ${\cal S}$ of $\mb{\Bb R}^n$, and let $\b a$ be a point of ${\cal S}$ such that the Jacobian matrix $\b J(\b a)$ is invertible, and $\b b=\b f\left(\b a \right)$. Then, there exist open sets ${\cal U}$ and ${\cal V}$ in $\mb{\Bb R}^n$ such that $\b a \in {\cal U}$, $\b b \in {\cal V}$, $\b f$ is one-to-one on ${\cal U}$, $\b f({\cal U})={\cal V}$, and $\b f$ is locally ${\cal C}^p$-invertible at $\b a$. 
\end{thm}
{\bf Proof} \quad We first show that there exists an open subset ${\cal U}\subseteq {\cal S}$ in which $\b f$ is one-to-one. Since $\b J^{-1}\left(\b a\right)$ exists, we can choose $s$ so that
\begin{equation}
\left\Arrowvert \b J^{-1}\left(\b a\right)\right\Arrowvert =\frac{1}{2s}.
\label{eq:defscals}
\end{equation}
By assumption $D \b f$ is continuous at $\b a$. Hence, there is a ball ${\cal U} \subseteq {\cal S}$ centered at $\b a$ such that
\begin{equation}
\left\Arrowvert \b J\left(\b x\right)-\b J\left(\b a\right)\right\Arrowvert < s, \quad \b x \in {\cal U}.
\label{eq:defseucal}
\end{equation}
For each $\b y \in \mb{\Bb R}^n$, we associate
\begin{equation}
\b F(\b x)=\b x+\b J^{-1}\left(\b a\right)\left(\b y-\b f(\b x) \right).
\label{eq:introfuncf}
\end{equation}
We have $\b f(\b x)=\b y$ if and only if $\b x$ is a fixed point of the map $\b F$ given above. The Jacobian matrix of $\b F$ is
\begin{equation}
D \b F(\b x)=\b I_n-\b J^{-1}\left(\b a\right)\b J(\b x)=\b J^{-1}\left(\b a\right)\left( \b J\left(\b a\right)-\b J(\b x)\right).
\label{eq:jacmatofbf}
\end{equation}
Applying~(\ref{eq:defscals}) and~(\ref{eq:defseucal}) to the above gives
\begin{equation}
\left\Arrowvert D\b F\left(\b x\right)\right\Arrowvert < \frac{1}{2},\quad \b x \in {\cal U}.
\label{eq:estnorofdf}
\end{equation}
By the Mean Value Theorem for maps, stated on page~\pageref{thm:meavalthfmap}, for any $\b x^{(1)}, \b x^{(2)}\in {\cal U}$ there exists $\b \xi \in [\b x^{(1)}, \b x^{(2)}]$ such that
\begin{equation}
\left\Arrowvert \b F\left(\b x^{(2)}\right)-\b F\left(\b x^{(1)}\right)\right\Arrowvert \le \left\Arrowvert D\b F(\b \xi)\left(\b x^{(2)}-\b x^{(1)}\right)\right\Arrowvert.
\label{eq:contrwohfp}
\end{equation}
The point $\b \xi$ is in ${\cal U}$ because the set ${\cal U}$, which is a sphere, is convex. Using~(\ref{eq:estnorofdf}) gives
\begin{eqnarray}
\left\Arrowvert \b F\left(\b x^{(2)}\right)-\b F\left(\b x^{(1)}\right)\right\Arrowvert &\le&\left\Arrowvert D\b F(\b \xi)\right\Arrowvert\left\Arrowvert\b x^{(2)}-\b x^{(1)}\right\Arrowvert\nonumber\\ 
&\le& \frac{1}{2}\left\Arrowvert\b x^{(2)}-\b x^{(1)}\right\Arrowvert .
\label{eq:onhalcomp}
\end{eqnarray}
Therefore, $\b F$ is a contraction map and can have at most one fixed point in ${\cal U}$ for a given $\b y$, which means that $\b f(\b x)=\b y$ for at most one $\b x\in {\cal U}$. This proves that $\b f$ is one-to-one in ${\cal U}$.

Let ${\cal V}=\b f({\cal U})$. We will show that for any $\b y^{(0)} \in {\cal V}$ there is a neighborhood contained in ${\cal V}$, which means that the set ${\cal V}$ open. If $\b y^{(0)} \in {\cal V}$, then there is $\b x^{(0)}\in {\cal U}$ such that $\b y^{(0)}=\b f\left( \b x^{(0)}\right)$. Denote by $B$ an open ball with center at $\b x^{(0)}$ and radius $r>0$. Choose $r$ so small that the closed ball $\bar{B}$ is in ${\cal U}$, that is,
\[
\bar{B}=\left\{\b x : \left\Arrowvert\b x-\b x^{(0)} \right\Arrowvert \le r \right \} \subseteq {\cal U}.
\]
We will now show that for any $\b y^{(0)}\in {\cal V}$ there is an open ball with center at $\b y^{(0)}$ and radius $rs$ that is contained in ${\cal V}$. For a given $\b y^{(0)}$ fix $\b y$ such that
\[
\left\Arrowvert \b y-\b y^{(0)}\right\Arrowvert < rs.
\]
Then, using~(\ref{eq:defscals}), we obtain
\begin{eqnarray}
\left\Arrowvert \b F(\b x) -\b x^{(0)} \right\Arrowvert &=& \left\Arrowvert \b J^{-1}\left(\b a\right)\left(\b y-\b y^{(0)} \right)\right\Arrowvert\nonumber\\
&\le & \left\Arrowvert \b J^{-1}\left(\b a\right)\right\Arrowvert rs\nonumber\\
&=& \frac{r}{2}.
\label{eq:rhwbf}
\end{eqnarray}
If $\b x$ is in $\bar{B}$, then using~(\ref{eq:onhalcomp}) and~(\ref{eq:rhwbf}), we get
\begin{eqnarray}
\left\Arrowvert \b F(\b x) -\b x^{(0)} \right\Arrowvert &\le&
\left\Arrowvert \b F(\b x) -\b F\left(\b x^{(0)}\right) \right\Arrowvert + \left\Arrowvert \b F\left(\b x^{(0)}\right) -\b x^{(0)} \right\Arrowvert \nonumber\\
&<& \frac{1}{2}\left\Arrowvert \b x-\b x^{(0)}\right\Arrowvert +\frac{r}{2}\nonumber\\
&\le& r.
\label{eq:pxmxor}
\end{eqnarray}
Hence, if $\b x\in \bar{B}$, then $\b F(\b x) \in B$, which means that $\b F$ is a contraction of $\bar{B}$ into $\bar{B}$. Since $\bar{B}$ is a closed subset of $\mb{\Bb R}^n$, it is complete. By Theorem~\ref{thm:contramap}, the map $\b F$ has a fixed point $\b x \in \bar{B}$. Furthermore, $\b y=\b f(\b x)$. Therefore,
\[
\b y \in \b f\left(\bar{B} \right)\subseteq \b f({\cal U})={\cal V}.
\]
This completes the proof of the fact that the set ${\cal V}$ is open. In summary, an inverse function $\b h:{\cal V} \to {\cal U}$ exists such that $x_i=h_i(\b y)$ for $\b y \in {\cal V}$.


We will now prove that the inverse function $\b h$ is a ${\cal C}^1$ map. Applying the Mean Value Theorem to the $i$-th component $f_i:\mb{\Bb R}^n \to \mb{\Bb R}$ of $\b f$, we obtain
\[
f_i\left(\b x^{(2)}\right)-f_i\left(\b x^{(1)}\right)=Df_i\left(\b \xi^{(i)}\right)\left( \b x^{(2)}-\b x^{(1)}\right),\quad i=1,2,\ldots,n,
\]
where $Df_i=\left[\begin{array}{cccc}
\frac{\partial f_i}{\partial x_1}&\frac{\partial f_i}{\partial x_2}&\cdots&\frac{\partial f_i}{\partial x_n}
\end{array}\right]$. The above equations can be represented in matrix form as
\begin{equation}
\b f\left( \b x^{(2)}\right)-\b f\left( \b x^{(1)}\right)=\left[\begin{array}{c}
Df_1\left(\b \xi^{(1)}\right)\\
Df_2\left(\b \xi^{(2)}\right)\\
\vdots\\
Df_n\left(\b \xi^{(n)}\right)
\end{array}\right]\left( \b x^{(2)}-\b x^{(1)}\right),
\label{eq:intfmvarxi}
\end{equation}
By assumption, the Jacobian matrix of $\b f$ is invertible at $\b a$, that is,
\[
\det D\b f\left(\b a\right)=\det \left[\begin{array}{c}
Df_1\left(\b a\right)\\
Df_2\left(\b a\right)\\
\vdots\\
Df_n\left(\b a\right)
\end{array}\right] \ne 0.
\]
Since $D\b f$ is continuous, there is a subset ${\cal U}$ of ${\cal S}$ within which $\det D\b f(\b x) \ne 0$ and
\begin{equation}
\det \left[\begin{array}{c}
Df_1\left(\b \xi^{(1)}\right)\\
Df_2\left(\b \xi^{(2)}\right)\\
\vdots\\
Df_n\left(\b \xi^{(n)}\right)
\end{array}\right] \ne 0.
\label{eq:deoffmvxi}
\end{equation}
Therefore, we can represent~(\ref{eq:intfmvarxi}) as
\begin{equation}
\b h\left( \b y^{(2)}\right)-\b h\left( \b y^{(1)}\right)=\left[\begin{array}{c}
Df_1\left(\b \xi^{(1)}\right)\\
Df_2\left(\b \xi^{(2)}\right)\\
\vdots\\
Df_n\left(\b \xi^{(n)}\right)
\end{array}\right]^{-1}\left( \b y^{(2)}-\b y^{(1)}\right).
\label{eq:eqrepoftabxi}
\end{equation}
Let
\[
\left[\begin{array}{c}
Df_1\left(\b \xi^{(1)}\right)\\
Df_2\left(\b \xi^{(2)}\right)\\
\vdots\\
Df_n\left(\b \xi^{(n)}\right)
\end{array}\right]^{-1}=\left[\begin{array}{c}
D^{-1}f_1\left(\b \xi^{(1)}\right)\\
D^{-1}f_2\left(\b \xi^{(2)}\right)\\
\vdots\\
D^{-1}f_n\left(\b \xi^{(n)}\right)
\end{array}\right],
\]
then we can write
\begin{equation}
h_i\left( \b y^{(2)}\right)-h_i\left( \b y^{(1)}\right)=D^{-1}f_i(\b \xi^{(i)})\left(\b y^{(2)} - \b y^{(1)} \right),\quad i=1,2,\ldots,n.
\label{eq:comwmvxi}
\end{equation}
Consider the limit
\begin{equation}
\lim_{\b y^{(2)} \to \b y^{(1)}}\frac{\left\arrowvert h_i\left( \b y^{(2)}\right)-h_i\left( \b y^{(1)}\right)-D^{-1}f_i(\b x^{(1)})\left(\b y^{(2)} - \b y^{(1)} \right)\right\arrowvert }{\left\Arrowvert \b y^{(2)} - \b y^{(1)} \right\Arrowvert },
\label{eq:limomvxi}
\end{equation}
where $D^{-1}f_i(\b x^{(1)})$ is the $i$th row of $D^{-1}\b f\left(\b x^{(1)}\right)$. Substituting~(\ref{eq:comwmvxi}) into~(\ref{eq:limomvxi}) gives
\[
\lim_{\b y^{(2)} \to \b y^{(1)}}\frac{\left\arrowvert \left(D^{-1}f_i\left(\b \xi^{(1)}\right)-D^{-1}f_i\left(\b x^{(1)}\right)\right)\left(\b y^{(2)} - \b y^{(1)} \right)\right\arrowvert }{\left\Arrowvert \b y^{(2)} - \b y^{(1)} \right\Arrowvert }=0
\]
because
\[
\lim_{\b x^{(2)} \to \b x^{(1)}}D^{-1}f_i\left(\b \xi^{(1)}\right)=D^{-1}f_i\left(\b x^{(1)}\right).
\]
Thus,
\[
Dh_i(\b y)=D^{-1}f_i(\b h(\b y)),
\]
which is continuous, and so $\b h$ is of class ${\cal C}^1$. Furthermore, if $\b f$ is of class ${\cal C}^p$, so is $\b h$.\\
\hspace*{5.5in} $\Box$

\subsection{The Implicit Function Theorem}
The implicit function theorem is closely related to the inverse function theorem. We illustrate the concept behind the implicit function theorem on a function on $\mb{\Bb R}^2$. Let ${\cal U}$ be an open set in $\mb{\Bb R}^2$, and let
\[
f:{\cal U} \to \mb{\Bb R}
\]
be a ${\cal C}^1$-function. Let $\left[\begin{array}{cc}
x_0 & y_0
\end{array}\right]^T$ be a point in ${\cal U}$, and let
\[
f(x_0,y_0)=0.
\]
Note that the right-hand side of the above equation can be an arbitrary constant. Without loss of generality, we can assume that this constant is $0$, as in the above equation. Our goal will be to determine whether there is a differentiable function $y=\phi(x)$ defined near $x=x_0$ such that $\phi(x_0)=y_0$ and
\[
f(x,\phi(x))=0
\]
for all $x$ near $x_0$. If such a function $\phi$ exists, then we say that $y=\phi(x)$ is the function determined implicitly by $f$.

As another illustrating example, consider a system of linear equations written as
\[
\left[\begin{array}{cc}
\b D & \b B
\end{array}\right]\left[\begin{array}{c}
\b x\\
\b y
\end{array}\right]-\b b=\b 0,
\]
where $\b D\in \mb{\Bb R}^{m \times n}$, $\b B\in \mb{\Bb R}^{m \times m}$, $\b x\in \mb{\Bb R}^n$, and $\b y \in \mb{\Bb R}^m$. A unique solution for $\b y$ exists if $\det \b B \ne 0$. We now generalize this result to a nonlinear case.
\begin{thm}
\label{thm:implictfunt}
Let
\[
\b f:\mb{\Bb R}^{n+m} \to \mb{\Bb R}^m
\]
be a ${\cal C}^p$, $p \ge 1$, function, where the $i$th component of $\b f$ is 
\[
f_i(x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_m),\quad i=1,2,\ldots,m.
\]
Let $\b x_0 \in \mb{\Bb R}^n$ and $\b y_0 \in \mb{\Bb R}^m$, and let $\b f\left( \b x_0,\b y_0\right) =\b 0$. Assume that at $\left( \b x_0,\b y_0\right)$
\[
\det \frac{\partial \b f}{\partial \b y} \ne 0.
\]
Then, there exists an open set ${\cal U} \subset \mb{\Bb R}^n$ containing $\b x_0$ and open set ${\cal V} \subset \mb{\Bb R}^m$ containing $\b y_0$ such that there exists a ${\cal C}^p$ function
\[
\b \phi:{\cal U} \to {\cal V}, \quad \b y=\b \phi(\b x),
\]
with $\b \phi(\b x_0)=\b y_0$ and $\b f(\b x,\b \phi (\b x))=\b 0$ for all $\b x$ in ${\cal U}$.
\end{thm} 
{\bf Proof} \quad Consider the following system of equations:
\begin{eqnarray*}
z_1 &=& x_1\\
{}&\vdots&{}\\
z_n &=& x_n\\
z_{n+1} &=& f_1(\b x,\b y)\\
{}&\vdots&{}\\
z_{n+m} &=& f_m(\b x,\b y),
\end{eqnarray*}
where
\begin{eqnarray*}
z_{10} &=& x_{10}\\
{}&\vdots&{}\\
z_{n0} &=& x_{n0}\\
z_{n+1,0} &=& f_1(\b x_0,\b y_0)=0\\
{}&\vdots&{}\\
z_{n+m,0} &=& f_m(\b x_0,\b y_0)=0.
\end{eqnarray*}
The above system defines a map $\b F:\mb{\Bb R}^{n+m} \to \mb{\Bb R}^{n+m}$. We claim that $\b F$ is locally ${\cal C}^p$-invertible at $\left[\begin{array}{cc}
\b x^T_0,&\b y^T_0
\end{array}\right]^T \in \mb{\Bb R}^{n+m}$. We compute the Jacobian matrix of $\b F$. We have
\[
D\b F=\left[\begin{array}{cc}
\b I_n & \b 0\\
\frac{\partial \b f}{\partial \b x} & \frac{\partial \b f}{\partial \b y}
\end{array}\right].
\]
The determinant of the above Jacobian matrix evaluated at $\left(\b x_0,\b y_0\right)$ is nonzero because
\[
\det D\b F=\det \frac{\partial \b f}{\partial \b y}.
\]
Hence, the inverse mapping theorem applies, and we have the inverse system
\begin{eqnarray*}
x_1 &=& z_1\\
{}&\vdots&{}\\
x_n &=& z_n\\
y_1 &=& h_1(z_1,z_2,\ldots,z_{n+m})\\
{}&\vdots&{}\\
y_m &=& h_m(z_1,z_2,\ldots,z_{n+m}).
\end{eqnarray*}
such that
\begin{eqnarray*}
z_{n+1} &=&  f_1(\b x,h_1(\b x,z_{n+1},\ldots,z_{n+m}),\ldots,h_m(\b x,z_{n+1},\ldots,z_{n+m}))\\
{}&\vdots&{}\\
z_{n+m} &=& f_m(\b x,h_1(\b x,z_{n+1},\ldots,z_{n+m}),\ldots,h_m(\b x,z_{n+1},\ldots,z_{n+m}))
\end{eqnarray*}
for all $z_{n+1},z_{n+2},\ldots,z_{n+m}$. In particular, for
\[
z_{n+1}=z_{n+2}=\ldots=z_{n+m}=0
\]
we have
\[
\b f\left( \b x,\b h(\b x,\b 0)\right)=\b 0,
\]
and
\begin{equation}
\b h\left(\b x_0,\b 0\right)=\b y_0.
\label{eq:imfthxoo}
\end{equation}
Thus,
\[
\b y=\b \phi(\b x)=\b h(\b x,\b 0).
\]
Note that so defined function $\b \phi$ is indeed the required function because by~(\ref{eq:imfthxoo}),
\[
\b y_0=\b h(\b x_0,\b 0)=\b \phi(\b x_0).
\]
This proves the implicit function theorem.\\
\hspace*{5.5in}$\Box$

=============================================
\clearpage

We now discuss a numerical approach to computing the largest Lyapunov exponent. One approach is to numerically integrate~(\ref{eq:tiinnosymole}) to obtain a reference trajectory $\b{\phi}_t(\b x_0)$, starting from a given initial point $\b x_0$. Then, at each time step $t_k$ integrate~(\ref{eq:tiinnosymole}) using the initial condition $\b{\phi}_{t_k}(\b x_0)+\varepsilon \b{\eta}$ arbitrarily close to $\b{\phi}_{t_k}(\b x_0)$, where $\|\b{\eta}\|=1$. Hence,
\[
\b{\phi}_{t_{k+1}}\left(\b{\phi}_{t_k}(\b x_0)+\varepsilon \b{\eta}\right)\approx\b{\phi}_{t_{k+1}}(\b x_0)+\varepsilon\,\b{\Phi}_{t_{k+1}}(\b x_0)\b \eta.
\]
Let $d_0(t_{k-1})=\varepsilon$ and $d(t_k)=\varepsilon\left\| \b{\Phi}_{t_{k+1}}(\b x_0)\b \eta\right\|$. Then, we could use~(\ref{larlyaex}) to evaluate the largest Lyapunov exponent.

We now describe a more efficient numerical method for evaluating the largest Lyapunov exponent, that can be found, for example, in the paper by Parker and Chua~\cite{parker87}. First, select the time interval $\Delta T$ and iteration count $N$. Then, integrate~(\ref{eq:tiinnosymole}) subject to a given initial condition $\b x(t_0)=\b x_0$ to obtain a reference trajectory $\b{\phi}_t(\b x_0)$ of the nonlinear system over the time interval $[t_0, N\Delta T]$. Select an arbitrary $\Delta \b x_0$ such that $\|\Delta \b x_0\|=1$. Find the solution $\Delta \b x(t_1)=\Delta\b x_1$ to
\begin{equation}
\frac{d}{dt}\Delta \b x=D\b f(\b{\phi}_t(\b x_{0}))\Delta \b x 
\label{eq:varlianotreq}
\end{equation}
subject to the initial condition $\Delta \b x_0$. Observe that we can set
\[
d_0(t_0)=\|\Delta \b x_0\|=1,
\]
and
\[
d(t_1)=\left\| \b{\Phi}_{t_1}(\b x_0)\Delta \b x_{0}\right\|=\left\| \Delta\b x_1\right\|.
\]
Next, normalize the solution $\Delta\b x_1$ and use this normalized solution as an initial condition to solve the differential equation~(\ref{eq:varlianotreq}) again. Repeat the process until $t_N=N\Delta T$. Denote $\Delta \b x(t_N)=\Delta \b x_N$. Then,
\begin{eqnarray}
\Delta \b x_N&=&\b{\Phi}_{t_N}(\b x_{N-1})\Delta \b x_{N-1}/\|\Delta \b x_{N-1} \|\nonumber\\
&=&\b{\Phi}_{t_N}(\b x_{N-1})\b{\Phi}_{t_{N-1}}(\b x_{N-2})\Delta \b x_{N-2}/\left(\|\Delta \b x_{N-1} \| \|\Delta \b x_{N-2} \|\right)\nonumber\\
&\vdots&\nonumber\\
&=&\b{\Phi}_{t_N}(\b x_{N-1})\b{\Phi}_{t_{N-1}}(\b x_{N-2})\nonumber\\
&{}&\qquad\cdots \b{\Phi}_{t_1}(\b x_0)\Delta \b x_{0}/\left(\|\Delta \b x_{N-1} \| \|\Delta \b x_{N-2} \|\cdots\|\Delta \b x_1\|\right),
\label{eq:proosotolimo}
\end{eqnarray}
Observe that we can set $d_0(t_{k-1})=1$ and $d(t_{k})=\left\|\Delta \b x_k\right\|$. We also have
\begin{equation}
\b{\Phi}_{t_N}(\b x_{0})\Delta\b x_0 = \b{\Phi}_{t_N}(\b x_{N-1})\b{\Phi}_{t_{N-1}}(\b x_{N-2})\cdots \b{\Phi}_{t_1}(\b x_0)\Delta \b x_{0}.
\label{eq:sostfrxz}
\end{equation}
Comparing~(\ref{eq:proosotolimo}) with~(\ref{eq:sostfrxz}) gives
\begin{equation}
\b{\Phi}_{t_N}(\b x_{0})\Delta\b x_0 = \Delta \b x_N\|\Delta \b x_{N-1} \| \|\Delta \b x_{N-2} \|\cdots\|\Delta \b x_1\|.
\label{eq:concattrama}
\end{equation}
Therefore, for large $N$,
\begin{eqnarray}
\mu_1 &\approx& \frac{1}{N\Delta T} \ln \left\| \b{\Phi}_{t_N}(\b x_{0})\Delta\b x_0\right\|\nonumber\\
&=& \frac{1}{N\Delta T} \ln \prod_{k=1}^{N} \left\| \Delta \b x_k\right\|\nonumber\\
&=& \frac{1}{N\Delta T}  \sum_{k=1}^N \ln \left\| \Delta \b x_k\right\|\\
&=& \frac{1}{N\Delta T}  \sum_{k=1}^N \ln \frac{d(t_k)}{d_0(t_{k-1})}, 
\label{eq:aproxlalyaex}
\end{eqnarray}
which is the defining formula~(\ref{larlyaex}).

======================
\clearpage

{\Large \bf LaSalle's Invariance Principle}

%\subsection{Notation and Definitions}
In this section, we generalize the Lyapunov function concept using LaSalle's approach as reported in~\cite{lasalle86}. This generalization is based on the idea of the so called invariant set. We first present this generalization for nonlinear dynamical systems modeled by the difference equation
\begin{equation}
\b x(k+1)=\b F(\b x(k)),
\label{eq:discsyswbf}
\end{equation}
where $k\in {\cal Z}_{+}$, ${\cal Z}_{+}$ denotes the set of nonnegative integers, $\b x:{\cal Z}_{+}\to \mb{\Bb R}^n$, that is, $\b x(k)$ is the state of the system model~(\ref{eq:discsyswbf}) at time $k$, and $\b F:\mb{\Bb R}^n \to \mb{\Bb R}^n$. We assume that the vector-valued function $\b F$ is continuous on $\mb{\Bb R}^n$, that is, if $\b x^j \to \b y$ then $\b F(\b x^j) \to \b F(\b y)$. If $\b x$ is a vector, then $\b F(\b x)$ is a vector and is the value of the function $\b F$ at $\b x$.

%If $\b x$ is a function, the symbol $\b F \b x$ denotes the composition of %functions
%\[
%\left(\b F \b x\right)(k)=\b F(\b x(k)).
%\]
%Thus the equation $\b x(k+1)=\b F(\b x(k))$ can also be written as $\b %x(k+1)=\b F \b x(k)$.

The solution to the initial value problem
\[
\b x(k+1)=\b F (\b x(k)), \quad \b x(0)=\b x^0
\]
is
\[
\b x(k)= \b x^k=\b F^k\left(\b x^0\right),
\]
where $\b F^k$ is the $k$-th iterate of $\b F$, that is, $\b F^0=\b I_n$, and $\b F^k=\b F \b F^{k-1}$.

A state ${\b x}_e \in \mb{\Bb R}^n$ is a {\em fixed point\/} or an {\em equilibrium state\/} of the system $\b x(k+1)=\b F (\b x(k))$ if $\b F\left({\b x}_e\right)={\b x}_e$. Thus the solution of the system that starts at ${\b x}_e$ stays at ${\b x}_e$ for all $k\ge 0$.

A subset ${\cal A} \subset \mb{\Bb R}^n$ is called {\em positively invariant\/} if $\b F({\cal A}) \subset {\cal A}$, that is, if $\b x \in {\cal A}$ then $\b F(\b x) \in {\cal A}$. It is clear that an equilibrium solution is invariant. The adjective ``positive'' is added to emphasize the fact that we will be interested in the behavior of the system for $k\ge 0$.

The solution through $\b x^0$ is bounded if there is a constant $M$ such that $\|\b F^k\left(\b x^0\right)\| \le M$ for all $k \ge 0$.

Consider again a particular solution $\b F^k\left(\b x^0\right)$. A point $\b y \in \mb{\Bb R}^n$ is a {\em positive limit point\/} or a {\em positive point of accumulation\/} of $\b F^k\left(\b x^0\right)$ if there is a subsequence $k_i$ such that $\b F^{k_i}\left(\b x^0\right) \to \b y$. The set of all positive limit points of $\b F^k\left(\b x^0\right)$ is called the {\em positive limit set\/} and denoted $\Omega\left(\b x^0\right)$.

A sequence $\{\b x^k\}$ is said to approach a set ${\cal A}$ if
\[
\rho\left(\b x^k,{\cal A}\right)=\inf \left\{\|\b x^k-\b y\|:\b y \in{\cal A} \right\} \to 0.
\]
\begin{lemma}
\label{lemma_lim_set}
If $\b F$ is continuous and $\b F^k\left(\b x^0\right)$ is bounded for all $k \ge 0$, then $\Omega\left(\b x^0\right)$ is non-empty, compact positively invariant set. Furthermore, $\b F^k\left(\b x^0\right) \to \Omega\left(\b x^0\right)$ as $k \to \infty$.
\end{lemma}
{\bf Proof}\quad Because the sequence $\left\{\b x^k\right\}$ is bounded, by the Bolzano-Weierstrass theorem, stated on page~\pageref{thm:bolzweierstr}, there is at least one positive limit point of $\left\{\b x^k\right\}$ and so $\Omega\left(\b x^0\right)$ is non-empty and bounded. For a proof that the set $\Omega\left(\b x^0\right)$ is closed, we refer to Khalil~[page~652]\cite{khalil96}. Because the set $\Omega\left(\b x^0\right)$ is also bounded, it is therefore compact.

We now show that $\Omega\left(\b x^0\right)$ is positively invariant.  For this let $\b y \in \Omega\left(\b x^0\right)$. Hence, there is a subsequence $k_i$ such that $\b x^{k_i} \to \b y$. Because $\b F$ is continuous, $\b x^{k_i + 1} = \b F\left(\b x^{k_i}\right) \to \b F(\b y)$ as $i \to \infty$. Therefore $\b F(\b y) \in \Omega\left(\b x^0\right)$ which implies that $\Omega\left(\b x^0\right)$ is invariant. Note that we do not have to have $\b y=\b F(\b y)$.

Finally, we will show that $\b F^k\left(\b x^0\right) \to \Omega\left(\b x^0\right)$ as $k \to \infty$. We shall prove the statement by contradiction. First observe that $\rho\left(\b x^k,\Omega\left(\b x^0\right)\right)$ is bounded because both $\left\{\b x^k\right\}$ and $\Omega\left(\b x^0\right)$ are. Assume that $\rho\left(\b x^k,\Omega\left(\b x^0\right)\right)$ does not converge to zero. Then, there is a subsequence $k_i$ such that $\b x^{k_i} \to \b y$ and $\rho\left(\b x^{k_i},\Omega\left(\b x^0\right)\right) \to a>0$. But since $\b y \in \Omega\left(\b x^0\right)$,
\[
\rho\left(\b x^{k_i},\Omega\left(\b x^0\right)\right)\le \|\b x^{k_i}-\b y\| \to 0,
\]
and thus $\rho\left(\b x^{k_i},\Omega\left(\b x^0\right)\right) \to 0$ which is a contradiction. The proof of the lemma is now complete.\\
\hspace*{5.5in} $\Box$


Let $V:\mb{\Bb R}^n \to \mb{\Bb R}$. Define the {\em Lyapunov difference\/} of $V$ relative to $\b x(k+1)=\b F (\b x(k))$ as
\[
\Delta V(\b x)=V\left(\b F(\b x)\right)-V(\b x),
\]
that is,
\[
\Delta V(\b x(k))=V\left(\b x(k+1)\right)-V(\b x(k)).
\]
If $\Delta V(\b x(k))\le 0$, then $V$ is non-increasing along solutions of the system.

We say that $V$ is a {\em Lyapunov\/} function for $\b x(k+1)=\b F (\b x(k))$ on a set ${\cal G} \subseteq \mb{\Bb R}^n$ if
\begin{enumerate}
\item $V$ is continuous on $\mb{\Bb R}^n$, and
\item $\Delta V(\b x(k))\le 0$ for all $\b x(k) \in {\cal G}$.
\end{enumerate}
A $c$-level surface of $V$ is the set
\[
V^{-1}(c)=\{\b x:V(\b x)=c,\; \b x\in \mb{\Bb R}^n\}.
\]
\begin{thm}[LaSalle's Invariance Principle]
If
\begin{enumerate}
\item $V$ is a Lyapunov function for $\b x(k+1)=\b F (\b x(k))$ in ${\cal G}$, and
\item the solution $\b F^k\left(\b x^0\right)$ is bounded and in ${\cal G}$,
\end{enumerate}
then, there is a number $c$ such that $\b F^k\left(\b x^0\right) \to {\cal M} \cap V^{-1}(c)$, where ${\cal M}$ is the largest positively invariant set contained in the set ${\cal E}=\left\{\b x \in \mb{\Bb R}^n:\Delta V = 0\right\}\cap \bar{\cal G}$, where $\bar{\cal G}$ denotes the closure of ${\cal G}$.
\end{thm}
{\bf Proof} \quad Because $\b x^k=\b F^k\left(\b x^0\right)$ is bounded and in ${\cal G}$, by Lemma~\ref{lemma_lim_set} the positive limit set $\Omega\left(\b x^0\right)$ is non-empty and in ${\cal G}$. Furthermore, $\b x^k$ tends to $\Omega\left(\b x^0\right)$. Now $\left\{V\left(\b x^k\right)\right\}$ is non-increasing and bounded below, so $V\left(\b x^k\right) \to c$ for some $c$. If $\b y \in \Omega\left(\b x^0\right)$, then there is a subsequence $k_i$ such that $\b x^{k_i} \to \b y$, and hence $V\left(\b x^{k_i}\right) \to V(\b y)$, that is, $V(\b y)=c$. Thus $V\left(\Omega\left(\b x^0\right) \right)=c$, and hence $\Omega\left(\b x^0\right) \subset V^{-1}(c)$. Because $V\left(\Omega\left(\b x^0\right) \right)=c$ and $\Omega\left(\b x^0\right)$ is positively invariant, we have $\Delta V\left(\Omega\left(\b x^0\right)\right)=0$. In summary
\[
\b x^k \to \Omega\left(\b x^0\right) \subset \left\{\b x \in \mb{\Bb R}^n: \Delta V=0 \right\}\cap \bar{\cal G} \cap V^{-1}(c).
\]
Since $\Omega\left(\b x^0\right)$ is positively invariant we have $\Omega\left(\b x^0\right) \subset {\cal M}$, and the proof of the theorem is complete.\\
\hspace*{5.5in} $\Box$\\
Using the preceding theorem we can study stability properties of difference equations.

LaSalle's Invariance Principle can be used to prove a result concerning the instability of equilibrium states.
%An equilibrium point ${\b x}_e$ is isolated if there is an $\varepsilon >0$ %such that there is no other equilibrium point, other than ${\b x}_e$, in %the ball $B_{\varepsilon}\left({\b x}_e\right)=\left\{\b x:\|\b x-\b %x_e\|<\varepsilon \right\}$.
\begin{thm}
Let ${\b x}_e$ be an equilibrium state of $\b x(k+1)=\b F (\b x(k))$. Let $\Delta V$ be positive definite with respect to ${\b x}_e$, and let $V$ take positive values arbitrarily close to ${\b x}_e$, and $V\left({\b x}_e\right)=0$, then ${\b x}_e$ is unstable.
\end{thm}
{\bf Proof} \quad We prove the theorem by contradiction.
%We thus assume that ${\b x}_e$ is stable. Let $\varepsilon > 0$ be %sufficiently small so that $\Delta V(\b x) >0$ for all $\b x \in %B_{\varepsilon}\left({\b x}_e\right)\setminus \left\{{\b x}_e\right\}$. %Because by assumption ${\b x}_e$ is stable, there is $\delta > 0$ so that %if $\b x^0 \in B_{\delta}\left({\b x}_e\right)$ then $\b x^k = \b %F^k\left(\b x^0\right) \in B_{\varepsilon}\left({\b x}_e\right)$ for all $k %\ge 0$. By assumption there is a point $\b x^0$ such that $V\left( \b x^0 %\right) >0$. Since $\b x^k$ is bounded and remains in %$B_{\varepsilon}\left({\b x}_e\right)$, by Lemma~\ref{lemma_lim_set} the %sequence $\left\{\b x^k\right\}$ tends to $\left\{\b x:\Delta V(\b x) = 0 %\right\} \cap B_{\varepsilon}\left({\b x}_e\right)={\b x}_e$.
%Another way to arrive at the above observation is as follows.
First observe that $-V$ is a Lyapunov function because $\Delta (-V)<0$. Since $\b x^k=\b F^k\left(\b x^0\right)$ is bounded we can apply the Invariance Principle to conclude that $\b x^k$ tends to $\left\{ \b x:\Delta (-V(\b x))=0 \right\}=\left\{{\b x}_e\right\}$, that is, $\b x^k \to {\b x}_e$. Using the above, we conclude that $V\left(\b x^k\right) \to V\left({\b x}_e \right) = 0$. However, $\Delta V\left(\b x^k\right) > 0$ and so
\[
V\left(\b x^k\right) \ge V\left(\b x^{k-1}\right)\ge \cdots \ge V\left(\b x^0\right) > 0.
\]
Hence, $V\left(\b x^k\right)\ge V\left(\b x^0\right)>0$ and thus we cannot have $V(\b x_e)=0$. The above contradiction completes the proof.\\
\hspace*{5.5in} $\Box$

\clearpage

\subsection{Properties of M-Matrices}

We start with the definition of the M-matrix.
\begin{defn}
A real $n \times n$ matrix $\mb{\bm$A$}$ is an M-matrix if all its off-diagonal elements are non-positive, that is, $a_{ij} \le 0$, $i \ne j$, and all its principal minors are positive.
\end{defn}
Note that if $\mb{\bm$A$}$ is an M-matrix, then its diagonal elements are positive since its principal minors are positive.\\
In establishing the needed properties of the M-matrices, we use the following technical lemma due to Fiedler and Pt\'{a}k~\cite{fiedler62}.
\begin{lemma}
\label{lemma:lu}
The following properties of an arbitrary matrix $\mb{\bm$A$} \in \mb{\Bb R}^{n \times n}$ are equivalent:
\begin{itemize}
\item[(i)] The leading principal minors of $\mb{\bm$A$}$ are positive,
\item[(ii)] There exists a lower triangular matrix $\mb{\bm$L$} \in \mb{\Bb R}^{n \times n}$ and an upper triangular matrix $\mb{\bm$U$} \in \mb{\Bb R}^{n \times n}$ both with positive diagonal elements such that $\mb{\bm$A$}=\mb{\bm$L$}\mb{\bm$U$}$
\end{itemize}
\end{lemma}
{\bf Proof}\quad We first prove the implication (i)$ \Rightarrow $(ii). The proof is by induction. Obviously the implication holds for $n=1$. Suppose the statement holds for all real matrices of order $n-1$. Let us represent $\mb{\bm$A$} \in \mb{\Bb R}^{n \times n}$ as follows:
\[
\mb{\bm$A$} = \left[\begin{array}{cc}
\mb{\bm$A$}_{n-1} & \mb{\bm$a$}\\
\b b^T & a_{nn}
\end{array} \right],
\]
where $\mb{\bm$A$}_{n-1} \in \mb{\Bb R}^{(n-1) \times (n-1)}$, $\mb{\bm$a$} \in \mb{\Bb R}^{(n-1) \times 1}$, $\b b^T \in \mb{\Bb R}^{1 \times (n-1)}$, and $a_{nn} \in \mb{\Bb R}$. From the inductive hypothesis, the matrix $\mb{\bm$A$}_{n-1}$ has positive leading principal minors, $\mb{\bm$A$}_{n-1}=\mb{\bm$L$}_{n-1}\mb{\bm$U$}_{n-1}$, where $\mb{\bm$L$}_{n-1} \in \mb{\Bb R}^{(n-1) \times (n-1)}$ is a lower triangular matrix with positive diagonal elements, and $\mb{\bm$U$}_{n-1} \in \mb{\Bb R}^{(n-1) \times (n-1)}$ is an upper triangular matrix with positive diagonal elements. Observe that
\[
\left[\begin{array}{cc}
\mb{\bm$I$}_{n-1} & \mb{\bm$0$}\\
-\b b^T \mb{\bm$A$}_{n-1}^{-1} & 1
\end{array} \right] \mb{\bm$A$} = \left[\begin{array}{cc}
\mb{\bm$A$}_{n-1} & \mb{\bm$a$}\\
\mb{\bm$0$} & a_{nn} - \b b^T\mb{\bm$A$}_{n-1}^{-1}\mb{\bm$a$}
\end{array}\right],
\]
where from the assumptions $\det \mb{\bm$A$}_{n-1}>0$, and $\det \mb{\bm$A$}>0$. Hence,
\[
0< \det \mb{\bm$A$}=\left( a_{nn} - \b b^T\mb{\bm$A$}_{n-1}^{-1}\mb{\bm$a$} \right) \det \mb{\bm$A$}_{n-1}.
\]
Thus, we have
\[
a_{nn} - \b b^T\mb{\bm$A$}_{n-1}^{-1}\mb{\bm$a$}>0.
\]
Let
\[
\mb{\bm$L$}=\left[\begin{array}{cc}
\mb{\bm$L$}_{n-1} & \mb{\bm$0$}\\
\b b^T \mb{\bm$U$}_{n-1}^{-1} & 1
\end{array} \right],
\]
and
\[
\mb{\bm$U$}=\left[\begin{array}{cc}
\mb{\bm$U$}_{n-1} & \mb{\bm$L$}_{n-1}^{-1}\mb{\bm$a$}\\
\mb{\bm$0$} & a_{nn} - \b b^T \mb{\bm$A$}_{n-1}^{-1}\mb{\bm$a$}
\end{array}\right].
\]
One can check that
\[
\mb{\bm$A$}=\mb{\bm$L$}\mb{\bm$U$},
\]
and that the matrices $\mb{\bm$L$}$ and $\mb{\bm$U$}$ satisfy~(ii).

We now prove the implication (i)$ \Leftarrow $(ii). From the generalized Cauchy's Theorem it follows that the leading principal minors of $\mb{\bm$A$}=\mb{\bm$L$}\mb{\bm$U$}$ are just the products of the corresponding leading principal minors of $\mb{\bm$L$}$ and $\mb{\bm$U$}$. This is because the matrix $\mb{\bm$L$}$ is lower triangular with positive diagonal elements and the matrix $\mb{\bm$U$}$ is upper triangular with positive diagonal elements. This completes our proof of the lemma.\\
\hspace*{5.5in} $\Box$

The following theorem, also due to Fiedler and Pt\'{a}k~\cite{fiedler62}, establishes some properties of the M-matrices in terms of their LU-decomposition.
\begin{thm}
\label{thm:m_matlu}
Let $\mb{\bm$A$} \in \mb{\Bb R}^{n \times n}$ be an M-matrix. Then, there is a lower triangular matrix $\mb{\bm$L$} \in \mb{\Bb R}^{n \times n}$ and an upper triangular matrix $\mb{\bm$U$} \in \mb{\Bb R}^{n \times n}$ both with positive diagonal elements. Their off-diagonal elements are non-positive. Furthermore, both $\mb{\bm$L$}^{-1}$ and $\mb{\bm$U$}^{-1}$ are non-negative which implies that $\mb{\bm$A$}^{-1}=\mb{\bm$U$}^{-1}\mb{\bm$L$}^{-1}$ is non-negative.
\end{thm}
{\bf Proof}\quad We prove this theorem by induction. The theorem holds for $n=1$. Suppose the theorem holds for all matrices of order $n-1$. Consider now the factorization from the proof of Lemma~\ref{lemma:lu}. We have
\[
\mb{\bm$A$}=\mb{\bm$L$}\mb{\bm$U$} = \left[\begin{array}{cc}
\mb{\bm$L$}_{n-1} & \mb{\bm$0$}\\
\b b^T\mb{\bm$U$}_{n-1}^{-1} & 1
\end{array} \right]\left[\begin{array}{cc}
\mb{\bm$U$}_{n-1} & \mb{\bm$L$}_{n-1}^{-1}\mb{\bm$a$}\\
\mb{\bm$0$} & a_{nn} - \b b^T\mb{\bm$A$}_{n-1}^{-1}\mb{\bm$a$}
\end{array}\right],
\]
where $\mb{\bm$L$}_{n-1}$, $\mb{\bm$U$}_{n-1}$, $\mb{\bm$L$}_{n-1}^{-1}$, $\mb{\bm$U$}_{n-1}^{-1}$ and $\mb{\bm$A$}_{n-1}^{-1}=\mb{\bm$U$}_{n-1}^{-1}\mb{\bm$L$}_{n-1}^{-1}$ satisfy the inductive hypotheses. We see that $l_{ij} \le 0$ for $i>j$ and $u_{kl} \le 0$ for $k<l$ which means that the off-diagonal elements of $\mb{\bm$L$}$ and $\mb{\bm$U$}$ are non-positive. Their diagonal elements are positive. The inverse of $\mb{\bm$L$}$ is
\[
\mb{\bm$L$}^{-1}=\left[\begin{array}{cc}
\mb{\bm$L$}_{n-1}^{-1} & \mb{\bm$0$}\\
-\b b^T\mb{\bm$L$}_{n-1}^{-1} & 1
\end{array}\right].
\]
From the inductive assumption $\mb{\bm$L$}_{n-1}^{-1}$ and $\mb{\bm$A$}_{n-1}^{-1}$ are non-negative and hence $\mb{\bm$L$}_{n-1}^{-1}$ is non-negative.\\
The inverse of $\mb{\bm$U$}$ is
\[
\mb{\bm$U$}^{-1} = \left[\begin{array}{cc}
\mb{\bm$U$}_{n-1}^{-1} & -\mb{\bm$A$}_{n-1}^{-1} \frac{\mb{\bm$a$}}{ a_{nn} - \b b^T \mb{\bm$A$}_{n-1}^{-1} \mb{\bm$a$}}\\
\mb{\bm$0$} & \left( a_{nn}-\b b^T\mb{\bm$A$}_{n-1}^{-1}\mb{\bm$a$} \right) ^{-1}
\end{array} \right].
\]
By the inductive assumptions and the fact that $a_{nn}-\b b^T\mb{\bm$A$}_{n-1}^{-1}\mb{\bm$a$}>0$, the matrix $\mb{\bm$U$}^{-1}$ is non-negative, and the proof is complete.\\
\hspace*{5.5in} $\Box$

We now consider a more general class of matrices called Z-matrices.
\begin{defn}
A real $n \times n$ matrix $\mb{\bm$A$}$ whose off-diagonal elements are non-positive is called a Z-matrix.
\end{defn}
Note that M-matrices are Z-matrices.\\
To simplify our presentation, we use the notation $\mb{\bm$B$}>0$, to mean that all the elements of $\mb{\bm$B$}$ are positive, where $\mb{\bm$B$}$ can be a matrix or a vector. Respectively, $\mb{\bm$B$} \ge 0$ means that all the elements of $\mb{\bm$B$}$ are non-negative. We are now ready to state and prove the following theorem concerning properties of Z-matrices. The theorem can be found in Fiedler and Pt\'{a}k~\cite{fiedler62}.
\begin{thm}
\label{thm:z_mat}
Let $\mb{\bm$A$} \in \mb{\Bb R}^{n \times n}$ be a Z-matrix. Then, the following conditions are equivalent:
\begin{itemize}
\item[(i)] There exists a vector $\mb{\bm$x$} \ge 0$ such that $\mb{\bm$Ax$}>0$;
\item[(ii)] There exists a vector $\mb{\bm$y$}>0$ such that $\mb{\bm$Ay$}>0$;
\item[(iii)] There exists a diagonal matrix $\mb{\bm$D$}$ with positive diagonal elements such that $\mb{\bm$ADe$}>0$, where $\mb{\bm$e$}=\left[\begin{array}{ccc}
1, & \ldots, & 1
\end{array}\right]^T \in \mb{\Bb R}^n$;
\item[(iv)] There exists a diagonal matrix $\mb{\bm$D$}$ with positive diagonal elements such that the matrix $\mb{\bm$W=AD$}$ has a dominant positive main diagonal, that is for $i=1,2,\ldots,n$, we have $w_{ii}>\sum_{\stackrel{j=1}{j \ne i}}^n w_{ij}$.
\end{itemize}
\end{thm}
{\bf Proof}\quad We prove this theorem using the following scheme:
\[
\mb{(i)} \Rightarrow \mb{(ii)} \Rightarrow \mb{(iii)} \Rightarrow \mb{(iv)} \Rightarrow \mb{(i)}.
\]
We begin with the implication (i)$ \Rightarrow $(ii). Thus suppose that there exists a vector $\mb{\bm$x$} \ge 0$ such that $\mb{\bm$Ax$} > 0$. Let $\mb{\bm$e$}=\left[\begin{array}{ccc}
1, & \ldots, & 1
\end{array}\right]^T \in \mb{\Bb R}^n$, $\epsilon > 0$, and $\mb{\bm$y$} = \mb{\bm$x$} + \epsilon \mb{\bm$e$} > 0$. Then
\[
\mb{\bm$Ay$} = \mb{\bm$A(x$} + \epsilon \mb{\bm$e$}) = \mb{\bm$Ax$} + \epsilon \mb{\bm$Ae$} > 0
\]
for a sufficiently small $\epsilon > 0$.

We next prove that (ii)$ \Rightarrow $(iii). For this let $\mb{\bm$y$}=\left[\begin{array}{ccc}
y_1, & \ldots, & y_n
\end{array}\right]^T > 0$ be such that $\mb{\bm$Ay$} > 0$. Let
\[
\mb{\bm$D$} = \left[\begin{array}{ccccc}
y_1 & 0 & 0 & \ldots & 0\\
0 & y_2 & 0 & \ldots & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
0 & 0 & 0 & \ldots & y_n
\end{array} \right].
\]
It then follows that $\mb{\bm$ADe$} = \mb{\bm$Ay$} > 0$.

To prove (iii)$ \Rightarrow $(iv), let $\mb{\bm$D$} > 0$ be a diagonal matrix with positive diagonal elements such that $\mb{\bm$ADe$} > 0$. We denote
\[
\mb{\bm$AD$}=\mb{\bm$W$} = \left[\begin{array}{cccc}
w_{11} & -w_{12} & \ldots & -w_{1n}\\
-w_{21} & w_{22} & \ldots & -w_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
-w_{n1} & -w_{n2} & \ldots & w_{nn}
\end{array} \right],
\]
where $w_{ij} \ge 0$ for $i \ne j$. Note that $\mb{\bm$ADe$}=\mb{\bm$We$}>0$ which is equivalent to
\[
w_{ii} > \sum_{\stackrel{j=1}{j \ne i}}^{n} w_{ij}, \qquad i=1,2,\ldots ,n.
\]
Since $w_{ij} \ge 0$, we have
\[
w_{ii} > \sum_{\stackrel{j=1}{j \ne i}}^{n} |w_{ij}|.
\]
The above means that $\mb{\bm$W$}$ is a row diagonal dominant matrix with positive main diagonal. Note $a_{ii} > 0$ since $0 < w_{ii} = a_{ii} d_i$ and $d_i > 0$.

To complete the proof of the theorem we now show that (iv)$ \Rightarrow $(i). For this let $\mb{\bm$D$}$ be a diagonal matrix with positive diagonal elements such that $\mb{\bm$W$} = \mb{\bm$AD$}$ has a positive dominant main diagonal. Then
\[
0 < \mb{\bm$We$} = \mb{\bm$ADe$} = \mb{\bm$Ax$},
\]
where
\[
\mb{\bm$x$}=\left[\begin{array}{ccc}
d_1 & \ldots & 0\\
\vdots & \ddots & \vdots\\
0 & \ldots & d_n
\end{array} \right] \left[\begin{array}{c}
1\\
\vdots\\
1
\end{array} \right]=\left[\begin{array}{c}
d_1\\
\vdots\\
d_n
\end{array}\right] > 0.
\]
Hence $(i)$ is satisfied.\\
\hspace*{5.5in} $\Box$

To proceed further, we need the following two technical results.
\begin{lemma}
\label{lemma:hadamard}
An $n \times n$ matrix $\mb{\bm$A$}$ with complex coefficients such that
\[
|a_{ii}| > \sum_{\stackrel{j=1}{j \ne i}}^{n} |a_{ij}|\quad\mb{for}\quad i=1,2,\ldots,n,
\]
is nonsingular, that is, $\det \mb{\bm$A$} \ne 0$.
\end{lemma}
{\bf Proof}\quad We prove the above lemma by contraposition. Suppose that $\det \mb{\bm$A$} = 0$. Then, there exists a nontrivial solution $\mb{\bm$x$} \ne \mb{\bm$0$}$ to $\mb{\bm$Ax=0$}$, that is for $k=1,2,\ldots,n$,
\[
\sum_{j=1}^{n} a_{kj} x_j = 0.
\]
Let
\[
x_i = \max_{1 \le k \le n} |x_k|.
\]
Rearranging $\sum_{j=1}^{n} a_{ij} x_j = 0$ yields
\[
-a_{ii}x_i=a_{i1}x_1 + \cdots + a_{i,i-1}x_{i-1} + a_{i,i+1}x_{i+1} + \cdots + a_{in}x_n.
\]
Taking the absolute values of the both sides of the above equation gives
\[
|a_{ii}||x_i|=|a_{i1}x_1 + \cdots + a_{i,i-1}x_{i-1} + a_{i,i+1}x_{i+1} + \cdots + a_{in}x_n| \le \sum_{\stackrel{j=1}{j \ne i}}^{n} |a_{ij}||x_j|.
\]
Thus
\[
|a_{ii}| \le \sum_{\stackrel{j=1}{j \ne i}}^{n} |a_{ij}| \frac{|x_j|}{|x_i|} \le  \sum_{\stackrel{j=1}{j \ne i}}^{n} |a_{ij}|
\]
which contradicts the assumption that $|a_{ii}| > \sum_{\stackrel{j=1}{j \ne i}}^{n} |a_{ij}|$.\\
\hspace*{5.5in} $\Box$

The above lemma says that if a matrix $\mb{\bm$A$}$ is row diagonal dominant then it is nonsingular. Following the arguments of the proof of the lemma, we can show that if a square, real or complex, matrix is column diagonal dominant then it is also nonsingular. We state this result in the following corollary.
\begin{corollary}
A real or complex $n \times n$ matrix $\mb{\bm$A$}$ such that 
for $j=1,2,\ldots,n$,
\[
|a_{jj}| > \sum_{\stackrel{k=1}{k \ne j}}^{n} |a_{kj}|
\]
is nonsingular. 
\end{corollary}

We now use Lemma~\ref{lemma:hadamard} to prove the following theorem due to Gershgorin.
\begin{thm}
\label{thm:gershgorin}
Given a real or complex $n \times n$ matrix $\mb{\bm$A$}$. Let $D_i$, $i=1,2,\ldots,n$, denotes the $i$-th closed disk in the complex plane centered at $a_{ii}$ whose radius is $r_i=\sum_{\stackrel{j=1}{j \ne i}}^{n} |a_{ij}|$. Then the eigenvalues of $\mb{\bm$A$}$ are located in the union $\bigcup_{i=1}^{n}D_i$. 
\end{thm}
{\bf Proof}\quad The eigenvalues of $\mb{\bm$A$}$ are the roots of the characteristic equation
\[
\det [\lambda \mb{\bm$I$} - \mb{\bm$A$}] = \det \left[\begin{array}{cccc}
\lambda - a_{11} & -a_{12} & \ldots & -a_{1n}\\
-a_{21} & \lambda - a_{22} & \ldots & -a_{2n}\\
\vdots & \vdots & \ddots & \vdots \\
-a_{n1} & -a_{n2} & \ldots & \lambda -a_{nn}
\end{array} \right]=0.
\]
By Lemma~\ref{lemma:hadamard}, the characteristic polynomial is nonzero if for all $i=1,2,\ldots,n$,
\[
|\lambda -a_{ii}| > \sum_{\stackrel{j=1}{j \ne i}}^{n} |a_{ij}|,
\]
that is, for all $i=1,2,\ldots,n$
\[
|\lambda -a_{ii}| > r_i.
\]
Thus the eigenvalues of $\mb{\bm$A$}$ must be in the set $\bigcup_{i=1}^{n} D_i$.\\
\hspace*{5.5in} $\Box$

In the following theorem, due to Fiedler and Pt\'{a}k~\cite{fiedler62}, we collect a number of equivalent conditions characterizing the M-matrices.
\begin{thm}
\label{thm:m_matsum}
Let $\mb{\bm$A$}$ be a Z-matrix. Then the following conditions are equivalent
\begin{itemize}
\item[(i)] There exists a vector $\mb{\bm$x$} \ge 0$ such that $\mb{\bm$Ax$} > 0$;
\item[(ii)] There exists a diagonal matrix $\mb{\bm$D$}$ with positive diagonal such that the matrix $\mb{\bm$W=AD$}$ has a positive main diagonal and is row diagonal dominant;
\item[(iii)] Eigenvalues of $\mb{\bm$W$}$ have positive real parts and principal minors of $\mb{\bm$W$}$ are positive;
\item[(iv)] All principal minors of $\mb{\bm$A$}$ are positive, that is, $\mb{\bm$A$}$ is an M-matrix;
\item[(v)] All leading principal minors of $\mb{\bm$A$}$ are positive;
\item[(vi)] There exists a lower triangular matrix $\mb{\bm$L$}$ and an upper triangular matrix $\mb{\bm$U$}$ both with positive diagonals such that $\mb{\bm$A=LU$}$. Furthermore, $l_{ij} \le 0$ for $i>j$, and $u_{kl} \le 0$ for $k<l$;
\item[(vii)] $\mb{\bm$A$}^{-1}$ exists and $\mb{\bm$A$}^{-1} \ge 0$.
\end{itemize}
\end{thm}
{\bf Proof}\quad The implication (i)$ \Rightarrow $(ii) follows from Theorem~\ref{thm:z_mat}. To prove (ii)$ \Rightarrow $(iii), we represent the matrix $\mb{\bm$W=AD$}$ as follows
\[
\mb{\bm$W=AD$}=\left[\begin{array}{cccc}
w_{11} & -w_{12} & \ldots & -w_{1n}\\
-w_{21} & w_{22} & \ldots & -w_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
-w_{n1} & -w_{n2} & \ldots & w_{nn}
\end{array} \right],
\]
where $w_{ij} \ge 0$ for $i \ne j$, and $w_{ii} > 0$, as follows from Theorem~\ref{thm:z_mat}. Furthermore
\[
w_{ii} > \sum_{\stackrel{j=1}{j \ne i}}^{n}w_{ij} \quad \mbox{for} \quad i=1,2,\ldots,n.
\]
The above implies that each principal minor matrix of $\mb{\bm$W$}$ is also row diagonal dominant. By the Theorem of Gershgorin, the eigenvalues of $\mb{\bm$W$}$ as well as its principal minor matrices are located on the disks with centers at $w_{ii}$ and radii $r_i < w_{ii}$. Hence they must have real positive parts.

We shall now show that (iii)$ \Rightarrow $(iv) holds. First note that since the determinant of a square matrix is the product of its eigenvalues and the product of complex eigenvalues of a real matrix is positive, it follows that all principal minors of the matrix $\mb{\bm$W$}$ are positive. Next, the matrix $\mb{\bm$W$}$ has the form
\[
\mb{\bm$W=AD$}=\left[\begin{array}{cccc}
a_{11} & -a_{12} & \ldots & -a_{1n}\\
-a_{21} & a_{22} & \ldots & -a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
-a_{n1} & -a_{n2} & \ldots & a_{nn}
\end{array} \right]
\left[\begin{array}{cccc}
d_{11} & \ldots & {} & 0\\
{} & d_{22} & {} & {}\\
\vdots & {} & \ddots & \vdots\\
0 & \ldots & {} & d_{nn}
\end{array} \right],
\]
where $a_{ij} \ge 0$ for $i \ne j$, $a_{ii} > 0$, and $d_{ii} > 0$. Thus if the principal minors of $\mb{\bm$W$}$ are positive, the principal minors of $\mb{\bm$A$}$ must be positive, and vice versa. This is because
\[
\b W\left(\begin{array}{cccc}
i_1 & i_2 & \ldots & i_k\\
i_1 & i_2 & \ldots & i_k
\end{array} \right)=
\b A\left[\begin{array}{cccc}
i_1 & i_2 & \ldots & i_k\\
i_1 & i_2 & \ldots & i_k
\end{array} \right]
\left[\begin{array}{cccc}
d_{i_1 i_1} & \ldots & {} & 0\\
{} & d_{i_2 i_2} & {}& {}\\
{} & {} & \ddots & {}\\
0 & \ldots & {} & d_{i_k i_k}
\end{array}\right],
\]
where
\[
\b W\left(\begin{array}{cccc}
i_1 & i_2 & \ldots & i_k\\
i_1 & i_2 & \ldots & i_k
\end{array} \right)
\]
is a matrix formed from $i_1,i_2,\ldots,i_k$ columns and $i_1,i_2,\ldots,i_k$ rows of the matrix $\mb{\bm$W$}$.

The implication (iv)$ \Rightarrow $(v) follows from the observation that the leading principal minors are also principal minors.

The implications (v)$ \Rightarrow \mb{(vi)} \Rightarrow $(vii) follow from Theorem~\ref{thm:m_matlu}.

Finally, to complete the proof, we show that (vii)$ \Rightarrow $(i). For this note that if $\mb{\bm$A$}^{-1}$ exists and $\mb{\bm$A$}^{-1} \ge \mb{\bm$0$}$, then
\[
\mb{\bm$x=A$}^{-1}\mb{\bm$e$} \ge \mb{\bm$0$},
\]
where $\mb{\bm$e$}=\left[1,1,\ldots,1\right]^T \in \mb{\Bb R}^n$. Hence
\[
\mb{\bm$Ax=e$} > \mb{\bm$0$},
\]
which implies that (i) is satisfied.\\
\hspace*{5.5in} $\Box$

\bibliography{brain,root2,mybook}
\bibliographystyle{plain}
\end{document}