Page 162 - Matrix Analysis & Applied Linear Algebra

156 Chapter 3 Matrix Algebra

3.10.4. If A is a nonsingular matrix that possesses an LU factorization, prove
that the pivot that emerges after (k + 1) stages of standard Gaussian
elimination using only Type III operations is given by
T
p k+1 = a k+1,k+1 − c A −1 b,
k
where A k and

b
A k
A k+1 =
c T a k+1,k+1
are the leading principal submatrices of orders k and k +1, respec-
tively. Use this to deduce that all pivots must be nonzero when an LU
factorization for A exists.

3.10.5. If A is a matrix that contains only integer entries and all of its pivots
are 1, explain why A −1 must also be an integer matrix. Note: This fact
can be used to construct random integer matrices that possess integer
inverses by randomly generating integer matrices L and U with unit
diagonals and then constructing the product A = LU.

 
β 1 γ 1 0 0
 α 1 β 2 γ 2 0 
0 α 2 β 3 γ 3
3.10.6. Consider the tridiagonal matrix T =   .
0 0 α 3 β 4
(a) Assuming that T possesses an LU factorization, verify that it
is given by
1 0 0 0 π 1 γ 1 0 0
   
1 0  0
 α 1 /π 1 0  π 2 γ 2 0 
0 α 2 /π 2 1 0 0 0 π 3 γ 3
L =   , U =   ,
0 0 α 3 /π 3 1 0 0 0 π 4
where the π i ’s are generated by the recursion formula
α i γ i
and .
π 1 = β 1 π i+1 = β i+1 −
π i
Note: This holds for tridiagonal matrices of arbitrary size
thereby making the LU factors of these matrices very easy to
compute.
(b) Apply the recursion formula given above to obtain the LU fac-
torization of
2 −1 0 0
 
 −1 2 −1 0 
0 −1 2 −1
T =   .
0 0 −1 1