Mathematics 372 – Numerical Linear Algebra Selected Solutions for Problem Set 3 February 9, 2007

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 whenever i + 2 ≤ j ≤ 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} = \frac{a_{1j}}{r_{11}} .

Since A is tridiagonal, a_{1j} = 0 when j ≥ 3. This shows that r_{1j} = 0 when j ≥ 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 whenever 1 ≤ i ≤ k and i + 2 ≤ j ≤ n.

In row k + 1, after the diagonal entry, the rest of the row is computed by

r_{k+1,j} = \frac{a_{k+1,j} − ∑_{l=1}^{k} r_{l,k+1}r_{l,j}}{r_{k+1,k+1}} .

We want to see what happens when j ≥ (k + 1) + 2 = k + 3. Since A is tridiagonal, a_{k+1,j} = 0. Furthermore, if j ≥ k + 3, then since l ≤ k, the difference between the column and row numbers in the second factor in the terms in the sum is

j − l ≥ k + 3 − l ≥ k + 3 − k ≥ 3.

By the induction hypothesis, all of the r_{l,j} = 0 when l ≤ k and j ≥ 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. 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_{lj} = 0.

III B. First we show the claim from Exercise 1.4.35 in the text. This is a case where induction is not the best way to go. We assume A has Cholesky factor R and then we consider the upper-left j × 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}Ax = (x_{j}^{t} 0) ( \begin{matrix}A_{j} & B \\ B^{t} & C \end{matrix} ) ( \begin{matrix}x_{j} \\ 0 \end{matrix} ) = x_{j}^{t}A_{j}x_{j}

Since x_{j} can be any nonzero vector in 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 = ( \begin{matrix}R_{j} & D \\ 0 & E \end{matrix} )

Then

R^{t}R = ( \begin{matrix}R_{j}^{t} & 0 \\ D^{t} & E^{t} \end{matrix} ) ( \begin{matrix}R_{j} & D \\ 0 & E \end{matrix} ) = ( \begin{matrix}A_{j} & B \\ B^{t} & C \end{matrix} ) .

Thinking about how matrix multiplication works, we see that the entries in the first j rows and columns are R_{j}^{t}R_{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 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} ≠ 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 × j positive-definite symmetric A, and consider A of size (j + 1) × (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 = ( \begin{matrix}A_{j} & c \\ c^{t} & a_{j+1,j+1} \end{matrix} )

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 = ( \begin{matrix}R_{j} & h \\ 0 & r_{j+1,j+1} \end{matrix} ) .

Then

R^{t}R = ( \begin{matrix}R_{j}^{t} & 0 \\ h^{t} & r_{j+1,j+1} \end{matrix} ) ( \begin{matrix}R_{j} & h \\ 0 & r_{j+1,j+1} \end{matrix} ) = ( \begin{matrix}R_{j}^{t}R_{j} & R_{j}^{t}h \\ h^{t}R_{j} & h^{t}h + r_{j+1,j+1}^{2} \end{matrix} ) = ( \begin{matrix}A_{j} & c \\ c^{t} & a_{j+1,j+1} \end{matrix} )

This shows

\begin{aligned}R_{j}^{t}h & = c \\ h^{t}h + r_{j+1,j+1}^{2} & = a_{j+1,j+1} \end{aligned}

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:

r_{11}h_{1} = 0
r_{12}h_{1} + r_{22}h_{2} = 0
⋮
r_{1,k−1}h_{1} + ⋯ + r_{k−1,k−1}h_{k−1} = 0
r_{1k}h_{1} + ⋯ + r_{kk}h_{k} = c_{k} ≠ 0

Then h_{1} = h_{2} = ⋯ = h_{k−1} = 0, but then h_{kk} = c_{k}/r_{kk} ≠ 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. (Comment: This is a very neat proof!!)