\documentclass[landscape,12pt]{article}
\newcommand{\bmat}{\left[ \begin{array}}
\newcommand{\emat}{\end{array} \right]}
% \newcommand{\pFq} {^{\phantom{\alpha}}_pF_q^\alpha}
\newcommand{\pFq} {_pF_q}
\newcommand{\chk} {\resizebox{0.5in}{0.5in}{\includegraphics*{check.pdf}}}
\newcommand{\ite}{\noindent\tb{$\bullet\;\,$}}


\pdfpagewidth 11in
\pdfpageheight 8.5in
\topmargin 0in
\headheight 0in
\headsep 0in


\textwidth10in
\oddsidemargin -0.5in
%\evensidemargin-0.5in
\textheight9.5in
\topmargin-1in

%\footheight 0in
%\textwidth 10in
%\oddsidemargin 0.5in
%\evensidemargin 0.5in



\pagestyle{empty}
% \newcommand{\ignore}[1]{}
\newcommand{\IGNORE}[1]{}
\newcommand{\ignore}[1]{#1}

\newcommand{\bits}{{\rm \# bits}}
\newcommand{\size}{{\rm size}}
\newcommand{\diag}{{\rm diag}}
% \newcommand{\det}{{\rm det}}
\usepackage{color}
\usepackage{graphics}
\usepackage{amsmath,amssymb}
% \usepackage{lscape}
% \input{psfig.sty}

\newcommand{\leadin}{{\phantom{X} \vskip0.2in}}

\newcommand{\slide}[1]
{
\newpage
\begin{center}
\phantom{X} \vskip0.2in
{\huge #1}
\end{center}
\hrule
\bigskip
}



\newcommand{\cond}{{\rm cond}}
\newcommand{\tb}{\textcolor{blue}}
\newcommand{\tr}{\textcolor{red}}
\newcommand{\tg}{\textcolor{green}}
% \newcommand{\det}{{\rm det}}
\begin{document}


\def\boxtext#1{%
\vbox{%
\hrule
\hbox{\strut \vrule{} #1 \vrule}%
\hrule
}%
}


\boldmath

\LARGE\bfseries\sffamily


%-----------------------------------------------------------
% Page 1

%\begin{landscape}

\begin{center}


\centerline{\resizebox{11.5in}{!}{\includegraphics*{MIT3.jpg}}}


\vskip-4.8in

{\huge Accurate Eigenvalues of Sign Regular Matrices}

\vskip0.3in


{\LARGE Plamen Koev}
\\
\Large Massachusetts Institute of Technology

\vskip0.5in

joint work with Froil\'an Dopico


\vskip0.4in
Supported by NSF
\vskip0.4in


{\large SIAM-GAMM Applied Linear Algebra Conference}

{\large D\"usseldorf, Germany, July, 2006}



\end{center}



% ----------------------------------------------------------


\slide{New Result}


\begin{itemize}

\item New $\mathcal{O}(n^3)$ eigenvalue algorithm for certain sign regular matrices

\item All eigenvalues computed to \underline{high relative accuracy}:

$$
|\lambda_i-\hat \lambda_i| = \mathcal{O}(\varepsilon) \tb{|\lambda_i|}
$$

as opposed to

$$
|\lambda_i-\hat \lambda_i| = \mathcal{O}(\varepsilon) \tr{|\lambda_{\max}|
\frac{1}{y_i^Tx_i}
}
$$

\item Uses only working precision
\item Accuracy unaffected by angle between left and right eigenvectors


\vskip1.2in
\item First example of:

$\mathcal{O}(n^3)$ accurate eigenvalue algorithm 
for a \underline{nonsymmetric} matrix
with both \underline{positive and negative} eigenvalues

% ------------------------------------------------------------------




\slide{What is a Sign-Regular Matrix?}


\vskip0.3in

\centerline{\tb{``A matrix whose $k$th order minors  
have
sign 
$(-1)^{k(k-1)/2}$''}}

\item Equivalently:

\vskip0.2in
\centerline{\textcolor{blue}{``Totally positive matrix with reversed columns''}}
\vskip0.2in


\item Recall: \tr{``Totally Positive''} means \tr{``all minors $>0$''}, 
e.g.,
$$
\begin{array}{ccc}
\quad
\bmat{ccccc}
1 & 1 & 1 & 1        \\
1 & 2 & 2^2 & 2^3  \\
1 & 3 & 3^2 & 3^3 \\
1 & 4 & 4^2 & 4^3
\emat
\quad
&
\quad
\bmat{cccc}
1         & ^1\!/\!_2 & ^1\!/\!_3 & ^1\!/\!_4  \\
^1\!/\!_2 & ^1\!/\!_3 & ^1\!/\!_4 & ^1\!/\!_5  \\
^1\!/\!_3 & ^1\!/\!_4 & ^1\!/\!_5 & ^1\!/\!_6  \\
^1\!/\!_4 & ^1\!/\!_5 & ^1\!/\!_6 & ^1\!/\!_7
\emat
\quad
&
\quad
\bmat{cccc}
1 & 1 & 1 & 1 \\
1 & 2 & 3 & 4  \\
1 & 3 & 6 & 10  \\
1 & 4 & 10 & 20
\emat
\quad
\\
\mbox{\tr{Vandermonde}} & \mbox{\tr{Hilbert}} & \mbox{\tr{Pascal}}
\end{array}
$$

\vskip0.3in

\item I.e., we consider
$$
\tr{\mbox{(Totally positive)}}\times
\bmat{cccc}
&&&1 \\
&&1\\
&1\\
1
\emat
$$

\item Generally unsymmetric; NOT similar to TP, but just as ill 
conditioned

% ------------------------------------------------------------------

\slide{$|$Eigenvalues$|$ of a $40\times 40$ Sign Regular Vandermonde}


\centerline{\resizebox{7in}{!}{
\includegraphics*{iwasep6f.pdf}
}}

$$
V =\left[x_i^{j-1}\right]_{i,j=1}^{40},\; x=(4.0,3.9,\ldots,0.1)
$$
\item Theory: $\lambda_i\in\mathbb{R},\; \mbox{sign}(\lambda_i)=(-1)^{i-1}$


% ----------------------------------------------------------------

\slide{Why Sign Regular Matrices?}

\vskip2in

Axel Ruhe comment in 2002:

\vskip1in

\tb{``... a class of matrices that I have never heard of}

\tb{... using algorithms I have never heard of}

\tb{... by people I have never heard of''}




% ----------------------------------------------------------------

\slide{Why Sign Regular Matrices?}

\vskip0.4in

\item Eigenvalues determined accurately!

\item The next logical item on the list of accurate algorithms:

\begin{itemize}
\item Vandermonde
\item Cauchy
\item polynomial Vandermonde
\item Generalized Vandermonde
\item M-matrices
\item Elliptic PDEs/Finite elements
\item Totally nonnegative
\item Sign regular
\end{itemize}



% --------------------------------------------------------------------

\slide{The business of $\lambda_i$ being determined accurately}

\item We will be computing eigenvalues of
$$
\tr{\mbox{(Totally positive)}}\times
\bmat{cccc}
&&&1 \\
&&1\\
&1\\
1
\emat
$$

\item Start with TP

\item Key fact: Demmel--Kahan 1990: $\sigma_i$ of 

$$
\bmat{cccc}
a_1 & b_1\\
&a_2 & b_2\\
&&\ddots & \ddots \\
&&&a_n 
\emat
$$

determined accurately by $a_i,b_i$.

% --------------------------------------------------------------------

\slide{The business of $\lambda_i$ being determined accurately}

\item We will be computing eigenvalues of
$$
\tr{\mbox{(Totally positive)}}\times
\bmat{cccc}
&&&1 \\
&&1\\
&1\\
1
\emat
$$

\item Start with TP

\item Key fact: Demmel--Kahan 1990: $\lambda_i$ of 

{\large
$$
\bmat{cccc}
1 \\
\tr {\!b_{21}}\!\!\!& 1 \\
& \tr {\!b_{32}}\!\!\!& 1\\
&& \tr {\!b_{43}}\!\!\! & 1
\emat
\bmat{cccc}
\tr {\!b_{11}}\!\!\! \\
& \tr {\!b_{22}}\!\!\! \\
& & \tr {\!b_{33}}\!\!\! \\
&&  & \tr {\!b_{44}}\!\!\!
\emat
\bmat{cccc}
1 & \tr {\!b_{12}} \!\!\!\\
& 1 & \tr {\!b_{23}}\!\!\!\\
& & 1 & \tr {\!b_{34}}\!\!\!\\
&&  & 1
\emat
$$
}

determined accurately by $\tr{b_{ij}}>0$.

% --------------------------------------------------------------------

\slide{The business of $\lambda_i$ being determined accurately}

\item We will be computing eigenvalues of
$$
\tr{\mbox{(Totally positive)}}\times
\bmat{cccc}
&&&1 \\
&&1\\
&1\\
1
\emat
$$

\item Start with TP

\item Key fact: Koev 2005: $\lambda_i$ of 

{\large
$$
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&\tr {\!b_{41}}\!\!\!& 1
\emat
\bmat{cccc}
1 \\
& 1 \\
&\tr {\!b_{31}}\!\!\!& 1\\
&&\tr {\!b_{42}}\!\!\!& 1
\emat
\bmat{cccc}
1 \\
\tr {\!b_{21}}\!\!\!& 1 \\
& \tr {\!b_{32}}\!\!\!& 1\\
&& \tr {\!b_{43}}\!\!\! & 1
\emat
\bmat{cccc}
\tr {\!b_{11}}\!\!\! \\
& \tr {\!b_{22}}\!\!\! \\
& & \tr {\!b_{33}}\!\!\! \\
&&  & \tr {\!b_{44}}\!\!\!
\emat
\bmat{cccc}
1 & \tr {\!b_{12}} \!\!\!\\
& 1 & \tr {\!b_{23}}\!\!\!\\
& & 1 & \tr {\!b_{34}}\!\!\!\\
&&  & 1
\emat
\bmat{cccc}
1 \\
& 1 & \tr {\!b_{13}}\!\!\!\\
& & 1 & \tr {\!b_{24}}\!\!\!\\
&&  & 1
\emat\bmat{cccc}
1 \\
& 1 \\
& & 1 & \tr {\!b_{14}}\!\!\!\\
&&  & 1
\emat
$$
}

determined accurately by $\tr{b_{ij}}>0$.

% --------------------------------------------------------------------

\slide{The business of $\lambda_i$ being determined accurately}

\item We will be computing eigenvalues of
$$
\tr{\mbox{(Totally positive)}}\times
\bmat{cccc}
&&&1 \\
&&1\\
&1\\
1
\emat
$$

\item Start with TP

\item New result for SR matrices: $\lambda_i$ of 


\end{itemize}


{\large
$$
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&\tr {\!b_{41}}\!\!\!& 1
\emat
\bmat{cccc}
1 \\
& 1 \\
&\tr {\!b_{31}}\!\!\!& 1\\
&&\tr {\!b_{42}}\!\!\!& 1
\emat
\bmat{cccc}
1 \\
\tr {\!b_{21}}\!\!\!& 1 \\
& \tr {\!b_{32}}\!\!\!& 1\\
&& \tr {\!b_{43}}\!\!\! & 1
\emat
\bmat{cccc}
\tr {\!b_{11}}\!\!\! \\
& \tr {\!b_{22}}\!\!\! \\
& & \tr {\!b_{33}}\!\!\! \\
&&  & \tr {\!b_{44}}\!\!\!
\emat
\bmat{cccc}
1 & \tr {\!b_{12}} \!\!\!\\
& 1 & \tr {\!b_{23}}\!\!\!\\
& & 1 & \tr {\!b_{34}}\!\!\!\\
&&  & 1
\emat
\bmat{cccc}
1 \\
& 1 & \tr {\!b_{13}}\!\!\!\\
& & 1 & \tr {\!b_{24}}\!\!\!\\
&&  & 1
\emat\bmat{cccc}
1 \\
& 1 \\
& & 1 & \tr {\!b_{14}}\!\!\!\\
&&  & 1
\emat
\tb{
\bmat{cccc}
&&&1\\&&1\\&1\\1
\emat
}
$$
}

determined accurately by $\tr{b_{ij}}>0$.


% ------------------------------------------------------------------

\slide{TP Eigenvalue algorithm}

\begin{itemize}
\item Using only
\begin{itemize}
\item Subtract a multiple of row from next to make a zero
\item Add a positive multiple of a row to next/previous

\end{itemize}
\item Both preserve TP structure
\item When applied implicitly, no subtractions are required

{\large
$$
\bmat{ccc}
 1 \\
& 1\\
&\tr {b_{31}}& 1
\emat
\bmat{ccc}
 1 \\
\tr {b_{21}}& 1\\
&\tr {b_{32}}& 1
\emat
\bmat{cccc}
 \tr {b_{11}} \\
 & \tr {b_{22}} \\
&  & \tr {b_{33}}
\emat
\bmat{ccc}
1 & \tr {b_{12}} \\
& 1 & \tr {b_{23}}\\
&  & 1
\emat
\bmat{ccc}
1 \\
& 1 & \tr {b_{13}}\\
&  & 1
\emat
$$
}
\tb{
$$
\downarrow % \mbox{EET}
$$
}
{\large
$$
\bmat{ccc}
 1 \\
\tr {b_{21}'}& 1\\
&\tr {b_{32}'}& 1
\emat
\bmat{cccc}
 \tr {b_{11}'} \\
 & \tr {b_{22}'} \\
&  & \tr {b_{33}'}
\emat
\bmat{ccc}
1 & \tr {b_{12}'} \\
& 1 & \tr {b_{23}'}\\
&  & 1
\emat
$$
}



%-----------------------------------------------------------
\slide{Why No Subtractive Cancellation?}

\item Relative accuracy preserved in $\times, +, /$

Proof: $(1+\delta)$ factors accumulate multiplicatively

\item Subtractions of approximate quantities dangerous:

\begin{center}
\begin{tabular}{rl}
   & $.123456789\color{red}{xxx}$ \\
$-$& $.123456789\color{red}{yyy}$ \\
\hline
   & $.000000000\color{red}{zzz}$
\end{tabular}
\end{center}


\item Initial data is OK to subtract: $(x_i-y_j)$
\item Reduction to anti-bidiagonal involves no subtractions








% ------------------------------------------------------------------

\slide{Algorithm Outline}


\item SR similar to a \tb{symmetric anti-bidiagonal}; \hskip0.4in (eigs 
then easy)

\begin{eqnarray*}
\bmat{cccc}
\tb+ &\tb+ &\tb+ &\tb+\\
\tb+ &\tb+ &\tb+ &\tb+\\
\tb+ &\tb+ &\tb+ &\tb+\\
\tb+ &\tb+ &\tb+ &\tb+
\emat
&\longrightarrow&
\bmat{cccc}
&&\tb+&\tb+\\
&\tb+&\tb+\\
\tb+&\tb+\\
\tb+
\emat\\
\\
\tb{\mbox{Sign regular\phantom{X}}}&\longrightarrow&\tb{\mbox{anti-bidiagonal}}
\end{eqnarray*}

\item But done by transforming the TP factor:
\begin{eqnarray*}
\bmat{cccc}
\tr+  &\tr+ &\tr+ &\tr+\\
\tr+  &\tr+ &\tr+ &\tr+\\
\tr+  &\tr+ &\tr+ &\tr+\\
\tr+  &\tr+ &\tr+ &\tr+
\emat
\cdot
\bmat{cccc} &&&1 \\ &&1 \\ &1 \\1\emat
&\longrightarrow&
\bmat{ccccc}
\tr+ &\tr+ \\
&\tr+ &\tr+ \\
&&\tr+ &\tr+ \\
&&&\tr+
\emat
\cdot
\bmat{cccc} &&&1 \\ &&1 \\ &1 \\1\emat
\\
\\
\tr{\mbox{Totally Positive}}\cdot \phantom{xX}
J\phantom{XXX}&\longrightarrow&\tr{\mbox{\phantom{X}Bidiagonal\phantom{xX}}}
\cdot \phantom{xxX}J
\end{eqnarray*}

\item using TP/Accuracy-preserving subtraction-free transformations 

\end{itemize}

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal}

\begin{itemize}

\item First reduce to (Upper Triangular) $\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{
\bmat{cccc}
1\\ & 1\\ && 1\\ &&- & 1
\emat
}
{
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
\tr +&+&+&+
\emat
}
\bmat{cccc}
&&&1\\ &&1 \\ &1 \\ 1
\emat
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 2}

\begin{itemize}

\item First reduce to (Upper Triangular) $\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\tb{\bmat{cccc} 1\\ & 1\\ && 1\\ &&- & 1 \emat}
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
\tr +&+&+&+
\emat
\bmat{cccc}
&&&1\\ &&1 \\ &1 \\ 1
\emat
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 3}

\begin{itemize}

\item First reduce to (Upper Triangular) $\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\tb{\bmat{cccc} 1\\ & 1\\ && 1\\ &&- & 1 \emat}
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
\tr +&+&+&+
\emat
\bmat{cccc}
&&&1\\ &&1 \\ &1 \\ 1
\emat
\tb{\bmat{cccc} 1\\ & 1\\ && 1\\ &&+ & 1 \emat}
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 4}

\begin{itemize}

\item First reduce to (Upper Triangular) $\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\tb{\bmat{cccc} 1\\ & 1\\ && 1\\ &&- & 1 \emat
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
\tr +&+&+&+
\emat
}
\bmat{cccc}
&&&1\\ &&1 \\ &1 \\ 1
\emat
{\bmat{cccc} 1\\ & 1\\ && 1\\ &&+ & 1 \emat}
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 5}

\begin{itemize}

\item First reduce to (Upper Triangular) $\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ && 1\\ &&- & 1 \emat}
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
\tr 0&+&+&+
\emat
\bmat{cccc}
&&&1\\ &&1 \\ &1 \\ 1
\emat
{\bmat{cccc} 1\\ & 1\\ && 1\\ &&+ & 1 \emat}
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 6}

\begin{itemize}

\item First reduce to (Upper Triangular) $\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ && 1\\ &&- & 1 \emat}
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
\tr 0&+&+&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} 1\\ & 1\\ && 1\\ &&+ & 1 \emat
\tb{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 7}

\begin{itemize}

\item First reduce to (Upper Triangular) $\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ && 1\\ &&- & 1 \emat}
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
\tr 0&+&+&+
\emat
\tb{
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} 1\\ & 1\\ && 1\\ &&+ & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 8}

\begin{itemize}

\item First reduce to (Upper Triangular) $\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ && 1\\ &&- & 1 \emat}
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
\tr 0&+&+&+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\tb{
\bmat{cccc} 1 & + \\ & 1\\ && 1\\ && & 1 \emat
}
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 9}

\begin{itemize}

\item First reduce to (Upper Triangular) $\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ && 1\\ &&- & 1 \emat}
\tb{
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
\tr 0&+&+&+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} 1 & + \\ & 1\\ && 1\\ && & 1 \emat
}
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$


% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 10}

\begin{itemize}

\item First reduce to (Upper Triangular) $\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ && 1\\ &&- & 1 \emat}
\tb{
\bmat{cccc}
\tr+&\tr+&+&+\\
\tr+&\tr+&+&+\\
\tr+&\tr+&+&+\\
\tr 0&\tr+&+&+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} 1 & + \\ & 1\\ && 1\\ && & 1 \emat
}
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$


% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 11}

\begin{itemize}

\item First reduce to (Upper Triangular) $\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ && 1\\ &&- & 1 \emat}
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
0&+&+&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$




% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 12}

\begin{itemize}

\item Making more zeros analogous

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ &-& 1\\ && & 1 \emat}
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
\tr+&+&+&+\\
0&+&+&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\phantom{
\bmat{cccc} 1\\ & 1\\ && 1\\ &&+ & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
}
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 13}

\begin{itemize}

\item Making more zeros analogous

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ &-& 1\\ && & 1 \emat}
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
\tr 0&+&+&+\\
0&+&+&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\phantom{
\bmat{cccc} 1\\ & 1\\ && 1\\ &&+ & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
}
$


% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 14}

\begin{itemize}

\item Making more zeros analogous

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ &-& 1\\ && & 1 \emat}
\bmat{cccc}
+&+&+&+\\
\tr 0&+&+&+\\
0&+&+&+\\
0&+&+&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\phantom{
\bmat{cccc} 1\\ & 1\\ && 1\\ &&+ & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
}
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 15}

\begin{itemize}

\item Making more zeros analogous

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ &-& 1\\ && & 1 \emat}
\bmat{cccc}
+&+&+&+\\
0&+&+&+\\
0&+&+&+\\
0&\tr 0&+&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\phantom{
\bmat{cccc} 1\\ & 1\\ && 1\\ &&+ & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
}
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 16}

\begin{itemize}

\item Making more zeros analogous

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ &-& 1\\ && & 1 \emat}
\bmat{cccc}
+&+&+&+\\
0&+&+&+\\
0&\tr 0&+&+\\
0&0&+&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\phantom{
\bmat{cccc} 1\\ & 1\\ && 1\\ &&+ & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
}
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 17}

\begin{itemize}

\item Making more zeros analogous

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ &-& 1\\ && & 1 \emat}
\bmat{cccc}
+&+&+&+\\
0&+&+&+\\
0&0&+&+\\
0&0&\tr 0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\phantom{
\bmat{cccc} 1\\ & 1\\ && 1\\ &&+ & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
}
$


% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 18}

\begin{itemize}

\item (Upper Triangular)$\times J\rightarrow \mbox{(Upper bidiagonal)}\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1\\ & 1\\ && 1\\ &&- & 1 \emat}
\bmat{cccc}
+&+&+&\tr+\\
0&+&+&+\\
0&0&+&+\\
0&0&0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\phantom{\bmat{cccc} 1\\ & 1\\ && 1\\ &&+ & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
}
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 19}

\begin{itemize}

\item (Upper Triangular)$\times J\rightarrow \mbox{(Upper bidiagonal)}\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&\tr+\\
0&+&+&+\\
0&0&+&+\\
0&0&0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} 1 & + \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 20}

\begin{itemize}

\item (Upper Triangular)$\times J\rightarrow \mbox{(Upper bidiagonal)}\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&\tr+\\
0&+&+&+\\
0&0&+&+\\
0&0&0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} 1 & + \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat}
\bmat{cccc}
+&+&\tr+&\tr0\\
0&+&\tr+&\tr+\\
0&0&\tr+&\tr+\\
0&0&\tr 0&\tr+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} 1  \\ & 1\\ && 1\\ && + & 1 \emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 21}

\begin{itemize}

\item (Upper Triangular)$\times J\rightarrow \mbox{(Upper bidiagonal)}\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&\tr+\\
0&+&+&+\\
0&0&+&+\\
0&0&0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} 1 & + \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat}
\bmat{cccc}
+&+&\tr+&\tr0\\
0&+&\tr+&\tr+\\
0&0&\tr+&\tr+\\
0&0&\tr 0&\tr+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} 1  \\ & 1\\ && 1\\ && + & 1 \emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat}
\bmat{cccc}
+&+&+&0\\
0&+&+&+\\
0&0&+&+\\
0&0&\tr+&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
%\bmat{cccc} 1  \\ & 1\\ && 1\\ && + & 1 \emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 22}

\begin{itemize}

\item (Upper Triangular)$\times J\rightarrow \mbox{(Upper bidiagonal)}\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&\tr+\\
0&+&+&+\\
0&0&+&+\\
0&0&0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} 1 & + \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat}
\bmat{cccc}
+&+&\tr+&\tr0\\
0&+&\tr+&\tr+\\
0&0&\tr+&\tr+\\
0&0&\tr 0&\tr+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} 1  \\ & 1\\ && 1\\ && + & 1 \emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat}
\bmat{cccc}
+&+&+&0\\
0&+&+&+\\
0&0&+&+\\
0&0&\tr 0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
%\bmat{cccc} 1  \\ & 1\\ && 1\\ && + & 1 \emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 23}

\begin{itemize}

\item (Upper Triangular)$\times J\rightarrow \mbox{(Upper bidiagonal)}\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&+\\
0&+&+&+\\
0&0&+&+\\
0&0&0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} 1 & + \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat}
\bmat{cccc}
+&+&+&0\\
0&+&+&+\\
0&0&+&+\\
0&0& 0&+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} 1  \\ & 1\\ && 1\\ && + & 1 \emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1  \\ & 1\\ && 1\\ && -  & 1 \emat}
\bmat{cccc}
 +& +&+&0\\
 0& +&+&\tr +\\
 0& 0&+&+\\
 0& 0& 0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 24}

\begin{itemize}

\item (Upper Triangular)$\times J\rightarrow \mbox{(Upper bidiagonal)}\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&+\\
0&+&+&+\\
0&0&+&+\\
0&0&0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} 1 & + \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat}
\bmat{cccc}
+&+&+&0\\
0&+&+&+\\
0&0&+&+\\
0&0& 0&+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} 1  \\ & 1\\ && 1\\ && + & 1 \emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1  \\ & 1\\ && 1\\ && -  & 1 \emat}
\bmat{cccc}
 +& +&\tr +&0\\
 0& +&+&\tr 0\\
 0& 0&+&+\\
 0& 0& 0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$


% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 25}

\begin{itemize}

\item (Upper Triangular)$\times J\rightarrow \mbox{(Upper bidiagonal)}\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&+\\
0&+&+&+\\
0&0&+&+\\
0&0&0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} 1 & + \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat}
\bmat{cccc}
+&+&+&0\\
0&+&+&+\\
0&0&+&+\\
0&0& 0&+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} 1  \\ & 1\\ && 1\\ && + & 1 \emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1  \\ & 1\\ && 1\\ && -  & 1 \emat}
\bmat{cccc}
 +& +&\tr 0&0\\
 0& +&+&\tr 0\\
 0& 0&+&+\\
 0& 0& 0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$
% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 26}

\begin{itemize}

\item (Upper Triangular)$\times J\rightarrow \mbox{(Upper bidiagonal)}\times J$

\end{itemize}

\bigskip
\bigskip

\noindent$
\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&+\\
0&+&+&+\\
0&0&+&+\\
0&0&0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} 1 & + \\ & 1\\ && 1\\ && & 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1 & - \\ & 1\\ && 1\\ && & 1 \emat}
\bmat{cccc}
+&+&+&0\\
0&+&+&+\\
0&0&+&+\\
0&0& 0&+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} 1  \\ & 1\\ && 1\\ && + & 1 \emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

\bigskip
\bigskip

\noindent$
\phantom{\bmat{cccc} 1  \\ & 1\\ && 1\\ && -  & 1 \emat}
\bmat{cccc}
 +& +& 0&0\\
 0& +&+& 0\\
 0& 0&+&+\\
 0& 0& 0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
=
\bmat{cccc}
&& + & + \\
& + & + \\
 + & + \\
 +
\emat
$

% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 27}

\begin{itemize}

\item Finally, symmetrizing:

\end{itemize}

$$
\bmat{cccc} d_1  \\ & d_2\\ && d_3\\ && & d_4 \emat
\bmat{cccc}
&&b_1 & a_1\\
&b_2 & a_2\\
b_3 & a_3\\
 a_4
\emat
\bmat{cccc} d_1 & \\ & d_2\\ && d_3\\ && & d_4 \emat^{-1}
$$

\bigskip
\bigskip

$$
=\bmat{cccc}
& & \sqrt{b_1b_3} & \sqrt{a_1a_4}\\
&b_2 & \sqrt{a_2a_3}\\
\sqrt{b_1b_3} &
\sqrt{a_2a_3}\\
\sqrt{a_1a_4}
\emat
$$

% ----------------------------------------------------------
\slide{Eigenvalues of a Sign Regular Matrix}



$$
\mbox{eig}(\mbox{Sign Regular})=
\mbox{eig}
\underbrace{
\left(
\bmat{ccccc}
&& & b_1 & a_1\\
& & b_2 & a_2\\
 & b_2 & a_3\\
 b_1 & a_2\\
 a_1
\emat
\right)}
_{\mbox{symmetric}\;\;\Rightarrow\; |\lambda_i|=\sigma_i}
$$

\begin{itemize}

\item sign $\lambda_i=(-1)^{i-1}$ (from theory)

\item Thus suffices to compute $\sigma_i$, but that's easy:

$$
\sigma_i\left(
\bmat{ccccc}
&& & b_1 & a_1\\
& & b_2 & a_2\\
 & b_2 & a_3\\
 b_1 & a_2\\
 a_1
\emat\right)
=
\sigma_i\left(
\bmat{ccccc}
a_1 &  b_1 \\
&a_1 &  b_2 \\
&&a_3 &  b_2 \\
&&&a_2 &  b_1 \\
&&&&a_1
\emat\right)
$$

\medskip

\noindent---the latter solved by Demmel and Kahan 1990




% -----------------------------------------------------------------
\slide{Conclusions}


\item New $O(n^3)$ algorithm
\item Computes all eigenvalues of a SR matrix to high relative accuracy
\item First example of negative eigenvalues of a nonsymmetric matrix
computed to high
relative accuracy


\bigskip
\bigskip
\bigskip

\centerline{\huge Open problems}
\item Sign regular matrices with other signatures---no parameterization
known, let alone algorithms
\item Eigenvectors: Products of accurate factors, but what does accuracy
mean?

\bigskip
\bigskip
\bigskip

\vskip0.8in

\item This talk, papers, software: \verb+http://math.mit.edu/~plamen+

\end{itemize}



% --------------------------------------------------------------------
\slide{Perturbation Theory}

{\large

\noindent
$
C=\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&\tr {\!b_{41}}\!\!\!& 1
\emat \!\!
\bmat{cccc}
1 \\
& 1 \\
&\tr {\!b_{31}}\!\!\!& 1\\
&&\tr {\!b_{42}}\!\!\!& 1
\emat \!\!
\bmat{cccc}
1 \\
\tr {\!b_{21}}\!\!\!& 1 \\
& \tr {\!b_{32}}\!\!\!& 1\\
&& \tr {\!b_{43}}\!\!\! & 1
\emat \!\!
\bmat{cccc}
\tr {\!b_{11}}\!\!\! \\
& \tr {\!b_{22}}\!\!\! \\
& & \tr {\!b_{33}}\!\!\! \\
&&  & \tr {\!b_{44}}\!\!\!
\emat \!\!
\bmat{cccc}
1 & \tr {\!b_{12}} \!\!\!\\
& 1 & \tr {\!b_{23}}\!\!\!\\
& & 1 & \tr {\!b_{34}}\!\!\!\\
&&  & 1
\emat \!\!
\bmat{cccc}
1 \\
& 1 & \tr {\!b_{13}}\!\!\!\\
& & 1 & \tr {\!b_{24}}\!\!\!\\
&&  & 1
\emat\!\!
\bmat{cccc}
1 \\
& 1 \\
& & 1 & \tr {\!b_{14}}\!\!\!\\
&&  & 1
\emat\!\!
\tb{
\bmat{cccc}
&&&1\\&&1\\&1\\1
\emat
}
$
}

\begin{itemize}
\item Fact: Any minor of $C$ is a linear function in any $b_{ij}$
      with coefficients of same sign

$\Rightarrow$ All minors are accurately determined by $b_{ij}$

\item In particular, $c_{ij}$ are accurately determined, and in turn,
the Perron root, $\lambda_1$, is accurately determined

\item Next, consider the second compound matrix, $\mathcal{C}_2$, ---the
$\binom{n}{2}\times \binom{n}{2}$ matrix with entries
all $2\times 2$ minors of $C$

\item The entries of
$\mathcal{C}_2$ are negative and accurately determined by $b_{ij}$

\item The Perron root of $\mathcal{C}_2$, $\lambda_1\lambda_2$,
is also accurately determined

\item Thus, $\lambda_2$ is accurately determined

\end{itemize}


% ----------------------------------------
\slide{Accurate ${\cal BD}$ of Vandermonde and Cauchy}

\begin{itemize}
\item \tb{$V=\left[
x_i^{j-1}\right]_{i,j=1}^n$} {\large \hskip0.5in(TP if $0<x_1<x_2<\cdots<x_n$)}

\large
\begin{eqnarray*}
\tr{D_{ii}}=\prod_{j=1}^{i-1}(x_i-x_j),
\hskip0.7cm
\tr{L_{i+1,i}^{(k)}}=\prod_{j=n-k}^{i-1}\frac{x_{i+1}-x_{j+1}}{x_i-x_j},
\hskip0.7cm \tr{U^{(k)}_{i,i+1}}=x_{i+n-k}
\end{eqnarray*}

\LARGE
\item
\tb{$\displaystyle C=\left[\frac{1}{x_i+y_j}\right]_{i,j=1}^n$}
\hskip0.1in{\large (TP if $0<x_1<\cdots<x_n,\;
0<y_1<\cdots <y_n$)}


\large

\begin{eqnarray*}
\tr{D_{ii}}& = & \prod_{k=1}^{i-1}\frac{(x_i-x_k)(y_i-y_k)}{(x_i+y_k)(y_i+x_k)}
\nonumber \\
\tr{L_{i,i+1}^{(k)}}&=&
\frac{x_{n-k}+y_{i-n+k+1}}{x_i+y_{i-n+k+1}}
\prod_{l=n-k}^{i-1}\frac{x_{i+1}-x_{l+1}}{x_i-x_l}
\cdot \prod_{l=1}^{i-n+k-1}\frac{x_i+y_l}{x_{i+1}+y_l}
\\
\tr{U^{(k)}_{i+1,i}}&=&
\frac{y_{n-k}+x_{i-n+k+1}}{y_i+x_{i-n+k+1}}
\prod_{l=n-k}^{i-1}\frac{y_{i+1}-y_{l+1}}{y_i-y_l}
\cdot \prod_{l=1}^{i-n+k-1}\frac{y_i+x_l}{y_{i+1}+x_l}
\nonumber
\end{eqnarray*}

\LARGE

\item Similar formulas for Cauchy--Vandermonde, confluent

      (Jos\'e Javier Mart\'inez)

\item \tb{No subtractive cancellation $\Rightarrow$ accurate}

\end{itemize}


% ------------------------------------------------------------
\slide{Applying EETs on ${\cal BD}(A)$ -- I}

\begin{itemize}

\item Subtracting a row from next to make a zero

\bigskip

\noindent
$
\tr{
\phantom{=
\bmat{cccc}
1 \\
& 1\\
& -7 & 1
\emat
}
}
\bmat{cccc}
1 & 2 & 6 \\
\tb 3 & \tb{10} & \tb{50}  \\
\tr {21} & \tb{102} & \tb{615}
\emat
$

\bigskip

\noindent
$
=
\phantom{
\tr{
\bmat{cccc}
1 \\
& 1\\
 & -7 & 1
\emat
}
}
\bmat{cccc}
1 \\
& 1 \\
& 7 & 1
\emat
\bmat{cccc}
1 \\
3 & 1 \\
&  8 & 1
\emat
\bmat{cccc}
1 \\
& 4 \\
& & 9
\emat
\bmat{cccc}
1 & 2 \\
& 1 &  5\\
& & 1 \\
\emat
\bmat{cccc}
1 \\
& 1 & 3\\
& & 1
\emat
$
\end{itemize}

% ------------------------------------------------------------
\slide{Applying EETs on ${\cal BD}(A)$ -- II}

\begin{itemize}

\item Subtracting a row from next to make a zero

\bigskip

\noindent
$
\tr{
\phantom{=}
\bmat{cccc}
1 \\
& 1\\
& -7 & 1
\emat
}
\bmat{cccc}
1 & 2 & 6 \\
\tb 3 & \tb{10} & \tb{50}  \\
\tr {21} & \tb{102} & \tb{615}
\emat
$

\bigskip

\noindent
$
=
\tr{
\bmat{cccc}
1 \\
& 1\\
 & -7 & 1
\emat
}
\bmat{cccc}
1 \\
& 1 \\
& 7 & 1
\emat
\bmat{cccc}
1 \\
3 & 1 \\
&  8 & 1
\emat
\bmat{cccc}
1 \\
& 4 \\
& & 9
\emat
\bmat{cccc}
1 & 2 \\
& 1 &  5\\
& & 1 \\
\emat
\bmat{cccc}
1 \\
& 1 & 3\\
& & 1
\emat
$

\end{itemize}

% ------------------------------------------------------------
\slide{Applying EETs on ${\cal BD}(A)$ -- III}

\begin{itemize}

\item Subtracting a row from next to make a zero

\bigskip

\noindent
$
\tr{
\phantom{=}
\bmat{cccc}
1 \\
& 1\\
& -7 & 1
\emat
}
\bmat{cccc}
1 & 2 & 6 \\
\tb 3 & \tb{10} & \tb{50}  \\
\tr {21} & \tb{102} & \tb{615}
\emat
$

\bigskip

\noindent
$
=
\tr{
\bmat{cccc}
1 \\
& 1\\
 & -7 & 1
\emat
}
\bmat{cccc}
1 \\
& 1 \\
& 7 & 1
\emat
\bmat{cccc}
1 \\
3 & 1 \\
&  8 & 1
\emat
\bmat{cccc}
1 \\
& 4 \\
& & 9
\emat
\bmat{cccc}
1 & 2 \\
& 1 &  5\\
& & 1 \\
\emat
\bmat{cccc}
1 \\
& 1 & 3\\
& & 1
\emat
$
\bigskip

\noindent
$
=\phantom{
\tr{
\bmat{cccc}
1 \\
& 1\\
 & -7 & 1
\emat
}         }
\bmat{cccc}
1 \\
& 1 \\
& \tr 0 & 1
\emat
\bmat{cccc}
1 \\
3 & 1 \\
&  8 & 1
\emat
\bmat{cccc}
1 \\
& 4 \\
& & 9
\emat
\bmat{cccc}
1 & 2 \\
& 1 &  5\\
& & 1 \\
\emat
\bmat{cccc}
1 \\
& 1 & 3\\
& & 1
\emat
$

\item Is equivalent to setting an entry of ${\cal BD}(A)$ to zero and performing
\tb{\em no arithmetic}.

\end{itemize}


%-----------------------------------------------------------
\slide{ Adding a multiple of a column to previous -- I}

\noindent
$
\phantom{=}
\bmat{cccc}
 1 \\
& 1\\
& a & 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 &e \\
& & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\underline{
\bmat{cccc}
 1 \\
 & 1 & k\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y\\
&x&z\\
\emat
}
}
$


%-----------------------------------------------------------
\slide{ Adding a multiple of a column to previous -- II}

\noindent
$
\phantom{=}
\bmat{cccc}
 1 \\
& 1\\
& a & 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 &e \\
& & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\underline{
\bmat{cccc}
 1 \\
 & 1 & k\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y\\
&x&z\\
\emat
}
}
$

\bigskip

\noindent$=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\underline{
\tr{
\bmat{cccc}
1\\
&y'\\
&x'&z'\\
\emat
}
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
}
$

\begin{eqnarray}
x'&=&x\nonumber \\
y'&=&y+kx\nonumber \\
z'&=&1/y'\nonumber \\
k'&=&kz/y_1\nonumber
\end{eqnarray}

\bigskip
\bigskip

... it's all qd recurrences



%-----------------------------------------------------------
\slide{ Adding a multiple of a column to previous -- III}

\noindent
$
\phantom{=}
\bmat{cccc}
 1 \\
& 1\\
& a & 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 &e \\
& & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & k\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y\\
&x&z\\
\emat
}
$

\bigskip

\noindent$=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\underline{
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y'\\
&x'&z'\\
\emat
}
}
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\noindent
$
=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\underline{
\tr{
\bmat{cccc}
1\\
&y''\\
&x''&z''\\
\emat
}
\bmat{cccc}
 1 & \tb { g'}\\
 & 1 & \tb {h'}\\
&  & 1
\emat
}
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$









%-----------------------------------------------------------
\slide{ Adding a multiple of a column to previous -- IV}

\noindent
$
\phantom{=}
\bmat{cccc}
 1 \\
& 1\\
& a & 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 &e \\
& & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & k\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y\\
&x&z\\
\emat
}
$

\bigskip

\noindent$=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y'\\
&x'&z'\\
\emat
}
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\noindent
$
=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\underline{
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\tr{
\bmat{cccc}
1\\
&y''\\
&x''&z''\\
\emat
}
}
\bmat{cccc}
 1 & \tb { g'}\\
 & 1 & \tb {h'}\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\noindent
$
=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\underline{
\tr{
\bmat{cccc}
1\\
&1\\
&x'''&1\\
\emat
}
\bmat{cccc}
 d \\
 & \tb{e'} \\
&  &\tb{f'}
\emat
}
\bmat{cccc}
 1 & \tb {g'}\\
 & 1 & \tb {h'}\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$


%-----------------------------------------------------------
\slide{ Adding a multiple of a column to previous -- V}

\noindent
$
\phantom{=}
\bmat{cccc}
 1 \\
& 1\\
& a & 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 &e \\
& & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & k\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y\\
&x&z\\
\emat
}
$

\bigskip

\noindent$=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\bmat{cccc}
 1 & g\\
 & 1 & h\\
&  & 1
\emat
\tr{
\bmat{cccc}
1\\
&y'\\
&x'&z'\\
\emat
}
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\noindent
$
=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\bmat{cccc}
 d \\
 & e \\
&  & f
\emat
\tr{
\bmat{cccc}
1\\
&y''\\
&x''&z''\\
\emat
}
\bmat{cccc}
 1 & \tb { g'}\\
 & 1 & \tb {h'}\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\noindent
$
=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\underline{
\bmat{cccc}
 1 \\
b& 1\\
& c& 1
\emat
\tr{
\bmat{cccc}
1\\
&1\\
&x'''&1\\
\emat
}
}
\bmat{cccc}
 d \\
 & \tb{e'} \\
&  &\tb{f'}
\emat
\bmat{cccc}
 1 & \tb {g'}\\
 & 1 & \tb {h'}\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\noindent
$=
\bmat{cccc}
 1 \\
& 1\\
& a& 1
\emat
\underline{
\bmat{cccc}
 1 \\
b& 1\\
& \tb {c+x'''}& 1
\emat
\bmat{cccc}
 d \\
 & \tb{e'} \\
&  & \tb {f'}
\emat
}
\bmat{cccc}
 1 & \tb {g'}\\
 & 1 & \tb {h'}\\
&  & 1
\emat
\bmat{cccc}
 1 \\
 & 1 & \tb {k'}\\
&  & 1
\emat
$

\bigskip

\tb{Done.}



\end{document}


