\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 M.I.T.

\vskip0.5in

joint work with Froil\'an Dopico


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


{\large IWASEP 6}

{\large PennState, May, 2006}



\end{center}




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

\slide{Recall: \tr{Totally Positive} Means All Minors $>0$}

\begin{itemize}


\item Examples:
$$
\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}
$$

\item Eigenvalues
$$
\begin{array}{rrr}
   71.5987     &   \phantom{XXXXXX}  1.5002 \phantom{XXXXXX} &   26.3047 \\
    3.6199     &   \phantom{XXXXXX}  0.1691 \phantom{XXXXXX}  &    2.2034 \\
    0.7168     &   \phantom{XXXXXX}  0.0067 \phantom{XXXXXX}  &    0.4538 \\
    0.0646     &   \phantom{XXXXXX}  0.0001 \phantom{XXXXXX}  &    0.0380
\end{array}
$$

\item Note: Despite possible nonsymmetry: $\lambda_i>0$, real!

\item Virtually all linear algebra possible accurately
(2 papers in SIMAX)

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

\slide{This Talk: \tb{Sign Regular} Matrices}

\item Consider
$$
\tr{\mbox{(Totally positive)}}\times
\bmat{cccc}
&&&1 \\
&&1\\
&1\\
1
\emat
$$

\noindent ---called \tb{Sign Regular}, meaning

\bigskip
\bigskip

\centerline{\tb{All minors of order $k$ have the same sign
$\rho_k \in \{-1,+1\}$}}

\bigskip
\bigskip

\item In our case $(\rho_1,\rho_2,\ldots)=(+1,-1,-1,+1,\ldots)$


\item Generally unsymmetric; NOT similar to TP

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

\slide{Eigenproblem for Sign Regular (SR) Matrices}

\item Examples of SR matrices

$$
\begin{array}{ccc}
\quad
\bmat{ccccc}
1 & 4 & 4^2 & 4^3 \\
1 & 3 & 3^2 & 3^3 \\
1 & 2 & 2^2 & 2^3  \\
1 & 1 & 1 & 1
\emat
\quad
&
\quad
\bmat{cccc}
^1\!/\!_4 & ^1\!/\!_5 & ^1\!/\!_6 & ^1\!/\!_7  \\
^1\!/\!_3 & ^1\!/\!_4 & ^1\!/\!_5 & ^1\!/\!_6  \\
^1\!/\!_2 & ^1\!/\!_3 & ^1\!/\!_4 & ^1\!/\!_5  \\
1         & ^1\!/\!_2 & ^1\!/\!_3 & ^1\!/\!_4
\emat
\quad
&
\quad
\bmat{cccc}
1 & 4 & 10 & 20\\
1 & 3 & 6 & 10  \\
1 & 2 & 3 & 4  \\
1 & 1 & 1 & 1
\emat
\end{array}
$$


\item Eigenvalues:

$$
\begin{array}{rrr}
   15.4897    & \phantom{XXXXX}   1.1194 \phantom{XXXXX}&  11.2006  \\
   -7.7063    & \phantom{XXXXX}  -0.1261 \phantom{XXXXX}&  -3.7655   \\
    1.2942    & \phantom{XXXXX}   0.0068 \phantom{XXXXX}&   0.6041   \\
   -0.0777    & \phantom{XXXXX}  -0.0002 \phantom{XXXXX}&  -0.0392
\end{array}
$$


\item Note: Despite nonsymmetry, $\lambda_k$ are real;
sign$(\lambda_k)=(-1)^{k-1}$


\item Notoriously ill conditioned, just like TP
\end{itemize}

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

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


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

$$
V =\left[x_i^{j-1}\right]_{i,j=1}^{40},\quad x=(4.0,3.9,3.8,\ldots,0.1)
$$


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

\slide{New Result: Accurate Eigenvalue Algorithm for SR Matrices}

\begin{itemize}

\item Takes $O(n^3)$ time
\item Uses only working precision
\item Accuracy unaffected by angle between left and right eigenvectors
\item All eigenvalues computed to 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}
}
$$

\vskip1.6in
\item First example of \underline{negative} eigenvalues of a
\underline{nonsymmetric} matrix
computed accurately

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

\slide{Outline}

\item (Almost) any matrix is similar to a \tb{symmetric anti-bidiagonal}

(eig of latter then easy)

$$
\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
$$

\item Trick: no subtractions in above reduction

\item We need a structure revealing representation---product of bidiagonals


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

\slide{Outline}

\item \tr{(Almost) any matrix is similar to a {symmetric anti-bidiagonal}}


(eig of latter then easy)

$$
\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
$$

\item Trick: no subtractions in above reduction

\item We need a structure revealing representation---product of bidiagonals

\end{itemize}



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


\begin{itemize}
\item Goal:
\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 Equivalently:
\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*}

\vskip1in

(Prefer TP $\cdot J$ since we know how to do TP linear algebra accurately)

\end{itemize}

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


\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*}


\vskip0.3in

\begin{itemize}
\item Nevermind the possible instability; it won't be an issue
\item Only 2 operations required; both performed on the \tr{TP} factor:
\begin{itemize}
\item Subtract a multiple of row from next to make a zero
\item Add a positive multiple of a column to next/previous
\end{itemize}
\item Both operations preserve the TP structure of the left factor

$\Rightarrow$ SR structure preserved at every step!

\item We know how to perform both operations accurately (later)

\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$
\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
\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$
\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
\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}
+&\tb+&\tb+&+\\
+&\tb+&\tb+&+\\
\tr 0&\tb+&\tb+&+\\
0&\tb+&\tb+&+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} 1\\ & 1 & \tb + \\ && 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 15}

\begin{itemize}

\item Making more zeros analogous

\end{itemize}

\bigskip
\bigskip

\noindent$
\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
\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}
+&\tb+&\tb+&+\\
+&\tb+&\tb+&+\\
\tr 0&\tb+&\tb+&+\\
0&\tb+&\tb+&+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} 1\\ & 1 & \tb + \\ && 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&+&+&+
\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$
\bmat{cccc} 1\\ & 1\\ &-& 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
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&+&+&+
\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&+&+&+
\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$
\bmat{cccc} 1\\ & 1\\ &-& 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
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&+&+&+
\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+&+&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

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

\begin{itemize}

\item Making more zeros analogous

\end{itemize}

\bigskip
\bigskip

\noindent$
\bmat{cccc} 1\\ & 1\\ &-& 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
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&+&+&+
\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&\tr0&+&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$

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

\begin{itemize}

\item Making more zeros analogous

\end{itemize}

\bigskip
\bigskip

\noindent$
\bmat{cccc} 1\\ & 1\\ &-& 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
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&+&+&+
\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&\tr0&+&+\\
0&0&\tr+&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$
% --------------------------------------------------------
\slide{Similarity Reduction to an Anti-Bidiagonal 20}

\begin{itemize}

\item Making more zeros analogous

\end{itemize}

\bigskip
\bigskip

\noindent$
\bmat{cccc} 1\\ & 1\\ &-& 1\\ && & 1 \emat
\bmat{cccc}
+&+&+&+\\
+&+&+&+\\
+&+&+&+\\
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&+&+&+
\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&\tr0&+
\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$
\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 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
$

% --------------------------------------------------------
\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}
+&+&+&\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 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}
+&+&+&\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 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$
\bmat{cccc} 1  \\ & 1\\ && 1\\ && -  & 1 \emat
\bmat{cccc}
+&+&+&0\\
0&+&+&+\\
0&0&+&+\\
0&0&\tr+&+
\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 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}
\tb +&\tb +&+&0\\
\tb 0&\tb +&+&+\\
\tb 0&\tb 0&+&+\\
\tb 0&\tb 0&\tr 0&+
\emat
\phantom{\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat}
\bmat{cccc} 1 & \tb +  \\ & 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 27}

\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&\tr 0&+
\emat
\bmat{cccc} &&&1\\ &&1 \\ &1 \\ 1 \emat
$


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

\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 29}

\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 30}

\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 31}

\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 32}

\begin{itemize}

\item Finally, symmetrizing

\end{itemize}

\bigskip
\bigskip

$$
\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}
$$

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

\begin{itemize}

\item Finally, symmetrizing

\end{itemize}

\bigskip
\bigskip

$$
\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}\left(
\bmat{ccccc}
&& & b_1 & a_1\\
& & b_2 & a_2\\
 & b_2 & a_3\\
 b_1 & a_2\\
 a_1
\emat\right)
$$

\begin{itemize}

\item The latter is symmetric, thus $|\lambda_i|=\sigma_i$
\item sign $\lambda_i=(-1)^{i-1}$ (from theory)

\item Thus suffices to compute
$$
\mbox{svd}\left(
\bmat{ccccc}
&& & b_1 & a_1\\
& & b_2 & a_2\\
 & b_2 & a_3\\
 b_1 & a_2\\
 a_1
\emat\right)
=
\mbox{svd}\left(
\bmat{ccccc}
a_1 &  b_1 \\
&a_1 &  b_2 \\
&&a_3 &  b_2 \\
&&&a_2 &  b_1 \\
&&&&a_1
\emat\right)
$$
---the latter solved by Demmel and Kahan 1990



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

\slide{Outline}

\item (Almost) any matrix is similar to a \tb{symmetric anti-bidiagonal}

(eig of latter then easy)

$$
\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
$$

\item \tr{Trick: no subtractions in above reduction}

\item We need a structure revealing representation---product of bidiagonals



%-----------------------------------------------------------
\slide{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{Outline}

\item (Almost) any matrix is similar to a \tb{symmetric anti-bidiagonal}

(eig of latter then easy)

$$
\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
$$

\item Trick: no subtractions in above reduction

\item \tr{We need a structure revealing representation---product of bidiagonals}

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

\slide{The Need for a Structure Revealing Representation}

\item Matrix entries are poor choice of parameters

\item An $\varepsilon$ perturbation in $(1,2)$ entry of the SR matrix

\begin{eqnarray*}
\bmat{cc} 1 & 1+ \tr{\varepsilon}\\ 1& 1
\emat & \quad \lambda_1\approx 1, \quad \lambda_2\approx \tr{-\varepsilon}
\\
\\
\downarrow \mbox{~~~~} \\
\\
\bmat{cc} 1 & 1+ \tr{2\varepsilon}\\ 1& 1
\emat & \quad \lambda_1\approx 1, \quad \lambda_2\approx \tr{ -2\varepsilon}
\end{eqnarray*}

results in a 100\% perturbation in $\lambda_2$

\item Better idea: product of bidiagonals

\end{itemize}



%-----------------------------------------------------------
\slide{Bidiagonal Decomposition of Totally Positive Matrices}


{\large

\noindent
$
\bmat{cccc}
\tr 1 & \tr 1 & \tr 1  & \tr 1    \\
\tr 1 & \tr 2 & \tr 4  & \tr 8    \\
\tr 1 & \tr 3 & \tr 9  & \tr {27}   \\
\tr 1 & \tr 4 & \tr {16} & \tr{ 64}
\emat
=
$


\bigskip

\noindent
$
\underbrace{
\bmat{cccc}
1 \\
& 1 \\
&& 1\\
&&\tr 1& 1
\emat
\bmat{cccc}
1 \\
& 1 \\
&\tr 1& 1\\
&&\tr 1& 1
\emat
\bmat{cccc}
1 \\
\tr 1& 1 \\
& \tr 1& 1\\
&& \tr 1 & 1
\emat
}_{\mbox{\Large $L$}}
\underbrace{
\bmat{cccc}
\tr 1 \\
& \tr 1 \\
& & \tr 2 \\
&&  & \tr 6
\emat
}_{\mbox{\Large $D$}}
\underbrace{
\bmat{cccc}
1 & \tr 1 \\
& 1 & \tr 2\\
& & 1 & \tr 3\\
&&  & 1
\emat
\bmat{cccc}
1 \\
& 1 & \tr 1\\
& & 1 & \tr 2\\
&&  & 1
\emat\bmat{cccc}
1 \\
& 1 \\
& & 1 & \tr 1\\
&&  & 1
\emat
}_{\mbox{\Large $U$}}
$

\bigskip
\bigskip


{\LARGE
\begin{itemize}


\item Any TP matrix
\end{itemize}
}


\noindent
$
\bmat{cccc}
\tr {a_{11}} & \tr {a_{12}} & \tr {a_{13}}  & \tr {a_{14}}    \\
\tr {a_{21}} & \tr {a_{22}} & \tr {a_{23}}  & \tr {a_{24}}    \\
\tr {a_{31}} & \tr {a_{32}} & \tr {a_{43}}  & \tr {a_{34}}    \\
\tr {a_{41}} & \tr {a_{42}} & \tr {a_{43}}  & \tr {a_{44}}
\emat
=
$


\bigskip

\noindent
$
\underbrace{
\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
}_{\mbox{\Large $L$}}
\underbrace{
\bmat{cccc}
\tr {\!b_{11}}\!\!\! \\
& \tr {\!b_{22}}\!\!\! \\
& & \tr {\!b_{33}}\!\!\! \\
&&  & \tr {\!b_{44}}\!\!\!
\emat
}_{\mbox{\Large $D$}}
\underbrace{
\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
}_{\mbox{\Large $U$}}
$



}


{\LARGE
\begin{itemize}


\item $\tr{b_{ij}}=$ multiplier used to make zero in position $(i,j)$
\end{itemize}
}



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

\slide{Representation of Sign Regular Matrices}

{\large

\noindent
$
\bmat{cccc}
\tb {c_{11}} & \tb {c_{12}} & \tb {c_{13}}  & \tb {c_{14}}    \\
\tb {c_{21}} & \tb {c_{22}} & \tb {c_{23}}  & \tb {c_{24}}    \\
\tb {c_{31}} & \tb {c_{32}} & \tb {c_{43}}  & \tb {c_{34}}    \\
\tb {c_{41}} & \tb {c_{42}} & \tb {c_{43}}  & \tb {c_{44}}
\emat
=
$

\bigskip

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


\bigskip

\noindent
$
\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
}
$
}

\vskip0.3in
\begin{itemize}

\item Any $\tr{b_{ij}}>0$ yield a SR matrix $\Rightarrow$
SR $=$ octant in $n^2$ space

\item For most famous SR matrices, $\tr{b_{ij}}$ computable accurately
\item We choose $\tr{b_{ij}}$ as inputs:

  \begin{itemize}
  \item $\tr{b_{ij}}$ reveal SR structure
  \item $\tr{b_{ij}}$ determine $\lambda_i$ accurately




  \end{itemize}

\end{itemize}

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

\slide{Representation of Sign Regular Matrices}

{\large

\noindent
$
\bmat{cccc}
\tb {c_{11}} & \tb {c_{12}} & \tb {c_{13}}  & \tb {c_{14}}    \\
\tb {c_{21}} & \tb {c_{22}} & \tb {c_{23}}  & \tb {c_{24}}    \\
\tb {c_{31}} & \tb {c_{32}} & \tb {c_{43}}  & \tb {c_{34}}    \\
\tb {c_{41}} & \tb {c_{42}} & \tb {c_{43}}  & \tb {c_{44}}
\emat
=
$

\bigskip

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


\bigskip

\noindent
$
\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
}
$
}

\vskip0.3in
\begin{itemize}

\item Any $\tr{b_{ij}}>0$ yield a SR matrix $\Rightarrow$
SR $=$ octant in $n^2$ space

\item For most famous SR matrices, $\tr{b_{ij}}$ computable accurately
\item We choose $\tr{b_{ij}}$ as inputs:

  \begin{itemize}
  \item $\tr{b_{ij}}$ reveal SR structure
  \item $\tr{b_{ij}}$ determine $\lambda_i$ accurately




  \end{itemize}

\end{itemize}

\medskip
\centerline{\tb{Rationale: $\hat \lambda_i$, as rational functions
of $b_{ij}$, likely contain no subtractions}}

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

\slide{How we avoid subtractions}

\begin{itemize}
\item Recall: We only need to apply 2 operations to TP:
\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 \\
& 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
$$
}

\end{itemize}












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


\begin{itemize}
\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

\centerline{\huge Other work}
\item
Eliptic
PDEs with tetrahedral finite elements (with Demmel and Vavasis)

\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}

