APPLICATIONS OF LINEAR ALGEBRA

ELECTRONIC VERSION OF LECTURE

Dr. Lê Xuân Đại

HoChiMinh City University of Technology
Faculty of Applied Science, Department of Applied Mathematics
Email: [email protected]

HCMC — 2020.
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 1 / 54
OUTLINE

1 LESLIE MATRIX

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 2 / 54

OUTLINE

1 LESLIE MATRIX

2 MARKOV CHAINS

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 2 / 54

OUTLINE

1 LESLIE MATRIX

2 MARKOV CHAINS

3 LEONTIEF INPUT-OUTPUT MODELS

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 2 / 54

OUTLINE

1 LESLIE MATRIX

2 MARKOV CHAINS

3 LEONTIEF INPUT-OUTPUT MODELS

4 CRYPTOGRAPHY

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 2 / 54

Leslie matrix Population growth

Matrices can be used to form models for

population growth. The first step in this
process is to group the female population
into age classes of equal duration. For
example, if the maximum life span of a
member is M years, then the n intervals
below represent the age classes
M
· ¶
0, ⇒ First age class
n
M 2M
· ¶
, ⇒ Second age class
n n
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 3 / 54
Leslie matrix Population growth

· ¸
(n − 1)M
,M ⇒ nth age class
n

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 4 / 54

Leslie matrix Population growth

· ¸
(n − 1)M
,M ⇒ nth age class
n
The age distribution vector X represents
the number of female population members
in each age class, where

x1 Number in first age class
x 
 2 Number in second age class
X =  ..  ...
 . 
xn Number in nth age class
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 4 / 54
Leslie matrix Population growth

M
Over a period of years, the probability
n
that a female member of the i th age class
will survive to become a member of the
(i + 1)th age class is p i , where

0 É p i É 1, i = 1, 2, . . . , n − 1.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 5 / 54

Leslie matrix Population growth

M
Over a period of years, the probability
n
that a female member of the i th age class
will survive to become a member of the
(i + 1)th age class is p i , where

0 É p i É 1, i = 1, 2, . . . , n − 1.

The average number of female offspring

produced by a member of the i th age class
is bi , where
0 É bi , i = 1, 2, . . . , n.
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 5 / 54
Leslie matrix Age transition matrix

 
b 1 b 2 . . . b n−1 bn
p1 0 . . . 0 0
 
 
 
L= 0 p2 . . . 0 0 
... ... . . . ... ... 
 

 
0 0 . . . p n−1 0

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 6 / 54

Leslie matrix Age transition matrix

 
b 1 b 2 . . . b n−1 bn
p1 0 . . . 0 0
 
 
 
L= 0 p2 . . . 0 0 
... ... . . . ... ... 
 

 
0 0 . . . p n−1 0
Multiplying this age transition matrix by
the age distribution vector for a specific
time period produces the age distribution
vector for the next time period.
LX j = X j +1 , j = 1, 2, . . . , n. (1)
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 6 / 54
Leslie matrix Age transition matrix

EXAMPLE 1.1 (A POPULATION GROWTH MODEL)

A population of female rabbits has the characteristics
below
1
Half of the rabbits survive their first year. Of those,
half survive their second year. The maximum life
span is 3 years.
2
During the first year, the rabbits produce no
offspring. The average number of offspring is 6
during the second year and 8 during the third year.
The population now consists of 24 rabbits in the first
age class, 24 in the second, and 20 in the third. How
many rabbits will there be in each age class after 1
year? After 2 years?
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 7 / 54
Leslie matrix Age transition matrix

Let x 1(t ), x 2(t ), x 3(t ) be the number of rabbits

in age from 0 to 1, 1 to 2, and 2 to 3,
respectively at time t . Then  thecurrent age
24
distribution vector is X 1 =  24 .
 
20

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 8 / 54

Leslie matrix Age transition matrix

The number of rabbits in age from 0 to 1

after 1 year is:
x 1 (2) = 0 × 24 + 6 × 24 + 8 × 20 = 304.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 9 / 54

Leslie matrix Age transition matrix

The number of rabbits in age from 0 to 1

after 1 year is:
x 1 (2) = 0 × 24 + 6 × 24 + 8 × 20 = 304.
The number of rabbits in age from 1 to 2
after 1 year is:
x 2 (2) = 0.5 × 24 + 0 × 24 + 0 × 20 = 12.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 9 / 54

Leslie matrix Age transition matrix

The number of rabbits in age from 0 to 1

after 1 year is:
x 1 (2) = 0 × 24 + 6 × 24 + 8 × 20 = 304.
The number of rabbits in age from 1 to 2
after 1 year is:
x 2 (2) = 0.5 × 24 + 0 × 24 + 0 × 20 = 12.
The number of rabbits in age from 2 to 3
after 1 year is:
x 3 (2) = 0 × 24 + 0.5 × 24 + 0 × 20 = 12.
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 9 / 54
Leslie matrix Age transition matrix

In matrix
 form,the age transition matrix is
0 6 8
L =  0.5 0 0  .
 
0 0.5 0

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 10 / 54

Leslie matrix Age transition matrix

In matrix
 form,the age transition matrix is
0 6 8
L =  0.5 0 0  . After 1 year, the age
 
0 0.5 0
distribution vector will be
     
0 6 8 24 304
X 2 = LX 1 =  0.5 0 0  .  24  =  12 
     
0 0.5 0 20 12

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 10 / 54

Leslie matrix Stable age distribution vector

After 2 year, the age distribution vector is

     
0 6 8 304 168
X 3 = LX 2 =  0.5 0 0  .  12  =  152 
     
0 0.5 0 12 6

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 11 / 54

Leslie matrix Stable age distribution vector

After 2 year, the age distribution vector is

     
0 6 8 304 168
X 3 = LX 2 =  0.5 0 0  .  12  =  152 
     
0 0.5 0 12 6
Note. From the age distribution vectors X 1 , X 2 , and
X 3 that the percent of rabbits in each of the three age
classes changes each year. To obtain a stable growth
pattern, one in which the percent in each age class
remains the same each year, the (n + 1)th age
distribution vector must be a scalar multiple of the
n th age distribution vector.

X n+1 = LX n = λX n (2)
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 11 / 54
Leslie matrix Stable age distribution vector

EXAMPLE 1.2
Find a stable age distribution vector for the
population of female rabbits.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 12 / 54

Leslie matrix Stable age distribution vector

EXAMPLE 1.2
Find a stable age distribution vector for the
population of female rabbits.
SOLUTION. To solve this problem, find an
eigenvalue λ and a corresponding
eigenvector X such that LX = λX .

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 12 / 54

Leslie matrix Stable age distribution vector

EXAMPLE 1.2
Find a stable age distribution vector for the
population of female rabbits.
SOLUTION. To solve this problem, find an
eigenvalue λ and a corresponding
eigenvector X such that LX = λX . The
characteristic polynomial of L is
|L − λI | = −(λ + 1)2 (λ − 2)

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 12 / 54

Leslie matrix Stable age distribution vector

EXAMPLE 1.2
Find a stable age distribution vector for the
population of female rabbits.
SOLUTION. To solve this problem, find an
eigenvalue λ and a corresponding
eigenvector X such that LX = λX . The
characteristic polynomial of L is
|L − λI | = −(λ + 1)2 (λ − 2)

Choose the positive eigenvalue λ = 2.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 12 / 54
Leslie matrix Stable age distribution vector

The corresponding
  eigenvectors are of the
16
form X = α  4  .
 
1

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 13 / 54

Leslie matrix Stable age distribution vector

The corresponding
  eigenvectors are of the
16
form X = α  4  . For example, if α = 2, then
 
1
the initial age distribution vector is

  
32 64
X 1 =  8  ⇒ X 2 = LX 1 = 2X 1 =  16 
   
2 4
The percent of the population in each age
class remains the same.
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 13 / 54
Markov Chains Stochastic matrices and Markov chains

Many types of applications

n involve
o a
finite set of state S 1, S 2, . . . , S n of a
population.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 14 / 54

Markov Chains Stochastic matrices and Markov chains

Many types of applications

n involve
o a
finite set of state S 1, S 2, . . . , S n of a
population.
For instance, residents of a city may live
downtown or in the suburbs. Soft drink
consumers may buy Coca-Cola, Pepsi, or
another brand.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 14 / 54

Markov Chains Stochastic matrices and Markov chains

Many types of applications

n involve
o a
finite set of state S 1, S 2, . . . , S n of a
population.
For instance, residents of a city may live
downtown or in the suburbs. Soft drink
consumers may buy Coca-Cola, Pepsi, or
another brand.
The probability that a member of a
population will change from the j th state
to the i th state is represented by a
number p i j , where 0 É p i j É 1.
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 14 / 54
Markov Chains Stochastic matrices and Markov chains

DEFINITION 2.1
 
p 11 p 12 . . . p 1n
 p 21 p 22 . . . p 2n 
The matrix P =  is called
 
 ... ... . . . ... 
p n1 p n2 . . . p nn
the matrix of transition probabilities.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 15 / 54

Markov Chains Stochastic matrices and Markov chains

DEFINITION 2.1
 
p 11 p 12 . . . p 1n
 p 21 p 22 . . . p 2n 
The matrix P =  is called
 
 ... ... . . . ... 
p n1 p n2 . . . p nn
the matrix of transition probabilities.
At each transition, each member in a given
state must either stay in that state or change
to another state. It means that
n
P
p i j = 1, ∀ j = 1..n.
i =1
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 15 / 54
Markov Chains Stochastic matrices and Markov chains

DEFINITION 2.2
The n th state vector of a Markov chain for
which P is the matrix of transition
probabilities and X 0 is the initial state vector
is

X n = P X n−1 = P 2 X n−2 = . . . = P n X 0 (3)

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 16 / 54

Markov Chains Stochastic matrices and Markov chains

EXAMPLE 2.1 (A CONSUMER PREFERENCE

MODEL)
Two competing companies offer satellite
television service to a city with 100 000
households. The figure below shows the
changes in satellite subscription each year.
Company A now has 15 000 subscribers and
Company B has 20 000 subscribers. How
many subscribers will each company have in
one year? After 10 years? After 15 years?
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 17 / 54
Markov Chains Stochastic matrices and Markov chains

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 18 / 54

Markov Chains Stochastic matrices and Markov chains

SOLUTION. The matrix of transition

probabilities is
 
0.70 0.15 0.15
P =  0.20 0.80 0.15 
 
0.10 0.05 0.70

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 19 / 54

Markov Chains Stochastic matrices and Markov chains

SOLUTION. The matrix of transition

probabilities is
 
0.70 0.15 0.15
P =  0.20 0.80 0.15 
 
0.10 0.05 0.70
and the initial state vector representing the
portions of the
 total population
 in the 3
15000
states is X 0 =  20000  .
 
65000
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 19 / 54
Markov Chains Stochastic matrices and Markov chains

To find the state vector representing the

portions of the population in the 3 states in
one year, multiply P by X 0 to obtain
  
0.70 0.15 0.15 15000
X 1 = P X 0 =  0.20 0.80 0.15   20000  =
  
0.10 0.05 0.70 65000
 
23250
=  28750 
 
48000

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 20 / 54

Markov Chains Stochastic matrices and Markov chains

To find the numbers of subscribers after 10

years, first find X 10
 
33290
X 10 = P 10 X 0 ≈  47150 
 
19570

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 21 / 54

Markov Chains Stochastic matrices and Markov chains

To find the numbers of subscribers after 10

years, first find X 10
 
33290
X 10 = P 10 X 0 ≈  47150 
 
19570
To find the numbers of subscribers after 15
years, first find X 15
 
33330
X 15 = P 15 X 0 ≈  47560 
 
19110
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 21 / 54
Markov Chains Steady State vector of a Markov chain

Note. There is little difference between the

numbers of subscribers after 10 years and
after 15 years. If we continue this process,
then the state vector X n eventually reaches
a steady state.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 22 / 54

Markov Chains Steady State vector of a Markov chain

Note. There is little difference between the

numbers of subscribers after 10 years and
after 15 years. If we continue this process,
then the state vector X n eventually reaches
a steady state.
DEFINITION 2.3
A stochastic matrix P is said to be regular if
P or some positive power of P has all
positive entries, and a Markov chain whose
transition matrix is regular is said to be a
regular Markov chain.
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 22 / 54
Markov Chains Steady State vector of a Markov chain

THEOREM 2.1
If P is the transition matrix for a regular
Markov chain, then
1
There is a unique probability vector X ,
which is called the steady-state vector of
the Markov chain, with positive entries
such that P X = X .

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 23 / 54

Markov Chains Steady State vector of a Markov chain

THEOREM 2.1
If P is the transition matrix for a regular
Markov chain, then
1
There is a unique probability vector X ,
which is called the steady-state vector of
the Markov chain, with positive entries
such that P X = X .
2
For any initial probability vector X 0, the
sequence of state vectors
X 0 , P X 0 , . . . , P n X 0 , . . . converges to X
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 23 / 54
Markov Chains Steady State vector of a Markov chain

EXAMPLE 2.2
Find the steady state vector X of the Markov
chain whose matrix of transition
probabilities is the regular matrix
 
0.70 0.15 0.15
P =  0.20 0.80 0.15 
 
0.10 0.05 0.70

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 24 / 54

Markov Chains Steady State vector of a Markov chain

 
x1
SOLUTION. Let X =  x 2  . Then use the
 
x3
matrix equation P X = X to obtain
    
0.70 0.15 0.15 x1 x1
 0.20 0.80 0.15   x 2  =  x 2 
    
0.10 0.05 0.70 x3 x3

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 25 / 54

Markov Chains Steady State vector of a Markov chain

Use these equations and the fact that

 we can
x 1 + x 2 + x 3 = 100000,  find
 the 
steady
100000
3
33333
1000000
state vector X =   ≈  47619 
   
21
400000
21
19048

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 26 / 54

Markov Chains Eigenvalue and eigenvector

P X = X = 1.X ,
so 1 is an eigenvalue of P with
corresponding eigenvector X .
Eigenvalues: λ1 = 1;λ2 =0.65; λ3= 0.55.

7 0
Eigenvectors: X 1 =  10  ; X 2 =  −1  ;
   
4 1
 
−2
X3 =  1  ;
 
1
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 27 / 54
Markov Chains Absorbing Markov Chains

Consider
n a Markovo chain with n different
states S 1, S 2, . . . , S n .
DEFINITION 2.4
The i th state S i is an absorbing state when,
in the matrix of transition probabilities P ,

pi i = 1 (4)

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 28 / 54

Markov Chains Absorbing Markov Chains

Consider
n a Markovo chain with n different
states S 1, S 2, . . . , S n .
DEFINITION 2.4
The i th state S i is an absorbing state when,
in the matrix of transition probabilities P ,

pi i = 1 (4)

That is, the entry on the main diagonal of P

is 1 and all the other entries in the i th
column of P are 0.
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 28 / 54
Markov Chains Absorbing Markov Chains

DEFINITION 2.5
An absorbing Markov chain has the two
properties listed below
1
The Markov chain has at least one
absorbing state.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 29 / 54

Markov Chains Absorbing Markov Chains

DEFINITION 2.5
An absorbing Markov chain has the two
properties listed below
1
The Markov chain has at least one
absorbing state.
2
It is possible for a member of the
population to move from any
nonabsorbing state to an absorbing state
in a finite number of transitions.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 29 / 54

Markov Chains Absorbing Markov Chains

EXAMPLE 2.3

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 30 / 54

Markov Chains Absorbing Markov Chains

EXAMPLE 2.3

The matrix of transition probabilities is

 
0.4 0 0
P =  0 1 0.5 
 
0.6 0 0.5
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 30 / 54
Markov Chains Absorbing Markov Chains

Therefore, the second state, represented by

the second column, is absorbing. Moreover,
the corresponding Markov chain is also
absorbing because it is possible to move
from S 1 to S 2 in two transitions (from S 1 to
S 3 and then from S 3 to S 2 ), and it is possible
to move from S 3 to S 2 in one transition
(from S 3 to S 2).

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 31 / 54

Markov Chains Absorbing Markov Chains

EXAMPLE 2.4

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 32 / 54

Markov Chains Absorbing Markov Chains

EXAMPLE 2.4

The matrix of transition probabilities is

 
0.5 0 0 0
 0.5 1 0 0 
P =
 
0 0 0.4 0.5

 
0 0 0.6 0.5
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 32 / 54
Markov Chains Absorbing Markov Chains

Therefore, the second state, represented by

the second column, is absorbing. However,
the corresponding Markov chain is NOT
absorbing because there is no way to move
from S 3 or S 4 to S 2.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 33 / 54

Leontief input-output models

LEONTIEF INPUT-OUTPUT MODELS

Consider an economic system that has n

different industries I 1, I 2, . . . , I n , each having
input needs (raw materials, utilities, etc.)
and an output (finished product). In
producing each unit of output, an industry
may use the outputs of other industries,
including itself. For example, an electric
utility uses outputs from other industries,
such as coal and water, and also uses its
own electricity.
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 34 / 54
Leontief input-output models The input-output matrix

Let di j be the amount of output the j th

industry needs from the i th industry to
produce one unit of output per year. The
matrix of these coefficients is the
input-output matrix
 
d 11 d 12 . . . d 1n
d
 21 d 22 . . . d 2n 
D =  ..

 . ... .
. . . .. 


d n1 d n2 . . . d nn

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 35 / 54

Leontief input-output models The input-output matrix

FORMING AN INPUT-OUTPUT MATRIX

EXAMPLE 3.1
Consider a simple economic system consisting of 3
industries: electricity, water, and coal. Production, or
output, of one unit of electricity requires 0.5 unit of
itself, 0.25 unit of water, and 0.25 unit of coal.
Production of one unit of water requires 0.1 unit of
electricity, 0.6 unit of itself, and 0 units of coal.
Production of one unit of coal requires 0.2 unit of
electricity, 0.15 unit of water, and 0.5 unit of itself.
Find the input-output matrix for this system.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 36 / 54

Leontief input-output models The input-output matrix

SOLUTION. The column entries show the

amounts each industry requires from the
others, and from itself, to produce one unit
of output

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 37 / 54

Leontief input-output models The input-output matrix

SOLUTION. The column entries show the

amounts each industry requires from the
others, and from itself, to produce one unit
of output
 
0.5 0.1 0.2
D =  0.25 0.6 0.15 
 
0.25 0 0.5
The row entries show the amounts each
industry supplies to the others, and to itself,
for that industry to produce one unit of
output.
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 37 / 54
Leontief input-output models Closed system

Let the total output of the i th industry be

denoted by x i . If the economic system is
closed (that is, the economic system sells its
products only to industries within the
system), then the total output of the i th
industry is

xi = di 1 x1 + di 2 x2 + . . . + di n xn (5)

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 38 / 54

Leontief input-output models Open system

If the industries within the system sell

products to nonproducing groups (such as
governments or charitable organizations)
outside the system, then system is open
and the total output of the i th industry is

xi = di 1 x1 + di 2 x2 + . . . + di n xn + e i (6)

where e i represents the external demand for

the i th industry’s product.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 39 / 54

Leontief input-output models Open system

The collection of total outputs for an open

system is


 x 1 = d 11 x 1 + d 12 x 2 + . . . + d 1n x n + e 1

 x = d x +d x +...+d x +e
2 21 1 22 2 2n n 2

 ...

x n = d n1 x 1 + d n2 x 2 + . . . + d nn x n + e n


Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 40 / 54

Leontief input-output models Open system

The collection of total outputs for an open

system is


 x 1 = d 11 x 1 + d 12 x 2 + . . . + d 1n x n + e 1

 x = d x +d x +...+d x +e
2 21 1 22 2 2n n 2

 ...

x n = d n1 x 1 + d n2 x 2 + . . . + d nn x n + e n


The matrix form of this system is

X = DX +E, (7)
where X is the output matrix and E is the
external demand matrix.
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 40 / 54
Leontief input-output models Open system

EXAMPLE 3.2
An economic system composed of 3
industries has the input-output matrix
 
0.1 0.43 0
D =  0.15 0 0.37 
 
0.23 0.03 0.02
Find the output matrix
 X when the external
20000
demands are E =  30000 
 
25000
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 41 / 54
Leontief input-output models Open system

SOLUTION.
X = D X + E ⇒ (I − D)X = E ⇒ X = (I − D)−1 E .
 
46616
X ≈  51058 
 
38014

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 42 / 54

Leontief input-output models Open system

SOLUTION.
X = D X + E ⇒ (I − D)X = E ⇒ X = (I − D)−1 E .
 
46616
X ≈  51058 
 
38014
To produce the given external demands, the
outputs of the 3 industries must be
approximately 46616 units for the industry I,
51058 units for industry II, and 38014 units
for industry III.
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 42 / 54
Cryptography Definition

CRYPTOGRAPHY

DEFINITION 4.1
A cryptogram is a message written
according to a secret code. One method of
using matrix multiplication to encode and
decode messages is introduced below.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 43 / 54

Cryptography Definition

CRYPTOGRAPHY

DEFINITION 4.1
A cryptogram is a message written
according to a secret code. One method of
using matrix multiplication to encode and
decode messages is introduced below.

t a b c d e f g h i j k ` m
0 1 2 3 4 5 6 7 8 9 10 11 12 13
n o p q r s t u v w x y z
14 15 16 17 18 19 20 21 22 23 24 25 26

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 43 / 54

Cryptography Definition

EXAMPLE 4.1
Write the uncoded row matrices of size 1 × 3
for the message MEET ME MONDAY

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 44 / 54

Cryptography Definition

EXAMPLE 4.1
Write the uncoded row matrices of size 1 × 3
for the message MEET ME MONDAY
SOLUTION.
m e e t t m e t m o n d a y t
13 5 5 20 0 13 5 0 13 15 14 4 1 25 0

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 44 / 54

Cryptography Definition

EXAMPLE 4.1
Write the uncoded row matrices of size 1 × 3
for the message MEET ME MONDAY
SOLUTION.
m e e t t m e t m o n d a y t
13 5 5 20 0 13 5 0 13 15 14 4 1 25 0
The uncoded row matrices of size 1 × 3 for the message are
[13 5 5]; [20 0 13]; [5 0 13]; [15 14 4]; [1 25 0].

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 44 / 54

Cryptography Encoding a message

To encode a message, choose an n × n

invertible matrix A and multiply the
uncoded row matrices on the right by A to
obtain coded row matrices.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 45 / 54

Cryptography Encoding a message

To encode a message, choose an n × n

invertible matrix A and multiply the
uncoded row matrices on the right by A to
obtain coded row matrices.
EXAMPLE 4.2  
1 −2 2
Use the invertible matrix A =  −1 1 3 
 
1 −1 −4
to encode the message MEET ME MONDAY.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 45 / 54

Cryptography Encoding a message

SOLUTION. Obtain the coded row matrices

by multiplying each of the uncoded row
matrices by the matrix A
 
1 −2 2
¡ ¢  ¡ ¢
13 5 5  −1 1 3  = 13 −26 21
1 −1 −4

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 46 / 54

Cryptography Encoding a message

SOLUTION. Obtain the coded row matrices

by multiplying each of the uncoded row
matrices by the matrix A
 
1 −2 2
¡ ¢  ¡ ¢
13 5 5  −1 1 3  = 13 −26 21
1 −1 −4
 
1 −2 2
¡ ¢  ¡ ¢
20 0 13  −1 1 3  = 33 −53 −12
1 −1 −4
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 46 / 54
Cryptography Encoding a message

 
1 −2 2
¡ ¢  ¡ ¢
5 0 13  −1 1 3  = 18 −23 −42
1 −1 −4

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 47 / 54

Cryptography Encoding a message

 
1 −2 2
¡ ¢  ¡ ¢
5 0 13  −1 1 3  = 18 −23 −42
1 −1 −4
 
1 −2 2
¡ ¢  ¡ ¢
15 14 4  −1 1 3  = 5 −20 56
1 −1 −4

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 47 / 54

Cryptography Encoding a message

 
1 −2 2
¡ ¢  ¡ ¢
5 0 13  −1 1 3  = 18 −23 −42
1 −1 −4
 
1 −2 2
¡ ¢  ¡ ¢
15 14 4  −1 1 3  = 5 −20 56
1 −1 −4
 
1 −2 2
¡ ¢  ¡ ¢
1 25 0  −1 1 3  = −24 23 77
1 −1 −4
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 47 / 54
Cryptography Encoding a message

The sequence of coded row matrices is

[13 − 26 21]; [33 − 53 − 12];
[18 − 23 − 42]; [5 − 20 56];
[−24 23 77].

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 48 / 54

Cryptography Encoding a message

The sequence of coded row matrices is

[13 − 26 21]; [33 − 53 − 12];
[18 − 23 − 42]; [5 − 20 56];
[−24 23 77].
Finally, removing the matrix notation
produces the cryptogram
13 − 26 21 33 − 53 − 12 18
−23 − 42 5 − 20 56 − 24 23 77.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 48 / 54

Cryptography Decoding a message

If X = [x 1 x 2 . . . x n ] is an uncoded 1 × n
matrix, then Y = X A is the corresponding
encoded matrix. The receiver of the
encoded matrix can decode Y by
multiplying on the right by A −1 to obtain

Y A −1 = (X A)A −1 = X (8)

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 49 / 54

Cryptography Decoding a message

EXAMPLE 4.3  
1 −2 2
Use the inverse matrix A =  −1 1 3  to
 
1 −1 −4
decode the cryptogram
13 − 26 21 33 − 53 − 12 18
−23 − 42 5 − 20 56 − 24 23 77.

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 50 / 54

Cryptography Decoding a message

EXAMPLE 4.3  
1 −2 2
Use the inverse matrix A =  −1 1 3  to
 
1 −1 −4
decode the cryptogram
13 − 26 21 33 − 53 − 12 18
−23 − 42 5 − 20 56 − 24 23 77.
SOLUTION.  
−1 −10 −8
A −1 =  −1 −6 −5 
 
0 −1 −1
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 50 / 54
Cryptography Decoding a message

To decode the message, partition the

message into groups of 3 to form the coded
row matrices [13 − 26 21];
[33 − 53 − 12]; [18 − 23 − 42];
[5 − 20 56]; [−24 23 77].
To obtain the decoded row matrices,
multiply each coded row matrix by A −1 on
the right.
 
−1 −10 −8
¡ ¢  ¡ ¢
13 −26 21  −1 −6 −5  = 13 5 5
0 −1 −1
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 51 / 54
Cryptography Decoding a message

 
−1 −10 −8
¡ ¢  ¡ ¢
33 −53 −12  −1 −6 −5  = 20 0 13
0 −1 −1

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 52 / 54

Cryptography Decoding a message

 
−1 −10 −8
¡ ¢  ¡ ¢
33 −53 −12  −1 −6 −5  = 20 0 13
0 −1 −1
 
−1 −10 −8
¡ ¢  ¡ ¢
18 −23 −42  −1 −6 −5  = 5 0 13
0 −1 −1

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 52 / 54

Cryptography Decoding a message

 
−1 −10 −8
¡ ¢  ¡ ¢
33 −53 −12  −1 −6 −5  = 20 0 13
0 −1 −1
 
−1 −10 −8
¡ ¢  ¡ ¢
18 −23 −42  −1 −6 −5  = 5 0 13
0 −1 −1
 
−1 −10 −8
¡ ¢  ¡ ¢
5 −20 56  −1 −6 −5  = 15 14 4
0 −1 −1
Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 52 / 54
Cryptography Decoding a message

 
−1 −10 −8
¡ ¢  ¡ ¢
−24 23 77  −1 −6 −5  = 1 25 0
0 −1 −1

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 53 / 54

Cryptography Decoding a message

 
−1 −10 −8
¡ ¢  ¡ ¢
−24 23 77  −1 −6 −5  = 1 25 0
0 −1 −1
The sequence of decoded row matrices is
[13 5 5]; [20 0 13]; [5 0 13];
[15 14 4]; [1 25 0].
The message is
13 5 5 20 0 13 5 0 13 15 14 4 1 25 0
m e e t t m e t m o n d a y t

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 53 / 54

Cryptography Decoding a message

THANK YOU FOR YOUR ATTENTION

Dr. Lê Xuân Đại (HCMUT-OISP) APPLICATIONS OF LINEAR ALGEBRA HCMC — 2020. 54 / 54