MTS2A1

Komputer & Simulasi

Bagian I – Aljabar Matrix

Dr. Nurly Gofar

Dr. Alfrendo Satyanaga
Program Studi Teknik Sipil
Program Pascasarjana
Universitas Bina Darma Palembang
1
 Kuliah 4:
Matrix Multiplication
❖ The product of two matrices B and C (in this order) is
defined as
Am×n = Bm×p Cp×n
Note the product is only defined (or exist) when the
second dimension of B (no. of columns) is the same as
the first dimension of C (no. of rows).
The element of matrix A is determined as
p
a jk =  b ji cik , j = 1 to m, k = 1 to n.
i=1
Why is matrix multiplication defined in this way?
(Linear Transformation) 2
 p
a jk =  b ji cik = b j1c1k + b j 2 c2k +  + b jp c pk
i=1
j = 1 to m, k = 1 to n
That is, to get ajk, multiply each entry in the jth row of B by
the corresponding entry in the kth column of C and then add
these p products.
 b11 b12 ... b1 p 
b b22 ... b2 p  c11 c12 ... c1k ... c1n 
 21   ... . ...
 . ... .   c 21 c22 ... c2k ... c2n
 = ... a jk ...
.
  . . ... . ... .  
b
 j1 b j2 ... b jp 
  ... . ...
 . . ... .  cp1 c p 2 ... c pk ... c pn 
 
bm1 bm2 ... bmp 
3

Multiplication of rows into columns

EXAMPLE
4 3  4 2 + 31 4 5 + 3 6  11 38
   2 5  = 16 47
BC = 7 2 =
1 6  7  2 + 21 7  5 + 2 6   
9 0 92 + 01 9 5 + 0 6 18 45

4 3
 2 5  
7 2
CB =  
 1 6   = undefined
9 0
EXAMPLE
4 3 2 5 11 38
BC =     =
7 2  1 6 16 47
2 5 4 3 43 16
CB =   
6  7
=
  BC 4

1 15
Properties of matrix multiplication
AB is not necessarily equal to BA
AB = 0 does not necessarily imply
that A = 0, B = 0, or BA = 0

AC = AD does not necessarily imply that C = D

AI = A = IA
(kA)B = k(AB) = A(kB) = kAB
A(BC) = (AB)C = ABC
(A+B)C = AC + BC; C(A+B) = CA + CB
(AB)T =BTAT (AB···PQ)T =QTPT ··· BTAT
5
1 1  −1 1  0 0
2 2  1 −1 = 0 0
    

−1 1  1 1  1 1
 1 −1 2 2 = −1 −1
    

1 1 2 1 4 3 1 1  3 0
2 2 2 2 = 8 6 = 2 2 1 3
       

6
EXAMPLE
4 9
 3 7
A = 0 2 B= 
2 8
1 6
4 9 30 100 
T

   3 7 T  4 16  =  30 4 15
(AB) = ( 0 2 
T ) =
2 8   100 16 55
1 6 15 55 
T 4 9
T

3 7     3 2   4 0 1
BTAT =    0 2 =    
2 8  1 6  7 8  9 2 6 
 
 30 4 15
=
16 55
Thus, BTAT = (AB)T
100 7
(AB)T =BTAT

(AB···PQ)T =QTPT ··· BTAT

8
❖Remarks: If the order of the factors in a product of matrices
is changed, the product matrix may change (or may not exist
at all!). Ignoring this is the source of many errors.

For example when multiplying a matrix equation B = C by

another matrix A, care must be taken to multiply B and C on
the same side by A.

Pre-multiplication AB = AC
Post-multiplication BA = CA

9
Example
If A, B and C are matrices such that AB = I and
CA = I, show that B = C.
Solution:

10
 2. Linear Equations
Example: (charity investment) A charity wishes to endow a
fund that will provide $50, 000 per year for cancer research.
The charity has $480, 000 and, to reduce risk, wants to
invest in two assets with returns 10% and 15% respectively.
How much should be invested in each asset?
Solution: Let x and y be the amount invested in the assets
earning 10% and 15%, respectively. Then
x + y = 480, 000
0.1x + 0.15y = 50, 000
The solution is x = 440, 000 and y = 40, 000.

What if the number of equations becomes very large?

11
❖ A linear equation in n variables x 1, x 2 ,..., x n is an
equation of
a1x1 + a 2 x 2 +  + a n x n = b
A solution is a set of x i ,i = 1,2,..., n which satisfies the
above equation.
❖ A system of linear equations is a finite list of linear
equations, i.e.
a11x1 + a 12 x 2 +  + a1n x n = b1
a 21 x 1 + a 22 x 2 +  + a 2n x n = b2
                             
a m1x 1 + a m2 x 2 +  + a mn x n = bm
12
The above equations can be written in matrix form as

 a11 a12 ... a1n   x1   b1

a  x  b 
 21 a22 ... a2n   2 =  2
 . . ... .  . .
a  x  b 
 m1 am2 ... amn   n  m
OR Ax = b

coefficient matrix variable vector constant vector

A solution is a set of x i ,i = 1,2,..., n which satisfies all
the m equations. The heart of linear algebra is a routine
procedure for finding all solutions to any system of linear
equations. 13
Geometry and solutions of system of equations
❖ A system of two linear equations
✓ A linear equation in two variables can be interpreted
as a line in the plane.
✓ A system of equations in two variables is a set of
such lines.
✓ A solution to the system of equations is then a point
which lies on all the lines, i.e. satisfy all the equations.

14
A Unique solution – The lines intersect in a single point.
x1 + x 2 = 1
x1 − x 2 = −0.5
Multiple solutions – The lines are identical, i.e. intersect at
infinite points.
x1 + x 2 = 1
2x 1 + 2x 2 = 2
No solution – The lines don’t intersect (i.e. parallel lines).
x1 + x 2 = 1
2x 1 + 2x 2 = 0
15
❖ The linear equations come in two forms:
Ax = b  0 ‘non-homogeneous’ equations
Ax = b = 0 ‘homogeneous’ equations
❖ For non-homogeneous equations, there are three possible
types of solutions:
A unique solution, Multiple solutions, No solution at all

while for homogeneous equations, only two possible

types of solutions:
A unique solution, Multiple solutions (why?)

How to systematically determine the solution of a

linear system?
16
 Gauss Elimination (GE) for Solving
Linear Equations
❖ The linear system of equations can be written as
Ax = b, where

 a11 a12 ... a1n   x1   b1

a a 
... a2n  x  b 
 21 22  2  2
x= b=
A=  . . ... .  . .
a  x  b 
 m1 am2 ... amn   n  m

17
Further, an augmented matrix is defined as A , i.e.

 a11 a12 ... a1n b1

a a22 ... a2n b2 
 21  = [A|b]
A= 
. . ... . .
a 
bm 
 m1 am2 ... amn
A has the dimension of m(n+1).
Solution of Ax = b by row operation
The basis of the GE solution method is the row operation on
the augmented matrix. There are three types of row operations
which will not change the solutions of the linear equations.
✓ Interchange two rows
✓ Multiply one row by a constant
✓ Add a multiple of one row to another row 18
❖ The above three operations are called elementary (row)
operations on the linear system. Elementary row
operations do not change the solutions of the system.

All the following row operations do not change the solutions.

x1 − x 2 = −3 Interchange rows x1 + 2x 2 = 1
x1 + 2x 2 = 1 x1 − x 2 = −3
x1 − x 2 = −3 Multiplying row 1 by 3 3x1 − 3x 2 = −9
x1 + 2x 2 = 1 x1 + 2x 2 = 1

x1 − x 2 = −3 (row 1) x 2 + row 2 → x1 − x 2 = −3
row 2
x1 + 2x 2 = 1 3x1 + 0 = −5
19
 Theorem:
If an elementary operation is performed on a
linear system, the resulting system is equivalent
to the original system.

❖ This theorem has profound consequences for linear

algebra. It allows us to apply a series of elementary
operations to the system with the goal of finding a
system that is easy to solve. This is the idea of
Gaussian Elimination (GE).

20
Algorithm of Gaussian Elimination (GE)

✓ Form the augmented matrix as [A|b]

✓ Eliminate the 1st element of each row except row 1
by row operation.
✓ Eliminate the 2nd element of each row except rows 1
and 2 by row operation.
✓ Eliminate the (m-1)th element of each row except rows
1,2,…,m-1.
✓Determine xm from the last row, then work backwards
to get all other variables.

21
EXAMPLE GE with unique solution

 1 1 1   x1   24 
 4  x  148
6 10
   2 =   (1)
1/2 1/ 4 1/ 3 x3   9 

 1 1 1 24 
 4 (row 2)/ 2 → row 2
6 10 148 
[A|b] =   (row 3)x12 → row 3
1/ 2 1/ 4 1/ 3 9 

row 2+(row 1)x (-2)

1 1 1 24  1 1 1 24 
2 3 5 74  → row 2
0 1 
  row 3+(row 1)x (-6) 
3 26

6 3 4 108 → row 3 0 − 3 − 2 − 36
22
1 1 1 24  row 3 + (row 2)x 3 1 1 1 24
0 1  → row 3 0 1 3 26 
3 26
   
0 − 3 − 2 − 36 0 0 7 42

1 1 1   x1  24
i.e. 0 1 3   x  26
   2 =   (2)
0 0 7  x3  42
So the solutions of (1) and (2) are the same, after many row
operations.
From the last equation of (2), 7x 3 = 42  x 3 = 6
By back-substitution, x 2+ 3 6 = 26  x 2 = 8
x1 + 8 + 6 = 24  x1 = 10
23
EXAMPLE GE with multiple solutions
 x1 
 3 2 2 −5  x   8 
0.6 1.5 1.5 − 5.4   2  2.7
   x3  =  
2.4 − 0.2 − 0.1 1.4     2.1
x4 
 3 2 2 −5 8 
[A|b] = 0.6 1.5 1.5 − 5.4 2.7
 
2.4 − 0.2 − 0.1 1.4 2.1
(row 2) + (row 1)x(-0.6/3) 3
 2 2 −5 8 
→ row 2
0 1.1 1.1 − 4.4 1.1 
(row 3) + (row 1)x(-2.4/3)  
→ row 3 
 0 −1.8 −1.7 5.4 − 4.3
49
24
 (row 3)+ (row 2)x(1.8/1.1) 3 2 2 −5 8 
→ row 3 0 1.1 1.1 − 4.4 1.1 
 
0 0 0.1 −1.8 − 2.5
The last augmented matrix represents the following equations:

 x1 
3 2 2 −5  x   8 
0 1.1 1.1 − 4.4 
   2  =  1.1 
 x3   
0 0 0.1 −1.8   x  −2.5
 4
Here, three equations with four unknowns, so there will be
multiple solutions.
25
Let x 4 be an arbitrary value, i.e. x 4 =
Therefore for a given value of x 4 , the three equations are
sufficient to determine the remaining three unknowns.
From the third equation,
0.1x 3 −1.8  = −2.5  x 3 = −25 +18 
Back-substitute to obtain x 2 = 26 −14  , x1 = 2 − 

The solutions can be expressed as

 x1   2   − 1
 x   26  −14
2
x=  = − 25 +   18  where  can be any value.
 x3   
 x   0   1 
 4
26
EXAMPLE GE with no solution

 3 2 1  x1  3
 2 1 1   x  0
   2 =  
6 2 4 x3  6

 3 2 1 3 (row 2) + (row 1)x(-2/3)

  → row 2
[A|b] = 2 1 1 0
  (row 3) + (row 1)x(-2)
6 2 4 6 → row 3

3 2 1 3  (row 3) + (row 2) 3 2 1 3
0 −1/ 3 1/ 3 − 2 x(-6) → row 3 0 −1/ 3 1/ 3 − 2
   
0 − 2 2 0  0 0 0 12 
27
 3 2 1 3
0 −1/ 3 1/ 3 − 2
 
0 0 0 12 

The last row represents an impossible equation, i.e.

0 x1 + 0 x 2 + 0 x 3 = 12
Thus, no set of values x 1 , x 2 and x 3 exists which satisfies
all the three equations.

28
Summary
In summary, the augmented matrix corresponding to a set of
linear equations after row operations becomes a triangle-type
of matrix (called echelon form) as (A4x4 for example):

= [A|b] (a f j ≠ 0)

If p = q = 0 multiple solutions
If p =0, q ≠ 0 no solution
If p ≠ 0 unique solution
The above conclusions can be further illustrated
using the concept of rank (dijelaskan pada sesi
29
yang akan datang
 Partial Pivoting
The standard procedure of GE is to use row operation to
make the augmented matrix into triangle-type matrix. In the
process, the off-diagonal entries can be eliminated using
(row k) + (row i) x (-aki/aii) → row k

 3 2 1 3 (row 2) + (row 1)x(-2/3) k=2,i=1

[A|b] = 2 1 1 0 → row 2
  (row 3) + (row 1)x(-2)
k=3,i=1
6 2 4 6 → row 3
pivot
3 2 1 3  (row 3) + (row 2)
0 −1/ 3 1/ 3 − 2 x(-6) → row 3
 
0 − 2 2 0  k=3,i=2
30
In order to avoid entries becoming too big during GE, the
factor (aki/aii) should be kept small. Partial pivoting is to make
the diagonal entries aii (absolute value) as big as possible.
EXAMPLE
0.0004 1.402 1.406  10
[A|b] =  Solution is  1

0.4003 −1.502 2.501  
Examine column 1. 0.4003 is the bigger number. So
exchange row 1 with row 2 to make 0.4003 at the diagonal.
(row 2) - (row 1)x
0.4003 −1.502 2.501 (0.0004/0.4003)→ row 2
0.0004 1.402 1.406 
 

31
 0.4003 −1.502 2.501 
 0   x 2 = 1, x1 = 10
 −1.404 −1.404 
If there is no pivoting
(row 2) - (row 1)x
0.0004 1.402 1.406  (0.4003/0.0004)→ row 2
0.4003 −1.502 2.501
 
0.0004 1.402 1.406  
 0 
x 2 = 0.9993, x 1 = 12.5
 −1405 −1404  Solution not accurate

Do partial pivoting only when (1) it is required (2) pivot is less

than 1/100 of the elements to be eliminated.
32