\documentstyle{article}
\setlength{\topmargin}{-0.5in}
\setlength{\textwidth}{5in}
\setlength{\textheight}{7.8in}
\setlength{\baselineskip}{13pt}
\newtheorem{theorem}{Theorem}[section]

\newlength{\boxwidth}
\setlength{\boxwidth}{\textwidth}
\addtolength{\boxwidth}{-20 pt}
\newcommand{\tr}{\mbox{tr}}
\newcommand{\boxer}[1]{\begin{center} \fbox{\fbox{
      \begin{minipage}{\boxwidth}  #1 \end{minipage}}} \end{center}}

\newcommand{\norm}[1]{\| #1 \|_2 }
\newcommand{\frob}[1]{\| #1 \|_F }
\newcommand{\bu}{\bar{U}}
\newcommand{ \real }{ I \kern - 4pt R}

\newcommand{\rtr}{R^T \! R}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\mrf}[1]{$(\ref{#1})$}
\newcommand{\abs}[1]{\! \mid #1 \mid \!}
 
\begin{document}



\vspace{0.1in}
 
\begin{center}
{\large \bf 
ON PARLETT'S MATRIX NORM INEQUALITY FOR THE
CHOLESKY DECOMPOSITION }
\\
\vspace{0.2in}
{\small 
ALAN EDELMAN}\\
{\small \it Department of Mathematics \\
and Lawrence Berkeley Laboratory\\
University of California \\
Berkeley, California 94720 \\
\verb+edelman@math.berkeley.edu+\\}
\vspace{0.2in}
{\small WALTER F.  MASCARENHAS\\
\small \it Dept. de Matematica \\
Universidade Estadual de Campinas \\
Caixa Postal 6065 \\
Barao Geraldo \\
Campinas SP 13081, Brazil} \\
{\verb+walterm@dcc.unicamp.br+}
\end{center}
\date{}

\begin{center}
\parbox{2.7in}{
\small
\begin{center}
Dedicated to our friends Beresford and Velvel on
the occasion of their sixtieth birthdays.
\end{center}
}
\end{center}

\vspace{1.0in}

\begin{center}
\small ABSTRACT
\end{center}

\begin{center}
\parbox{4.5in}{
\setlength{\baselineskip}{10pt}

\hspace*{.15in} \small 
We show that a certain matrix norm ratio studied by Parlett
has a supremum that is $O(\sqrt{n})$ when the chosen
norm is the Frobenius norm, while it is $O(\log n)$
for the 2-norm.  This ratio arises in Parlett's analysis
of the Cholesky decomposition of an $n$ by $n$ matrix.
\\ \\
{\it Keywords:} Cholesky, norm inequality, perturbation.
}
\end{center}

\setlength{\baselineskip}{13pt}
\section{Introduction}

\normalsize
Let $U$ be a non-zero upper triangular matrix with diagonal
entries $u_{ii} \ge -1$.
Define
\[
\tau(U) \; \equiv \; \frac {\|U\|}{\|U^T+U+U^TU\|}.
\]
Parlett \cite{parlett} asked for bounds for
\[
\chi(n) \equiv \sup_{u_{ii} \ge -1} \tau(U),
\]
where the supremum is taken over all such upper triangular
$U$ of dimension $n$.  


The quantity $\chi(n)$ arises in Parlett's \cite{parlett}
perturbation theory
of the Cholesky decomposition. The term 
$U^TU$ in the denominator would be neglected by first order
perturbation theory but, according to Parlett, it actually helps in
the analysis.  

Consider perturbations $\delta A$ to the identity
matrix.   (The analysis for perturbing any positive definite
matrix can be reduced to this case through an appropriate
change of coordinates \cite{parlett}.)
The Cholesky factorization is
$$I+\delta A=(I+\delta U)^T(I+\delta U),$$
where $\delta U$ is upper triangular, so that
$$\delta A=\delta U^T + \delta U+ \delta U^T \delta U.$$
It follows that
$$\frac{\|\delta U\|}{\|\delta A\|}=\tau(\delta U).$$
Given $\|\delta A\|$, it is natural to ask 
for the maximum value of $\|\delta U\|$
and hence we study $\chi(n)$.



We bound the quantity $\chi(n)$ for both
the Frobenius norm $\|A\|_F \equiv  \sqrt{\sum a_{ij}^2}
\equiv \sqrt{\sum \sigma_i^2}$
and  the 2-norm $\|A\|_2=\sigma_{\max}$,
where the $\sigma_i$ denote the singular values of $A$.
We will denote our supremum as
$\chi_F(n)$
and $\chi_2(n)$ respectively for the 
Frobenius norm and the 2-norm.
Section 2 discusses the bounds
for the Frobenius norm 
while Section 3 discusses the bounds for the 2-norm.

Other approaches to this problem may be found in
\cite{dov} and \cite{sun}.  Our bounds are
tighter and have shorter proofs.
The  results indicate quite a difference in asymptotic behaviors
as $n \rightarrow \infty$:
\boxer{
Frobenius norm bound:
\beq
\label{frobn}
\sqrt{2n - 1} \; \leq \chi_F(n) < \sqrt{n} \left( 1+\sqrt{1+n^{-1/2}}
\right) .
\eeq

2-norm bound:
\beq
\label{twon}
 0.22 \log_2( n-1) - 0.362  \; < \chi_2(n) \;
 < 2\log_2 n + 4 .
\eeq
}






\section{The Frobenius norm's $\chi_F(n)$}

\noindent
{\bf Lower Bound:}
Let $U$ be the $n \times n$ 
matrix defined by
$$
u_{ij}= \left\{
\begin{array}{rl}
-1 & j=i \\
1  & j=i+1 \\
0 & \mbox{otherwise}.
\end{array}
\right.
$$
$U$ has Frobenius norm $\sqrt{2n - 1}$ 
and $U^T + U + U^T U $ has norm $1$. Therefore
$\chi(n) \geq \sqrt{2n - 1}$. 

\vspace{0.2in}
\noindent
{\bf Upper Bound:}
Though not logically necessary, we will find it
convenient at times to make
the change of variables $R=I+U.$
We may then define
$$
\rho(R) \equiv \tau(R-I)=\frac{\|I-R\|_F}{\|I-\rtr\|_F},
$$
and ask for
$$
\chi(n)\equiv \sup_{r_{ii} \ge 0} \rho(R)
$$
where the supremum is over the set of $n$ by $n$ upper triangular matrices
$R$ with non-negative diagonals $r_{ii}$, excluding the identity matrix.





Our upper bound \mrf{frobn}
is 
\beq
\label{bound}
\rho(R) < 
\sqrt{n} \left( 1+\sqrt{1+n^{-1/2}} \right)  .
\eeq
for any upper triangular matrix $R$ with 
$r_{ii} \ge 0$ and $R \ne I$.
For $n$ large, this is roughly $2\sqrt{n}$.

Given our expression for $\rho(R)$, it is natural
to study three cases: a large numerator,
a small denominator, or neither a large numerator nor
small denominator.  Each possibility yields a bound 
for $\rho(R)$.  The three cases are indicated
schematically in Figure 1.

\parbox{6in}{
\input{psfig}
\begin{center}~
\psfig{figure=diagram.ps,height=133pt}
\end{center}
\begin{center}
\parbox{4.5in}{
{\bf Figure 1}
Proof outline:
 I: $R$ large,
 II: $R \approx I$,
 III: $R$ in between
}
\end{center}}


Notice that if $\|R\|_F$ is very large, the quadratic term
in the denominator of $\rho(R)$ is roughly the
square of the numerator.  
This  is the beauty of Parlett's suggestion
of keeping the quadratic term -- it will allow us to bound
$\rho(R)$ for $\|R\|_F$ large.
As $R$ tends to the identity $I$, a simple argument shows
that $\rho(R) \le 2^{-1/2}$ suggesting the existence of
a small bound for $\rho(R)$ when $R$ is near the identity.
If neither of these two hypotheses is  true, then we
again obtain a bound because
the numerator in our expression for $\rho(R)$ is not
too large, and also the denominator is not too small. 
We proceed to  quantify these ideas.



$\bullet$ {\bf Case I:} If $\|R\|_F$ is so large that
$\|R\|_F>\sqrt{n}$, then
\[
\rho(R) \le  \frac{\sqrt{n}}{\|R\|_F-\sqrt{n}}
\]

{\bf Proof:} 
Jensen's inequality states that the square of an
average is no bigger than the average of squares:
$$
(\frac{1}{n} \sum \sigma_i^2
)^2 \le \frac{1}{n} \sum (\sigma_i^2)^2.
$$
Thanks to the singular value definition of the Frobenius norm
$$
\frac{1}{\sqrt{n}}\|R\|_F^2 \le
\| \rtr\|_F.
$$
Therefore,
$\|I-\rtr\|_F \ge \|\rtr\|_F-\|I\|_F \ge \frac{1}{\sqrt{n}}(\|R\|_F^2-n)$
giving a bound for the denominator.

The triangle inequality bounds the numerator:
$\|I-R\|_F \le \|R\|_F+\|I\|_F=\|R\|_F+\sqrt{n}$,
and the result follows upon division.

$\bullet$ {\bf Case II:} If $\|I-\rtr\|_F=\kappa$ for some $0<\kappa<1$,
then
\[
\rho(R) <  \sqrt{2n-1} .
\]

{\bf Proof:}
If
$\|I-\rtr\|_F=\kappa$, then
the upper left entry
of $I-\rtr$ tells us that 
$(1-r_{11}^2)^2 \le \kappa^2$, so
$$(1-r_{11})^2 \le \kappa^2/(1+r_{11})^2 < \kappa^2$$
since $r_{11} \ge 0$ and equality would violate $\kappa<1$.


Let $w_1$ be the row vector obtained by deleting $r_{11}$ from the first
row of $R$.  The first row (column)
of $I-\rtr$ with its first component
deleted is $r_{11}w_1$ (transposed). 
Since $\|I-\rtr\|_F=\kappa$,
$$(1-r_{11})^2+2r_{11}^2\|w_1\|^2_2 \le \kappa^2.$$
We claim that $\|w_1\|_2^2 < \kappa^2$ for otherwise
$(1-r_{11}^2)^2 \le (1-2r_{11}^2) \kappa^2$,
which implies that $\kappa^2 \ge \frac{(1-r_{11}^2)^2}{1-2r_{11}^2} \ge 1$,
which would contradict the hypothesis $\kappa < 1$.

Since $\rtr$ is similar to $RR^T$, we deduce that
 $\|I-RR^T\|_F=\|I-\rtr\|_F=\kappa$.
 Let $R_k$ be the submatrix of $R$ obtained by taking rows and columns
 $k$ through $n$.   The matrix in the corresponding position of
 $I-RR^T$ is $I-R_kR_k^T$ so that $
 \|I-R_k^T \! R_k\|_F=\|I-R_kR_k^T\|_F\le \kappa$.
Now the argument that we  applied to the first row of $R$ may be applied
to the first row of each $R_k$ so that
$$(1-r_{kk})^2 <   \kappa^2
 \ \ \ \mbox{  and  } \ \ \
\|w_k\|^2_2 < \kappa^2,$$
for every row $k$.  Here $w_k$ denotes  the row vector past the diagonal
of $R$ in row $k$ for  $k=1,\ldots,n-1$.
Add up the contributions from the rows of $I-R$ to conclude
$$\|I-R\|_F^2 <  (2n-1) \kappa^2, $$
yielding  the upper bound for $\rho(R)$ claimed in this case.

We remark that, since this upper bound matches the lower bound obtained
earlier from an example $U$ on the boundary of this case,
the worst case cannot fall in Case II.  We suspect that $\rho(R)$
achieves its maximum $\chi(n)$ for some $R=I+U$
similar to the example, but slightly outside Case II.



$\bullet$ {\bf Case III:} If 
$\|I-\rtr\|_F > 1$ then 
$$\rho(R) < \|R\|_F +\sqrt{n}.$$


{\bf Proof:}
The triangle inequality.

$\bullet${\bf Final Assembly}
If $\|R\|_F >\sqrt{n}\sqrt{1+n^{-1/2}}$ apply Case I.
If $\|I-\rtr\|_F \le 1$ apply Case II, possibly
taking the limiting case of $\kappa=1$ by continuity.  Otherwise
$\|R\|_F  \le \sqrt{n}\sqrt{1+n^{-1/2}}$ and Case III applies
completing the proof.




\section{The 2-norm's $\chi_2(n)$ }

\noindent
{\bf Lower Bound:}
We are indebted to Roy Mathias \cite{mathias}
for the realization that 
an example of Kahan  \cite{velvel}
serves as a lower bound for the 2-norm.
The discussion that follows is a reformulation
and enhancement of Mathias' observation.


We begin with the observation that if $U$ is any
non-zero upper triangular matrix, then
\[
\label{lim}
\lim_{\epsilon \rightarrow 0} \tau(\epsilon U)
=\frac{\norm{U}}{\norm{U^T+U}}.
\]

Therefore 
$$\chi_2(n) \ge \sup \frac{\norm{U}}{\norm{U^T+U}},$$
the supremum taken over all non-zero upper triangular
matrices.


Kahan \cite{velvel} shows that the upper triangular
matrix $W \in \real^{m \times m}$ with
$$W_{ij}=\left\{ \begin{array}{cl}
\frac{1}{j-i} & j>i \\
0 & j \le i
\end{array}
\right.
$$
satisfies $\|W+W^T\|_2>2\log m+\frac{1}{2}-2 \log 2 +\frac{1}{m}
> 2 \log m -0.8863$.
Therefore $\|W\|_2>\log m-0.44315$ by the triangle
inequality.



Kahan also shows  $\|W-W^T\|_2<\pi$ for all $m$.
Define a $2m$ by $2m$ matrix
$$Y=\left( \begin{array}{rc}
0 & W \\
-W & 0
\end{array}
\right)
.
$$
It follows that
$\|Y\|_2 =\|W\|_2>\log m - 0.44315 $  and
that $\|Y+Y^T\|_2=\|W-W^T\|_2<\pi$.

Performing
a perfect shuffle\footnote{A perfect shuffle
rearranges the numbers $1,\ldots,2n$ into
$1,n+1,2,n+2,3,n+3,\ldots,n,2n$.}
n the rows and columns of $Y$ produces a
$2m$ by $2m$ strictly upper triangular matrix $U$
for which 
\[
\frac{\norm{U}}{\norm{U+U^T}} > \frac{1}{\pi}\log(m)
-\frac{0.44315}{\pi}.
\]
Replacing $2m$ with $n$ or $n-1$ depending on whether
$n$ is even or odd, numerically computing
$(0.44315+\log 2)/\pi$, and switching to base 2 logarithms, we may conclude
that there exists an $n \times n$ strictly
upper triangular matrix $U'$ such that 
$$\tau(U') > \frac{1}{\pi}\log (n-1) - 0.362
> 0.22 \log_2 (n-1)-0.362 .$$

\vspace{0.2in}

\noindent
{\bf Upper Bound:} In the following analysis we always
assume that
$U$ is  not the zero matrix.


\begin{theorem}
\label{T2}
If $U \in \real^{2^k \times 2^k}$
is upper triangular, 
 with $u_{ii} \ge - 1$ for $1 \leq i \leq 2^k $, then 
\[
\tau(U) = \frac{ \norm{U} }{ \norm{ U + U^T + U^TU} }  \; 
<\;  2 k + 2.
\]
Furthermore, if $U \in \real^{n \times n}$ with the same hypotheses,
$$\tau(U) < 2\log_2 n+4.$$
\end{theorem}

\noindent
{\bf Proof:}
The second statement follows from the first by adding rows and columns
of zeros so that $2^k$ is the smallest power of $2$ bigger than $n$.
The proof of the first statement
is a divide and conquer style argument
by induction on $k$,  the $\log_2$ of the dimension of $U$.
The theorem is true for $k = 0$ since for
$1 \times 1$ matrices with $u_{11} \geq -1$,
\[
\tau{(U)} \;  = \; \frac{ \abs{u_{11}} }{\abs{2u_{11} + u_{11}^2}} \; 
= \; \frac{1}{2 + u_{ii}} \; \leq \; 1 \; < \; 2 \times 0 \;  + \;  2.
\]

Now let us assume that the theorem holds for dimension $2^{(k - 1 )}$. 
Take a  $2^k \times 2^k$ matrix $U$ satisfying the hypotheses of Theorem 3.1.
We once again take the same strategy as in Section 2.  We first consider
the case that the numerator in $\tau(U)$ is large, and then second
that the denominator is not too small.  The only non-trivial
part of the argument is the case when the denominator may be small,
but the numerator is not large.
We chose two  convenient numbers for large and small:
$3$ and $3/4$ respectively.  Slightly better bounds may be
obtained with different choices.

If $\norm{U} \geq 3$ then 
\[
\norm{U^T + U + U^TU} \geq \norm{U^TU} - \norm{U^T} - \norm{U} =
\norm{U} \left( \norm{U} - 2 \right) \geq \norm{U}.
\]
Therefore, if $\norm{U} \geq 3$ then 
$ \tau(U) \leq \norm{U}/ \norm{U}=1 < 2 k + 2$.
On the other hand, if $\norm{U} < 3 $, $k \geq 1$ and 
$\norm{U + U^T + U^TU} \geq 3/4 $, then
$ \tau(U) \; < \;  4 \; \leq \; 2 k + 2$.

We have only left the case 
$\norm{U + U^T + U^TU} < 3/4 $ and $\norm{U} < 3$. 
In this case we write
\beq
\label{decomp}
U = 
\left(
\begin{array}{cc}
X & Y \\
0 & Z \\
\end{array}
\right)
=
\left(
\begin{array}{cc}
X & 0 \\
0 & Z \\
\end{array}
\right)
+
\left(
\begin{array}{cc}
0 & Y \\
0 & 0 \\
\end{array}
\right)
\eeq
where each block $X,Y,Z$ has dimension $2^{(k-1)}$.
The $X$ and $Z$ may be thought of as the easy part of
the divide and conquer, while the $Y$ is more of a nuisance
term that needs to be handled gingerly.

Our  partition of $U$ leads to 
\beq
\label{uut}
UU ^T 
=
\left(
\begin{array}{cc}
X & Y \\
0 & Z \\
\end{array}
\right)
\left(
\begin{array}{cc}
X^T &  0 \\
Y^T &  Z^T \\
\end{array}
\right)
=
\left(
\begin{array}{cc}
X X^T + Y Y^T &  Y Z^T  \\
Z Y^T &  Z Z^T \\
\end{array}
\right),
\end{equation}
\beq
\label{buut}
B \equiv  \; U + U^T + U U^T \; = \; 
\left(
\begin{array}{cc}
?  &  Y ( I + Z^T ) \\
? & Z + Z^T +  Z Z^T \\
\end{array}
\right),
\eeq
and 
\beq
\label{butu}
B' \equiv  \; U + U^T + U^T U \;  = \; 
\left(
\begin{array}{cc}
X + X^T + X^T X  & ? \\
? &  ?  \\
\end{array}
\right).
\eeq
The question marks indicate matrix elements that
are of no immediate interest to us.
Since $(I+U)(I+U)^T$ is similar to
$(I+U)^T(I+U)$, we learn
that the
$B$ and $B'$ defined in \mrf{buut} and \mrf{butu}  are
similar symmetric matrices.
In particular, $\|B\|=\|B^\prime\|$.
The same holds if $U$ is replaced with $Z$ or $X$.


The proof follows from the three claims below:
\begin{itemize}
\item{Claim 1:} $ \norm{X} \;  < \; 2k \; \norm{B}$.
\item{Claim 2:} $ \norm{Z} \; < \; 2k \;  \norm{B}$.
\item{Claim 3:} $ \norm{Y} \; <   \; 2 \;        \norm{B} $.
\end{itemize}

In fact, if these claims are true then 
{from} \mrf{decomp}, 
\[
\norm{U} \; \le \; \max \{ \; \norm{X}, \; \norm{Z} \; \} \;  + \; \norm{Y} \;
 < \; (2k+2) \; \norm{ B },
\]
completing the induction.

Let us now prove the three claims above.
Since $Z + Z^T + Z Z^T$ is the lower right corner of $B$ in
\mrf{buut} we can use the induction hypothesis to conclude that
\[
\norm{Z} \; < \; ( 2 (k - 1)  + 2 )  \; \norm{Z + Z^T + Z Z^T} \leq 
\;  2 k  \; \norm{B}.
\]
Analogously, Since $X + X^T + X X^T$ is the upper right corner of $B'$ ,
\[
\norm{X} \; < \; ( 2 (k - 1) + 2 ) \;  \norm{X + X^T + X X^T} \leq \; 
 2 k  \; \norm{B'}   =
 2 k  \; \norm{B},
\]
and we have proved the first two claims.

Now the proof of the third claim. 
Using (6) and standard norm inequalities we obtain,
\beq
\norm{B} \; \ge \; \norm{Y(I+Z^T) } \; 
\ge \; \frac{\norm{Y}}{\norm{ (I+Z^T)^{-1} } }
\; = \; 
\frac{\norm{Y} }{ \norm{ (I+Z)^{-1} }  } 
\eeq



So as to obtain information about $(I+Z)^{-1}$, we look
at the partition
\[
(I + U)^{-1} 
=
\left(
\begin{array}{cc}
? & ? \\
   0        & ( I + Z )^{-1} \\
\end{array}
\right),
\]
{from} which it is clear that 
\beq
\norm{ (I + Z)^{-1} } \; \leq \;
\norm{ (I + U)^{-1} }.
\eeq
Finally, the
assumption that
$\|(I+U)^T(I+U)-I\|_2<3/4$ means that all the
eigenvalues of the positive definite matrix $(I+U)^T(I+U)$
are greater than $1/4$,
{from} which it readily follows that 
\beq \|(I+U)^{-1}\|_2<2.\eeq
Claim 3 is a direct consequence of
(8), (9), and (10). This completes our proof.
\

\

\section{Concluding Remarks}

We suspect more precise  bounds for $\chi(n)$
are obtainable.  Indeed
there is evidence that $\chi_F(n)$ may be $\sqrt{2n}$
asymptotically  as it was in our Case II.
We  can also slightly improve the
2-norm bound.
We satisfy ourselves here with 
the bounds \mrf{frobn} and \mrf{twon} as they are tight enough to demonstrate
Parlett's point that 
keeping the quadratic term helps produce better bounds.
\\ \\


\noindent
{\Large \bf Acknowledgements} \\ \\
We would like to thank Beresford Parlett for inviting us to
work on this problem while one author was visiting the
other author at Berkeley during 
May of 1992.  We would further like to thank
Velvel Kahan who served as a not very  anonymous referee  suggesting
many valuable improvements including the observation that our original
upper bound for $\chi_F(N)$
of $2.7\sqrt{n}$ could be reduced to 
a quantity that is roughly  $2\sqrt{n}$.
This work was
supported by the Applied Mathematical Sciences subprogram of
the Office of Energy Research, U.S. Department of Energy under
Contract DE-AC03-76SF00098.


\vspace{0.2in} 

\def\\{\medskip\noindent\hangindent .3in{}}
\setlength{\baselineskip 11pt}
\frenchspacing
\begin{thebibliography}{9}


\bibitem{dov}
Z.Drma\v{c}, M.Omladi\v{c}, K.Veseli\'{c},
On the perturbation of the Cholesky factorization,
November 1992, preprint.

\bibitem{velvel}
W. Kahan,
Every $n \times n$ matrix $Z$ with real spectrum satisfies
$\|Z-Z^*\|\le\|Z+Z^*\|(\log_2n+0.038)$,
{\sl Proc. Amer. Math. Soc. 39} (1973), 235--241. \newline
{\small
(
On page 238 the term $(\log n+\frac{1}{4}-\frac{1}{2}\log 2 +1/2n)$
that appears on Line 3 of Section 1 should be 
$(\log n+\frac{1}{4}-\log 2 +1/2n)$.
On the next line, the term $0.92 \log_2 n$ should be
$0.44 \log_2 n$, while the $\log 2$ factor on line -2 of
page 238, should be $2\log 2$.
The author acknowledges
these corrections.)}

\bibitem{mathias}
R.Mathias,
Personal Communication to  B. Parlett, 1991.

\bibitem{parlett}
B.N.Parlett,
Perturbation theory for QR,
lecture given at the Fourth SIAM Conference on Applied Linear
Algebra, Minneapolis, September 1991.
Document in preparation.  


\bibitem{sun}
J.-G. Sun,
Perturbation bounds for the Cholesky and QR factorizations,
{\sl BIT 31} (1991), 341--352.

\end{thebibliography}

\end{document}










