15- Matrix Factorizations VU

Lecture 15

Matrix Factorizations

Matrix Factorization
A factorization of a matrix as a product of two or more matrices is called Matrix
Factorization.
Uses of Matrix Factorization
Matrix factorizations will appear at a number of key points throughout the course. This
lecture focuses on a factorization that lies at the heart of several important computer
programs widely used in applications.

LU Factorization or LU-decomposition
LU factorization is a matrix decomposition which writes a matrix as the product of a
lower triangular matrix and an upper triangular matrix. This decomposition is used to
solve systems of linear equations or calculate the determinant.
Assume A is an m × n matrix that can be row reduced to echelon form, without row
interchanges. Then A can be written in the form A = LU, where L is an m × m lower
triangular matrix with 1’s on the diagonal and U is an m × n echelon form of A. For
instance, such a factorization is called LU factorization of A. The matrix L is invertible
and is called a unit lower triangular matrix.
1 0 0 0   • * * * * 
* 1 0 0  0 • * * * 
A=  
* * 1 0  0 0 0 • * 
  
* * * 1  0 0 0 0 0 
L U

LU factorization.

Remarks
1) If A is the square matrix of order m, then the order of both L and U will also be m.
2) In general, not every square matrix A has an LU-decomposition, nor is an LU-
decomposition unique if it exists.
Theorem If a square matrix A can be reduced to row echelon form with no row
interchanges, then A has an LU-decomposition.
Note
The computational efficiency of the LU factorization depends on knowing L and U. The
next algorithm shows that the row reduction of A to an echelon form U amounts to an LU
factorization because it produces L with essentially no extra work.

An LU Factorization Algorithm
Suppose A can be reduced to an echelon form U without row interchanges. Then, since
row scaling is not essential, A can be reduced to U with only row replacements, adding a

©Virtual University Of Pakistan 175

15- Matrix Factorizations VU

multiple of one row to another row below it. In this case, there exist lower triangular
elementary matrices E 1 , …, E p such that
Ep … E1A = U (1)
-1
So A = (E p …E 1 ) U = LU
Where L = (E p … E 1 )-1 (2)
It can be shown that products and inverses of unit lower triangular matrices are also unit-
lower triangular. Thus, L is unit-lower triangular.

Note that the row operations in (1), which reduce A to U, also reduce the L in (2) to I,
because E p … E 1 L = (Ep…E 1 )(E p … E 1 )-1 = I. This observation is the key to
constructing L.

Procedure for finding an LU-decomposition

Step 1: Reduce matrix A to row echelon form U without using row interchanges, keeping
track of the multipliers used to introduce the leading 1’s and the multipliers used to
introduce zeros below the leading 1’s.

Step 2: In each position along the main diagonal of L, place the reciprocal of the
multiplier that introduced the leading 1 in that position in U.

Step 3: In each position below the main diagonal of L, place the negative of the
multiplier used to introduce the zero in that position in U.

Step 4: Form the decomposition A = LU.

Example 1 Find an LU-decomposition of

6 -2 0 
A =  9 -1 1 
 3 7 5 
Solution We will reduce A to a row echelon form U and at each step we will fill in an
entry of L in accordance with the four-step procedure above.
6 -2 0  * 0 0 
A =  9 -1 1  * * 0 
 
 3 7 5  * * * 
* denotes an unknown entry of L.
1 - 31 0  6 0 0 
  * * 0 
9 -1 1  ← multiplier = 61  
3 7 5  * * * 

1 − 13 0  6 0 0 
  ← multiplier =
−9 9 * 0 
0 2 1  
  ← multiplier =
−3
 3 * * 
0 8 5

©Virtual University Of Pakistan 176

15- Matrix Factorizations VU

1 − 13 0
 6 0 0 
0 1 1  9 2 0 
← multiplier =
1
 
 2 2

0 8  3 * * 
 5 
1 − 13 0  6 0 0 
  9 2 0 
0 1 2  ← multiplier = −8
1
 
0 0 1   
   3 8 *
1 − 13 0  6 0 0 
 
U= 0 1 2  ← multiplier= 1
1
L = 9 2 0 
0 0 1   3 8 1 
 
(No actual operation is performed here since there is already a leading 1 in the third row.)
So
6 0 0  1 − 13 0 
=A LU= 9 2 0  0 1 12 
 3 8 1  0 0 1 

OR
Solution We will reduce A to a row echelon form U and at each step we will fill in an
entry of L in accordance with the four-step procedure above.
6 -2 0  * 0 0 
A =  9 -1 1  * * 0 
 
 3 7 5  * * * 
* denotes an unknown entry of L.
 6 -2 0 
6 6 6  6 0 0 
  1 * * 0 
≈  9 -1 1  R1  
3 7 5 6
* * * 
 
 
 -1 
1 3 0 
 
= 9 -1 1 
3 7 5
 
 

©Virtual University Of Pakistan 177

15- Matrix Factorizations VU

 -1 
 1 3
0

  6 0 0 
R2 − 9 R1 9 * 0 
≈ 9 - 9(1) -1- 9( ) 1- 9(0) 
-1
 3  R3 − 3R1  
   3 * * 
 3 - 3(1) -1
7 - 3( ) 5 - 3(0)
 3 
 -1 
1 3 0
 
= 0 2 1
0 8 5
 
 

 -1 
1 3
0
  6 0 0 
≈
0 2 1 1
R2 9 2 0 
2 2 2 2  
   3 * * 
0 8 5
 
 -1 
1 3 0
 
= 0 1
1
 2
 
0 8 5
 
 -1 
 1 3
0 
  6 0 0 
≈ 0 1
1 
R3 − 8 R2 9 2 0 
 2   
   3 8 * 
0 - 8(0) 1
8 - 8(1) 5 - 8( ) 
 2 
 -1 
1 3 0
 
= 0 1
1
 2
 
0 0 1
 

©Virtual University Of Pakistan 178

15- Matrix Factorizations VU

1 − 13 0 6 0 0 
 
U= 0 1 2  ← multiplier= 1
1
L = 9 2 0 
0 0 1   3 8 1 

So
6 0 0  1 − 13 0 
= = 9 2 0  0 1 12 
A LU
 3 8 1  0 0 1 

2 −4 −2 3 
6 −9 −5 8 

Example 2 Find an LU factorization of A =  2 −7 −3 9 
 
4 −2 −2 −1
 −6 3 3 4 
Solution
 2 −4 −2 3  1 0 0 0 0 
 6 −9 −5 8  * 1 0 0 0 
   
A =  2 −7 −3 9  * * 1 0 0 
   
 4 −2 −2 −1 * * * 1 0 
 −6 3 3 4  * * * * 1 
* denotes an unknown entry of L.
 3 1
1 −2 −1  ← multiplier 2 0 0 0 0

2

2 * 1 0 0 0 
6 −9 −5 8 
2 * * 1 0 0
−7 −3 9  
 
4 −2 −2 −1 * * * 1 0
 −6  * 1 
4 
* * *
 3 3
 3
1 −2 −1 2 0 0 0 0
2 6
  ← multiplier − 6
 1 0 0 0 
0 3 1 −1
0 ← multiplier − 2 2 * 1 0 0
−3 −1 6  
  ← multiplier − 4
0 6 2 −7  4 * * 1 0
0 ← multiplier 6 -6 1 
13 
* * *
 −9 −3

©Virtual University Of Pakistan 179

15- Matrix Factorizations VU

 3 
1 −2 −1
2  2 0 0 0 0
  6 0 
1
0 1 1  ← multiplier  3 0 0
1 − 3
 3 3 2 * 1 0 0
   
0−3 −1 6 
4 * * 1 0
06 2 −7  -6 * * * 1 
 
0−9 −3 13 
 3 
−2 −1
1 2  2 0 0 0 0
  6
0 1 1  3 0 0 0 
1 −
 3 3  ← multiplier 3 2 -3 1 0 0
   
00 0 5  ← multiplier − 6
4 6 * 1 0
00 0 −5  ← multiplier 9 -6 -9 * * 1 
 
00 0 10 
 3 
1 −2 −1 2  2 0 0 0 0
  6
0 1 1 − 1   3 0 0 0 
 3 3  ← multiplier − 1 2 -3 1 0 0
0 0 0 5   5  
 4 6 0 -5 0 
0 0 0 1  -6 -9 0 * 1 
 
0 0 0 10 
 3 
1 −2 −1 2  2 0 0 0 0
  6
0 1 1 − 1   3 0 0 0 
U = 3 3  ← multiplier − 10 L = 2 -3 1 0 0
0 0 0 5   
 4 6 0 -5 0
0 0 0 1  -6 -9 0 10 1 
 
0 0 0 0 
Thus, we have constructed the LU-decomposition
 3
 1 -2 -1
 2 0 0 0 0 2
 6 3 0 0 0  
 
 0 1 1
- 
1
=A LU =  2 -3 1 0 0   3 3
  0 0 0 5 
 4 6 0 -5 0   
-6 -9 0 10 1  0 0 0 1 
 
0 0 0 0 

©Virtual University Of Pakistan 180

15- Matrix Factorizations VU

 6 -2 -4 4 
 3 -3 -6 1 
Example 3 Find LU–decomposition of A =  
-12 8 21 -8 
 
 -6 0 -10 7 

Solution
 6 −2 −4 4 1 0 0 0 
 3 −3 −6 1  * 1 0 0 
A=  L= 
 −12 8 21 −8  * * 1 0 
   
 −6 0 −10 7  * * * 1 
* denotes an unknown entry of L.
 1 2 2 1
 1 − −  ← multiplier 6 0 0 0
3 3 3 6 *
 
 1 0 0 
 3 −3 −6 1 
 −12 8 * * 1 0
21 −8   
  * * * 1
 −6 0 −10 7 

 1 2 2
1 − 3 −  6 0 0 0
3 3  3
  ← multiplier − 3
 1 0 0 
0 −2 −4 −1
0 4 ← multiplier 12  −12 * 1 0
13 0   
  ← multiplier 6  −6 * * 1
0 −2 −14 11

 1 22
1 − 3 −
33  6 0 0 0
  1  3
0 1 1  ← multiplier −  −2 0 0 
2 2
 2  −12 * 1 0
   
0 4 13 0 
 −6 * * 1
0 −2 −14 11

©Virtual University Of Pakistan 181

15- Matrix Factorizations VU

 1 22
1 − 3 −
33  6 0 0 0
   3
0 1 1  −2 0 0 
2
 2  ← multiplier − 4  −12 4 1 0
   
0 0 5 −2 ← multiplier 2
 −6 −2 * 1
0 0 −10 12 
 1 22 
1 − 3 −
33 
   6 0 0 0
1   3
0 1 2  −2 0 0 
 2 
   −12 4 5 0
2  
0 0 1 −  ← multiplier 1
 5  −6 −2 * 1
5
0 0 −10 12 


 1 2 2
1 - 3 - 3 3 
   6 0 0 0
0 1 2 1   3 −2 0 0 
 2 
   −12 4 5 0
0 0 1 - 2  ← multiplier 10  
 5  −6 −2 −10 1
0 0 0 8 
 

 1 2 2 
1 − 3 −
3 3 
   6 0 0 0
1   3
0 1 2 −2 0 0 
U = 2  L=
   −12 4 5 0
2  
0 0 1 −  ← multiplier 1
 5  −6 −2 −10 8
8
0 0 0 1 


 1 2 2 
 1 − −
 6 0 0 0  3 3 3 

 3 1 
 −2 0 0  0 1 2
Thus=
A LU
=  2 
 −12 4 5 0  
  0 0 2
1 −
 −6 −2 −10 8   5
0 0 0 1 


©Virtual University Of Pakistan 182

15- Matrix Factorizations VU

 2 4 −1 5 −2
 −4 −5 3 −8 1 
Example 4 Find an LU factorization of A =  
 2 −5 −4 1 8 
 
 −6 0 7 −3 1 

Solution
 2 4 −1 5 −2 1 0 0 0 
 −4 −5 3 −8 1  * 1 0 0 
A=   L= 
 2 −5 −4 1 8  * * 1 0 
   
 −6 0 7 −3 1  * * * 1 
* denotes an unknown entry of L.
 1 5  1
1 2 − −1 ← multiplier 2 0 0 0
2 2 2 *
 
 1 0 0 
 −4 −5 3 −8 1 
 2 −5 −4 1 8  * * 1 0
   
 −6 0 7 −3 1  * * * 1

 1 5 
 1 2 − −1 2 0 0 0
2 2  −4
  ← multiplier 4
 1 0 0 
0 3 1 2 −3 
0 −9 −3 −4 ← multiplier − 2 2 * 1 0
10   
  ← multiplier 6  −6 * * 1
0 12 4 12 −5 

 1 5 
1 2 − 2 2 −1
2 0 0 0
  1  −4
0 1 1 2  ← multiplier  3 0 0 
−1 3
 3 3  2 * 1 0
   
0 −9 −3 −4 10 
 −6 * * 1
0 12 4 12 −5 

 1 5 
1 2 − −1
2 2 2 0 0 0
   −4 3
0 1 2 0 0 
1 −1 
 3 3   2 −9 1 0
   
0 0 0 2 1  ← multiplier 9
 −6 12 * 1
0 0 0 4 7  ← multiplier − 12

©Virtual University Of Pakistan 183

15- Matrix Factorizations VU

 1 5 
1 2 − −1
2 2 2 0 0 0
 
1 2  −4 3
0 1 −1 0 0 
U = 3 3  L=
   2 −9 1 0
0 0 0 2 1  
 7  −6 12 0 4
1
0 0 0 1 
 4  ← multiplier 4

 1 5 
1 2 − −1
2 0 0  2 2
0 
 −4 3 0 0  0 1
1 2
−1
Thus= = 
A LU  3 3 
 2 −9 0 
1 
1
  0 0 0 2
 −6 12 0 4 
 7
0 0 0 1 
 4

Matrix Inversion by LU-Decomposition

Many of the best algorithms for inverting matrices use LU-decomposition. To understand
how this can be done, let A be an invertible n × n matrix, let A−1 = [ x1 x2  xn ] be
its unknown inverse partitioned into column vectors, and let I = [ e1 e2  en ] be then
n × n identity matrix partitioned into column vectors. The matrix equation AA−1 = I can
be expressed as
A [ x1 x2  xn ] = [ e1 e2  en ]
[ Ax1 Ax2  Axn ] = [ e1 e2  en ]
which tells us that the unknown column vectors of A−1 can be obtained by solving the n-
linear systems.
= Ax1 e= 1 , Ax2 e2 ,=
, Axn en (1*)
As discussed above, this can be done by finding an LU-decomposition of A, and then
using that decomposition to solve each of the n systems in (1*).

Solving Linear System by LU-Factorization

When A =LU, the equation Ax = b can be written as L (Ux) = b. Writing y for Ux, we can
find x by solving the pair of equations; Ly = b and Ux = y (2*)

First solve Ly = b for y and then solve Ux = y for x. Each equation is easy to solve
because L and U are triangular.

©Virtual University Of Pakistan 184

15- Matrix Factorizations VU

Procedure
Step 1: Rewrite the system A x = b as LU x = b (3*)

Step 2: Define a new unknown y by letting U x = y (4*)

And rewrite (3*) as L y = b

Step 3: Solve the system L y = b for the unknown y.

Step 4: Substitute the known vector y into (4*) and solve for x.

This procedure is called the method of LU-Decomposition.

Although LU-Decomposition converts the problem of solving the single system A x = b

into the problem of solving the two systems, L y = b and U x = y, these systems are easy
to solve because their co-efficient matrices are triangular.

Example 5 Solve the given system (Ax =b) by LU-Decomposition

2 x1 + 6 x2 + 2 x3 =
2
−3 x1 − 8 x2 =
2 (1)
4 x1 + 9 x2 + 2 x3 =
3

Solution We express the system (1) in matrix form:

 2 6 2   x1   2 
 −3 −8 0   x  =  
   2   2
 4 9 2   x3   3 
A x = b
We derive an LU-decomposition of A.
 2 6 2 1 0 0 
 3 −8 0 
A =− L =* 1 0 
 
 4 9 2  * * 1 

 1 3 1 2 0 0
 −3 −8 0  ← multiplier 1 * 1 0
  2  
 4 9 2   * * 1 
1 3 1 2 0 0
 1 3  ← multiplier 3  1 0 
0  −3
0 −3 −2  ← multiplier − 4  4 * 1 
1 3 1 2 0 0
0 1 3 ← multiplier 3  −3 1 0 
 
0 0 1  4 −3 1 

©Virtual University Of Pakistan 185

15- Matrix Factorizations VU

1 3 1  2 0 0
0 1 3 ← multiplier 1
U=  −3 1 0 
L=
  7  
0 0 1  4 −3 7 

 2 6 2  2 0 0  1 3 1
Thus  −3 −8 0  =−  1 0  0 1 3 (2)
   3
 4 9 2   4 −3 7  0 0 1
A = L U
From (2) we can rewrite this system as
 2 0 0  1 3 1  x1   2 
 −3 1 0  0 1 3  x2  =
2 (3)
   
 4 −3 7  0 0 1  x3   3 
L U x = b
As specified in Step 2 above, let us define y 1 , y 2 and y 3 by the equation
1 3 1  x1   y1 
 0 1 3  x  =  y  (4)
  2  2
0 0 1  x3   y3 
U x = y
which allows us to rewrite (3) as
 2 0 0   y1   2 
 −3 1 0   y  =   (5)
   2  2
 4 −3 7   y3   3 
L y = b
2 y1 =2
or equivalently, as −3 y1 + y2 =
2
4 y1 − 3 y2 + 7 y3 =
3

This system can be solved by a procedure that is similar to back substitution, except that
we solve the equations from the top down instead of from the bottom up. This procedure,
called forward substitution, yields
y 1 = 1, y 2 = 5, y 3 = 2.
As indicated in Step 4 above, we substitute these values into (4), which yields the linear
system
1 3 1  x1  1 
 0 1 3  x  =  5 
  2  
0 0 1  x3   2 

©Virtual University Of Pakistan 186

 15- Matrix Factorizations VU

x1 + 3 x2 + x3 =
1
or equivalently, x2 + 3 x3 =
5
x3 = 2

Solving this system by back substitution yields x 1 = 2, x 2 = –1, x 3 = 2

Example 6 It can be verified that

 3 −7 −2 2  1 0 0   3 −7 −2 2 
0
 −3 5 1 0   0  0 −2 −1 2 
= A =    −1 1 0
= LU
 6 −4 0 −5  2 −5 0  0 0 −1 1 
1
    
 −9 5 −5 12   −3 8 1  0 0 0 −1
3
 −9 
5
Use this LU factorization of A to solve Ax = b, where b =  
7
 
 11 
Solution The solution of Ly = b needs only 6 multiplications and 6 additions, because the
arithmetic takes place only in column 5. (The zeros below each pivot in L are created
automatically by our choice of row operations.)

 1 0 0 0 −9  1 0 0 0 −9 
 −1 1 0 0 5  0 1 0 0 −4 
[ L b] =   [I y]
 2 −5 1 0 7  0 0 1 0 5 
   
 −3 8 3 1 11  0 0 0 1 1 

Then, for Ux = y, the “backwards” phase of row reduction requires 4 divisions, 6

multiplications, and 6 additions. (For instance, creating the zeros in column 4 of [U y]
requires 1 division in row 4 and 3 multiplication – addition pairs to add multiples of row
4 to the rows above.)
 3 −7 −2 2 −9  1 0 0 0 3  3
0 −2 −1 2 −4  0 1 0 0 4  4
[U y ] =      , x  
0 0 −1 1 5  0 0 1 0 −6   −6 
     
0 0 0 −1 1  0 0 0 1 −1  −1

To find x requires 28 arithmetic operations, or “flops” (floating point operations),

excluding the cost of finding L and U. In contrast, row reduction of [A b] to [I x] takes
62 operations.

Numerical Notes
The following operation counts apply to an n × n dense matrix A (with most entries
nonzero) for n moderately large, say, n ≥ 30.

©Virtual University Of Pakistan 187

15- Matrix Factorizations VU

1. Computing an LU factorization of A takes about 2n3/3 flops (about the same as

row reducing [A b]), whereas finding A-1 requires about 2n3 flops.
2. Solving Ly = b and Ux = y requires about 2n2 flops, because n × n triangular
system can be solved in about n2 flops.
3. Multiplication of b by A-1 also requires about 2n2 flops, but the result may not be
as accurate as that obtained from L and U (because of round off error when
computing both A-1 and A-1b).
4. If A is sparse (with mostly zero entries), then L and U may be sparse, too,
whereas A-1 is likely to be dense. In this case, a solution of Ax = b with an LU
factorization is much faster than using A-1.

Example 7(Gaussian Elimination Performed as an LU-Decomposition)

In Example 5, we showed how to solve the linear system
2 6 2   x1   2 
 −3 −8 0   x  =  
   2   2 (6)
 4 9 2   x3   3 
using an LU-decomposition of the coefficient matrix, but we did not discuss how the
factorization was derived. In the course of solving the system, we obtained the
1 
intermediate vector y =  5  by using forward substitution to solve system (5).
 2 
We will now use the procedure discussed above to find both the LU-decomposition and
the vector y by row operations on the augmented matrix for (6).
 2 6 2 2 * 0 0 
 
 A b  =  −3 −8 0 2  * * 0  = L (* = unknown entries )
 
 4 9 2 3  * * * 
 1 3 1 1 2 0 0
 −3 −8 0 2  * * 0
   
 4 9 2 3   * * * 

1 3 1 1   2 0 0
   
0 1 3 5   −3 * 0 
0 −3 −2 −1  4 * * 

1 3 1 1   2 0 0
0 1 3 5   −3 1 0 
   
0 0 7 14   4 −3 * 

©Virtual University Of Pakistan 188

15- Matrix Factorizations VU

1 3 1 1   2 0 0
= 
U y  0 1 3 5 =  −3 1 0  L
 
0 0 1 2   4 −3 7 

These results agree with those in Example 5, so we have found an LU-decomposition of

the coefficient matrix and simultaneously have completed the forward substitution
required to find y.

All that remains to solve the given system is to solve the system Ux = y by back
substitution. The computations were performed in Example5.

A Matrix Factorization in Electrical Engineering

Matrix factorization is intimately related to the problem of constructing an electrical
network with specified properties. The following discussion gives just a glimpse of the
connection between factorization and circuit design.

Suppose the box in below Figure represents some sort of electric circuit, with an input
v 
and output. Record the input voltage and current by  1  (with voltage v in volts and
 i1 
v 
current i in amps), and record the output voltage and current by  2  . Frequently, the
 i2 
v  v 
transformation  1  →  2  is linear. That is, there is a matrix A, called the transfer
 i1   i2 
v  v 
matrix, such that  2  = A  1 
 i2   i1 

i1 i2

input v1 electric v2 output

terminals circuit terminals

Figure A circuit with input and output terminals.

Above Figure shows a ladder network, where two circuits (there could be more) are
connected in series, so that the output of one circuit becomes the input of the next circuit.
The left circuit in Figure is called a series circuit, with resistance R 1 (in ohms);

The right circuit is a shunt circuit, with resistance R 2 . Using Ohm’s law and Kirchhoff’s
laws, one can show that the transfer matrices of the series and shunt circuits, respectively,
are:

©Virtual University Of Pakistan 189

15- Matrix Factorizations VU

1 − R1   1 0
0 1  and  −1/ R 1 
   2 
Transfer matrix Transfer matrix
of series circuit of shunt circuit

Example 8
a) Compute the transfer matrix of the ladder network in the above Figure .
 1 −8
b) Design a ladder network whose transfer matrix is  .
 −0 ⋅ 5 5 
Solution
a) Let A 1 and A 2 be the transfer matrices of the series of the series and shunt circuits,
respectively. Then an input vector x is transformed first into A 1 x and then into
A 2 (A 1 x). The series connection of the circuits corresponds to composition of linear
transformations; and the transfer matrix of the ladder network is (note the order)
 1 0  1 − R1   1 − R1 
= A2 A1 =      (6)
 −1/ R2 1  0 1   −1/ R2 1 + R1 / R2 
 1 −8
b) We seek to factor the matrix   into the product of transfer matrices, such
 −0 ⋅ 5 5 
as in (6). So we look for R 1 and R 2 to satisfy
 1 − R1   1 −8
 −1/ R 1 + R / R  =  −0 ⋅ 5 5 
 2 1 2  
From the (1, 2) – entries, R 1 = 8 ohms, and from the (2, 1) – entries, 1/R 2 = 0.5 ohm and
R 2 = 1/0.5 = 2 ohms. With these values, the network has the desired transfer matrix.
Note
A network transfer matrix summarizes the input-output behavior (“Design
specifications”) of the network without reference to the interior circuits. To physically
build a network with specified properties, an engineer first determines if such a network
can be constructed (or realized). Then the engineer tries to factor the transfer matrix into
matrices corresponding to smaller circuits that perhaps are already manufactured and
ready for assembly. In the common case of alternating current, the entries in the transfer
matrix are usually rational complex-valued functions. A standard problem is to find a
minimal realization that uses the smallest number of electrical components.

©Virtual University Of Pakistan 190

 15- Matrix Factorizations VU

Exercises
Find an LU factorization of the matrices in exercises 1 to 8.

 3 −1 2 
2 5  −3 −2 10 
1.  −3 −4  2.
 
   9 −5 6 

1 3 −5 −3
 3 −6 3   −1 −5 8
 6 −7 2   4 
3. 4.
   4 2 −5 −7 
 −1 7 0   
 −2 −4 7 5 

 2 −6 6 
 −4 5 −7 
 2 −4 4 −2   
5.
 6 −9 7 −3 6.  3 5 −1
   
 −1 −4 8 0   −6 4 −8 
 8 −3 9 

2 −4 −2 3 
 1 4 −1 5  6
 3 7 −2 9   −9 −5 8 
7.   8. 2 −7 −3 9 
 −2 −3 1 −4   
  4 −2 −2 −1
 −1 6 −1 7   −6 3 3 4 

Solve the equation Ax = b by using LU-factorization.

 3 −7 −2   −7   4 3 −5 2
A=       4
 −3 5 1  , b =
5 A =−
 4 −5 7  , b =−
9. 10.
 
 6 −4 0   2   8 6 −8  6 

 2 −1 2  1   2 −2 4  0
A=       −5
 −6 0 −2  , b =
0  A=
1 −3 1  , b =
11. 12.
 
 8 −1 5   4   3 7 5   7 

 1 −2 −4 −3 1  1 3 4 0 1
 2 −7 −7 −6  7   −3 −6 −7 2   −2 
=13. A =  ,b  
= 14. A =  ,b  
 −1 2 6 4 0  3 3 0 −4   −1
       
 −4 −1 9 8  3  −5 −3 2 9  2

©Virtual University Of Pakistan 191