Stability of the Bruhat Decomposition

Omar Odeh

Department of Computer Science

University of Victoria

oodeh@gulf.uvic.ca

For any nonsingular matrix A, there exists a decomposition A = V P U, 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 × 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.