\documentstyle[11pt]{article}
\newcommand{\r}[1]{(\ref{#1})}
 
\renewcommand{\thefootnote}{\alph{footnote}}
\begin{document}
\setcounter{footnote}{0}
 
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prop}{Proposition}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{cor}{Corollary}[section]
\newtheorem{defn}{Definition}[section]
\newcommand{\proof}{\noindent{\bf Proof }}
 
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
 
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qed}{\hfill\hfill\vbox{\hrule\hbox{\vrule\squarebox
   {.667em}\vrule}\hrule}\smallskip}
 
\newcommand{\ia}{I^{\alpha}}
\newcommand{\Prr}{\mbox{Prob}}
\newcommand{\M}{\tilde{M}}
\newcommand{\A}{\tilde{A}}
\newcommand{\W}{\tilde{W}}
\newcommand{\X}{\tilde{X}}
\newcommand{\G}{\tilde{G}}
\newcommand{\la}{{\lambda}}
\newcommand{\xt}{\tilde{x}}
\newcommand{\K}{\tilde{K}}
\newcommand{\Ka}{{\tilde{\kappa}}}
\newcommand{\ha}{\frac{1}{2}}
\newcommand{\lmax}{{\lambda_{\max}}}
\newcommand{\lmin}{{\lambda_{\min}}}
%\newcommand{\ltmin}{{\tilde{\lambda}}_{\min}}
%\newcommand{\ltmax}{{\tilde{\lambda}}_{\max}}
\newcommand{\lnt}{\frac{\lambda n}{2}}
\newcommand{\lt}{\frac{\lambda}{2}}
\newcommand{\lit}{\frac{\lambda_i}{2}}
\newcommand{\h}{\hbox{\hspace{0.5in}  }}
\newcommand{\ap}{\stackrel{p}{\rightarrow}}
 
\renewcommand{\thefigure}{\arabic{section}.\arabic{figure}}
\renewcommand{\thetable}{\arabic{section}.\arabic{table}}
\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\newcommand{\sect}[1]{\vspace{0.1in}{\section{#1}}
{\setcounter{table}{0}}
{\setcounter{equation}{0}}
{\setcounter{figure}{0}}}
\vspace{0.1in}
 
\title{On the Distribution of a Scaled Condition Number} 
\author{\sl{Alan Edelman*}
\footnotemark[0]
\\ Department of Mathematics \\
University of California \\
Berkeley, California 94720
} 

\date{} 
\maketitle
\footnotetext{\\ Key words and phrases:
condition number, ill-conditioning,
multivariate statistics,  numerical analysis, random matrix \\
$^*$This work was started while the author was a Visiting
Scholar in the Department of Mathematics, MIT, and completed at
CERFACS with the support of the North Atlantic Treaty Organization
under a Grant awarded in 1989.  
}
 
 
\setcounter{footnote}{0}
\renewcommand{\thefootnote}{\arabic{footnote}}
 
\begin{center}{\bf Abstract}\end{center}
 
In this note, we give the exact distribution of a scaled condition
number used by Demmel to model the probability that matrix
inversion is difficult.
Specifically, consider a random matrix $A$ and the scaled 
condition
number $\kappa_D(A)=\|A\|_F \cdot \|A^{-1}\|.$  
Demmel provided bounds for the condition number distribution
when $A$ has real or complex normally distributed elements. 
Here, we give the exact formula.


 
\newpage
 
\setlength{\baselineskip}{20pt}
\sect{Introduction and statement of results }

In \cite{D}, Demmel investigates the probability that
numerical analysis problems are difficult by unifying
the common algebraic and geometric structures underlying
the notion of ill-conditioning.
As an application of his theory, he constructs a probabilistic model
to examine the probability that matrix inversion
is difficult. 
It is our goal in this note to work 
exclusively within
his framework and derive exact distributions for the
condition numbers that he considers. 
This condition number is a measure of difficulty in that
the larger the value of the condition number, the more
``difficult" matrix inversion becomes.
The limitations of the model are discussed in \cite{D}.
We consider it a
rather remarkable accident of mathematics that these
distributions can be written down in a closed form at all. 
Although, as Demmel states, the assumption that matrices
are uniformly distributed spherically is rather strong, 
the mathematics
stands on its own, and indeed might have further applications 
to the ``tubular neighborhoods" that he uses 
and perhaps also in  multivariate statistics.  

The objects of study are a  scaled version $\kappa_D(A) \equiv \|A\|_F \cdot
\|A^{-1}\|$ of the usual condition number, and its distribution when
considering random real and complex
$n$ by $n$
matrices with elements distributed 
uniformly on the sphere $1=\|A\|_F^2=\sum a_{ij}^2.$
Because of the scale invariance of the condition number and
special properties of the normal distribution, it is
equivalent to assume
that the random matrices are generated with independent elements
from a real or complex standard normal distribution.
Demmel concludes that for real matrices
$$
\frac{C(1-1/x)^{n^2-1}}{x} \le \Prr(\kappa_D(A) \ge x) \le
\sum_{k=1}^{n^2} 2  {n^2\choose{k}}\left( \frac{2n}{x} \right)^k,$$
where $C$ is a constant.
For complex matrices, on the other hand, he concludes that
\be
\frac{(1-x^{-1})^{2n^2-2}}{2n^4x^2} \le
\Prr(\kappa_D(A)\ge x) \le \frac{e^2n^5(1+n^2/x)^{2n^2-2}}{x^2},
\ee
and that asymptotically
$$
\Prr(\kappa_D(A) \ge x) = \frac{n(n^2-1)}{x^2}+o(\frac{1}{x^2}),
$$
as $x \rightarrow \infty$ for fixed $n$.
 
In this note, we derive the exact probability distribution
by  combining exact distribution expressions for the
smallest singular values \cite{Ed1,Ed2} of
these random matrices
with equations from \cite{Davis,KS} 
which relate to $\kappa_D$. 
Our results are:
\vspace{0.2in}

\begin{tabular}{|c|} \hline
Probability Densities for $\kappa_D(A)$:  \\ \hline
Real $n$ by $n$ matrices: \\
$\mu x^{1-n^2}(x^2-n)^{\frac{n(n+1)}{2}-2}{}_2F_1 \left(\frac{n}{2}-\frac{1}{2},
\frac{n}{2}+1;\frac{n^2}{2}+\frac{n}{2}-1;-(x^2-n) \right) $ \\
$\mu=\frac{2n \Gamma(\frac{n+1}{2})\Gamma(\frac{n^2}{2})}
           {\sqrt{\pi} \Gamma(\frac{n(n+1)}{2}-1)} $ \\ \hline
Complex $n$ by $n$  matrices: \\
$2n(n^2-1)x^{1-2n^2}(x^2-n)^{n^2-2} $
\\ \hline
\end{tabular}


\vspace{0.2in}
Here ${}_2F_1$ denotes the Gauss hypergeometric function.
Since obviously $\sqrt{n} \le \kappa_D(A)$, these
formulas are valid only for $x \ge \sqrt{n}$.
 
For real matrices,
the formula is cumbersome.
For large $x$ and $n>20$, say, the formula below is quite adequate:
$$ \Prr(\kappa_D(A) \ge x) \approx  n^{3/2}/x, \ \ x \gg \sqrt{n}, n \gg 1. $$
For complex matrices the exact distribution is a simple
expression:  
$$ \Prr(\kappa_D(A) \ge x) =1-(1-n/x^2)^{n^2-1}, \ \  x>\sqrt{n}.$$


For large $n$, the condition numbers
of real and complex matrices  scale like $n^{3/2}$.
To be precise let $\kappa^\prime$ be the random variable
$2 \kappa_D/n^{3/2}$.  Then as $n \rightarrow \infty$,
for real matrices,
\be
\label{Intro1}
\Prr(\kappa^\prime < x) \rightarrow e^{-2/x-2/x^2}.
\ee
For complex matrices,
\be
\label{Intro2}
\Prr(\kappa^\prime < x) \rightarrow e^{-4/x^2}.
\ee
In fact, for large $n$ the Demmel condition number $\kappa_D$
of random uniformly distributed matrices
is roughly $\sqrt{n}/2$ times as big as the ordinary
2-norm condition number $\kappa_2$. To be precise, 
as 
$n \rightarrow \infty$,
$\frac{2}{\sqrt{n}}
\kappa_D/\kappa_2$
converges almost surely to $1$.
Thus for large $n$, $\kappa_D$  truly deserves
to be called a scaled condition number, and the
distribution of $\kappa^\prime$ is the same as the
distribution of $\kappa_2/n$ which we have presented in
\cite{Ed1,Ed2}.  

 
 
 
\sect{The distribution of $\kappa_D$ (real case) }
 
Let $A$ be a real random $n \times n$  matrix with independent and
identically distributed ({\bf iid}) elements from
a standard normal distribution.
The matrix $W=AA^T$ is said to be a Wishart matrix or to have the
Wishart distribution.
Our goal is 
to study the random quantity
$$ \kappa_D(A) = \sqrt{\frac{\sum_{i=1}^n \lambda_i}{ \lambda_n}},$$
where $\lambda_1 \ge \ldots \ge  \lambda_n\ge 0$ are the eigenvalues
of $AA^T$.
Clearly $\kappa_D(A) \ge \sqrt{n}$.
 
Let $f_n$ be the probability density function (pdf) of
$\left( \kappa_D(A) \right)^{-2}=
\lambda_n / \sum_{i=1}^n \lambda_i$, and let $g_n$ be
the pdf of $\lambda_n$.
The distribution function for $\kappa_D(A)$
will be derived from two lemmas
regarding $f_n$ and $g_n$.
 
\begin{lemma}
(Davis) The pdfs $f_n$ and $g_n$ are related by
$$L \left( (1+w)^{\ha n^2-2} f_n \left( \frac{1}{1+w}
\right) \right) (s) = 2\Gamma(n^2/2)e^s s^{-\frac{1}{2}n^2+1}
g_n(2s),$$
where $L$ denotes the Laplace transform.
\end{lemma}
 
This lemma was proved in \cite{Davis}, where the more
general case of $\lambda_j / \sum_{i=1}^n \lambda_i$ is
examined.  These ratios arise in the multivariate
analysis of variance (MANOVA) as described in multivariate
analysis books such as \cite{Anderson}.
 
The density function $g_n$ is known exactly (see \cite{Ed1}
or \cite{Ed2}):
\begin{lemma}
The density of the smallest eigenvalue of a Wishart
matrix is
$$g_n(x)= \frac{n}{\sqrt{2\pi}}\Gamma \left(\frac{n+1}{2}\right)
x^{-1/2}e^{-x n/2}
U(\frac{n-1}{2},-\ha, x/2).$$
When $a>0$ and $b<1$,
the Tricomi function,
$U(a,b,z),$ is the unique  solution to
Kummer's
equation
\be  z\frac{d^2w}{dz^2}+(b-z)\frac{dw}{dz}-aw=0, \label{Kummer} \ee
satisfying $U(a,b,0)=\Gamma(1-b)/\Gamma(1+a-b)$ and
$U(a,b,\infty)=0$.
\end{lemma}
 
Combining Lemma 2.1 and Lemma 2.2, we obtain
 
\begin{theorem}
The density of $\left( \kappa_D(A) \right)^{-2}$ is
$$f_n(x)=
\alpha x^{n^2/2-2}(x^{-1}-n)^{\frac{n(n+1)}{2}-2}
{}_2F_1 \left(\frac{n}{2}-\frac{1}{2},
\frac{n}{2}+1;\frac{n^2}{2}+\frac{n}{2}-1;-(x^{-1}-n) \right),$$
where
$$\alpha=\frac{n \Gamma(\frac{n+1}{2})\Gamma(\frac{n^2}{2})}
           {\sqrt{\pi} \Gamma(\frac{n(n+1)}{2}-1)} $$
and ${}_2F_1$ is the Gauss (hypergeometric) function.
\end{theorem}
 
\proof
According to \cite{GR} (formula 7.522.4$^6$,  p. 850),\footnote{
This formula is incorrect in older editions of \cite{GR}.
%The error can be traced back to \cite{BA}.
We have verified
that  the formula as listed in our edition of \cite{GR} is
indeed correct.}
if $b>0$,
\be
\label{LT}
L \left(w^{b-1}
{}_2F_1(a,a-c+1;b;-w) \right) (s) =
\Gamma(b) s^{a-b}U(a,c,s),
\ee
where ${}_2F_1$ is  the Gauss (hypergeometric) function.

With $a=\frac{n}{2}-\frac{1}{2}$, $b=\frac{n^2}{2}+
\frac{n}{2}-1$, $c=-\frac{1}{2}$, and $d=\frac{n}{2}+1$,
we have from Lemmas 2.1 and 2.2 that
\be
\label{first}
L \left( (1+w)^{\frac{1}{2}n^2-2}
f_n \left( \frac{1}{1+w} \right) \right)
(s) = \alpha e^{s(1-n)}\Gamma(b)s^{a-b}U(a,c,s).
\ee
From \ref{LT} we have
$$
L \left( \alpha w^{b-1}
{}_2F_1(a,d;b;-w) \right)
(s)= \alpha \Gamma(b) s^{a-b}U(a,c,s). $$ 
Using familiar results concerning 
the Laplace transform, we then obtain
\be
\label{second}
L \left( \alpha (w-n+1)^{b-1}
{}_2F_1(a,d;b;-(w-n+1)) \right)
(s)= \alpha e^{s(1-n)} \Gamma(b) s^{a-b}U(a,c,s). 
\ee
Combining \ref{first} and \ref{second}, we obtain
$$
(1+w)^{\frac{1}{2}n^2-2}
f_n \left( \frac{1}{1+w} \right)
=
\alpha (w-n+1)^{b-1} 
{}_2F_1(a,d;b;-(w-n+1)) $$
from which the theorem follows.
\qed

 
 

\begin{cor}
Let $h_n$ ($x \ge \sqrt{n}$)
be the density of $\kappa_D(A)$
for real matrices.
Then
$$h_n(x)=
\mu x^{1-n^2}(x^2-n)^{\frac{n(n+1)}{2}-2}{}_2F_1 \left(\frac{n}{2}-\frac{1}{2},
\frac{n}{2}+1;\frac{n^2}{2}+\frac{n}{2}-1;-(x^2-n) \right),$$
where
$$\mu=\frac{2n \Gamma(\frac{n+1}{2})\Gamma(\frac{n^2}{2})}
           {\sqrt{\pi} \Gamma(\frac{n(n+1)}{2}-1)} $$
and ${}_2F_1$ is the Gauss (hypergeometric) function.
\end{cor}

\proof
This follows from Theorem 2.1 using the standard change of
variable formula for probability densities.

 
\begin{cor}
For fixed $n$,  as $x \rightarrow \infty,$
$$h_n(x) \sim \nu_n x^{-2},$$
where
$$\nu_n = \frac{n\Gamma(\frac{n+1}{2})\Gamma(\frac{n^2}{2})}
{\Gamma(\frac{n^2-1}{2})\Gamma(\frac{n+2}{2})}. $$
For $n>20,$ $\nu_n \approx n^{3/2}$.
\end{cor}
 
\proof
The asymptotic formula for $h_n$ follows from 
15.3.4
and 15.1.20 of \cite{AS}.
 
 
 
\sect{The distribution of $\kappa_D$ (complex case) }
 
The complex case is much easier than the real case, and
the resulting formulas are considerably simpler.
In \cite{Ed2}, we gave a complete derivation of the exact 
density from first principles, but here we will
proceed in an analogous manner to the real case. 
 
Let $A$ be a  complex $n \times n$  matrix with independent and
identically distributed ({\bf iid}) elements from
a complex standard normal distribution. A complex standard
normal distribution can be defined as $u+vi,$
where $u$ and $v$ are independent 
standard normals.
 
The matrix $W=AA^H$ is said to be a complex Wishart matrix or have the
complex Wishart distribution.
Again our goal is to study
the random quantity
$$\kappa_D(A)  =  \sqrt{ \frac{ \sum_{i=1}^n \lambda_i}{\lambda_n}},$$
where $\lambda_1 \ge \ldots \ge  \lambda_n\ge 0$ are the eigenvalues
of the complex Wishart matrix $AA^H$.
As in the real case, $\kappa_D(A) \ge \sqrt{n}$. 
 
Using the same notation as in the real case,
let $f_n$ be the probability density function (pdf) of
$ (\kappa_D(A))^{-2}=
\lambda_n / \sum_{i=1}^n \lambda_i$ and let $g_n$ be
the pdf of $\lambda_n$.
The generalization of Lemma 2.1 for the complex case can be found
in \cite{KS}.
 
\begin{lemma}
(Krishnaiah and  Schuurmann) The pdfs $f_n$ and $g_n$ are related by
$$L \left( (1+w)^{n^2-2} f_n \left( \frac{1}{1+w}
\right) \right) (s) = \Gamma(n^2)e^s s^{1-n^2}
g_n(s).$$
\end{lemma}
 
Again, we have the density function $g_n$ exactly (see \cite{Ed1}
or \cite{Ed2}):
\begin{lemma}
The density of the smallest eigenvalue of a complex Wishart
matrix is
$g_n(x)=ne^{-xn},$
i.e, $n\lmin$ is exponentially distributed.
\end{lemma}
 
 
\begin{theorem}
The density of $\left( \kappa_D(A) \right)^{-2}$ is
$$f_n(x)=n(n^2-1)(1-nx)^{n^2-2}.$$
\end{theorem}
 
\proof
This formula can be derived from the two lemmas, and
the integral formula for the gamma function.
\qed

\begin{cor}
Let $h_n(x)$ ($x \ge \sqrt{n}$)  be the density of the condition number
$\kappa_D(A)$ for complex matrices.  Then
$$h_n(x) = 2n(n^2-1)x^{1-2n^2}(x^2-n)^{n^2-2}.$$
\end{cor}
 
\begin{cor}
The probability distribution of
$\kappa_D$ is
given in the complex case by
$$P(\kappa_D \ge x)=1-(1-n/x^2)^{n^2-1}, \ \  x>\sqrt{n}.$$
\end{cor}
 
The above result allows us to verify 
that indeed
\begin{cor}
For fixed $n$,
as $x \rightarrow \infty$,
$$P(\kappa_D \ge x) \sim n(n^2-1)/x^2.$$
\end{cor}


\clearpage
\newpage
\noindent
{\Large \bf Acknowledgements}

I would like to thank Jim Demmel for the inspiration
for studying this condition number, and Tim Davis 
for the large amount of time he spent 
showing me how to use the
Alliant FX/80 to perform 
random matrix experiments to check this work
on eight processors in parallel. 
Also I wish to thank Nick Trefethen's red pen for
several useful suggestions.  

\vspace{.5in}
 
 
 
 
\def\\{\medskip\noindent\hangindent .3in{}}
\setlength{\baselineskip 11pt}
\frenchspacing
\begin{thebibliography}{99}
 
 
\bibitem{AS}
M.~Abramowitz and I.A.~Stegun, eds.,
{\sl Handbook of Mathematical Functions,}
Dover Publications,  New York,
1970.
 
 
\bibitem{Anderson}
T.W.~Anderson,
{\sl An Introduction to Multivariate Statistical Analysis,}
John Wiley \& Sons, New York,
1958.
 
 
\bibitem{Davis}
A.W.~Davis,
On the ratios of the individual latent roots
to the trace of a Wishart matrix,
{\sl J. Mult. Anal. 2}
(1972), 440--443.
 
\bibitem{D}
J.W.~Demmel,
The probability that a numerical analysis problem is
difficult,
{\sl Math. Comput. 50}
(1988), 449--480.
 
\bibitem{Ed1}
A.~Edelman,
Eigenvalues and condition numbers of random matrices,
{\sl SIAM J.  Matrix Anal. Appl. 9}
(1988), 543--560.
 
\bibitem{Ed2}
A.~Edelman,
{\sl Eigenvalues and Condition
Numbers of Random Matrices,} Ph.D. thesis, Dept. of Math., M.I.T., 1989.
 
\bibitem{GR}
I.S.~Gradshteyn and I.W.~Ryzhik,
{\sl Table of Integrals, Series, and Products,}
6th printing,  Academic Press, New York, 1980.
 
\bibitem{KS}
P.R.~Krishnaiah and F.J.~Schuurmann,
On the evaluation of some distributions that arise in simultaneous
tests for the equality of the latent roots of the covariance matrix,
{\sl J. Mult. Anal. 4} (1974), 265--282.
 
\bibitem{SKC}
F.J.~Schuurmann, P.R.~Krishnaiah, and A.K.~Chattopadhyay,
On the distributions of the ratios of the extreme roots
to the trace of the Wishart matrix,
{\sl J. Mult. Anal. 3}
(1973), 445--453.
 
 
 
 
 
\end{thebibliography}
 
\end{document}
