\begin{filecontents}{seceqn.sty} % seceqn.sty % From TeXhax 89.37 % % Substyle file for use with "article" to cause equations to be numbered % within sections. % % 13 Apr 89 Jerry Leichter \typeout{Document Option `seceqn': 13 Apr 89} \@addtoreset{equation}{section} %Make equation=0 when section steps \def\theequation{\thesection.\arabic{equation}} %How an equation number looks % From NUMINSEC.STY (with SIAM stuff). \@addtoreset{figure}{section} \def\thefigure{\thesection.\@arabic\c@figure} \@addtoreset{table}{section} \def\thetable{\thesection.\@arabic\c@table} \end{filecontents} %\documentclass[landscape,slideColor,colorBG]{seminar} \documentclass[autumn_m,distiller,nototal,slideColor,colorBG]{prosper} %\documentclass[a4,portrait]{seminar} %\usepackage{semcolor} %\input{seminar.bug} %\usepackage{theorem,exscale} %\usepackage{fullpage} % was not available on PC? %\usepackage{float} %\usepackage{psfrag} %\usepackage{algorithmic} % was not available on PC? %\usepackage{hyperref} %\usepackage{seceqn} %\usepackage{epsfig} %\usepackage{amssymb} %\usepackage{amssymb,epsfig} %\usepackage{amsmath,amsthm,amsfonts,latexsym,amssymb,epsfig} %\usepackage{fullpage} % was not available on PC? %\usepackage{float} %\usepackage{algorithmic} % was not available on PC? %\usepackage{epsf} %\usepackage{hyperref} %\usepackage{seceqn} %\usepackage[dvips]{graphicx} \usepackage{graphics} \usepackage{graphicx} %\usepackage{amsmath,amssymb,amsthm} %\usepackage{subeqnarray} \usepackage{hyperref} \usepackage{epsfig} \usepackage{float} \usepackage{seceqn} \usepackage{amssymb} \newenvironment{pf}{\parindent=0pt{\textbf{Proof: }}}{\hfill $\blacksquare$ \\} \newcounter{ctr} \newtheorem{thm}{Theorem}[section] \newtheorem{lemma}{Lemma}[section] \newtheorem{cor}{Corollary}[section] \newtheorem{con}{Conjecture}[section] \newtheorem{prop}{Proposition}[section] \newtheorem{defi}{Definition}[section] \newtheorem{example}{Example}[section] \newtheorem{rem}{Remark}[section] \newtheorem{alg}{Algorithm}[section] \newtheorem{ex}{Exercise}[section] \newcommand{\adj}{{\rm adj\,}} \newcommand{\trace}{{\rm trace\,}} \newcommand{\spanl}{{\rm span\,}} \newcommand{\tr}{{\rm trace\,}} \newcommand{\Rn}{\mathbb{R}^{n}} \newcommand{\Sn}{{\mathcal S^n\,}} \newcommand{\St}{{\mathcal S^{n-1}\,}} \newcommand{\Mn}{{\mathcal M^n\,}} \newcommand{\Mmn}{{\mathcal M^{n-1}\,}} \newcommand{\beq}{\begin{equation}} \newcommand{\eeq}{\end{equation}} \newcommand{\beqr}{\begin{eqnarray}} \newcommand\C{\mathbb C} \newcommand{\EE}{{\mathcal E^n\,} } \newcommand{\DD}{{\mathcal D\,} } \newcommand{\NN}{\mathcal N} \newcommand{\LL}{\mathcal L} \newcommand{\A}{\mathcal A} \newcommand{\PP}{\mathcal P} \newcommand{\RR}{\mathbb R} \newcommand{\VV}{\mathbb V} \newcommand{\benum}{\begin{enumerate}} \newcommand{\eenum}{\end{enumerate}} \newcommand{\st}{\textnormal{s.t.}} \newcommand{\TRSe}{TRS$_=\;$} \newcommand{\disp}{\displaystyle} \newcommand{\QED}{{\black \hfill ~\rule[-1pt] {8pt}{8pt}\par\medskip ~~}} \newcommand{\bpr}{\textsc{proof: }} \newcommand{\epr}{\QED} \newcommand{\Diag}{{\rm Diag\,}} \newcommand{\diag}{{\rm diag\,}} \newcommand{\offDiag}{{\rm offDiag\,}} \newcommand{\usMat}{{\rm us2Mat\,}} \newcommand{\sMat}{{\rm sMat\,}} \newcommand{\usvec}{{\rm us2vec\,}} \newcommand{\svec}{{\rm svec\,}} \newcommand{\kvec}{{\rm vec\,}} \newcommand{\ZS}{{\mathcal Z_S} } \newcommand{\XS}{{\mathcal X} } \newcommand{\WW}{{\mathcal W} } %\newcommand{\XS}{{\mathcal X_s} } \newcommand{\XSu}{{\mathcal X_{u}} } \newcommand{\XSd}{{\mathcal X_{d}} } \newcommand{\XX}{{\mathcal X} } \newcommand{\II}{{\mathcal I} } %\newcommand{\SO}{{\mathcal S^s} } \newcommand{\SO}{{\mathcal S} } \newcommand{\SOu}{{\mathcal S} } %\newcommand{\SOu}{{\mathcal S^{su}} } \newcommand{\Ss}{{\mathcal S} } %\newcommand{\Stn}{{{\mathcal S}^{\scriptsize{\pmatrix{n\cr 2}}}\,}} \newcommand{\Stn}{{\mathcal S^{n-1}\,}} \newcommand{\tn}{{\scriptsize{\pmatrix{n\cr 2}}}\,} \newcommand{\Rtnp}{{\R^{\scriptsize{\pmatrix{n+1\cr 2}}}\,}} \newcommand{\EDM}{{\bf{\rm EDM\,}}} \newcommand{\EDMC}{{\bf{\rm EDMC\,}}} \newcommand{\SDP}{{\bf{\rm SDP\,}}} % Nick's definitions. \def\Rnbyn{\mathbb{R}^{n\times n}} \def\R{\mathbb{R}} \def\normF#1{\|#1\|_F} \def\normt#1{\|#1\|_2} \def\norm#1{\|#1\|} \def\cm{correlation matrix} \def\cms{correlation matrices} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % All refs in roman. \def\eqref#1{{\normalfont(\ref{#1})}} \title{ %\cyan Cone Preserving Maps } \subtitle{ \small{ Invariant Operators on Ellipsoidal and \SDP cones } } \author{Henry Wolkowicz} \institution{Department of Combinatorics and Optimization\\ University of Waterloo\\ \begin{figure} \psfig{file=UWlogori.ps,height=10mm} \end{figure} } \email{hwolkowicz@uwaterloo.ca } \begin{document} \bibliographystyle{plain} \maketitle \begin{slide}{ ICCOPT 2004} \begin{center} {\bf First Mathematical Programming Society\\ $\begin{array}{cccccc} {\rm International}& {\rm Conference} & {\rm on} & {\rm Continuous} & {\rm Optimization}\\ {\blue \rm I}& {\blue \rm C}&& {\blue \rm C}& {\blue \rm OPT}& {\cyan \rm I} \end{array}$ } \end{center} \begin{center} \mbox{ \begin{figure} %\psfig{file=logoagogo.jpg,width=32mm,height=23mm} %\psfig{file=headerleft.ps,width=50mm,height=15mm} \end{figure} } \end{center} ~~\\ \begin{center} {\large \yellow Cone Preserving Maps } \end{center} \vspace{.5in} Henry Wolkowicz\\ Dept. Combinatorics and Optimization\\ University of Waterloo \end{slide} \begin{slide}{OUTLINE} \begin{description} \item $\bullet$ Background on Ellipsoidal and SDP Cones;\\ \hspace{1.4in} Notation and Motivation \item \item $\bullet$ Invariant examples on \EDM and \SDP cones \item \item $\bullet$ Invariant Ellipsoidal Cones \item \item $\bullet$ Extensions to Invariant \SDP Cones \end{description} \end{slide} \begin{slide}{Notation and Motivation} Vandergraft68-Elsner70 \qquad {\blue Extension} of classical\\ {\green Perron-Frobenius Theory of Nonnegative Matrices}:\\ (Google uses Perron vector)\\ \begin{quote} {\cyan spectral conditions on $A, ~ n \times n$, to characterize existence of a proper cone $K \subset \R^n$ such that $A$ is $K$-nonnegative, denoted $A \succeq^{\!\!K} 0$,\\ \[ A(K) \subset K. \] } \end{quote} {\yellow $K$ proper cone} - closed, \\ \hspace{1.1in} convex ($\lambda K \subset K, \forall \lambda \geq 0, K+K \subset K$), \\ \hspace{1.1in} pointed ($K \cap -K = \{0\}$),\\ \hspace{1.1in} ${\rm int\,} K \neq \emptyset$ \end{slide} \begin{slide}{Preliminaries} Also, $A$ is: {\cyan $K$-positive, $K$-irreducible, $K$-strongly nonnegative} \vspace{.2in} Here we add the restriction: $K$ is {\yellow ellipsoidal}\\ (ellipsoidal cross sections, translations of Lorentz (ice-cream, $2$-nd order) cone; subset of {\blue rotund cones}, i.e. all proper faces are $1$-dimensional exposed rays) \vspace{.2in} {\green Preview of Results:\\ \hspace{.2in} Stern-W91:} Characterizations unchanged for stronger than $K$-nonnegativity. But, if degree of spectral radius of $A$ is $ \geq 3$, then no invariant ellipsoidal cone exists with $A$ $K$-nonnegative. \hspace{.2in} {\green new:} extensions to cones in $\Sn$ \end{slide} \begin{slide}{Ellipsoidal Cones, $K$} $Q=Q^T, n \times n$ with exactly one negative eigenvalue \[ \lambda_n < 0 < \lambda_{n-1} \leq \ldots \leq \lambda_1 \] with corresponding normalized eigenvectors $u^i$ \[ K := \left\{ x \in \R^n : x^TQx \leq 0, x^T u^n \geq 0 \right\} \quad \mbox{\blue ellipsoidal cone} \] $\bullet H:= \{u^n\}^\perp$ is supporting hyperplane to $K$ and to $-K$.\\ $\bullet u^n \in {\rm int\,} K$\\ $\bullet$ For $\alpha > 0$, $S_\alpha := \left\{ x \in K : x^T u^n = \alpha \right\}$ is an \mbox{\blue ellipsoid} in the \\ \quad hyperplane $H_\alpha := \left\{ x \in \R^n : x^T u^n = \alpha \right\}$.\\ $\bullet$ Each $z \in \partial K$, has unique supporting hyperplane $H_z= (Qz)^\perp$.\\ $\bullet H_z \cap K$ is an (exposed) extreme ray. \end{slide} \begin{slide}{Ice-Cream (Lorentz, $2$-nd order) Cone} {\blue PROPOSIITON:} Suppose $K$ is ellipsoidal cone. Then \[ K = \left\{x \in \R^n : x^TQx \leq 0, v^Tx \geq 0 \right\}, \] if $v$ satisfies $v^Tu^n \geq 0$ and $\left\{v^Tx=0, x^TQx\leq 0\right\} \Rightarrow x=0$. \epr \[ K_n:= \left\{ x\in \R^n: \sqrt{\sum_{i=1}^{n-1}x_i^2} \leq x_n \right\} \qquad \mbox{ice-cream cone} \] where $Q = \pmatrix{I_{n-1} & 0 \cr 0 & -1}$ and $u^n=e^n$ \end{slide} \begin{slide}{Ellipsoidal $\leftrightarrow$ Ice-Cream Cones} {\blue PROPOSIITON:} $K$ is an {\cyan ellipsoidal cone} if and only if $K=T(K_n)$, for some nonsingular $T$. In particular, $T=UD$, where $D$ is diagonal with elements $D_{ii}=\sqrt{\frac 1{|\lambda_i|}}, i=1, \ldots, n$, and $\Lambda = U^TQU$ is the orthogonal diagonalization of $Q$. \QED {\blue COROLLARY:} $K$ ellipsoidal, $T$ nonsingular, implies $T(K)$ ellipsoidal. \end{slide} \begin{slide}{Real Canonical Form} $A$ real $n \times n$, $C(A)$ is the {\cyan Real Canonical Form}; real similarity of $A$, unique up to order of blocks; \[ B(\lambda;1):= \pmatrix{\lambda}, \qquad \mbox{order-$1$ block} \] \[ B(\lambda;k):= \pmatrix{\lambda & \cr 1 & \lambda & \cr & 1 & \lambda & \cr && \ldots & \ldots& \cr &&& \ldots & \ldots& \cr &&& & 1& \lambda \cr }, \qquad \mbox{order-$k$ block} \] complex eigenvalue $\lambda=a+ib$, $b>0$, and conjugate $\bar \lambda$, \[ \lambda \leftarrow B(a,b;2):= \pmatrix{a &b \cr -b & a }, 1 \leftarrow I_2 \qquad \mbox{order-$2$ blocks} \] \end{slide} \begin{slide}{Real Canonical Form} $\sigma(A)$ - {\cyan spectrum}; $\rho(A)$ - {\cyan spectral radius}\\ for $\lambda \in \sigma(A)$ (spectrum): larger below smaller blocks\\ for $|\lambda| > |\mu|$ blocks for $\lambda$ below those for $\mu$.\\ {\cyan degree of $\lambda$}, $d(\lambda)$, size of largest block in Jordan canonical form \vspace{.2in} {\blue LEMMA:} \begin{enumerate} \item $\|B(a;1)\|^2=a^2$ \item $\|B(a;2)\|^2 \leq a^2 + |a|+1$ \item $\|B(a;k)\|^2 \leq a^2 + 2|a|+1$, for $k \geq 3$ \item $\|B(a,b;2)\|^2 = a^2 + b^2$ \item $\|B(a,b;4)\|^2 \leq a^2 + b^2 + |a| + |b|+1$ \item $\|B(a,b;2k)\|^2 \leq a^2 + b^2 + 2(|a| + |b|)+1$, for $k\geq 3$ \end{enumerate} \end{slide} \begin{slide}{Nonnegativity Definitions for\\ $K$ Proper Cone} \begin{table} \begin{center} \begin{tabular}{|c|c|c|c|c|} \hline name & notation & definition & set & ellips.\\ \hline $A$ $K$-positive & $A \succ^{\!\!K} 0$ & $A(K\backslash \{0\} ) \subset {\rm int\,} K$ & $\Pi^P$ & $\Pi^P_e$\\ \hline $A$ $K$-nonnegative & $A \succeq^{\!\!K} 0$ & $A(K ) \subset K$ & $\Pi^N$ & $\Pi^N_e$\\ \hline $A$ $K$-irreducible & $A \succeq^{\!\!KI} 0$ & $\begin{array}{c} A(K ) \subset K\\ \mbox{no eigenv. in } \partial K\end{array}$ & $\Pi^I$ & $\Pi^I_e$\\ \hline $\begin{array}{c} A \mbox{ strongly}\\ \mbox{$K$-nonnegative} \end{array}$ & $A \succeq^{\!\!SK} 0$ & $\begin{array}{c} A(K ) \subset K\\ \mbox{eigenv. in } {\rm int\,} K\end{array}$ & $\Pi^{SN}$ & $\Pi^{SN}_e$\\ \hline \end{tabular} \end{center} \end{table} \end{slide} \begin{slide}{$A$ $K$-positive, $A \succ^{\!\!K} 0$, $A(K\backslash \{0\} ) \subset {\rm int\,} K$ } $\Pi^P= \{A: A \succ^{\!\!K} 0, \mbox{ for some {\green proper} cone} K\}$, $\Pi^P_e= \{A: A \succ^{\!\!K} 0, \mbox{ for some {\green ellipsoidal} cone} K\}$ \vspace{.4in} {\blue THEOREM (V.-E.)}\\ $A \in \Pi^P$\\ {\cyan iff}\\ $\rho(A)$ is a simple eigenvalue $>$ modulus of other eigenvalues \epr ($K$ is not ellipsoidal but rather polyhedral in proof.) \vspace{.2in} {\cyan THEOREM (S.W.)}\\ For fixed $n$, $\Pi^P=\Pi^P_e$. \epr \end{slide} \begin{slide}{Proof Outline} Suppose $\rho(A)$ is a simple eigenvalue $>$ modulus of other eigenvalues. We need only find appropriate $K$ ellipsoidal. Wlog $A$ is in real canonical form. (Will show $A \succ^{\!\!K_n} 0$.) $A$ is made up of diagonal blocks corresp. to $m$ distinct eigs: \[ A=\Diag \left(Q_m, \ldots, Q_2, \rho(A)=Q_n\right). \] Suppose $\lambda_j=a_j+ib_j$ and $(*)~~a_j^2+b_j^2+2(|a_j|+|b_j|)+1 < \rho(A)^2, ~j=2,\ldots,m$.\\ For partitioned $0\neq x \in K_n$ (ice-cream cone) $\Rightarrow$\\ $x_n\neq 0$ and $\|Q_j\|< \rho(A),~j=2,\ldots,m$ $\Rightarrow$\\ $Ax \in {\rm int\,} K_n$ from $(*)$ and \[ \sum_2^m \|Q_jx^j\|^2 \leq \sum_2^m \|Q_j\|^2\|x^j\|^2 < \rho(A)^2(x_n)^2. \] \end{slide} \begin{slide}{Proof Outline Cont...} If $(*)$ fails, since $\rho(A)> |\lambda|$, \[ \lim_{\gamma \rightarrow \infty} \frac {(\gamma \rho(A))^2} { (\gamma a_j)^2+ (\gamma b_j)^2+ 2(|\gamma a_j|+ |\gamma b_j|)+1 } =\frac {(\rho(A))^2} { (a_j)^2+ (b_j)^2}>1. \] Now use $\gamma A \in \Pi_e^P$ iff $A \in \Pi_e^P$. \epr \end{slide} \begin{slide}{$A$ $K$-irreducible,\\ $A \succeq^{\!\!KI} 0$; $A \succeq^{\!\!K} 0$ and no $v \in \partial K$ } $\Pi^I= \{A: A \succ^{\!\!KI} 0, \mbox{ for some {\green proper} cone} K\}$, $\Pi^I_e= \{A: A \succ^{\!\!KI} 0, \mbox{ for some {\green ellipsoidal} cone} K\}$ \vspace{.4in} {\blue THEOREM (V.-E.)}\\ $A \in \Pi^I$\\ {\cyan iff}\\ $\rho(A)$ is a simple eigenvalue; $|\lambda|=\rho(A)$ implies $d(\lambda)=1$. \epr \vspace{.2in} {\cyan THEOREM (R.S.)}\\ For fixed $n$, $\Pi^I=\Pi^I_e$. \epr \end{slide} \begin{slide}{Proof Outline} Same proof as above shows that $A \succeq^{\!\!K} 0$.\\ Wolg $A$ in real canonical form. Then only eigenvector of $\rho(A)$ is unit vector $e^n \in {\rm int\,} K_n$.\\ If $v$ is eigenvector corresponding to $|\lambda|=\rho(A)$, then $v$ is linear combination of unit vectors not containing $e^n$, so $v \notin K_n$. \epr \end{slide} \begin{slide}{$A$ Strongly $K$-nonnegative,\\ $A \succeq^{\!\!SK} 0$; $A \succeq^{\!\!K} 0$ and $v \in {\rm int\,} K$ } $\Pi^{SN}= \{A: A \succeq^{\!\!SK} 0, \mbox{ for some {\green proper} cone} K\}$, $\Pi^{SN}_e= \{A: A \succeq^{\!\!SK} 0, \mbox{ for some {\green ellipsoidal} cone} K\}$ \vspace{.4in} {\blue THEOREM (V.-E.)}\\ $A \in \Pi^{SN}$\\ {\cyan iff}\\ $\rho(A)\in \sigma(A)$; $|\lambda|=\rho(A)$ implies $d(\lambda)=1$. \epr \vspace{.2in} {\cyan THEOREM (R.S.)}\\ For fixed $n$, $\Pi^{SN}=\Pi^{SN}_e$. \epr \end{slide} \begin{slide}{Proof Outline} Similar proof; eigenvector in $\partial K$ possible since multiple $1 \times 1$ blocks for $\rho(A)$ is possible, e.g. $e^n+e^{n-1}$. \epr {\cyan REMARK} The three results hold for any {\yellow class} of cones which contain ellipsoidal cones, e.g. rotund cones. \end{slide} \begin{slide}{Nonnegative Case;\\ $A \succeq^{\!\!K}0$; $\Pi^N \neq \Pi^N_e$ for $n\geq 3$} $\Pi^{N}= \{A: A \succeq^{\!\!K} 0, \mbox{ for some {\green proper} cone} K\}$, $\Pi^{N}_e= \{A: A \succeq^{\!\!K} 0, \mbox{ for some {\green ellipsoidal} cone} K\}$ \vspace{.2in} {\blue THEOREM (V.-E.)}\\ \begin{quote} $A \in \Pi^{N}$\\ {\cyan iff}\\ $\rho(A)\in \sigma(A)$; $|\lambda|=\rho(A)$ implies $d(\lambda)\leq d(\rho(A))$. \end{quote} Furthermore, $A \succeq^{\!\!K}0$ implies $K$ contains an eigenvector corresponding to $\rho(A)$. \epr \vspace{.1in} {\cyan THEOREM (R.S.)}\\ $\Pi^{N}=\Pi^{N}_e$ iff $n \leq 2$. \quad ($n=1,2$: all cones are rotund) \epr \end{slide} \begin{slide}{Geometrical LEMMA 1} $K$ ellipsoidal; $0 \neq z \in \partial K$; $H=(Qz)^\perp$. Then:\\ \begin{enumerate} \item $H$ is the unique supporting hyperplane at $z$; $v=Qz$ is an outward normal to $K$ at $z$ ($v^Tx \leq 0, \forall x \in K$). \item $H \cap K = \{\alpha z : \alpha \geq 0\}$ \item $z-\epsilon v \in {\rm int\,} K$ for all suff. small $\epsilon > 0$ \end{enumerate} \end{slide} \begin{slide}{Geometrical LEMMA 2} $A \succeq^{\!\!K} 0$; $K$ ellipsoidal; eigenvector $z \in \partial K$. Then:\\ $v=Qz$ is a left eigenvector of $A$ corresp. to nonneg. eigenvalue. \end{slide} \begin{slide}{Geometrical LEMMA 3} $A$ in Jordan canonical form; $B$ a block corresp. $\lambda \in \sigma(A)$; eigenvector $v$ assoc. with $\lambda$ {\cyan corresponds} to $B$ provided all its nonzero entries correspond to positions occupied by $B$ in $A$. \\ $A$ has only one eigenvector, $v$, in $K$; $v \in \partial K$ and corresp. to the maximal-order block for $\rho(A)$. \vspace{.2in} {\cyan Geometrical LEMMA 3}\\ $A \succeq^{\!\!K} 0$; $K$ ellipsoidal; $D(\rho(A))> 1$. Then:\\ Jordan canonical form of $A$ has only one maximal-order block for $\rho(A)$. eigenvector $z \in \partial K$. \end{slide} \begin{slide}{Example of $A$} Let \[ A:=B(0;3)= \pmatrix{ 0 & 0 & 0 \cr 1 & 0 & 0 \cr 0 & 1 & 0 }, \quad (d(a) =3 > 1) \] Suppose $K$ ellipsoidal exists for $A \succeq^{\!\!K} 0$.\\ Then Lemma 3 implies eigenvector $z=\pmatrix{0& 0& \beta}^T \in \partial K$;\\ Lemma 2 implies that the outward normal $v=\pmatrix{\gamma & 0 & 0}$ is a left eigenvector of $A$;\\ Lemma 1 yields $\epsilon > 0$ small so that $p=z-\epsilon v {\rm int\,}K$.\\ Then $Ap= \pmatrix{0& -\epsilon & 0}^T\in (H \cap K)$, where $H=v\perp$. But, $Ap \neq \alpha z$, for any $\alpha$.\\ Contradicts Lemma 1. \epr \end{slide} \begin{slide}{Invariant \SDP and \EDM Cones} {\yellow Operator Notation} \[\blue x=\svec(X) \in \R^{n+1 \choose 2}, \] $\sqrt{2}$ times vector (columnwise) from upper-triang of $X$. ${n+1\choose 2}=n(n+1)/2$; $\sqrt{2}$ guarantees isometry. \[ \blue \sMat:=\svec^{-1} \] adjoint transformation $\blue \sMat^*= \svec$: \begin{eqnarray*} \left<\sMat(v),S\right> &=& \trace \sMat(v)S \\ &=& v^T \svec(S) = \left \end{eqnarray*} \end{slide} \begin{slide}{Cone of\\ Euclidean Distance Matrices} \[ \EE := \{ D=(d_{ij})\in \Sn : d_{ij} = \|x_i-x_j\|^2, \mbox{ for some } x_i \in \Re^k \} \] $k$ is {\em embedding dimension} \end{slide} \begin{slide}{Operator $\LL : S^{n-1} \rightarrow \Sn$} \green \begin{center} $D \in \EE$ \quad ($\subset \Sn$)\\ ~\\ \fbox{ {\em \cyan iff} } ~\\ \end{center} \[ D=\LL( X):=\pmatrix{0 & \diag ( X)^T \cr \diag ( X) & \diag(X)e^T+e\diag(X)^T -2X }, \] \begin{center} for some $X \succeq 0, X \in {\mathcal S}^{n-1}$ \end{center} ~~\\ \blue ($e$ is vector of ones) ~~\\ \cyan \[ \LL: \Stn \rightarrow \Sn, \quad \LL({\mathcal S}^{n-1}_+) = \EE \] \end{slide} \begin{slide}{Properties of $\LL$} with partition: \[ D=\left[\matrix{\alpha & d^T\cr d& {\bar D} \cr}\right], \] where $\alpha \in \R$ \blue \[ \LL^*(D)=2\left(\Diag(d)+\Diag(\bar De) -\bar D\right) \] \cyan \[ \LL^\dagger (D)= \frac 12 \left( de^T+ed^T - \bar D \right) \] \green \[ \LL^*,\LL^\dagger: \Sn \rightarrow \Stn, \quad \LL^\dagger (\EE)={\mathcal S}^{n-1}_+ \] \end{slide} \begin{slide}{Invariance on \SDP and $\EE$ Cones} { Let $H$ be $n \times n$ symmetric matrix with nonnegative elements and 0 diagonal and with no zero row (or column). } \[ \cyan X \succeq 0 ~~(\mbox{resp. } \succ 0) \Rightarrow \LL ^*(H^{(2)} \circ \LL(X)) \succeq 0 ~~(\mbox{resp. } \succ 0), \] \yellow i.e. $\Ss^n_+$ (and its interior) is invariant under the operator \[ \cyan \WW(\cdot ) := \LL ^*(H^{(2)} \circ \LL(\cdot)) \] \end{slide} \begin{slide}{Perron Roots/Vectors} \[ \cyan \WW_E(\cdot):=\LL ^*\LL(\cdot) \mbox{ is strongly } \Ss^n_+ \mbox{ nonnegative} \] The Perron root and eigenvector are: \[ \lambda = (2n+1) + \frac {\sqrt{(4n+2)^2 -32}}2 > 0, \qquad X = \alpha e e^T+ \beta I \succ 0, \] where $\alpha = -\frac {4 \beta}{\lambda},~ \beta > 0$. \end{slide} \begin{slide}{Perron Roots/Vectors cont...} Similarly: {\cyan The cone $\EE$ is invariant under the linear operator $\VV := \LL \LL^*$.}\\ The Perron root and vector of $\LL \LL^*$ are \[ \lambda= (2n-1) + \sqrt{ (2n-3)^2 +8(n-2) } > 0 \] and \[ D=\pmatrix{0 & e^T \cr e & \alpha (E - I)}, \quad \alpha > 0, \] where \[ \alpha= \frac 1{2(n-2)} \left\{(2n-3) + \sqrt{ (2n-3)^2 +8(n-2) } \right\}, \] $D$ is nonsingular and $\LL^\dagger (D) \succ 0$. \end{slide} \begin{slide}{Ellipsoidal Cones in $\Sn$ $(\subset, \supset \Ss^n_+)$} {\cyan LEMMA} Let $\alpha \neq 0$.\\ \[ \green K_{\alpha}:=\{X \in \Sn : \alpha^2 \trace X^2 - \frac {\alpha^2+1}n (\trace X)^2\leq 0, \trace X \geq 0\} \] is an {\blue ellipsoidal cone}.\\ And: \[ \qquad \alpha^2 {\yellow \geq} n-1 \quad {\cyan \Rightarrow} \quad {\green K_{\alpha}} \subset {\mathcal S^n_+} \] \[ \qquad \alpha^2 {\yellow \leq} \frac 1{n-1} \quad {\cyan \Rightarrow} \quad {\green K_{\alpha}} \supset {\mathcal S^n_+} \] \end{slide} \begin{slide}{Proof Outline} Consider the Rayleigh Principle (and Courant-Fisher): ${\blue \min\limits_X} \yellow \quad \alpha^2 \trace X^2 - \frac {\alpha^2+1}n (\trace X)^2 \green = \left<\svec (X), Q \svec (X)\right>$\\ with constraint $\yellow \trace X^2=1$, i.e. \[ 0= \nabla L(X,\lambda)=2\alpha^2X -2\frac {\alpha^2+1}n (\trace X)I -2\lambda X \] implies the eigenvector $\yellow X=\frac 1{\sqrt n} I$ and the eigenvalue $\yellow \lambda_{\min}= \alpha^2 \trace X^2 - \frac {\alpha^2+1}n (\trace X)^2 =-1{\blue < 0}$.\\ {\green And} the second eigenvector $\left=0, X\neq 0$ implies $\trace X=0, X\neq 0$\\ implies $ \alpha^2 \trace X^2 - \frac {\alpha^2+1}n (\trace X)^2= \alpha^2 \trace X^2 {\blue >0}$,\\ i.e. $K_{\alpha}$ is ellipsoidal. \end{slide} \begin{slide}{Proof Outline Cont...} Suppose $X \in K_{\alpha}$, with eigs $\lambda_i$, i.e. ${\cyan (*)} (n-1)\sum_i\lambda_i^2 -(\sum_i \lambda_i)^2 \leq 0$.\\ Now $\min \lambda_n$ subject to {\cyan *}.\\ Get \[ \lambda_n = \frac {\trace X}n-\sqrt{n-1} \sqrt{\frac {\trace X^2}n - \left(\frac {\trace X}n\right)} \geq 0. \] \epr \end{slide} %\bibliography{.master,.psd,.publs,.bjorBOOK} \end{document}