Condition Numbers of Random Triangular Matrices.
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 kn, the 2-norm condition number of Ln, 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 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 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.
Introduction
Random dense matrices are well-conditioned. If each of the n 2 entries of a
matrix of dimension n is an independent N(0; 1) variable, Edelman has shown
This work was supported by NSF Grant DMS-9500975CS and DOE Grant DE-FG02-
y Department of Computer Science, Cornell University, Ithaca, NY 14853 (diva-
kar@cs.cornell.edu and lnt@cs.cornell.edu)

Figure

1: Empirical cumulative density functions of n
-n , for triangular and
unit triangular matrices respectively, with obtained from 1000
random matrices for each n. The random entries are N(0; 1) variables. The
higher values of n correspond to the steeper curves. In the limit n ! 1, the
cdfs converge to Heaviside step functions with jumps at the dashed lines.
that the probability density function (pdf) of -n=n, where -n is the 2-norm
condition number of such a matrix, converges pointwise to the function
as the distribution of -n=n is independent of n in the limit
1, we can say that the condition numbers of random dense matrices
grow only linearly with n. Using this pdf, it can be shown, for example, that
E(log(-n
In striking contrast, the condition number of a random lower triangular
matrix Ln , a matrix of dimension n all of whose diagonal and subdiagonal
entries are independent N(0; 1) variables, grows exponentially with n. If -n is
the 2-norm condition number of Ln (defined as kLn k
show that
almost surely
as n !1 (Theorem 4.3). Figure 1a illustrates this result.
The matrices that arise in the experiments reported in Figure 1 are so ill-conditioned
that the standard method of finding the condition number using
the SVD [10] fails owing to rounding errors. A numerically stable approach for
computing the condition number, which was used to generate the figures, is to
find the inverse of the triangular matrix explicitly using the standard algorithm
for triangular inversion, and then find the norms of the matrix and its inverse
independently.
The exponential growth of -n with n is not due to small entries on the
diagonal since the probability of a diagonal entry being exponentially small is
also exponentially small. For a further demonstration that the diagonal entries
do not cause the exponential growth in -n , we consider condition numbers of
unit triangular matrices, i.e., triangular matrices with ones on the diagonal. If
-n is the condition number of a unit lower triangular matrix of dimension n
with subdiagonal entries taken as independent N(0; 1) variables, then
almost surely
as n !1 (Theorem 5.3). Obviously, in this case the ill-conditioning has nothing
to do with the diagonal entries (i.e., the eigenvalues) since they are all equal
to 1. Section 7 discusses the relationship of the exponential ill-conditioning of
random unit triangular matrices to the stability of Gaussian elimination with
partial pivoting.
We will use Ln to refer to triangular matrices of various kinds - real or
complex, with or without a unit diagonal. But Ln always denotes a lower
triangular matrix of dimension n. If the entries of Ln are random variables, they
are assumed to be independent. Thus, if we merely say that Ln has entries from
a certain distribution, those entries are not only identically distributed but also
independent. Of course, only the nonzero entries of Ln are chosen according to
that distribution. The condition number always refers to the 2-norm condition
number. However, all our results concerning the limits lim n!1 n
-n apply to
all the L p norms, and the L p norms
differ by at most a factor of n. The 2-norm condition number of Ln , defined as
denoted by -n . The context will make clear the distribution
of the entries of Ln .
The analyses and discussions in this paper are phrased for lower, not upper,
triangular matrices. However, all the theorems are true for upper triangular
matrices as well, as is obvious from the fact that a matrix and its transpose
have the same condition number.
We obtain similar results for triangular matrices with entries chosen from
the complex normal distribution ~
we denote the complex
normal distribution of mean 0 and variance oe 2 obtained by taking the real and
imaginary parts as independent N(0; oe 2 =2) variables. Let Ln denote a triangular
matrix with ~
almost surely
as
normal entries tend to have smaller condition numbers than triangular matrices
with real normally distributed entries.
Similarly, let Ln denote a unit lower triangular matrix with ~
subdiagonal
entries. Then,
almost surely
as (Theorem 7.4). Thus, unit triangular matrices with complex normal
entries tend to have slightly bigger condition numbers than unit triangular
matrices with real normal entries.
Our results are similar in spirit to results obtained by Silverstein for random
dense matrices [14]. Consider a matrix of dimension n \Theta (yn), where y 2 [0; 1],
each of whose n 2 y entries is an independent N(0; 1) variable. Denote its largest
and smallest singular values by oe max and oe min , respectively. It is shown in [14]
that
oe
y almost surely
as 1. The complex analogues of these results can be found in [4]. The
technique used in [14] is a beautiful combination of what is now known as the
Golub-Kahan bidiagonalization step in computing the singular value decomposition
with the Gerschgorin circle theorem and the Mar-cenko-Pastur semicircle
law. The techniques used in this paper are more direct.
The exponential growth of
is due to the second factor.
We outline the approach for determining the rate of exponential growth of -n
by assuming Ln triangular with N(0; 1) entries. In Section 2, we derive the joint
probability density function for the entries in any column of L \Gamma1
(Proposition
2.1). If T k is the 2-norm of column
, i.e., the column with
nonzero entries, both positive and negative moments of T k are explicitly derived
in Section 3 (Lemma 3.2). These moments allow us to deduce that n
converges to 2 almost surely (Theorem 4.3). A similar approach is used to determine
the limit of n
with ~
(Theorems 5.3,
7.3, and 7.4 respectively).
The same approach is used more generally to determine the limit of n
as n !1 for Ln with entries drawn from any symmetric, strictly stable distribution
(Theorems 8.3 and 8.5). These theorems are specialized to the Cauchy
distribution, which is symmetric and strictly stable, in Theorems 8.4 and 8.6.
2 Inverse of a Random Triangular Matrix
Consider the matrix
ff 11
\Gammaff 21 ff 22
\Gammaff n1 \Gammaff
where each ff ij is an independent N(0; 1) variable. Consider L \Gamma1
n , and denote
the first k entries in the first column of L \Gamma1
. The t i satisfy the
(a) (b)

Figure

2: Entries of L \Gamma1
n on the same solid line in (a) have the same pdf. Sets
of entries of L \Gamma1
n in the boxes in (b) have the same jpdf.
following relations:
This system of equations can be interpreted as a system of random recurrence
relations. The first entry t 1 is the reciprocal of an N(0; 1) variable. The kth
entry t k is obtained by summing the previous entries t independent
as coefficients, and dividing that sum by an independent
Next, consider an arbitrary column of L \Gamma1
n and denote the first k entries of
that column from the diagonal downwards by t . The entries t i satisfy
random recurrence relations similar in form to (2.1), but the ff ij are a different
block of entries in Ln for different columns. For example, any diagonal entry of
n is the reciprocal of an N(0; 1) variable; the kth diagonal entry is 1=ff kk .
These observations can be represented pictorially. Every entry of L \Gamma1
n at
a fixed distance from the diagonal has the same probability density function
(pdf). We may say that the matrix L \Gamma1
n , like Ln , is "statistically Toeplitz." See
Figure 2a. Moreover, if we consider the first k entries of a column of L \Gamma1
n from
the diagonal downwards, those k entries will have the same joint probability
density function (jpdf) irrespective of the column. See Figure 2b. The different
columns of L \Gamma1
, however, are by no means independent.
Our arguments are stated in terms of the columns of L \Gamma1
n . However, rows
and columns are indistinguishable in this problem; we could equally well have
framed the analysis in terms of rows.
Denote the jpdf of t In the next propo-
sition, a recursive formula for f k is derived. For simplicity, we introduce the
further notation T
k . Throughout this section, Ln is the random
triangular matrix of dimension n with N(0; 1) entries.
Proposition 2.1. The jpdf f the following recurrence:
f
Proof. The t k are defined by the random recurrence in (2.1).
The expression for f 1 is easy to get. If x is an N(0; 1) variable, its pdf isp
The change of variable
To obtain the recursive expression (2.3) for f k , consider the variable - k obtained
by summing the variables t
are independent
variables. For fixed values of t the variable
being a sum of random normal variables, is itself a random normal variable
of mean 0 and variance T 2
. Therefore, the jpdf of - k and t
By (2.1), the variable t k can be obtained as - k =ff, where ff is an independent
variable. The jpdf of ff, - k and t
Changing the variable - k to t integrating out ff, we obtain
i.e., f k is given by (2.3).
Note that the form of the recurrence for f k in Proposition 2.1 mirrors the
random recurrence (2.1) for obtaining t k from the previous entries t
In the following corollary, an explicit expression for f k in terms of the t i is
stated.
Corollary 2.2. For k ? 1, the jpdf f
3 Moments of T k
In this section and the next, Ln continues to represent a triangular matrix
of dimension n with N(0; 1) entries. As we remarked earlier, the exponential
growth of
is due to the second factor kL \Gamma1
. Since the
2-norm of column
n has the same distribution as Tn\Gammai , we derive
formulas for various moments of T k with the intention of understanding the
exponential growth of kL \Gamma1
In the lemma below, we consider the expected value E(T -
positive
and negative values of -. By our notation, j. The notation
is used to reduce clutter in the proof. As usual, R k denotes the real
Euclidean space of dimension k.
The next lemma is stated as a recurrence to reflect the structure of its proof.
Lemma 3.2 contains the same information in a simpler form.
Lemma 3.1. For any real - ! 1, E(T -
k ) is given by the following recurrence:
E(T -
E(T -
E(T -
dx
For
k ) is infinite.
Proof. To obtain (3.1), use T and the pdf of t 1 given by Equation (2.2).
It is easily seen that the integral is convergent if and only if - ! 1.
Next, assume k ? 1. By definition,
E(T -
Z
Using the recursive equation (2.3) for f k , and writing T k in terms of t k and
E(T -
Z
Z
R
By the substitution t the inner integral with respect to dt k can be
reduced to
dx
Inserting this in the multiple integral (3.3) gives the recursive equation (3.2) for
E(T -
k ). It is easily seen that the integral in (3.2) is convergent if and only if
dx
Beginning with the substitution in (3.4), it can be shown that
is the beta function. The relevant expression for
the beta function B(x; y) is Equation (6.2.1) in [1]. Also, if x is chosen from
the standard Cauchy distribution, then We do not need
in terms of the beta function, however; the integral expression (3.4) suffices
for our purposes. Lemma 3.1 can be restated in a more convenient form using
Lemma 3.2. For
- for a finite positive constant C - . Also,
Proof. The expression for E(T -
k ) is a restatement of Lemma 3.1. By elementary
and by the form of the integral in (3.4),
and
Lemma 3.2 implies that the positive moments of T k grow exponentially with
k while the negative moments decrease exponentially with k.
Obtaining bounds for P now a simple matter.
Lemma 3.3. For
Proof.
\Gamma- to obtain an expression for E(T \Gamma-
apply Markov's inequality
[2].
Lemma 3.4. For k - 1,
Proof. As in Lemma 3.3, - ? 0 implies that P
Again, the proof can be completed by obtaining an expression for E(T -
using
Lemma 3.2 followed by an application of Markov's inequality.
4 Exponential Growth of - n
We are now prepared to derive the first main result of the paper, namely, n
almost surely as entries. In
the sequel, a.s. means almost surely as n ! 1. The definition of almost sure
convergence for a sequence of random variables can be found in most textbooks
on probability, for example [2]. Roughly, it means that the convergence holds
for a set of sequences of measure 1.
Lemma 4.1. kLnk 1=n
almost surely as n !1.
Proof. The proof is easy. We provide only an outline. The Frobenius norm of
F , is a sum of n(n variables of mean 1. By the
strong law of large numbers,
F
The proof can be completed using the inequalities n \Gamma1=2 kLnkF - kLn k 2 -
kLn
The proof of Lemma 4.2 is very similar to the proofs of several standard
results in probability, for example the strong law of large numbers [2, p. 80].
Lemma 4.2. As n !1, for any 0
almost surely.
Proof. By Lemma 4.1, it suffices to show that
a:s:
We consider the lower bound first. The 2-norm of the first column of L \Gamma1
n , which
has the same distribution as Tn , is less than or equal to kL \Gamma1
. Therefore, for
Using Lemma 3.3 with
\Gamma-
where
\Gamma- (fl \Gamma1=-
ffl is finite. The first
lemma [2] can be applied to obtain
infinitely often as n
Taking the union of the sets in the above equation over all rational ffl in (0; 1)
and considering the complement of that union, we obtain
\Gamma- as n
In other words, fl \Gamma1=-
a.s.
The upper bound can be established similarly. At least one of the columns of
must have 2-norm greater than or equal to n \Gamma1=2 kL \Gamma1
. Since the 2-norm
of column k + 1 has the same distribution as Tn\Gammak ,
Bounding each term in the summation using Lemma 3.4 gives
Lemma 3.2, the largest term in the summand occurs when
From this point, the proof can be completed in the same manner as the proof
of the lower bound.
Theorem 4.3. For random triangular matrices with N(0; 1) entries, as
almost surely.
Proof. By an inequality sometimes called Lyapunov's [11, p. 144] [2],
ff
for any real fi ! ff. Thus the bounding intervals [fl \Gamma1=-
shrink as - decreases from 1 to 0. A classical theorem [11, p. 139] says that
these intervals actually shrink to the following point:
lim
dx
The exact value of the limit can be evaluated to 2 using the substitution
tan ' followed by complex integration [3, p. 121]. Thus n
Theorem 4.3 holds in exactly the same form if the nonzero entries of Ln are
independent N(0; oe 2 ) variables rather than N(0; 1) variables, since the condition
number is invariant under scaling.
Our approach to Theorem 4.3 began by showing that E(T -
- for
both positive and negative -. Once these expressions for the moments of T k
were obtained, our arguments did not depend in an essential way on how the
recurrence was computed. The following note summarizes the asymptotic information
about a recurrence that can be obtained from a knowledge of its
moments.
be a sequence of random variables. If E(jt exponentially
with n at the rate - n
almost surely as
Similarly, if E(jt exponentially with n at the rate - n
- as
almost surely as n !1. Thus, knowledge
of any positive moment of t n yields an upper bound on n
knowledge of any negative moment yields a lower bound.
5 Unit Triangular Matrices
So far, we have considered triangular matrices whose nonzero entries are inde-
pendent, real N(0; 1) variables. In this section and in Section 7, we establish the
exponential growth of the condition number for other kinds of random triangular
matrices with normally distributed entries. The key steps in the sequence of
lemmas leading to the analogs of Theorem 4.3 are stated but not proved. The
same techniques used in Sections 2, 3 and 4 work here too.
Let Ln be a unit lower triangular matrix of dimension n with N(0; oe 2 ) subdiagonal
entries. Let s be the first k entries from the diagonal downwards
of any column of L \Gamma1
n . The entries s i satisfy the recurrence
are N(0; oe 2 ) variables. The notation S
is used below.
Proposition 5.1. The jpdf of s by the recur-
rence
exp(\Gammas 2
exp(\Gammas 2
and the fact that s
Lemma 5.2. For any real -, E(S -
The note at the end of Section 4 provides part of the link from Lemma 5.2
to the following theorem about -n .
Theorem 5.3. For random unit triangular matrices with N(0; oe 2 ) entries, as
almost surely.
If this limit is denoted by C(oe), then
being the Euler constant.
Proof. The constant K is given by
r-
To evaluate K, we used integral 4:333 of [8].
In contrast to the situation in Theorem 4.3, the constant that n
to in Theorem 5.3 depends on oe. This is because changing oe scales only the
subdiagonal entries of the unit triangular matrix Ln while leaving the diagonal
entries fixed at one. For the case discussed in the Introduction, numerical
integration shows that the constant is
6 A Comment on the Stability of Gaussian
Elimination
The conditioning of random unit triangular matrices has a connection with the
phenomenon of numerical stability of Gaussian elimination. We pause briefly
to explain this connection.
For decades, the standard algorithm for solving general systems of linear
equations has been Gaussian elimination (with "partial" or row pivot-
ing). This algorithm generates an "LU factorization"
permutation matrix, L is unit lower triangular with subdiagonal entries - 1 in
absolute value, and U is upper triangular.
In the mid-1940s it was predicted by Hotelling [12] and von Neumann [9]
that rounding errors must accumulate exponentially in elimination algorithms
of this kind, causing instability for all but small dimensions. In the 1950s,
Wilkinson developed a beautiful theory based on backward error analysis that,
while it explained a great deal about Gaussian elimination, confirmed that for
certain matrices, exponential instability does indeed occur [17]. He showed that
amplification of rounding errors by factors on the order of kL may take place,
and that for certain matrices, kL \Gamma1 k is of order 2 n . Thus for certain matrices,
rounding errors are amplified by O(2 n ), causing a catastrophic loss of n bits of
precision.
Despite these facts, the experience of fifty years of computing has established
that from a practical point of view, Hotelling and von Neumann were wrong:
Gaussian elimination is overwhelmingly stable. In fact, it is not clear that a
single matrix problem has ever led to an instability in this algorithm, except for
the ones produced by numerical analysts with that end in mind, although Foster
and Wright [18] have devised problems leading to instability that plausibly
"might have arisen" in applications. The reason appears to be statistical: the
matrices A for which kL \Gamma1 k is large occupy an exponentially small proportion of
the space of all matrices, so small that such matrices "never" arise in practice.
Experimental evidence of this phenomenon is presented in [16].
This raises the question, why are matrices A for which kL \Gamma1 k is large so
rare? It is here that the behavior of random unit triangular matrices is rele-
vant. A natural hypothesis would be that the matrices L generated by Gaussian
elimination are, to a reasonable approximation, random unit triangular matrices
with off-diagonal entries of a size dependent on the dimension n. If such
matrices could be shown to be almost always well-conditioned, then the stability
of Gaussian elimination would be explained.
We have just shown, however, that unit triangular matrices are exponentially
ill-conditioned. Thus this attempted explanation of the stability of Gaussian
elimination fails, and indeed, the same argument suggests that Gaussian
elimination should be unstable in practice as well as in the worst case. The
resolution of this apparent paradox is that the matrices L produced by Gaussian
elimination are far from random. The signs of the entries of these matrices are
correlated in special ways that have the effect of keeping kL almost always
very small. For example, it is reported in [16] that a certain random matrix A
with led to kL
was taken to be the same matrix
but with the signs of its subdiagonal entries randomized, the result became
From a comparison of Theorem 5.3 with half a century of the history of
Gaussian elimination, then, one may conclude that unit triangular factors of
random dense matrices are very different from random unit triangular matrices.
An explanation of this difference is offered in [15] along the following lines. If
A is random, then its column spaces are randomly oriented in n-space. This
implies that the same holds approximately for the column spaces of L. That
condition, in turn, implies that large values kL \Gamma1 k can arise only exponentially
rarely.
7 Complex Matrices
We now consider matrices with complex entries. Let Ln be a lower triangular
matrix with ~
entries. The complex distribution ~
defined in
the

Introduction

. Let t denote the first k entries from the diagonal
downwards of any column of L \Gamma1
n . The quantities t k satisfy (2.1), but the ff ij
are now independent ~
by R k .
Proposition 7.1. The jpdf of r by the recur-
rence
r 2; (7.1)
h
for
Proof. We sketch only the details that do not arise in the proof of Proposition
2.1. If x and y are independent N(0; oe 2 ) variables,
r cos(') and
r sin('), then r and ' are independent. Moreover, the distribution of r is
Poisson with the pdf
Consider the sum - taken as independent
~
variables. For fixed are independent.
To see their independence, we write out the equations for Re(- k ) and Im(- k ) as
follows:
Re(ff ki
Re(ff ki )Im(t
The linear combinations of Re(ff ki ) and Im(ff ki ) in these two equations can be
realized by taking inner products with the two vectors
The independence of Re(- k ) and Im(- k ) is a consequence of the orthogonality
of v and w, i.e., (v; and the invariance of the jpdf of independent,
identically distributed normal variables under orthogonal transformation [13].
Thus for fixed t the real and imaginary parts of - k are independent
normal variables of mean 0 and variance R k\Gamma1 =2. By Equation (7.3), the pdfs
of are given byR
exp(\Gammax=R
for positive x; y. The expression (7.2) for h k can now be obtained using r
Lemma 7.2. For any - ! 1, E(R -
r 2\Gamma-
Z 1dx
The constant - in Lemma 7.2 can be reduced to
ever, as with fl - in Section 3, the integral expression for - is more convenient
for our purposes. As before, the note at the end of Section 4 is an essential part
of the link from the previous lemma to the following theorem about -n .
Theorem 7.3. For random triangular matrices with complex ~
as n !1,
almost surely:
Theorem 7.3 holds unchanged if the entries are ~
As with
Theorem 4.3, this is because the condition number is invariant under scaling.
let Ln be a unit lower triangular matrix of dimension n with ~
subdiagonal entries. We state only the final theorem about -n .
Theorem 7.4. For random unit triangular matrices with complex ~
tries, as n !1,
almost surely,
where Ei is the exponential integral. If this limit is denoted by C(oe), then
being the Euler constant.
Proof. To obtain K, we evaluated
using the Laplace transform of log(x) given by integral 4.331.1 of [8]. The
explicit formula involving Ei(oe \Gamma2 ) was obtained using integral 4.337.2 of [8].
For
-n converges to
8 Matrices with Entries from Stable Distribution

The techniques used to deduce Theorem 4.3 require that we first derive the
joint density function of the t k , defined by recurrence (2.1), as was done in
Proposition 2.1. That proposition made use of the fact that when the ff ki are
independent and normally distributed, and the t i are fixed, the sum
is also normally distributed. This property of the normal distribution holds for
any stable distribution.
A distribution is said to be stable, if for X i chosen independently from that
distribution,
has the same distribution as c n X has the same distribution as
are constants [6, p. 170]. If the distribution
is said to be strictly stable. As usual, the distribution is symmetric if X has
the same distribution as \GammaX . A symmetric, strictly stable distribution has
exponent a if c standard result of probability theory says that any
stable distribution has an exponent 0 ! a - 2. The normal distribution is stable
with exponent
The techniques used for triangular matrices with normal entries work more
generally when the entries are drawn from a symmetric, strictly stable distri-
bution. Let Ln be a unit lower triangular matrix with entries chosen from a
symmetric, strictly stable distribution. Denote the pdf of that stable distribution
by OE(x). The recurrence for the entries s i of the inverse L \Gamma1
n is given by
(5.1), but ff ki are now independent random variables with the density
function OE(x).
The proposition, the lemma and the theorem below are analogs of Proposition
5.1, Lemma 5.2, and Theorem 5.3 respectively. If the exponent of the
stable distribution is a, denote (js 1 j a
Proposition 8.1. If OE(x) is the density function of a symmetric, strictly stable
distribution with exponent a, the jpdf of s
the recurrence
and the fact that s
Proof. The proof is very similar to the proof of Proposition 2.1. We note that
if ff ki are independent random variables with the pdf OE(x), and the s i
are fixed, then the sum
has the pdf OE(x=S pg. 171].
Lemma 8.2. For any real -, E(S -
Theorem 8.3. For random unit triangular matrices with entries from a sym-
metric, strictly stable distribution with density function OE(x) and exponent a, as
a
almost surely:
Theorem 5.3 is a special case of Theorem 8.3 when OE(x) is the density function
for the symmetric, strictly stable distribution N(0; oe 2 ). Another notable
symmetric, strictly stable distribution is the Cauchy distribution with the density
function
The exponent a for the Cauchy distribution is 1 [6]. Using Theorem 8.3 we
obtain,
Theorem 8.4. For random unit triangular matrices with entries from the standard
Cauchy distribution, as n !1,
almost surely.
Numerical integration shows the constant to be
A similar generalization can be made for triangular matrices without a unit
diagonal. However, the analog of Theorem 8.3 for such matrices involves not
OE(x), but the density function /(x) of the quotient obtained by taking
z as independent variables with the pdf OE. The distribution / can be difficult
to compute and work with.
let Ln be a triangular matrix with entries chosen from a symmetric,
strictly stable distribution with the density function OE(x). We state only the
final theorem about -n .
Theorem 8.5. For random triangular matrices with entries from a symmetric,
strictly stable distribution with density function OE(x) and exponent a, as n !1,
a
almost surely,
where /(x) is the density function of the quotient of two independent variables
with the density function OE(x).
Theorem 4.3 is a special case of Theorem 8.5 when OE(x) is the density function
of the distribution N(0; oe 2 ). The /(x) corresponding to N(0; oe 2 ) is the
standard Cauchy distribution. To apply Theorem 8.5 for the Cauchy distribu-
tion, we note that
log jxj
is the density function of the quotient if the numerator and the denominator
are independent Cauchy variables. Therefore, Theorem 8.5 implies
Theorem 8.6. For random triangular matrices with entries from the standard
Cauchy distribution, as n !1,
almost surely.
The constant of convergence in Theorem 8.6 is
9

Summary

Below is a summary of the exponential growth factors lim n!1 n
-n that we
have established for triangular matrices with normal entries:
Real triangular 2 Theorem 4.3
Real unit triangu-
lar, Theorem 5.3
Complex triangular e Theorem 7.3
Complex unit trian-
gular, Theorem 7.4
The theorems about unit triangular matrices with normally distributed, real
or complex entries apply for any variance oe 2 , not just oe
of convergence for any symmetric, strictly stable distribution were derived in
Theorems 8.3 and 8.5. Those two theorems were specialized to the Cauchy
distribution in Theorems 8.4 and 8.6.
Similar results seem to hold more generally, i.e., even when the entries of
the random triangular matrix are not from a stable distribution. Moreover, the
complete knowledge of moments acheived in Lemma 3.2 and its analogs might be
enough to prove stronger limit theorems than Theorem 4.3 and its analogs. We
will present limit theorems and results about other kinds of random triangular
matrices in a later publication. We will also discuss the connection between
random recurrences and products of random matrices, and the pseudospectra
of infinite random triangular matrices.
We close with two figures that illustrate the first main result of this paper,
namely, for random triangular matrices with N(0; 1) entries, n
almost
surely as n !1 (Theorem 4.3). Figure 3 plots the results of a single run of the
random recurrence (2.1) to 100; 000 steps, confirming the constant 2 to about
two digits. The expense involved in implementing the full recurrence (2.1) for
so many steps would be prohibitive. However, since t k grows at the rate 2 k , we
need include only a fixed number of terms in (2.1) to compute t k to machine
precision. For the figure, we used 200 terms, although half as many would have
been sufficient. Careful scaling was necessary to avoid overflow while computing
this figure.

Figure

4 plots the condition number of a single random triangular matrix
for each dimension from 1 to 200. The exponential trend at the rate 2 n is clear,
but as in Figure 1, the convergence as n !1 is slow.

Acknowledgements

We thank D. Coppersmith, P. Diaconis, H. Kesten, A. Odlyzko, J. Sethna, and
H. Wilf for helpful discussions. We are especially grateful to Prof. Diaconis for
introducing us to stable distributions.

Figure

3: Illustration of Theorem 4.3. After 100; 000 steps of the random recurrence
has settled to within 1% of its limiting value 2. The
implementation is explained in the text.
-n

Figure

4: Another illustration of Theorem 4.3. Each cross is obtained by computing
the condition number -n for one random triangular matrix of dimension
n with N(0; 1) entries. The solid line represents 2 n .



--R

Handbook of Mathematical Func- tions
Probability and Measure
Functions of One Complex Variable
Eigenvalues and Condition Numbers of Random Matrices
Eigenvalues and condition numbers of random matrices
An Introduction to Probability Theory and Its Applications
Gaussian elimination with partial pivoting can fail in practice
Table of Integrals
Numerical inverting of matrices of high order
Matrix Computations

Some new methods in matrix calculation
Random Matrices and the Statistical Theory of Energy Levels
The smallest eigenvalue of a large-dimensional Wishart matrix


Analysis of direct methods of matrix inversion
A collection of problems for which Gaussian elimination with partial pivoting is unstable
--TR

--CTR
R. Barrio , B. Melendo , S. Serrano, On the numerical evaluation of linear recurrences, Journal of Computational and Applied Mathematics, v.150 n.1, p.71-86, January
Kenneth S. Berenhaut , Daniel C. Morton, Second-order bounds for linear recurrences with negative coefficients, Journal of Computational and Applied Mathematics, v.186 n.2, p.504-522, 15 February 2006
exponentially nonnormal matrices;matrix condition numbers;random triangular matrices;strong limit theorems