Condition Numbers of Random Triangular Matrices

Abstract

Let Ln be a lower triangular matrix of dimension n each of whose nonzero entries is an independent N(0, 1) variable, i.e., a random normal variable of mean 0 and variance 1. It is shown that kappa(n), the 2-norm condition number of L-n, satisfies n root kappa(n) --> 2 almost surely as n --> infinity. This exponential growth of kappa(n) with n is in striking contrast to the linear growth of the condition numbers of random dense matrices with n that is already known. This phenomenon is not due to small entries on the diagonal (i.e., small eigenvalues) of Ln. Indeed, it is shown that a lower triangular matrix of dimension n whose diagonal entries are fixed at 1 with the subdiagonal entries taken as independent N(0, 1) variables is also exponentially ill conditioned with the 2-norm condition number kappa(n) of such a matrix satisfying n root kappa(n) --> 1.305683410... almost surely as n --> infinity. A similar pair of results about complex random triangular matrices is established. The results for real triangular matrices are generalized to triangular matrices with entries from any symmetric, strictly stable distribution.