%kaispap.tex 97/07/17 18:00 % # 135 published in Fuhrmann Proc's \documentclass[12pt, leqno]{article} \usepackage{amsmath} \usepackage{amssymb} \newcommand{\msn}{\medskip\noindent} \newcommand{\bsn}{\bigskip\noindent} \newcommand{\be}{\begin{equation}} \newcommand{\ee}{\end{equation}} \newcommand{\ben}{\begin{enumerate}} \newcommand{\een}{\end{enumerate}} \newcommand{\np}{\newpage \noindent} \newcommand{\bc}{\begin{center}} \newcommand{\ec}{\end{center}} %\newcommand{\R}{{\bf R}} %\newcommand{\C}{{\bf C}} \newcommand{\spec}{\mbox{spec}} \newcommand{\ci}{\subseteq} \newcommand{\Hn}{\mathcal{H}_n} \newcommand{\Pn}{\mathcal{P}_n} \newcommand{\mbf}{\underline} \newcommand{\ga}{\alpha} \newcommand{\gm}{\gamma} \newcommand{\vph}{\varphi} \newcommand{\cd}{^{\centerdot}} %symbol for real numbers \newcommand{\R}{\mathbb{R}} %symbol for complex numbers \newcommand{\C}{\mathbb{C}} \newcommand{\mc}{\mathcal{C}} %\input amsfonts.sty %\begin{document} %\huge \baselineskip=25pt %\magnification1200 % onto #1, superimpose a centered dot -#2ex from the right and #3ex up. \def\withdot#1#2#3{{#1}\kern-#2ex\raise#3ex\hbox{$\centerdot$}\kern#2ex} % e.g., here are reasonable definitions of < and > and \geq with a centered % dot inside: \def\ltdot{\mathbin{\withdot<{.9}{.35}}} \def\gtdot{\mathbin{\withdot>{1.4}{.35}}} \def\gndot{\mathbin{\withdot\gneq{1.4}{.53}}} \def\gedot{\mathbin{\withdot\geq{1.4}{.53}}} % and here is the test %$$a\ltdot b,\quad a\gtdot b, \quad a\gedot b, \quad a \gndot b$$ %$$a \gneq b, \quad a \gtrdot b$$ %$$\dot{>} \ \Dot{>} \dot{\geq}$$% %$$ \centerdot{>} \ \cdot{>} \Dot{>} \ \centerdot{\geq} \ \centerdot{\leq}$$ %$$\gtrdot \ \underline{\gtrdot} \geq \not\underline\gtrdot$$ %$$>^\centerdot \ \geq^\centerdot > \ ^\centerdot\geq $$% %$$\geq\cd$$ $$>_\centerdot \ \geq_\centerdot \ _\centerdot > %\_\centerdot\geq$$ \bibliographystyle{plain} \begin{document} \title {LYAPUNOV REVISITED:\\ VARIATIONS ON A MATRIX THEME} \author {Hans Schneider \thanks {Work supported by NSF Grant DMS-9424346.} \\Department of Mathematics \\University of Wisconsin \\ Madison, Wisconsin 53706, USA} \date{} \maketitle \bc {\bf Dedicated to Paul~A. Fuhrmann\\ on the occasion of his 60th birthday} \ec \begin{abstract} \noindent In this expository note it is shown that a cone version of the Perron--Frobenius theorem implies various generalizations of a matrix form of Lyapunov's famous theorem: \msn Si les \'equations diff\'erentielles du mouvement troubl\'e sont telles qu'il est possible de trouver une fonction d\'efinie $V$, dont la d\'eriv\'ee $\dot{V}$ soit une fonction de signe fixe et contraire \`a celui de $V$, ou se r\'eduise identiquement \`a z\'ero, le mouvement non troubl\'e est stable. \end{abstract} \noindent Lyapunov's basic result on the stability of solutions of differential equations \cite[Ch.I, \S16, Th.I]{Lyap} is here quoted from the French translation of his 1892 memoir. Lyapunov also investigated a more restrictive concept, that of asymptotic stability, in the case of linear differential equations with constant coefficients where $V$ is a homogeneous form of degree $m$, see \cite[Ch. II]{Lyap}. Gantmacher \cite[Ch.XV, \S5]{Gant} considered the case of constant coefficients $\dot{x} = Ax, \ x \in \C^n,\ A \in \C^{nn}$, and restricted $V$ to a homogeneous quadratic form. Thus $$V(x) = x^*Hx, \ \ H^* = H$$ and $$\dot V(x) = \dot{x}^*Hx + x^*H\dot{x} = x^*(A^*H + HA)x.$$ Putting $$W(x) = x^*Kx,\ K \gtdot 0,$$ where $$K \gtdot 0 := K \ {\rm positive \ definite},$$ and noting that $$x(t) \rightarrow 0 \ {\rm as} \ t \rightarrow \infty \Leftrightarrow \Re(\lambda) < 0, \ {\rm all} \ \lambda \in \spec(A),$$ he obtained a result \cite[Ch.XV, Th.3']{Gant} that is usually called ``Lyapunov's theorem'' by matrix theorists which I state in a slightly more general form: \bsn {\em Theorem 0} : Let $A \in \C^{nn}$ and let $K \gtdot 0$. Then there exists $H \gtdot 0$ such that $AH + HA^* = K$ if and only if $A$ is positive stable (i.e. has all eigenvalues in the {\em right} half plane). \bsn Gantmacher's reformulation, see also \cite[Kap. II, \S 8]{Hahn}, had a deep influence on the inertia theory of matrices as developed in the 1960's and subsequently, but I shall pursue this topic no further. Note that in Lyapunov's original formulation the theorem concerned the {\em existence} of a function $V$ with certain properties, while Gantmacher's version concerns {\em solving} a matrix equation. The two formulations are equivalent for we have: $$ \forall K \gtdot 0,\ \exists H \gtdot 0,\ AH+HA^* = K \\ \Longleftrightarrow \\ \exists H \gtdot 0,\ AH + HA^* \gtdot 0. $$ I had met this situation before in Perron--Frobenius theory. Thus we define, for $P \in \R^{mn}$, $$ P > 0 := p_{ij} > 0, \ {\rm all} \ (i,j),$$ $$ P \geq 0 := p_{ij} \geq 0, \ {\rm all} \ (i,j)$$ and employ the spectral radius $\rho(P)$ defined as usual by $$\rho(P) = \max\{|\lambda| : \lambda \in \spec(P)\}.$$ If $P \geq 0$ it follows by Perron--Frobenius that $\rho(P)$ is an eigenvalue of $P$. We further have, see e.g. \cite[Theorem 6.2.]{BePl}, \bsn {\em Theorem} 1 : Let $A = \sigma I - P$ where $P \geq 0$. Then the following are equivalent: \begin{enumerate} \item $\sigma > \rho(P)$. \item For all $y > 0$, there exists $x > 0$ such that $ Ax = y$. (viz. $A^{-1} > 0)$. \item There exists $x > 0$ such that $Ax > 0$. \end{enumerate} Again we have $$\forall \Longleftrightarrow \exists \ .$$ In \cite{Schn} I found a unified treatment and generalized Lyapunov's theorem. The key is a generalization of Perron--Frobenius to cones which is due to Krein--Rutman \cite{KrRu} in a Banach space. We consider only the finite dimensional case here. \msn {\em Definition}: A subset $\mc$ of a (finite dimensional) space $V$ over $\R$ is a (pointed, full, closed)) {\em cone} if \begin{enumerate} \item $\mc + \mc \ci \mc, \ {\rm viz.}\ x + y \in \mc, \ \forall x, y \in \mc$. \item $\R_+ \mc \ci \mc, \ {\rm viz.}\ \alpha x \in \mc, \ \forall \alpha \geq 0, x \in \mc$. \item $\mc \cap -\mc = \{0\}, \ {\rm viz.}\ x, -x \in \mc \Rightarrow x = 0$. \item $\mc - \mc = V \ {\rm viz.}\ \forall z \in V,\ \exists x,y \in \mc,\ z = x-y, \\ {\rm equivalently,\ the\ interior} \ \mc^0 \not=\ \phi$. \item $\mc$ is closed. \end{enumerate} \noindent We now redefine for $x \in V$: $$ x \geq 0 \ : \ x \in \mc,$$ $$ x > 0 \ : \ x \in \mc^0,$$ and for $T \in {\rm Hom}(V)$: $$T \geq 0 :\ T\mc \ci \mc.$$ %$$T > 0 : T\mc \ci \mc^0$$. Again, Perron--Frobenius (Krein--Rutman) applies: If $ T \geq 0$ then \mbox{$ \rho(T) \in \spec(T)$}, and as a consequence we obtain \bsn {\em Theorem} 2 : Let $\mc$ be a cone. Let $T = R - S \in {\rm Hom}(V)$:{$$ T = R - S ,\ R^{-1} \geq 0,\ S \geq 0.$$ Then the following are equivalent: \begin{enumerate} \item $\rho(R^{-1}S) < 1$. \item \label{one} $T^{-1}\mc^0 \ci \mc^0 \ \ (T^{-1} \geq 0)$. \item $T\mc^0 \cap \mc^0 \ne \phi$. \end{enumerate} \noindent The obvious model is $\mc = \R^n_+$, the set of all vectors with nonnegative components in $\R^n$. In this case Theorem 2 is a slight generalization of Theorem~1 to splittings of type $T = R - S$ which Varga exploited and called {\em regular splittings}, see \cite[p. 88]{Varg}. We, however, are interested in the following set up: $$V = \Hn, \ \mc = \Pn,$$ where $$\Hn = {\rm real\ space\ of\ Hermitians\ in} \C^{nn},$$ $$\Pn = {\rm cone\ of\ positive\ semidefinite\ Hermitians\ in\ }\Hn.$$ If $R \in {\rm Hom}(\Hn)$ is defined by $R(H) = AHA^*$, where $A \in C^{nn}$ is nonsingular, then $R \ge 0$ and $R^{-1} \geq 0$. If $S \in$ Hom$(\Hn)$ is defined by $ S(H) = \Sigma_k C_k^*HC_k$ then $S \geq 0$. The operator $R^{-1}S$ in (1.) of Theorem 2 now becomes $$ R^{-1}S\ =\ \Sigma_{k=1}^s\ (A^{-1}C_k \times \bar{A}^{-1}\bar{C}_k) $$ where $\times$ is the Kronecker (tensor) product. Thus Theorem 2 specializes to: \bsn {\em Theorem} 3 : Let $A,\ C_k,\ k = 1, \ldots, s$, be complex $n \times n$ matrices. Let $H$ be Hermitian. Then the following are equivalent: \begin{enumerate} \item $A$ is nonsingular and $$\rho(\Sigma_{k=1}^s A^{-1}C_k \times \bar{A}^{-1}\bar{C}_k)< 1.$$ \item For all $K \gtdot 0$, there exists a unique \mbox{$H \gtdot 0$} such that $$AHA^* - \Sigma^s_{k=1} C_kHC_k^* = K.$$ \item There exists an \mbox{$H \gtdot 0$} such that $$AHA^* - \Sigma^s_{k=1} C_kHC_k^* \gtdot 0.$$ \item $A$ is nonsingular and there exists an \mbox{$H \gtdot 0$} such that $$\rho((\Sigma_{k=1}^s A^{-1}C_k HC^*_k A^{*-1})H^{-1})< 1.$$ \end{enumerate} Condition (4.) of Theorem 3 is a consequence of (3.) and was pointed out to me by S. Friedland. \msn The spectral radius of the operator in (1.) of Theorem 3 can be evaluated in terms the eigenvalues of its constituent matrices (only) under special assumptions. One such assumption is that the matrices $A,\ C_k,\ k = 1, \dots, s$, are {\em simultaneously triangulable}, viz. there exists $Q \in \C^{nn}$ such that $Q^{-1}AQ,\ Q^{-1}C_k Q$, \mbox{$k = 1, \dots, s$}, are (upper) triangular. In this case there exists an obvious {\em natural correspondence} \mbox{$(\ga_i, \gamma^{(1)}_i,\ldots,\gamma^{(s)}_i)$}, \mbox{$ i =1,\ldots, n$}, of the eigenvalues of $A,\ C_k$, \ \mbox{$k = 1, \dots, s$},\ such that every (noncommutative) polynomial \mbox{$p(A,C_1,\ldots,C_s)$} has eigenvalues \mbox{$p(\ga_i, \gamma^{(1)}_i,\ldots,\gamma^{(s)}_i)$},\ \mbox{$ i =1,\ldots, n$}. (A theorem of McCoy's assert that this latter property is equivalent to simultaneous triangulability). It was known to Frobenius that a set of pairwise commutative matrices is simultaneously triangulable. In particular, if $C_k = C^k,\ k = 0, \dots, s$, then the $C_k$ can be simultaneously triangulated. See \cite{Taus} for more information and references on this topic. \msn If $A,\ C_k$,\ \mbox{$k = 1, \dots, s$}, are simultaneously triangulable, then for the operator $R^{-1}S$ in Theorem 3 we have $$\spec(R^{-1}S)\ = \{\Sigma^s_{k=1}\ga^{-1}_i\gm^{(k)}_i \bar{\ga_j}^{-1}\bar\gm^{(k)}_j : i,j =1,\dots,n\}.$$ We may apply Cauchy's inequality to obtain \cite[Theorem 1]{Schn}: \bsn {\em Theorem} 4 : Let $A,\ C_k,\ k = 1, \ldots, s$, be complex $n \times n$ matrices which can be simultaneously triangulated. Suppose the eigenvalues of $A,\ C_k$ under a natural correspondence are $\ga_i,\ \gm^{(k)}_i,\ i = 1, \ldots, n,\ k = 1, \ldots, s$. For Hermitian $H$, let $$T(H) = AHA^* - \Sigma^s_{k=1} C_kHC_k^*.$$ Then the following are equivalent: \begin{enumerate} \item \mbox{$\epsilon_i := |\ga_i|^2 - \Sigma^s_{k=1}|\gm^{(k)}_i|^2 > 0,\ i = 1,\ldots, n$}. \item For all $K \gtdot 0$, there exists a unique \mbox{$H \gtdot 0$} such that T(H) = K. \item There exists an $H \gtdot 0$ such that \mbox{$T(H) \gtdot 0$}. \end{enumerate} \bsn We note the following special cases: \msn \begin{description} \item If $$T(H) = (B+I)H(B+I)^* - (BHB^* + IHI^*)\\ = BH+HB^*$$ then $\epsilon_i = \beta_i + \bar{\beta_i}$ and thus we obtain Lyapunov's Theorem. \item If $$T(H) = IHI^* - CHC^*$$ then $\epsilon_i = 1 - |\gm_i|^2$ and thus we have a result due to Stein. \end{description} \bsn We now turn to a generalization due to D.H. Carlson, published in \cite{Hill}. Let $$ \Phi = \Phi^* \in \C^{s+1,s+1}$$ and consider the operator $T$ defined by $$T(H) = \Sigma^{s}_{h,k=0}\ \varphi_{hk} C_hHC_k^*$$ for $H \in \Hn$. We define the $n \times (s+1)n$ matrix $$\mbf{C} = [C_0,\ \ldots,\ C_s]$$ and we obtain $$T(H) = \mbf{C}(\Phi \times H)\mbf{C}^* = \mbf{C}(U \times I) (\Delta \times H)(U^* \times I) \mbf{C}^* = \mbf{B}(\Delta \times H) \mbf{B}^*,$$ where $U$ is a unitary matrix, $\Phi = U\Delta U^*$ and $\mbf{B} = \mbf{C}U \in \C^{n,(s+1)n}$. If \mbox{$C_0, \ \dots,\ C_s$} are simultaneously triangulable and we put $$\mbf{\gm_{i}} = [\gm_i^{(0)},\ \dots,\ \gm_i^{(s)}], \ i = 1,\dots,n,$$ where $(\gm_i^{(0)} \ \dots \ \gm_i^{(s)}), \ i = 1,\dots,n$, is a natural correspondence of the eigenvalues, $k = 0,\dots,s$. Since the eigenvalues of $B_k,\ k = 0,\dots,s$, are \mbox{$\Sigma^s_{h = 0} \gm_h^{(i)} u_{hk}$,} \mbox{$i = 1, \dots, n$}, Theorem 4 can be generalized to the following result, where by $\pi(\Phi)$ we denote the number of positive eigenvalues of the Hermitian matrix $\Phi$. \bsn {\em Theorem} 5 : Let $ C_k,\ 0 = 1, \ldots, s$, be complex $n \times n$ matrices which can be simultaneously triangulated. Suppose the eigenvalues of \mbox{$ C_0, \ \dots, \ C_s$} under a natural correspondence are \mbox{$ \gm^{(0)}_i,\ \dots \gm^{(s)}_i, \ i = 1,\ \dots,\ n$}. Let $\Phi = \Phi^* \in \C^{s+1,s+1}$, where $\pi(\Phi) = 1$. For Hermitian $H$, let $$T(H) = \Sigma^s_{h,k=0}\ \varphi_{hk} C_hHC_k^*.$$ \noindent Then the following are equivalent: \begin{enumerate} \item $\mbf{\gm_i}\Phi\mbf{\gm_i}^* > 0, \ i = 1, \dots, n.$ \item For all $K \gtdot 0$, there exists a unique \mbox{$H \gtdot 0$} such that T(H) = K. \item There exists an $H \gtdot 0$ such that \mbox{$T(H) \gtdot 0$}. \end{enumerate} \bsn Clearly the assumptions of Theorem 5 are satisfied if $A \in \C^{nn}$ and $C_k = A^k,\ k = 1, \dots, n$. Thus we derive a result independently due to Kharitonov \cite{Khar}, see also \cite[Theorem 6.1]{Gutm}. \bsn {\em Theorem} 6 : Let $A \in \C^{nn}$ have eigenvalues $\ga_i,\ i = 1,\ldots,n$. Let $K \in \C^{nn}$ be positive definite and suppose that $\Phi$ is a Hermitian matrix in $\C^{s+1,s+1}$ with $\pi(\Phi) = 1$. %$$T(H) = \Sigma^s_{h,k=1}\ \varphi_{hk} A_hHA_k^*.$$ Then the following are equivalent: \begin{enumerate} \item $ \Sigma^s_{h,k=0}\ \ga^h_i \varphi_{hk} \bar{\ga}^k_i > 0,\ i = 1,\ldots, n$. \item The (unique) solution $H$ of \mbox{$ \Sigma^s_{h,k=0}\ \varphi_{hk} A^hHA^{k*} = K$} is positive definite. \end{enumerate} \bsn Theorems 5 and 6 do not hold without the assumption that $\pi(\Phi) = 1$, as is shown by the following example with $\pi(\Phi) = 2$. Let $$A = \left[ \begin{matrix} 2 & 0 \\ 0 & 2 \end{matrix} \right], \ C = \left[ \begin{matrix} 1 & 0 \\ 0 & -1 \end{matrix} \right], \ H = \left[ \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right]. $$ Then $$AHA^* + CHC^* = \left[ \begin{matrix} 5 & 3 \\ 3 & 5 \end{matrix} \right]. $$ A perturbation argument shows that we can find $H$ with $\pi(H) = 1$ or \mbox{$\pi(H) = 2$} such that \mbox{$AHA^* + CHC^* \gtdot 0$}. However, a weaker result holds, see \cite{Hill} for remarks on this topic. We need an additional assumption, which is again satisfied if the $C_k, \ k = 0, \dots, s$, commute pairwise and hence if \mbox{$C_k = A^k, \ k = 0, \dots s$}, see \cite{CaPi} for information. Dropping the assumption that $\pi(\Phi) = 1$, we still have \bsn {\em Theorem} 7 : Let $ C_k,\ k = 0, \ldots, s$, be complex $n \times n$ matrices which can be simultaneously triangulated . Assume that for each distinct sequence of corresponding eigenvalues \mbox{$(\gm_i^{(0)}, \ \dots, \ \gm_i^{(s)})$,} \ \mbox{$i = 1, \ \dots, \ n$,} of \mbox{$ C_0,\ \dots, \ C_s$} there exists a common eigenvector. Let $\Phi = \Phi^* \in \C^{s+1,s+1}$. Then the following are equivalent: \begin{description} \item[{\rm 1.}] $\mbf{\gm_i}\Phi\mbf{\gm_i}^* > 0, \ i = 1, \dots, n.$ \item[{\rm 3.}] There exists an $H \gtdot 0$ such that \mbox{$\Sigma^s_{h,k=0}\ \varphi_{hk} C_hHC_k^* \gtdot 0.$} \end{description} \msn As a special case of Theorem 7 we state \bsn {\em Theorem} 8 : Let $A \in \C^{nn}$ have eigenvalues $\ga_i,\ i = 1,\ldots,n$. Suppose that $\Phi$ is a Hermitian matrix in $\C^{s+1,s+1}$. Then the following are equivalent: \begin{description} \item[{\rm 1.}] $ \Sigma^s_{h,k=0}\ \ga^h_i \varphi_{hk} \bar{\ga}^k_i > 0,\ i = 1,\ldots, n$. \item[{\rm 3.}] There exists $H \gtdot 0$ such that $\Sigma^s_{h,k=0}\ \varphi_{hk} A^hHA^{k*} \gtdot 0$. \end{description} \msn Proofs of the last two theorems are implicit in \cite{Hill} or \cite{Khar}. \begin{thebibliography}{9999} \bibitem[BePl]{BePl} Berman, A. \& Plemmons, R.J., {\em Nonnegative matrices in the Mathematical Sciences}, Academic (1979) and SIAM (1994) \bibitem[CaPi]{CaPi} Carlson, D.H. \& Pierce, S., Common eigenvectors and quasicommutativity of simultaneously triangulable matrices, {\em Lin. Alg. Appl.} 71:49--55 (1985). %bibitem[Draz]{Draz} %Drazin, M.P., %Some generalizations of matrix commutativity, %{\em Proc. London Math. Soc.} (3)1:222--231 (1951). \bibitem[Gant]{Gant} Gantmacher, F.R., (i)\ {\em Teoriya Matrits}, Gosd. Isd. Tech-teoret. (1953), (ii)\ {\em Theory of Matrices}, Chelsea (1959). \bibitem[Gutm]{Gutm} Gutman, S., Root clustering in parameter space, {\em Lecture Notes in Control and Information Sciences}, Springer (1990). \bibitem[Hahn]{Hahn} Hahn, W., Theorie und Anwendung der zweiten Methode von Ljapunov, {\em Ergeb. Math. Grenzg.}, N.F. 22, Springer (1959), \bibitem[Hill]{Hill} Hill, R.D., Inertia theory for simultaneously triangulable complex matrices, {\em Lin. Alg. Appl.} 2:131--142 (1969). \bibitem[Khar]{Khar} Kharitonov, V.L., Distribution of the roots of an autonomous system, {\em Avtomatika i Telmekhanika} 5:42--47 (1981). \bibitem[KrRu]{KrRu} Krein, M.G. \& Rutman M.A., Linear operators leaving invariant a cone in Banach space, (i)\ {\em Uspehi Mat. Nauk} 3(23):3--95 (1948), (ii)~\ {\em Trans. Amer. Math. Soc.} Ser. 1, 10:199--325 (1952). \bibitem[Lyap]{Lyap} Lyapunov (Liapunoff) M.A., Probl\`eme g\'en\'eral de la stabilit\'e du mouvement, (i)\ {\em Comm. Math. Soc. Kharkov} (1892) (ii)\ {\em Ann. Fac. Sci. Toulouse} 9(2)(1907) (iii)\ {\em Ann. Math. Studies}, 17(1947), Princeton U.P. \bibitem[Schn]{Schn} Schneider, H., Positive operators and an inertia theorem, {\em Num. Math.} 7:11--17 (1965). \bibitem[Taus]{Taus} Taussky, O., Commutativity in finite matrices, {\em Amer. Math. Month.} 64:229--235 (1957). \bibitem[Varg]{Varg} Varga, R.S., {\em Matrix Iterative Analysis}, Prentice--Hall (1962). \end{thebibliography} \end{document}