Chi-Kong Ng, SEEM2420, Dept.

of SEEM, CUHK 2:1

Chapter 2.

Mathematical Background for Linear

Programming
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:2

2.1. Definition of a Matrix

• A matrix is a rectangular array of elements.
• The element aij of the matrix A occupies the ith row and jth
column of the array.
• A matrix with m rows and n columns is said to be of size (or order )
m × n.
• Example:
 
a11 a12 ··· a1n
 a a22 ··· a2n
 
A =  21  = [aij ]m×n

 ··· ··· ··· ··· 
am1 am2 ··· amn
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:3

2.2. Types of Matrices

• A square matrix has m = n.

• An identity matrix In is a square matrix of size n × n in which the

main diagonal elements aii (i = 1, . . . , n) are 1 and the off-diagonal
elements aij (∀i 6= j) are 0.

• A row vector is a matrix with one row and n columns.

Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:4

• A column vector is a matrix with m rows and one column.

• The matrix AT is the transpose of A if the element aij in A equals

the element aji in AT for all i and j.

• A matrix B = 0 is a zero matrix if every element of B is 0.

• Two matrices A = [aij ] and B = [bij ] are equal

⇐⇒ A and B have the same size and aij = bij for all i and j.
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:5

2.3. Matrix Arithmetic Operations

2.3.1. Addition and Subtraction of Matrices
• If A = [aij ]m×n and B = [bij ]m×n , then
A ± B = [aij ± bij ]m×n

2.3.2. Multiplication by a Scalar

• If A = [aij ]m×n and α is a scalar, then
α A = A α = [α aij ]m×n
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:6

2.3.3. Product of Matrices

• The product D = AB of two matrices, A = [aij ] and B = [bij ], is
defined
⇐⇒ the number of columns of A equals the number of rows of B.
• If A is of size (m × r) and B is of size (r × n), then D must be of
size (m × n), where m and n are arbitrary positive integer values.
• In this case, the elements of D are computed as
r
X
dij = aik bkj , for all i and j.
k=1
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:7

• Example: Consider a general linear system of equations:

a11x1 + a12x2 + · · · + a1nxn = b1
a21x1 + a22x2 + · · · + a2nxn = b2
...
am1x1 + am2x2 + · · · + amnxn = bm
It is equivalent to the following matrix equation:
Ax = b
where
     
a11 a12 ··· a1n x1 b1
 a a22 ··· a2n x2 b2
     
A =  21 x= b=
    
... ...
 ··· ··· ··· ···
  
    
am1 am2 ··· amn xn bm
m×n n×1 m×1
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:8

2.3.4. Multiplication of Partitioned Matrices

• Let A be an (m × r)-matrix and B an (r × n)-matrix.
• Assume that A and B are partitioned as follows:
 
  B11 B12
A11 A12 A13
A= , B =  B21 B22  .
A21 A22 A23
B31 B32
The partitioning assumes that the number of columns of Aij is equal
to the number of rows of Bjk for all i, j and k.
• AB =
 
A11B11 + A12B21 + A13B31 A11B12 + A12B22 + A13B32
A21B11 + A22B21 + A23B31 A21B12 + A22B22 + A23B32
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:9

• Example:     
1 2 3 4 30
 1 0 5   1  =  44 
2 5 6 8 61

• Example:     
1 3 5 7 9 23 31 9
=
2 4 6 8 0 34 46 18
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:10

2.4. Determinant of a Square Matrix

2.4.1. Determinant of a 1 × 1 Matrix
• If A = [a11], then
det(A) = a11.

2.4.2. Determinant of a 2 × 2 Matrix

 
a11 a12
• If A = , then
a21 a22
a11 a12
det(A) ≡ |A| ≡ = a11a22 − a12a21.
a21 a22
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:11

2.4.3. Determinant of an n × n Matrix (n ≥ 2)

• For any values of i and j, the ijth minor of det(A) (or the minor
of aij in det(A)) (written Mij ) is the determinant of the (n − 1) ×
(n − 1) sub-matrix of A obtained by deleting row i and column j
of A.
• Example:  
a11 a12 a13
A =  a21 a22 a23 
a31 a32 a33
a22 a23 a a a a
M11 = , M12 = 21 23 , . . . , M33 = 11 12
a32 a33 a31 a33 a21 a22
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:12

• The ijth cofactor of det(A) (or the cofactor of aij in det(A)) is

defined as
Cij = (−1)i+j Mij .

• (Cofactor Expansions of Determinants.) The determinant of an

n × n matrix A = [aij ] can be expressed as
det(A) = ai1Ci1 + ai2Ci2 + · · · + ainCin ∀i
= a1j C1j + a2j C2j + · · · + anj Cnj ∀j
• Example:
a11 a12 a13
a a a a a a
a21 a22 a23 = a11 22 23 − a12 21 23 + a13 21 22
a32 a33 a31 a33 a31 a32
a31 a32 a33
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:13

2.5. Nonsingular Matrix and the Inverse of

a Nonsingular Matrix
• Let A be a square matrix. If det(A) 6= 0, then A is called a
nonsingular or full-rank matrix. On the other hand, if det(A) = 0,
then A is called a singular matrix.

• An n×n matrix A is called invertible if there exists an n×n matrix

B such that AB = BA = In. B is called the inverse of A and the
common notation for inverse is A−1 .

• A is invertible ⇐⇒ A is nonsingular.
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:14

• (Uniqueness of Inverse Matrix.)

If AB = I and A is nonsingular, then
B = A−1

• If A is nonsingular, then
AB = AC =⇒ B=C

• If A and B are nonsingular n × n matrices, then

(AB)−1 = B −1 A−1

• If A is a nonsingular matrix, then

(A−1 )−1 = A
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:15

2.6. Computing the Inverse of Matrix

2.6.1. The Adjoint Matrix Method
• The adjoint matrix of A is defined by:
adj(A) = [Cij ]T
where Cij is the ijth cofactor of det(A).
• If A is a nonsingular matrix, then
1
A−1 = adj(A).
|A|
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:16

• Example:
     
4 1 1 2 −1 2/5 −1/5
A= =⇒ A−1 = =
3 2 5 −3 4 −3/5 4/5
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:17

• If  
a b
A=
c d
and |A| = ad − bc 6= 0, then
 
1 d −b
A−1 = .
|A| −c a
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:18

2.6.2. The Row Operations (Gauss-Jordan)

Method
• The following are the three types of elementary row operations on
matrix A:
1. Multiply any single row by a nonzero constant.
2. Interchange two rows of A.
3. Add a constant multiple of one row to another row.
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:19

• Two matrices are called row-equivalent if one can be obtained from

the other by a finite sequence of elementary row operations.

• If A is a nonsingular matrix, then A is row-equivalent to the n × n

identity matrix In .
 
• Consider the partitioned matrix A I , where A is nonsingular.
Pre-multiplying by A−1 , we obtain
A−1 A I = A−1A A−1 I = I A−1 .
     

Thus, applying a specific sequence of elementary row operations, A

is changed to I and I is changed to A−1 .
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:20

2.7. Solving a Linear System of n

Equations in n Unknowns
Consider the matrix equation: Ax = b, where A is a nonsingular
n × n matrix and b is an n × 1 column vector.

2.7.1. Method I
• Compute A−1 (by the Adjoint Matrix Method or the Row Opera-
tions Method).
• x = A−1b.
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:21

2.7.2. Method II
• By row operations:
−1 −1
   
A A b = I A b .
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:22

2.7.3. Method III

• Cramer’s Rule.
 
Let A = a1 · · · ai · · · an , where ai (for i = 1, 2, . . . , n) is
the ith column of the matrix A. Then
 
det a1 · · · ai−1 b ai+1 · · · an
xi = .
det(A)
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:23

2.8. Solving a Linear System of m

Equations in n (≥ m) Unknowns
• Consider the linear system of 2 equations in 3 unknowns:
a11x1 + a12x2 + a13x3 = b1
a21x1 + a22x2 + a23x3 = b2

• It is equivalent to the following system:

a11x1 + a12x2 = b1 − a13x3
a21x1 + a22x2 = b2 − a23x3
Chi-Kong Ng, SEEM2420, Dept. of SEEM, CUHK 2:24

• By Cramer’s Rule, we have

b1 − a13x3 a12 b1 a12 a a
− x3 13 12
b2 − a23x3 a22 b2 a22 a23 a22
x1 = =
a11 a12 a11 a12
a21 a22 a21 a22

a11 b1 − a13x3 a11 b1 a a

− x3 11 13
a21 b2 − a23x3 a21 b2 a21 a23
x2 = =
a11 a12 a11 a12
a21 a22 a21 a22

• Degree of freedom = number of unknowns − number of equations