\magnification=\magstep1
\overfullrule = 0pt
\centerline{Mathematics 372 -- Numerical Linear Algebra}
\centerline{Selected Solutions for Problem Set 3}
\centerline{February 9, 2007}
\bigskip
\noindent
I C.  Let $A$ be a tridiagonal positive-definite symmetric matrix.
We want to show that the Cholesky factor $R$ of $A$ is also 
tridiagonal (and upper-triangular).  This means that we want to 
show that in $R$, 
$$r_{ij} = 0\quad {\rm whenever}\quad  i + 2\le j \le n.$$
We can prove this by induction on $i$, using the ``row-by-row''
form of the Cholesky factorization discussed in class (see equation
(1.4.14) in text).
Note that that process automatically produces an upper-triangular
$R$, so the entries below the main diagonal will always be zero.

The base case is $i = 1$.  In row 1, the diagonal entry is computed
by $r_{11} = \sqrt{a_{11}}$.  Then the remainder of the first row
entries are
$$r_{1j} = {a_{1j}\over r_{11}}.$$
Since $A$ is tridiagonal, $a_{1j} = 0$ when $j \ge 3$.  This shows
that $r_{1j} = 0$ when $j \ge 3$ too.

Now assume that we have shown that the first $k$ rows of $R$ have
the zeros ``in the right places'':
$$r_{ij} = 0 \quad  {\rm whenever} \quad 1 \le i \le k\quad {\rm and} 
\quad  i + 2 \le j \le n.$$
In row $k+1$, after the diagonal entry, the rest of the row 
is computed by 
$$r_{k+1,j} = {a_{k+1,j} - \sum_{l=1}^k r_{l,k+1} r_{l,j}\over r_{k+1,k+1}}.$$
We want to see what happens when $j \ge (k+1) + 2 = k+3$.
Since $A$ is tridiagonal, $a_{k+1,j} = 0$.  Furthermore, if $j \ge k+3$,
then since $l \le k$, the difference between the column and row numbers
in the second factor in the terms in the sum is
$$j - l \ge k+3 - l \ge k+3 - k \ge 3.$$  
By the induction hypothesis, {\it all} of the $r_{l,j} = 0$
when $l \le k$ and $j \ge k+3$.  
This means that all the terms on the top of the formula 
for $r_{k+1,j}$ are zero, so $r_{k+1,j} = 0$.   This concludes the proof.

\noindent
{\it Comment}:  It's true of course that most of the 
first factors $r_{l,k+1}$ are zero too.  This only fails when
$l = k$, but even then the other factor $r_{l j} = 0$.

\bigskip
\noindent
III B.  First we show the claim from Exercise 1.4.35 in the text.  This 
is a case where induction is {\it not} the best way to go.  
We assume $A$ has Cholesky factor $R$ and then we consider
the upper-left $j\times j$ submatrix $A_j$ in $A$ (the entries from rows 
1 through $j$ and columns 1 through $j$).  

(Incidentally, you might wonder how we know $A_j$ is positive-definite.  
The reason is that we can consider all nonzero vectors with zeroes in 
entries $j+1$ through $n$.  For any such vector $x = (x_j\ 0)^t$, 
we have, since $A$ is positive-definite,
$$0 < x^t A x = (x_j^t\ 0) \pmatrix{A_j & B\cr
                              B^t& C\cr} \pmatrix{x_j\cr 0\cr} = x_j^t A_j x_j$$
Since $x_j$ can be any nonzero vector in ${\bf R}^j$, this implies $A_j$
is also positive-definite.)

Now, the problem is to 
show that the similarly-located submatrix $R_j$ of $R$ is
the Cholesky factor of $A_j$.  That is, we must show that 
$R_j^t R_j = A_j$, $R_j$ is upper-triangular, and has positive
diagonal entries.  The second two statements here are automatic
because $R$ is upper-triangular with positive diagonal entries.
$R_j$ consists of the entries in rows 1 to $j$ and columns 1 to $j$
of $R$, so $R_j$ is also upper-triangular, and the diagonal entries
 in $R_j$ are the same as the first $j$ diagonal entries in $R$.  The 
equation $R_j^t R_j = A_j$ comes by considering the partitioned form of 
$R$ and $A$.  Write 
$$R = \pmatrix{R_j & D\cr
                0 & E\cr}$$
Then 
$$R^t R = \pmatrix{R_j^t & 0\cr
                    D^t & E^t\cr}\pmatrix{ R_j & D\cr 0 & E\cr} = \pmatrix{A_j & B\cr 
                                                                            B^t & C\cr}.$$
Thinking about how matrix multiplication works, we see that the entries
in the first $j$ rows and columns are 
$R_j^tR_j = A_j$, since the rest of the entries on the first $j$ rows of $R^t$ are zero.  
This proves 1.4.35.

Now, to prove the envelope theorem, we want to think of organizing the 
computation of the Cholesky factor $R$ {\it column-by-column} rather than
row-by-row as in the discussion from class and the proof of I C above. 
The key point of what we want to show is that if $A$ has zero entries
in column $j$ and rows $i = 1$ to row $k(j)-1$ for some $k(j) < i$, but
$a_{k(j),j} \ne 0$, then the 
same is true for the Cholesky factor $R$.  We argue by induction on 
the size $n$ of the matrix.  

In the base case $n = 1$, there is nothing to prove: $R = (r_{11})$ has
the same envelope as $A = (a_{11})$ by definition.  So assume the result
is true for all $j\times j$ positive-definite symmetric $A$, and consider
$A$ of size $(j+1) \times (j+1)$.  We partition the matrix $A$ as
in 1.4.35, but making $A_j$ consist of all but the last row and column:
$$A = \pmatrix{A_j & c\cr
                c^t & a_{j+1,j+1}\cr}$$
If $R$ is the Cholesky factor of $A$, then 1.4.35 says the submatrix $R_j$
of $R$ is the Cholesky factor of $A_j$, so by induction those matrices
have the same envelopes.  

We only need to consider what happens in the final column.  So write
$$R = \pmatrix{R_j & h\cr
                0  & r_{j+1,j+1}\cr}.$$
Then 
$$R^t R = \pmatrix{R_j^t & 0\cr
                    h^t  & r_{j+1,j+1}\cr}\pmatrix{R_j & h\cr
                                                    0  & r_{j+1,j+1}\cr} = 
\pmatrix{R_j^t R_j & R_j^t h\cr
          h^t R_j  & h^t h + r_{j+1,j+1}^2\cr} = \pmatrix{A_j & c\cr
                                                           c^t & a_{j+1,j+1}\cr}$$
This shows
$$\eqalign{R_j^t h &= c\cr
           h^t h + r_{j+1,j+1}^2 &= a_{j+1, j+1}\cr}$$
Suppose the first nonzero entry in $c$ (down from the top of the matrix)
is in row $k$.  We solve for $h$ from the equation $R_j^t h = c$
by forward substitution:
$$\eqalign{r_{11} h_1 &= 0\cr
           r_{12} h_1 + r_{22} h_2 &= 0\cr
                                   &\ \ \vdots \cr
           r_{1,k-1} h_1 + \cdots + r_{k-1,k-1} h_{k-1} &= 0 \cr
           r_{1k} h_1 + \cdots + r_{kk} h_k &= c_k \ne 0\cr}$$
Then $h_1 = h_2 = \cdots = h_{k-1} = 0$, but then $h_{kk} = c_k/r_{kk} \ne 0$.
This shows that $R$ has its first nonzero in the same location in column $j+1$ as
$A$ does, so the envelopes are the same because the parts of the envelopes
in columns $1$ through $j$ also work by the induction hypothesis.  
({\it Comment}: This is a very neat proof!!)
\bye  

  
