Matrices

Discrete Mathematical Structures:

Theory and Applications
 Matrices and Modeling
• A matrix (plural: matrices, not matrixes) is a
rectangular array of numbers such as

1 2 3 6000 
2 3 2 7000
 
1 1 2 4000
• Matrices are useful when modeling a variety
of real-life problems, and are the abstract
mathematical counterparts of array data
structures in programming. 2
 Matrix Entries
• In this section we show how to add and multiply
matrices.
• We shall identify the numbers inside a matrix by
their position. In matrix

 1 2 0
A=   3 4 3
 
• we may describe the number 1 as “the entry in
the first row, first column”, or more tersely write
a11 = 1. 3
 Matrix Entries
• Similarly a12 = 2 is the entry in the first row,
second column.
• Matrices come in different sizes. Since A has two
rows and three columns, we call A a 2×3 or
“2 by 3” matrix.
• The size of a matrix determines what other
matrices it can be added to or multiplied with.
• Matrices are equal if they have the same size and
their corresponding entries are equal. 4
 Addition
• Two matrices A and B of the same size can be
added together and the sum A+B is obtained
by adding the corresponding entries.
• For example

1 0   3 6  4 6
 0 2   5  3  5  1
     
2  1  0 1  2 0

5
 Addition
• However, the sum

 1 0  1 3 4 
 0 2   2 2 5
   
2  1 3 1 6

is not defined, since the first matrix is 3×2 but

the second is 3 × 3.

6
 Scalar Multiplication
• To multiply a matrix A by a scalar c just means
that c is some real number and that we
multiply every entry in A by c.
• Let
1 6 
A = 
1  2 0 
and let c = 2 , then
1 
2 3
1
A 
2  
1 0 7
 Difference
• The difference A - B of two matrices of the
same size is just another way of writing
A + (-1)B:

1 6    1 4   1 6    1 4  2 2
2 0   0 3  2 0  (1)  0 3  2  3
         

8
 Matrix Multiplication
• If A is a k × m matrix and B is an m × n matrix,
then the product C = AB is the k×n matrix whose
entries are found as follows:
• To calculate cij, take row i from matrix A and
column j from matrix B, multiply the corresponding
entries together, and add up the results.
• Note that AB is defined iff the number of columns
of A matches the number of rows of B.
9
 Matrix Multiplication
• For example
1 6  0 4
2 5 2 2
  
3 4  4 0

is undefined, because the matrices to be

multiplied are 3 × 2 and 3 × 2.
• So it is possible to have two matrices that can
be added but not multiplied together.
10
 Examples of Products
0 
1 2    6
 3
where the matrices to be multiplied are 1 × 2
and 2 × 1, so that multiplication is defined and
the product is 1 × 1.
 3 1  3  0  1  2 3  (1)  1  4 
2 0 0  1  2  0  0  2 2  (1)  0  4
  2 4   
 2 1    2  0  1  2 2  (1)  1  4 

11
 Examples of Products

2 1
 0  2
 2 2 

where the matrices to be multiplied are 3 × 2

and 2 × 2, so that multiplication is defined and
the product is 3 × 2.

12
 Representing Systems of
Equations
• Here is another use for products. The system
of linear equations
2x - 3y = 5
4x + y = 0
can be represented compactly by the matrix
equation:
2  3  x  5
 4 1   y   0
    

13
 Representing Systems of
Equations

which is of the form

AX = B
where
2  3  x 5 
A  , X  ,B 
4 1   y 0 

14
 Solving Linear Equations
• In this section we show how matrices arise
when solving systems of linear equations.

• Key concepts in this section: system of linear

equations, augmented matrix, coefficient
matrix, elementary transformation, echelon
form, rank of a matrix.

15
 Echelon Form
• Assume that we have the following system of
equations to solve:
x + 2y + 3z = 6000
2x + 3y + 2z = 7000
x + y + 2z = 4000

• but it is unclear what values of x, y, and z

would satisfy the equations.
16
 Echelon Form
• So we transform this system into a new system which
has the same solutions but is easier to solve.
• If the new system is in echelon form it is easy to solve:
x + 2y + 3z = 6000
y + 4z = 5000
3z = 3000
• Now z = 1000 and back-substituting gives
y = 5000-4000 = 1000 and
x = 6000-2000-3000 =1000.
17
 Matrix Representation
• Suppose we are going to transform the system
of equations into a new system in echelon form.
• It will reduce the labour if we simplify the
representation.
• Instead of writing down the equations, we write
down just the coefficients of the unknowns on
the left and the constants on the right, giving us
the augmented matrix of the system.
18
 Matrix Representation
• So from the system
x + 2y + 3z = 6000
2x + 3y + 2z = 7000
x + y + 2z = 4000
• we get the augmented matrix
1 2 3 6000 
2 3 2 7000
 
1 1 2 4000
19
 Elementary Transformations
We can change a system of equations into a
new system with the same solutions:
• by swapping equations
or
• by multiplying through by a nonzero number
or
• by adding one equation to another.
• In terms of the augmented matrix, this means
we may:
20
 Elementary Transformations
• interchange two rows: Rj ↔ Rk
• multiply through by a nonzero number:
Rj ⟶ c × Rj
• add one row to another row: Rj ⟶ Rj + Rk.
• In fact, we often combine the last two
transformations so as to add a multiple of one
row to another row:
• Rj ⟶ Rj + c × Rk
21
 Example
• The system of linear equations gives
1 2 3 6000 
2 3 2 7000
 
1 1 2 4000
• R2 ⟶ R2 - 2R1 and then R3 ⟶ R3 – R1 give
1 2 3 6000 
0  1  4  5000
 
0  1  1  2000 
22
 Example
• R2 ⟶ (-1) R2 and then R3 ⟶ R3 + R2 give
1 2 3 6000 
0 1 4 5000
 
0 0 3 3000 
• This matrix represents the system of equations
x + 2y + 3z = 6000
y + 4z = 5000
3z = 3000
23
 Example
with solutions x = 1000, y = 1000, and z = 1000.

• By using elementary transformations to reduce

the augmented matrix to echelon form.
• We get a new system of equations with the
same solutions as the original system.
• The technique is called Gaussian elimination.

24
 Coefficient Matrix
• The coefficient matrix of the linear system :
x + 2y + 3z = 6000
2x + 3y + 2z = 7000
x + y + 2z = 4000
is the matrix in which only the values of the
coefficients of the unknowns are displayed:
1 2 3 
 2 3 2
 
1 1 2
25
 Rank
• The rank of a matrix is the number of nonzero
rows left after the matrix has been reduced to
echelon form.
• The only way for a system to have no solutions
is for the augmented matrix in echelon form
to have as its last nonzero row
[0 … 0 c] with c ≠ 0.
• Why?
26
 No Solutions?
• Because when the augmented matrix of a
system of linear equations in n unknowns is
reduced to echelon form and the last row is of
the form
[0 … 0 c] with c ≠ 0
so that the corresponding equation is
0 x1 + …+ 0 xn = c
• which has no solution, because no matter
what values we substitute for the unknowns.
27
 Rank
• The rank of the augmented matrix in this case
is greater than the rank of the coefficient
matrix.
• So if the ranks are equal, it means that this
case cannot arise.
• A system of linear equations has a solution iff
the rank of the augmented matrix is equal to
the rank of the coefficient matrix.
28
 Infinitely Many Solutions
• Suppose our model was initially the system
x + 2y + 3z = 6000
2x + 3y + 2z = 7000
3x + 5y + 5z = 13000
• which we reduced to echelon form to get
x + 2y + 3z = 6000
y + 4z = 5000
0=0
29
 Infinitely Many Solutions
• So if the rank of the augmented matrix is equal
to the rank of the coefficient matrix and the
last row of the augmented matrix has only zero
coefficient
[0 …0 0]
• Then the system has infinitely many solutions,
since the final equation is
0x1 + …+ 0xn = 0
• so no matter what value we substitute for the
last unknown xn ,we can find a solution. 30
 Infinitely Many Solutions
• Instead of a unique value for z, we can let z be
any real number t, and then get values for y and
x in terms of t, namely y = 5000 - 4t and
x = 6000 - 2(5000 - 4t) - 3t = 5t - 4000.
• We can produce specific solutions by giving t
specific values such as t = 0 (so that x = -4000,
y = 5000, and z = 0) and t = 1 (so that x =-3995,
y = 4996, and z = 1).
31
 Definition
Identity Matrix: a 2 X 2 identity matrix is

1 0
I = 
0 1
What is an identity matrix?
Example:
 2 1  1 0  2 1 Which is identical to
 4 3  0 1  =  4 3 the first one.
    
32
 Definition
The Determinant of a 2 X 2 matrix A where
a c 
A=  
b d 
is the number ad – bc.
a c 
 
b d 
Some Notation: det(A) = ad – bc
33
 Example

 3 4
A=  
7 1
Find the determinant of A

Det(A) =3x1 – 7x4

Det(A) = - 25
34
 Definition
The inverse of a matrix A, written A-1, is the
matrix such that:
A A-1 =  = A-1A
a c  a and d change position

If A =  
b d 
then A =
-1 1  d c 
ad  bc  b a


The determinant of A c and b change
sign
35
35
 To find the inverse of a matrix
Step 1: Exchange the elements in the leading
diagonal.

Step 2: Change the sign of the other two

elements.

Step 3: Multiply by the reciprocal of the

determinant.

36
 Example
 1 3 
P=   Find P-1
 1 2 
 2 3  Exchange the elements in the
Step 1:   leading diagonal
 1 1
 2 3  Change the sign of the other two
Step 2:   elements.
 1 1 

Step 3: det(P) = -1x2– (-1)x3 = 1

1  2 3   2 3 
P-1 =   =  
1  1 1   1 1 
37
 check
To check if the answer is correct:
P P-1 = I

 1 3   2 3   1 2  3 1 1  3  3  1 
   =  1 2  2 1 1  3  2  1
 1 2   1 1   
1 0
=  
0 1
Yes! It is correct.
38
 What Use Are Inverse Matrices?
• Consider the system of linear equations
2x + 2y = 4
1
2 x+y=3
• which can be written as a matrix equation

2 2
   x 4
      
1    
1  y 3

2 


39
 What Use Are Inverse Matrices?
• If A-1 exists, then a matrix equation AX = B has
the solution X = A-1 B, since we may multiply
from the left by A-1 on both sides of AX = B to
get A-1 AX = A-1 B, and A-1 AX = IX = X.
• In the case of our example we know A-1 and so
 1  2
 x   4  46    2
 y   1    
3 
 2  6
 
4 
   2     

 2 


• so that x = -2 and y = 4.
40
 Applications: Cryptology
Matrix inverses can be used to encode and
decode messages.
To start: Set up a code.
The letters of the English alphabet are given
corresponding numbers from 1-26.
The number 27 is used to represent a space
between words.
ABC DEFGHI J K L MN OP QR S TUVWX Y Z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
41
 Secret Code
In this code, the words
SECRET CODE is given by:
19 5 18 5 20 27 3 15 4 5

27 represents the space between the words.

Any 2X2 matrix, with positive integers and

where the inverse matrix exists, can be used
as the encoding matrix.
42
  4 3
Let’s use A =   as the encoding matrix.
 1 1

To encode the message SECRET CODE, we

need to create a matrix with 2 rows.
 19 3 5 27 15 5
 
 5 18 20 3 4 ?
The last entry is blank, so we enter 27 for a
space.
 19 3 5 27 15 5
 
 5 18 20 3 4 27

We are now ready to encode the message. 43

 To encode the message, multiply by A:

Encoding  4 3   193 5 27 15 5 
   
matrix first  1 1   518 20 3 4 27 
 91 66 80 117 72 101
=  
 24 21 25 30 19 32 

The encryption for SECRET CODE is

91 24 66 21 80 25 117 30 72 19 101 32

44
 Decoding
To decode a message, simply put it back in
matrix form and multiply on the left with the
inverse matrix A-1

Since only A and A-1 are the only “keys”

needed to encode and decode a message,
it becomes easy to encrypt a message.

The difficulty is in finding the key matrix.

45
 Example

 1 2
Encoding matrix A =  
1 3 
(i) Use this matrix and the code for the English
alphabet above, to encode the message
DISCRETE MATHS.

(ii) Also, decode

55 70 75 102 22 31 58 85 49 69
46
 D S R T A H
(i) DISCRETE MATHS  
 I C E E M T S
 4 19 18 20 27 1 8 
 
 9 3 5 5 13 20 19 
 1 2   4 19 18 20 27 1 8 
   
ENCODE  1 3   9 3 5 5 13 20 19 

 22 25 28 30 53 41 46 
=  
 31 28 33 35 56 60 65 
Encoded message:22 31 25 28 28 33 30 35 53 56 41 46 65
47
 1  3 2 
(ii) A =
-1
 
1 3  1 2  1 1 
 3 2 
 
 1 1 

Decode:  3 2   55 75 22 58 49 
  
 1 1   70 102 31 85 69 
 25 21 4 4 9 
=  
 15 27 9 27 20 
25 15 21 27 4 9 4 27 9 20
Y o u did i t 48