\documentstyle[12pt]{article}
\pagestyle{empty}
\textwidth11cm
\textheight22cm
\parindent0cm
\parskip0.2cm plus0.1cm minus0.05cm
\begin{document}
\begin{center}
{\large \bf
%Please insert here the title of your contribution!
Stability of the Bruhat Decomposition
}
\bigskip
%Please insert here the address(es) of the author(s)!
%\begin{center}
{\bf Omar Odeh}
Department of Computer Science
University of Victoria
oodeh@gulf.uvic.ca
\end{center}
\bigskip
%Please insert here the abstract!
For any nonsingular
matrix $A$, there exists a decomposition
$A=VPU$, where $P$ is a unique permutation matrix and $V$ ,$U$ are
lower triangular and $U$ (resp.$ V$) is normalized, such a decomposition is
called the left (resp. right) Bruhat decomposition of A.
The numerical stability of an algorithm computing a matrix factorization depends on the
growth of elements in the derived matrices. For example, for Gaussian elimination with partial
pivoting (GEPP), the growth of elements in the derived matrices is measured using the growth factor
is exponential in n) for the matrices given by Wilkinson and recently (from a practical
application) by Foster. We show that the left Bruhat decomposition gives at most linear growth
in n for these matrices demonstrating its stability.
Furthermore, we specify a partial pivoting strategy for the Bruhat decomposition and
determine simple relationships between the derived matrices, permutation matrices and the matrices
of multipliers associated with this algorithm (applied to matrix $A$) and,
where $r$ is the permutation matrix that reverses the order
of the columns of $A$).
All real matrices that give the maximum exponential growth factor
with GEPP were characterized by Higham and Higham.
These matrices and the matrix of Foster are
a rank one perturbation of an upper triangular matrix.
We show that the Bruhat decomposition with partial pivoting applied to a nonsingular
$n \times n$
matrix that is a rank one perturbation of an upper triangular matrix
gives a linear growth factor less than or equal to $2(n-1)$.
Thus Bruhat decomposition
with partial pivoting is stable for matrices that give the maximum exponential growth factor with
GEPP as well as the matrix of Foster. For cases in which GEPP is unstable, a stable alternative
could be application of Bruhat decomposition with partial pivoting to A.
\end{document}