\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<v,\svec(S)\right>
\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<X,I\right>=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}
