Condition Numbers of Random Triangular Matrices

Abstract

\begin{abstract} Let $L_n$ be a lower triangular matrix of dimension $n$ each of whose nonzero entries is an independent $N(0,1)$ variable, \ie, a random normal variable of mean $0$ and variance $1$. It is shown that $\kn$, the 2-norm condition number of $L_n$, satisfies \begin{equation*} \sqrt[n]{\kn} \rightarrow 2 \:\:\: \text{\it almost surely} \end{equation*} as $n\rightarrow\infty$. This exponential growth of $\kn$ with $n$ is in striking contrast to the linear growth of the condition numbers of random {\it dense} matrices with $n$ that is already known. This phenomenon is not due to small entries on the diagonal (\ie, small eigenvalues) of $L_n$. 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 $\kn$ of such a matrix satisfying \begin{equation*} \sqrt[n]{\kn}\rightarrow 1.305683410\ldots \:\:\:\text{\it almost surely} \end{equation*} as $n\rightarrow\infty$. 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. \end{abstract}