1 Matrix Algebra

Reading [SB] 8.1-8.5, pp. 153-180.

1.1 Matrix Operations

1. Addition
   
a11 a12 ... a1n b11 b12 ... b1n
 a21 a22 ... a2n   b21 b22 ... b2n 
   
 + =
 ... ... ... ...   ... ... ... ... 
am1 am2 ... amn bm1 bm2 ... bmn
 
a11 + b11 a12 + b12 ... a1n + b1n
 a21 + b21 a22 + b22 ... a2n + b2n 
 
 .
 ... ... ... ... 
am1 + bm1 am2 + bm2 ... amn + bmn
This operation is
- associative A + (B + C) = (A + B) + C;
- commutative A + B = B + A;
- has a neutral element O + A = A, here O is the null matrix
 
0 0 ... 0
 0 0 ... 0 
O=


.
 ... ... ... ... 
0 0 ... 0

2. Scalar multiplication
   
a11 a12 ... a1n ka11 ka12 ... ka1n
 a21 a22 ... a2n   ka21 ka22 ... ka2n 
   
k· = .
 ... ... ... ...   ... ... ... ... 
am1 am2 ... amn kam1 kam2 ... kamn
3. Multiplication of matrixes
   
a11 ... a1j ... a1n b11 ... b1j ... b1k
   


... ... ... ...  
 
... ... ... ... ... 

 ai1 ... aij ... ain · bi1 ... bij ... bik =
   
   
 ... ... ... ... ...   ... ... ... ... ... 
am1 ... amj ... amn bn1 ... bnj ... bnk
 
c11 ... c12 ... c1k
 


... ... ... ... ... 

 ci1 ... cij ... cik 
 
 
 ... ... ... ... ... 
cm1 ... cmj ... cmk

1
where n
X
cij = ai1 b1j + ... + aik bkj + ... + ain bnj = aik bkj
k=1

1.2 Transpose of a matrix

Transpose of a m × n matrix A is the n × m matrix AT whose i-th column
is is the i-th row of A.  
à ! 1 4
1 2 3
For example the transpose for A = is AT =  
 2 5 .
4 5 6
3 6
Properties of transposes
1. (AT )T = A;
2. (A + B)T = AT + B T ;
3. (A · B)T = B T · AT .

1.3 Multiplication matrix × column vector

     
a11 a12 ... a1n x1 a11 x1 + a12 x2 + ... + a1n xn
 a21 a22 ... a2n   x2   a21 x1 + a22 x2 + ... + a2n xn 
     
 · = 
 ... ... ... ...   ...   ....................................... 
am1 am2 ... amn xn am1 x1 + am2 x2 + ... + amn xn
thus a system of linear equations


 a11 x1 + a12 x2 + ... + a1n xn = c1

 a21 x1 + a22 x2 + ... + a2n xn = c2


 .......................................

am1 x1 + am2 x2 + ... + amn xn = cm .

can be written in matrix form as

     
a11 a12 ... a1n x1 c1
 a21 a22 ... a2n   x2   c2 
     
 · = 
 ... ... ... ...   ...   ... 
am1 am2 ... amn xn cn
or
A · x = c.

1.4 Special Kinds of Matrices

Bellow k denotes the number of rows and n denotes the number of columns.

Square matrix. k = n.

Column matrix. n = 1.

2
Row matrix. k = 1.

Diagonal matrix. k = n and aij = 0 for i 6= j.

What can you say about the product of two diagonal matrices?

Upper-triangular matrix. k = n and aij = 0 for i > j.

What can you say about the product of two upper-triangular matrices?

Lower-triangular matrix. k = n and aij = 0 for i < j.

What can you say about the product of two lower-triangular matrices?

Symmetric matrix. aij = aji , equivalently AT = A.

Is a symmetric matrix necessarily square matrix?
What can you say about the product of two symmetric matrices?

Idempotent matrix. A · A = A.
Is an idempotent matrix necessarily square matrix?
What can you say about the determinant of an idempotent matrix?
What can you say about a nonsingular idempotent matrix?

Orthogonal matrix. A−1 = AT .

What can you say about the determinant of an orthogonal matrix?
What can you say about the inverse of an orthogonal matrix?
What can you say about the transpose of an orthogonal matrix?
What can you say about the product of two orthogonal matrices?
What can you say about the sum of two orthogonal matrices?

Involutory matrix. A · A = I.
Is an involutory matrix necessarily square matrix?
What can you say about the determinant of an involutory matrix?
What can you say about the inverse of an involutory matrix?
What can you say about a singular involutory matrix?
What can you say about the transpose of an involutory matrix?
What can you say about the symmetric involutory matrix?

Nilpotent matrix. k = n and Am = 0 for some positive integer m.

Permutation matrix. k = n and each row and each column contains

exactly one 1 and all other entries are 0.

Non singular matrix. k = n is an invertible = nonzero determinant =

maximal rank (see bellow).

3
2 Algebra of Square Matrices
The sum, difference, product of square n × n matrices is n × n again, besides
the n × n identity matrix I is true multiplicative identity

I · A = A · I = A.

So the set of all n × n matrices Mn carries algebraic structure similar to that

of real numbers R. But there are some differences:

1. Multiplication in Mn is not commutative: generally A · B 6= B · A.

2. Mn has zero divisors: there exist nonzero matrices A, B ∈ Mn such

that A · B = O.

3. Not all nonzero matrices have inverse.

2.1 Inverse Matrix

Definition. A matrix A ∈ Mn is called invertible there exists its inverse, a
matrix A−1 such that
A · A−1 = A−1 · A = I.

Theorem. An n × n matrix A can have at most one inverse.

Proof. Suppose A−1 and Ā−1 are two inverses for A. Then from one hand
side
A−1 · A · Ā−1 = A−1 · (A · Ā−1 ) = A−1 · I = A−1 ,
and from another hand side

A−1 · A · Ā−1 = (A−1 · A) · Ā−1 = I · Ā−1 = Ā−1

thus A−1 = A−1 · A · Ā−1 = Ā−1 .

2.1.1 Some Properties of Inverse

1. (A−1 )−1 = A.
2. (AT )−1 = (A−1 )T .
3. (A · B)−1 = B −1 · A−1 .

4
2.2 Solving Systems Using Inverse
As we know each system of linear equations


 a11 x1 + a12 x2 + ... + a1n xn = c1

 a x + a x + ... + a x = c
21 1 22 2 2n n 2


 .......................................

am1 x1 + am2 x2 + ... + amn xn = cm .
can be written in matrix form A · x = c.
Theorem. If A is invertible then the system of linear equations A · x = c
has the unique solution given by x = A−1 · c.
Proof.
A · x = c ⇒ A−1 · (A · x) = A−1 · c ⇒ (A−1 · A) · x =
A−1 · c ⇒ I · x = A−1 · c ⇒ x = A−1 · c.

2.3 How to Find the Inverse matrix if it Exists

If a matrix  
a11 a12 ... a1n
 a21 a22 ... a2n 
A=



 ... ... ... ... 
an1 an2 ... ann
is invertible, then A−1 can be found using Gauss-Jordan elimination for the
matrix (A|I) which is augmentation of A by the unit matrix I
 
a11 a12 ... a1n | 1 0 ... 0
 a21 a22 ... a2n | 0 1 ... 0 
 
(A|E) =  
 ... ... ... ... | ... ... ... 
an1 an2 ... ann | 0 0 ... 1.

Performing Gauss-Jordan elimination for (A|I) we obtain (I|A−1 ).

2.4 Inverse of an 2 × 2 Matrix

The Gauss-Jordan elimination for an 2 × 2 matrix
à !
a b
A=
c d
gives the following inverse matrix
à !
−1 1 d −b
A = .
ad − bc −c a
The condition
ad − bc 6= 0
is necessary and sufficient for the existence of inverse matrix.

5
2.5 Input-output analysis for two goods production
To produce 1 unit of good I1 a11 units of good I1 and a21 units of good I2 are
needed.
To produce 1 unit of good I2 a12 units of good I1 and a22 units of good I2 are
needed. Ã !
a11 a12
The input-output matrix (or technology matrix) is A = .
a21 a22
Problem. How many units of good I1 and good I2 must be produced to
satisfy the demand d1 units of good I1 and d2 of good I2 ?
Solution. Suppose x1 units of good I1 and x2 units of good I2 are produced.
One part will be used for production and other for consumption.
a11 · x1 units of good I1 will be used for production of good I1 ;
a12 · x2 units of good I1 will be used for production of good I2 ;
d1 units of good I1 will be used for consumption.
Thus x1 = a11 · x1 + a12 · x2 + d1 .
Similarly x2 = a21 · x1 + a22 · x2 + d2 .
To find x1 and x2 for the consumptions d1 and d2 the following Leontieff
system must be solved
( ¯
x1 = a11 · x1 + a12 · x2 + d1 ¯
¯
¯⇒
x2 = a21 · x1 + a22 · x2 + d2 ¯

( ¯
(1 − a11 ) · x1 − a12 · x2 = d1 ¯
¯
¯.
−a21 · x1 + (1 − a22 ) · x2 = d2 ¯

The matrix à !
a11 a12
A=
a21 a22
is called input-output, or technology matrix.

The matrix of this system

à !
1 − a11 −a12
I −A=
−a21 1 − a22

is called Leontieff matrix.

2.5.1 Example
A company produces two products CORN (C) and FERTILIZER (F).
To produce 1 ton of C are needed: 0.1 tons of C and 0.8 tons of F.
To produce 1 ton of F are needed: 0.5 tons of C and 0 tons of F.
Problem. How many tons of C and F must be produced for consumption

6
of 4 tons of C and 2 tons of F?
Solution. Suppose for this xC tons of C and xF tons of F. Then
( ¯
xC = 0.1xC + 0.5xF + 4 ¯ 0.9x − 0.5x = 4
¯ C F
¯ .
xF = 0.8xC + 2 ¯ −0.8xC + xF = 2

2.6 Productivity of Input-output Matrix

The economical nature of the problem dictates the following restrictions:
(i) All input-output coefficients aij are nonnegative.
(ii) All the demands di are nonnegative.
(iii) The solutions xi also must be nonnegative.
So we need not all but just nonnegative solutions of the Leontief system.

Definition 1 An input-output matrix A is called productive if the Leontief

system has unique nonnegative solution for each nonnegative demand vector
d.

What conditions must satisfy the input-output matrix A for this?

Definition 2 An industry Ik is called profitable if the sum of the k-th column

of the input-output matrix is less than 1.

Theorem 1 If an input-output matrix A is nonnegative, that is aij ≥ 0 and

the sum of entries of each column is less than 1, then the Leontief matrix
I − A has inverse (I − A)−1 with all nonnegative entries.

Proof. Let us proof the theorem for

à !
a b
.
c d

By the assumptions of theorem, the input-output matrix has a form

à !
1−c−² b
A=
c 1−b−δ

with 0 ≤ b < 1, 0 ≤ c < 1, ² > 0, δ > 0. Then its Leontieff matrix looks as
à !
c + ² −b
I −A= ,
−c b + δ

thus its determinant is

∆ = bc + cδ + b² − bc = cδ + b² + ² · δ

7
which, by assumption, is positive, thus I − A is invertible. Furthermore, the
inverse (I − A)−1 looks as
à !
1 b+δ b
·
∆ c c+²

where all entries are nonnegative. Q.E.D.

Corollary 1 If each industry is profitable, then the economy is productive.

Proof. For each demand vector d the solution of the Leontief system is given
by x = (I − A)−1 · d and since all entries of (I − A)−1 and d are nonnegative,
each xi is nonnegative too. Q.E.D.
So the profitability of each industry is sufficient for productivity. But not
necessary: take à !
0 2
A=
0 0
where the second industry is definitely nonprofitable, nevertheless its Leon-
tieff matrix looks as à !
1 −2
I −A=
0 1
and its inverse à !
−1 1 2
(I − A) =
0 1
is a nonnegative matrix.

3 Markov Chains

Reading: [Chang], section 4.7, p. 78-81, [Simon], section 23.6, p. 615-619.

The Markov process is a process when the state of the system depends
on the previous state and not on the whole history.
Suppose there are n populations. A Markov process is described by a
transition matrix (Stochastic matrix, Markov matrix)
 
P11 P12 ... P1n
 
M =  ... ... ... ... 
Pn1 Pn2 ... Pnn

where Pij denotes the probability of moving from population j to population

i.
P
The sum of elements of each column of Markov matrix is 1: nk=1 akj = 1.

8
  
x1 [t]
 
Suppose x[t] =  ...  is the state of the system at the moment t.
xn [t]
Then after one transition the state of the system will be x[t + 1] = M · x[t],
and after k transition the state of the system will be x[t + k] = M k · x[t].
A steady state is defined as x[t] such that x[t + 1] = M · x[t] = x[t],
that is it remains unchanged and the process remains stabile starting from
this state.
If x[t] is a steady state, then k · x[t] is a steady state too:

M · (k · x[t]) = k · (M · x[t]) = k · x[t].

If you remember the definitions of eigenvectors and eigenvalue (if not -

do not mind, we come back to this question later):
Theorem. A Markov matrix has an eigenvalue equal to 1.
An eigenvector x corresponding to this eigenvalue λ = 1 is a stady-state
that is it does not change by further transitions: M · x = x.
à !
p q
How to find a steady state for a Markov matrix ? Just
1−p 1−q
à ! à ! à !
p q x x
solve · = :
1−p 1−q y y
( ¯ ¯
px + qy = x ¯ px + qy = x ¯
¯ ¯
¯ ¯ (p − 1)x + qy = 0.
(1 − p)x + (1 − q)y = y ¯ px + qy = x ¯

3.1 Examples

Example 1
Two populations A and B.
PAA probability that A remains in A
PAB probability that A moves to B
PBB probability that B remains in B
PBA probability that B moves to A

PAA , PAB , PAA , PBB ≥ 0,

PAA + PAB = 1, PBA + PBB = 1.

Transition matrix (Stochastic matrix, Markov matrix)

à !
PAA PBA
M= .
PAB PBB

9
Let xA (0) be the initial population of A and xB (0) be the initial population
of B. After one transition the distribution of population will be
à ! à ! à !
xA (1) PAA PBA xA (0)
= · =
xB (1) PAB PBB xB (0)
à !
PAA · xA (0) + PBA · xB (0)
PAB · xA (0) + PBB · xB (0)
After n transition the distribution of population will be
à ! à !n à !
xA (n) PAA PBA xA (0)
= ·
xB (n) PAB PBB xB (0)

Example 2
Let for the population L the probability to stay in L during one year be
0.8 and the probability to pass to D be 0.2.
Let for the representatives of D the probability to stay in D be 1 and the
probability to pass to L be 0.
Let the initial population of L and D be xL (0) = 1000, xD (0) = 0. What
will be the populations of L and D after 1 year? After 2 years?
Solution.
à ! à ! à ! à !
xL (1) 0.8 0 1000 800
= · = ,
xD (1) 0.2 1 0 200
à ! à ! à ! à !
xL (2) 0.8 0 800 640
= · = .
xD (2) 0.2 1 200 360

Example 3. Unemployment
Assume the population is divided into two parts: E-employed persons
and U -unemployed persons.
Suppose further that the probability of an employed person to remain
employed during one week is q. Then the probability to loose a job is 1 − q.
Similarly, suppose the probability of an unemployed person to find a job
after one week is p. Then the probability to satay unemployed is 1 − p.
So the transition matrix looks as
à !
q p
.
1−q 1−p
Let x0 be the percentage of employed persons and y0 be the percentage
of unemployed persons (the unemployment rate), so x0 + y0 = 1.
How the unemployment rate will change after one week?
The answer is
à ! à ! à ! à !
x1 q p x0 qx0 + py0
= · = .
y1 1−q 1−p y0 (1 − q)x0 + (1 − p)y0

10
 Exercises

1. Let
     
a11 a12 ... a1n b11 b12 ... b1q x1
 a21 a22 ... a2n   b21 b22 ... b2q   x2 
A=

 
, B = 
 
, x = 


 ... ... ... ...   ... ... ... ...   ... 
am1 am2 ... amn bp1 bp2 ... bpq xr

Find the values of m, n, p, q, r for which exist the following products, and
find the dimensions of these products when they exist:
(a) A · B, (b) B · A, (c) B T · AT , (d) AT · B T , (e) A · B T ,
(f) A · x, (g) A · xT , (h) x · A, (i) xT · A (j) x · xT , (k) xT · x, (l) x · x, (m)
xT · xT .

2. Suppose for the population of L the probability to stay in L during

one year is 0.8 and the probability to pass to D is 0.2.
Suppose for the representatives of D the probability to stay in D is 0.1
and the probability to pass to L is 0.9.
(a) Let the initial population of L be x[0] = 1000 and the initial popula-
tion of D be y[0] = 2000. What will be the populations of L and D after 1
year x[1], y[1]? After 2 years x[2], y[2]?
(b) Find the steady-state with y = 1500.
(c) Find the steady-state with x = 5000.
à !
q p
3. Let M = be a Markov matrix.
r s
à !
x0
(a) Let be a starting state and
y0
à ! à !
x1 x0
=M· .
y1 y0

Show that x0 + y0 = x1 + y1 . Ã !
xs
(b) Find the steady-state(s) with xs + ys = d.
ys

4. Suppose we consider a simple economy with a lumber industry and a

power industry. Suppose further that production of 10 units of power require
4 units of power and 25 units of power require 5 units of lumber. 10 units
of lumber require 1 unit of lumber and 25 units of lumber require 5 units of
power. If surplus of 30 units of lumber and 70 units of power are desired,
find the gross production of each industry.

5. The economy of a developing nation is based on agricultural products,

steel, and coal. An input of 1 ton of agricultural products requires an input

11
of 0.1 ton of agricultural products, 0.02 ton of steel, and 0.05 ton of coal. An
output of 1 ton of steel requires an input of 0.01 ton of agricultural products,
0.13 tons of steel, and 0.18 tons of coal. An output of 1 ton of coal requires
an input of 0.01 ton of agricultural products, 0.2 tons of steel, and 0.05 ton
of coal. Find the necessary gross productions to provide surpluses of 2350
tons of agricultural products, 4552 tons of steel, and 911 tons of coal.

Exercises 6.3, 6.4, 6.5, 6.6, 8.1-8.5, 8.6-8.10, 8.15-8.22, 8.24-8.29

Homework

Exercises 8.6, 8.19, 8.24 from [SB], problem 3, problem 4.

12