Math 6610 • Analysis of Numerical Methods I

(Properties of Gaussian Elimination). Show that for Gaussian elimination with partial pivoting applied to any matrix \(B \in \mathbb {C}^{n \times n}\), the growth factor \(\rho \) satisfies \(\rho \le 2^{n-1}\). Recall that the growth factor is defined as, \[ \rho = \frac {\max _{i,j}|u_{ij}|}{\max _{i,j}|b_{ij}|}, \] where \(u_{i,j}\) are the entries of the upper triangular matrix that results from performing Gaussian elimination on \(B\).