On growth in Gaussian elimination with complete pivoting

Abstract. It has been conjectured that when Gaussian elimination with complete pivoting is applied to a real n-by-n matrix, the maximum possible growth is n. In this note, a 13-by-13 matrix is given, for which the growth is 13.0205. The matrix was constructed by solving a large nonlinear programming problem. Growth larger than n has also been observed for matrices of orders 14, 15, and 16. Key words. Gaussian elimination, growth, complete pivoting, nonlinear programming methods AMS(MOS) subject classifications. 65F05, 65G05 1. Introduction. Let A be an n-by-n real matrix, let A() A, and let A(k+), for k 1, n 1, be the n k-by-n k matrix derived from A by elimination operations. That is, if we partition Ak) as (1.1) A) = (a) A(k