Course in Operational Research - A.Y.

2024/25, II semester

Lecturer: Dr. Serena Crisci

Organization
• Timetable:
Tuesday, 1.10pm to 2.50pm, room E
Friday, 2.50pm to 5.20pm, Laboratorio di Programmazione e
Calcolo (LPC), ground floor

• Contacts: [Link]@[Link]
• Exam: written and oral exam
• Web page of the course: link
• Microsoft Team: only for sharing information on the lessons
and class materials (team code: tnglqx8)

S. Crisci
Course in Operational Research - A.Y. 2024/25, II semester

Information about the course

• Content: Recalls on basics linear algebra and geometry of space;
introduction to optimization and decision problems; linear
programming, the simplex method; fundamentals of integer linear
programming.
• Textbooks and reading lists:
[1] Introduction to Applied Linear Algebra - Vectors, Matrices, and
Least Squares, S. Boyd and L. Vandenberghe, Cambridge University
Press ([Link]
[2] Introduction to Linear Optimization, D. Bertsimas and J. N.
Tsitsiklis, Athena Scientific, (1997)
[3] Linear and Nonlinear Programming, D. G. Luenberger and Y. Ye,
Fourth edition, Springer, (2016)
[4] Advanced Optimization and Operations Research, A. K. Bhunia,
L. Sahoo, A. A. Shaikh, Springer, (2020)
[5] Teaching materials provided by the teacher

S. Crisci
Introduction

Operational research (OR) deals with the development and

application of quantitative methods for solving optimization
problems, in order to improve decision-making process

• Historical origins: 17-th century

• Modern operations research: dates back to the 1940s providing
solutions to problems of military operations during World War II
• OR has been applied in wide range of different industries:
production, transport, telecommunication, shipping, healthcare,
education, ...
• and different context: business setting, speed or distance in a
physical problem, expected return in the environment of risky
investments or social welfare in the context of government planning, ...

Any time you need to make decisions to optimize the use of (limited)
resources!

S. Crisci
Introduction

Optimization problem: requires to maximize a profit (income) or

minimize a cost (loss) subject to constraints that introduce
limitation to the exploitable resources.
In a decision process, we need to design an objective function

• to quantify performance,
• to measure the quality of the decision.

If one aspect of a problem can be isolated and characterized by an

objective function (profit or loss) optimization may provide a
suitable framework for analysis.
Mathematical techniques for operational research: Linear
programming, integer programming, dynamic programming,
nonlinear programming, stochastic programming

S. Crisci
Introduction

To sum up
Phases of a decision process:
• identification of the problem and its characteristics called
variables or unknowns
• formulation of a mathematical model
• finding one or more solutions through an optimization
algorithm
• validation of the model
• analysis of the results

There is no universal optimization algorithm!

S. Crisci
Example: Stigler’s diet problem (1945)

In his book The Man Who Ate Everything, Jeffrey Steingarten (1998),
the food editor for Vogue magazine, notes (p. 33):
Years ago I read somewhere that the absolutely cheapest survival
diet consists of peanut butter, whole wheat bread, nonfat dry milk
and a vitamin pill

S. Crisci
Example: Stigler’s diet problem (1945)

George Stigler (Nobel laureate in economics in 1982), posed the

following problem
For a moderately active man (economist) weighing 154 pounds (70
kg), how much of each of 77 foods should be eaten on a daily basis
so that the man’s intake of nine nutrients (including calories) will
be at least equal to the recommended dietary allowances (RDAs)
suggested by the National Research Council in 1943, with the cost
of the diet being minimal?

Stigler’s diet problem is a prime example of an OR model that

faithfully describes the real-world situation (but whose solution
validity is close to zero)

S. Crisci
Example: Stigler’s diet problem (1945)

[S. G. Garille, S. I. Gass, (2001) Stigler’s Diet Problem Revisited. Operations Research]
Stigler’s diet for 1939 data costs $39.93 per year, or $0.1093 per day,
equivalent to $840 in 2022, or $2 per day

It was the first large-scale problem that was solved using the simplex
method (Dantzig, 1947)

S. Crisci
Example: the knapsack problem

The knapsack problem is the following problem

Given a set of items, each with a weight and a value, deter-
mine which items to include in the collection so that the to-
tal weight is less than or equal to a given limit and the total
value is as large as possible.

S. Crisci
Example: the knapsack problem

The knapsack problem is the following problem

Given a set of items, each with a weight and a value, deter-
mine which items to include in the collection so that the to-
tal weight is less than or equal to a given limit and the total
value is as large as possible.

It derives its name from the problem faced by someone who is constrained
by a fixed-size knapsack and must fill it with the most valuable items.

Applications: resource allocation, space allocation, machine scheduling,

portfolio optimization . . .

The knapsack problem has been studied for more than a century, with early
works dating as far back as 1897

S. Crisci
Recall on basics of linear algebra
Vector space

Basic concept in linear algebra → Vector space

A vector space V over a field K (K = R or K = C) is a set of object
called vectors such that two binary operations are defined on V:

• vector addition

V×V → V
(u, v) → u+v

• scalar multiplication

K×V → V
(α, v) → α·v

S. Crisci
Vector space

For having a vector space, the two binary operations must satisfy
the following axioms
• u + (v + w) = (u + v) + w, ∀u, v, w ∈ V (associativity of +)
• u + v = v + u, ∀ u, v ∈ V (commutativity of +)
• ∃0 ∈ V such that v + 0 = v, ∀v ∈ V (identity element of +)
• For every v ∈ V, ∃ − v ∈ V, such that v + (−v) = 0 (inverse
elements of +)
• α(βv) = (αβ)v, ∀α, β ∈ K, ∀v ∈ V (compatibility of · with field
multiplication)
• α(u + v) = αu + αv, ∀α ∈ K, ∀u, v ∈ V (distributivity of · with
respect to +)
• (α + β)v = αv + βv, ∀α, β ∈ K, ∀v ∈ V (distributivity of · with
respect to field addition)
• ∃1 ∈ K such that 1v = v, ∀v ∈ V (identity element of scalar
multiplication)

S. Crisci
Vector space

The elements of V are called vectors, the elements of K are called

scalars, 0 ∈ V is called zero vector, −v is said additive inverse (or
opposite) of v.
Examples
R is a vector space on R
R2 is a vector space on R (ordered pair of real numbers)
Rn is a vector space on R
a vector is an ordered finite list of numbers
 
x1
  entries, coefficients, components
z }| {
 x2 
 .  or (x1 , x2 , . . . , xn )
 . 
 . 
xn

Size (dimension or length) of v: is the number of its elements

S. Crisci
Vectors

     
x1 y1 x1 + y1
     
 x2   y2   x2 + y2 
 .. + .. = .. 
     
 .   .   . 
xn yn xn + yn
   
x1 αx1
   
 x2   αx2 
α·
 ..  
= .. 

 .   . 
xn αxn
Zero vector → 0 = (0, . . . , 0)
Unit vector → e1 = (1, 0, . . . , 0), e2 = (0, 1, 0, . . . , 0), . . .
Zero and unit vectors are sparse, nnz(v) denotes the number of
non-zero entries of v

S. Crisci
Further examples

An n−vector can be used to represent n quantities or values in an

application

S. Crisci
Further examples

An n−vector can be used to represent n quantities or values in an

application
Vectors in the plane or space
A 2−vector can be used to represent a position or location in a
plane, a 3−vector is used to represent a position or location of
some point in 3-dimensional space

S. Crisci
Further examples

An n−vector can be used to represent n quantities or values in an

application
Quantities
An n-vector v can represent the amounts or quantities of n different
resources or products held by an entity such as a company.
Negative entries mean an amount of the resource owed to another
party (or consumed, or to be disposed of)

S. Crisci
Further examples

An n−vector can be used to represent n quantities or values in an

application
Vector space of polynomials
The set of polynomials of degree at most n with coefficients in R (or
a field K) is a vector space over R, denoted Pn [x]

Pn [x] = {a0 + a1 x + a2 x2 + · · · + an xn | a0 , a1 , . . . , an ∈ R, n fixed}

Vector addition and scalar multiplication are defined in the obvious

manner

S. Crisci
Linear combination

Let V be a vector space over R, let consider α1 , α2 , . . . , αn ∈ R and

v1 , v2 , . . . , vn ∈ V, then the following vector

α1 v1 + α2 v2 + · · · + αn vn ∈ V

is said a linear combination of the vectors v1 , v2 , . . . , vn ; the scalars

α1 , α2 , . . . , αn are called the coefficients of the linear combination

S. Crisci
Linear combination

Let V be a vector space over R, let consider α1 , α2 , . . . , αn ∈ R and

v1 , v2 , . . . , vn ∈ V, then the following vector

α1 v1 + α2 v2 + · · · + αn vn ∈ V

is said a linear combination of the vectors v1 , v2 , . . . , vn ; the scalars

α1 , α2 , . . . , αn are called the coefficients of the linear combination
Example
In R2 let consider the vectors v1 = (1, 0), v2 = (1, 2), v3 = (0, 2),
α1 = 2, α2 = 1, α3 = −1, then

α1 v1 + α2 v2 + α3 v3 = 2(1, 0) + 1(1, 2) − 1(0, 2)

= (2, 0) + (1, 2) − (0, 2) = (3, 0)

(3, 0) is a linear combination of v1 , v2 , v3 with coefficients α1 = 2,

α2 = 1, α3 = −1

S. Crisci
Linear combination of unit vectors

Any n−vector v ∈ V can be written as linear combination of unit

vectors e1 = (1, 0, . . . , 0), e2 = (0, 1, . . . , 0), . . . , en = (0, 0, . . . , 1) as

v = α1 e1 + α2 e2 + · · · + αn en

Here, α1 = v1 , α2 = v2 , . . . , αn = vn , where v = (v1 , v2 , . . . , vn )

The set {e1 , e2 , . . . , en } is called natural or canonical basis of V
A set B = {w1 , w2 , . . . , wn } ⊆ V is called a basis if ∀v ∈ V may be
written in a unique way as
n
X
v= βi wi = β1 w1 + β2 w2 + · · · + βn wn
i=1

The coefficients βi , i = 1, . . . , n, are referred to as components or

coordinates of the vector with respect to the basis B.

S. Crisci
Special linear combinations

Given m vectors {v1 , v2 , . . . , vm }

m
X
• αi vi with α1 = · · · = αm = 1 → sum
i=1
m
X
• αi vi with α1 = · · · = αn = 1/m → average
i=1
m
X
• αi vi with αi ≥ 0 and α1 + · · · + αn = 1 → convex combination
i=1
As a particular example, every convex combination of two
points (vectors) lies on the line segment between the points.

S. Crisci
Inner product (algebraic definition)

The inner product (or scalar product ) of two vectors

   
x1 y1
   
 x2   y2 
x=  .. 
 , y = 
 .. 

 .   . 
xn yn

is defined as

xT y = x1 y1 + x2 y2 + · · · + xn yn é it is a scalar!

Here, xT denotes the transpose of vector x

xT = [x1 , x2 , . . . , xn ]

S. Crisci
Properties of the inner product

Let u, v, and w be vectors of the same size, and let α ∈ R, we have

• uT v = vT u (commutativity)
• (αu)T v = α(uT v) (associativity with respect to scalar
multiplication)
• (u + v)T w = uT w + vT w (distributivity with respect to vector
addition)

Combining these properties we obtain the following useful example

(u + v)T (w + z) = uT w + uT z + vT w + vT z

that is is analogous to expanding a product of sums in algebra

S. Crisci
Some useful applications of inner product

Sum of squares
xT x = x21 + x22 + · · · + x2n → sum of the squares of the elements of x

Selective sum
Let x be a vector with entries equal to either 0 or 1. Then xT y is the
sum of the elements in y for which xi = 1

S. Crisci
Some useful applications of inner product

Co-occurrence
Let x and y be vectors such that each of their elements is either 0 or
1, then xT y is the number of co-occurences

If x and y describe subsets of n objects, then xT y gives the number of

objects in the intersection of the two subsets

S. Crisci
Some useful applications of inner product

Price-quantity
p → prices of n goods
q → quantities of the n goods

pT q is the total cost of the goods given by the vector q

S. Crisci
Some useful applications of inner product

Weights and features

f → features of an object
w → vector of the weights (of the same size of f)

wT f is the sum of the feature values, scaled (or weighted) by the

weights (and is sometimes called a score)

S. Crisci
Some useful applications of inner product

Document sentiment analysis

x → histogram of word occurrences in a document from a dictionary
of n words
Each word is assigned to one of three sentiment categories:
• Positive
• Negative
• Neutral (words that are neither positive nor negative)

w → encodes the word categories, i.e.

• wi = 1 if word i is positive
• wi = −1 if word i is negative
• wi = 0 if word i is neutral

wT x → gives a rough measure of the sentiment of the document

S. Crisci
Exercise

Word count and word count histogram vectors

Suppose the n-vector w is the word count vector associated with a
document and a dictionary of n words. For simplicity we will assume
that all words in the document appear in the dictionary.

(a) What is 1T w?
(b) What does w282 = 0 mean?
(c) Let h be the n-vector that gives the histogram of the word
counts, i.e., hi is the fraction of the words in the document that
are word i. Use vector notation to express h in terms of w. (You
can assume that the document contains at least one word.)

S. Crisci
Exercise

Average age in a population

Suppose the 100−vector x represents the distribution of ages in
some population of people, with xi being the number of i − 1 year
olds, for i = 1, . . . , 100. (Assume that x ̸= 0, and that there is no one
in the population over age 99) Find expressions, using vector
notation, for the following quantities

(a) The total number of people in the population

(b) The total number of people in the population age 65 and over
(c) The average age of the population

S. Crisci
Linear dependence and independence

Let v1 , v2 , . . . , vm be vectors of the space vector V over the field K.

These vectors are linearly dependent if there exist α1 , α2 , . . . , αn
that are not all zero such that

α1 v1 + α2 v2 + · · · + αm vm = 0.

When a collection of vectors is linearly dependent, at least one of

the vectors can be expressed as a linear combination of the other
vectors (and conversely).
The vectors v1 , v2 , . . . , vm are linearly independent if they are not
linearly dependent, i.e. if

α1 v1 + α2 v2 + · · · + αm vm = 0

only holds for

α1 = α2 = · · · = αn = 0.

S. Crisci
Linear dependence and independence

• Any list of vectors containing the zero vector is linearly

dependent
• The standard unit vectors e1 , · · · , en are linearly independent
• A linearly independent collection of n−vectors can have at
most n elements
• A basis is a collection of n linearly independent n−vectors
• If x is a linear combination of linearly independent vectors, the
coeffcients that form x are unique

S. Crisci
Linear functions

Let V and W be vector spaces over the same field K

A function f : V → W is a linear function if

• f(v1 + v2 ) = f(v1 ) + f(v2 ) ∀v1 , v2 ∈ V (additivity)

• f(αv) = αf(v) ∀v ∈ V, α ∈ K (homogeneity)

Remark. The operations at the left-hand side are performed in V,

while those at the right-hand side are performed in W

Characterization of a linear function f

f : V → W is linear ⇔ f(αv1 + βv2 ) = αf(v1 ) + βf(v2 ),
∀α, β ∈ K, v1 , v2 ∈ V

S. Crisci
Linear functions

Examples
• Null function
f : V → W such that f(v) = 0, is a linear function
• Identity function
i : V → V such that i(v) = v, is a linear function
• Inner product function
f : Rn → R such that f(x) = aT x, for some fixed vector a

If a function f : Rn → R is linear, then f can be expressed as the inner

product of its argument with some fixed vector and this
representation is unique

S. Crisci
Linear functions

Let f : U → V and g : V → W be linear functions.

• The composition of f and g, h = g ◦ f, is a linear function

• The sum f + g is a linear function
• Let α ∈ K, the function αf is a linear function

Properties of a linear function f : V → W

• f(0) = 0
• f(−v) = −f(v)
• f(v1 − v2 ) = f(v1 ) − f(v2 )
• If v1 , v2 , . . . , vn are linearly dependent in V, then
f(v1 ), f(v2 ), . . . , f(vn ) are linearly dependent in W
• If f(v1 ), f(v2 ), . . . , f(vn ) are linearly independent, then
v1 , v2 , . . . , vn are linearly independent

S. Crisci
Examples

Average
The mean or average value of an n-vector defined as
1
f(x) = (x1 + x2 + · · · + xn )
n
is a linear function

Maximum
The maximum element of an n−vector x

f(x) = max{x1 , x2 , . . . , xn }

is NOT a linear function (except when n = 1).

Counterexample:
n = 2, take x = (1, −1), y = (−1, 1), α = 1/2, β = 1/2

S. Crisci
Exercise

Linear or not linear

Determine whether each of the following scalar-valued functions of
n− vectors is linear. If it is a linear function, give its inner product
representation, i.e., an n−vector a for which f(x) = aT x for all x. If it
is not linear, give a counterexample.

(a) The spread of values of the vector, defined as

f(x) = maxk xk − mink xk
(b) The difference of the last element and the first, f(x) = xn − x1
(c) The median of an n−vector, where we will assume n = 2k + 1 is
odd. The median of the vector x is defined as the (k + 1)st
largest number among the entries of x. For example, the
median of (−7.1; 3.2; −1.5) is −1.5.

S. Crisci
Matrices

Let m, n be positive natural numbers.

A real matrix m × n is a rectangular array with real entries, m rows
and n columns  
a11 a12 · · · a1n
 a 
 21 a22 · · · a2n 
 . 
 . 
 . 
 
 .. 
 . 
am1 am2 · · · amn

m × n is the size or dimension of the matrix, i.e. the numbers of

rows and columns.
The subscripts i and j are called the (row and column) indices.
Let A = (aij ), B = (bij ) m × n matrices, A = B if aij = bij , ∀i, j

S. Crisci
Examples

The most direct interpretation of a matrix is as a table of numbers

that depend on two indices, i and j.
Images
A black and white image with M × N pixels is naturally represented
as an M × N matrix. The row index i gives the vertical position of the
pixel, the column index j gives the horizontal position of the pixel

Prices from multiple suppliers

An m × n matrix P gives the prices of n different goods from m
different suppliers (or locations)

S. Crisci
Matrices

• A square matrix has an equal number of rows and columns. A

square matrix of size n × n is said to be of order n

• [x1 , x2 , · · · , xn ] → 1 × n matrix
 
x1
 
 x2 
•  . 

 → n × 1 matrix
 .. 
xn
 
a11 a12 ··· a1n  
 a21 a22 ··· a2n  a1j
   
 ..   a 
  j  2j , Ai = (ai1 , ai2 , . . . , ain )
A= . , A =  . 



..   .. 
 .  amj
am1 am2 ··· amn

S. Crisci
Matrices

• Zero matrix → matrix with all elements equal to zero

• Identity matrix → square matrix such that its diagonal
elements, i.e., those with equal row and column indices, are all
equal to 1, and its off-diagonal elements (those with unequal
row and column indices) are zero
Example
 
1 0 0 0
 0 1 0 0  h i
 
I=  = e1 e2 e3 e4 (block matrix notation)
 0 0 1 0 
0 0 0 1

S. Crisci
Sparse matrices

A matrix A is said to be sparse if many of its entries are zero

• sparsity pattern: is the set of indices (i, j) such that aij ̸= 0
• If A is m × n, nnz(A) ≤ mn
• density of A: nnz(A)/(mn) ≤ 1
Densities of sparse matrices that arise in applications are
typically small or very small, as in 10−2 or 10−4

A matrix is sparse if it has enough zero entries that it pays to take

advantage of them (James H. Wilkinson)
Sparse matrices can be stored and manipulated efficiently on a
computer.
Many common matrices are sparse: zero matrix, identity matrix,
diagonal matrix, triangular matrix.

S. Crisci
Matrices

• Matrix transpose. Let A = (aij ) be a m × n matrix, the transpose

of A is a n × m matrix given by AT = (bij ) such that bij = aji
Example  
" # 0 3
0 2 1  
A= AT =  2 7 
3 7 2
1 2
• Transpose of block matrix. Let consider a 2 × 2 block matrix

" # " #
A B AT CT
M= MT =
C D BT DT
where A, B, C, and D are matrices with compatible sizes
• Symmetric matrix. A matrix A = (aij ) is symmetric if A = AT , that
means aij = aji , ∀i, j. A symmetric matrix is always square.

S. Crisci
Operations with matrices

• Matrix addition. If A and B are matrices of the same size, then

they can be added

A + B = (cij ), with cij = aij + bij

• Scalar multiplication. A matrix A = (aij ) can be multiplied by a

scalar α ∈ R as follows:

αA = (dij ), with dij = αaij

S. Crisci
Operations with matrices

• Matrix-vector multiplication. If A is an m × n matrix and x is an

n−vector, the matrix-vector multiplication is the m−vector
y = Ax given by  
A1 x
 
 A2 x 
y= . 


 .. 
Am x
where Ai x denotes the inner product between i−th row of
matrix A and the vector x

S. Crisci
Operations with matrices

• Matrix-vector multiplication. If A is an m × n matrix and x is an

n−vector, the matrix-vector multiplication is the m−vector
y = Ax given by  
A1 x
 
 A2 x 
y= . 


 .. 
Am x
where Ai x denotes the inner product between i−th row of
matrix A and the vector x

Remark. We have Ix = x for any n−vector x (the identity matrix here

has size n × n)

S. Crisci
Operations with matrices

• Matrix-vector multiplication. If A is an m × n matrix and x is an

n−vector, the matrix-vector multiplication is the m−vector
y = Ax given by  
A1 x
 
 A2 x 
y= . 


 .. 
Am x
where Ai x denotes the inner product between i−th row of
matrix A and the vector x

Picking out columns and rows.

Aej = Aj , the j−th column of A. Multiplying a unit vector by a matrix
‘picks out’ one of the columns of the matrix, while AT ei = ATi (i.e.
(AT ei )T = Ai )

S. Crisci
Operations with matrices

• Matrix-vector multiplication. If A is an m × n matrix and x is an

n−vector, the matrix-vector multiplication is the m−vector
y = Ax given by  
A1 x
 
 A2 x 
y= . 


 .. 
Am x
where Ai x denotes the inner product between i−th row of
matrix A and the vector x

Input-output interpretation.
Let A be an m × n matrix, we can interpret the relation y = Ax as a
mapping from the n-vector x to the m-vector y, in other words, we
may think of x as an input, and y as the corresponding output.

S. Crisci
Operations with matrices

• Matrix-vector multiplication. If A is an m × n matrix and x is an

n−vector, the matrix-vector multiplication is the m−vector
y = Ax given by  
A1 x
 
 A2 x 
y= . 


 .. 
Am x
where Ai x denotes the inner product between i−th row of
matrix A and the vector x

Properties of matrix-vector multiplication

A(u + v) = Au + Av
(A + B)v = Av + Bv
(αA)v = α(Av)

S. Crisci
Operations with matrices

• Matrix multiplication. If A is m × n and B is n × p, then the

product AB is defined, and the size of the product matrix AB is
m×p  
A1 B1 A1 B2 · · · A1 Bp
 
 A2 B 1 A2 B 2 · · · A2 B p 

AB =  . .. 

 .. . 
1 2 p
Am B Am B · · · Am B

where Ai Bj denotes the inner product between i−th row of

matrix A and the j−th column of matrix B

S. Crisci
Operations with matrices

• Matrix multiplication. If A is m × n and B is n × p, then the

product AB is defined, and the size of the product matrix AB is
m×p  
A1 B1 A1 B2 · · · A1 Bp
 
 A2 B 1 A2 B 2 · · · A2 B p 

AB =  . .. 

 .. . 
1 2 p
Am B Am B · · · Am B

where Ai Bj denotes the inner product between i−th row of

matrix A and the j−th column of matrix B

Properties of matrix multiplication

AI = A and IA = A
AB ̸= BA → matrix multiplication is (in general) NOT commutative!
A(BC) = (AB)C; A(B + C) = AB + AC; α(AB) = (αA)B
(AB)T = BT AT
S. Crisci
Systems of linear equations

A system of m linear equations in n variables (or unknowns)

x1 , x2 , . . . , xn is given by


 a11 x1 + a12 x2 + · · · + a1n xn = b1


 a21 x1 + a22 x2 + · · · + a2n xn = b2
 .
..




am1 x1 + am2 x2 + · · · + amn xn = bm
The coefficients aij are the entries of a matrix A of size m × n and the
right-hand sides bi are the entries of a n−vector b, so we have the
matrix notation
Ax = b, A ∈ Rm×n , b ∈ Rm , x ∈ Rn
 
x1
 . 
An n-vector x =  
 ..  is a solution of the linear system if equation
xn
Ax = b is verified by its entries

S. Crisci
Systems of linear equations

Given a system of m linear equations in n variables, we may have

• m > n → over-determined
• m < n → under-determined
• m = n → square

A system of equations with zero right-hand side,

Ax = 0

is called a homogeneous system of equations. Any homogeneous

system of equations has x = 0 as a solution.

S. Crisci
Example

Coefficients of linear combinations

Let A1 , A2 , . . . , An denotes the columns of a m × n matrix A, the
system of linear equations Ax = B can be viewed as

x1 A1 + x2 A2 + · · · + xn An = b

that is, b is a linear combination of the columns of A with

coefficients x1 , x2 , . . . , xn .

Then, solving Ax = b is the same as finding coefficients that express

b as a linear combination of the vectors A1 , A2 , . . . , An .

S. Crisci
Example

Leontief input-output model

A simple economy model developed, in the late 1940s, by Wassily Leontief, a
russian-american economist who won the Nobel Prize in 1973

Model hypotheses:
• n industries producing n different goods
• each industry sells its products to other industries and external
consumers such that input equals the output, that means
consumption equals production

S. Crisci
Example

Leontief input-output model

A simple economy model developed in the late 1940s by Wassily Leontief, a
russian-american economist who won the Nobel Prize in 1973

Variables of the model:

• xi → units of good i (output)
• j-th sector, in order to produce 1 unit, must use aij units from
sector i, then aij xj is the input of sector i that flows to sector j
• bi → external demand for sector i

Let x1 , x2 , . . . , xn be the total outputs of industries S1 , S2 , . . . , Sn ,

respectively. We can write


 x1 = a11 x1 + a12 x2 + · · · + a1n xn + b1


 x2 = a21 x1 + a22 x2 + · · · + a2n xn + b2
 ..

 .


xn = an1 x1 + am2 x2 + · · · + ann xn + bn

S. Crisci
Example

Leontief input-output model

A simple economy model developed in the late 1940s by Wassily Leontief, a
russian-american economist who won the Nobel Prize in 1973

The total consumption equals the total production for the product
of each industry Si . In matrix form:

x = Ax + b

• A → input-output matrix
• b → external demand vector
• x → production level vector

When b ̸= 0 the model is referred to as open Leontief model

Given A and b, the problem is to determine x as a solution of

x = Ax + b ⇐⇒ (In − A)x = b

S. Crisci
Exercise

Application - Leontief model

In a village there is a farmer, a carpenter, and a tailor, who provide the three
essential goods: food, shelter, and clothing.
Let us assume:

• whatever the farmer produces, 20% is used by him, 15% by the

carpenter, 10% by the tailor, and the consumer uses the other 40
billion dollars worth of the food;
• 10% percent of the carpenter’s production is used by him, 25% by the
farmer, 5% by the tailor, and 50 billion dollars worth by the consumer;
• 15% of the clothing is used by the tailor, 10% by the farmer, 5% by the
carpenter, and the remaining 60 billion dollars worth by the consumer.

Write the internal consumption in a table, and express the consumer

demand as the vector b.
What should be, in billions of dollars, the required output by each industry
to meet the demand given by b?

S. Crisci
Solving a linear system of equations

A solution of a linear system Ax = b is an assignment of values to

the variables x1 , x2 , . . . , xn such that each of the equations is
satisfied. The set of all possible solutions is called the solution set.

A linear system may have:

• infinitely many solutions
• a single unique solution
• no solution

S. Crisci
Solving a linear system of equations

Geometric interpretation

from [Link]

S. Crisci
Solving a linear system of equations

Geometric interpretation

from [Link]

S. Crisci
Solving a linear system of equations

A linear system Ax = b is said to be consistent if it admits at least

one solution; otherwise, if it has no solution, it is inconsistent.

A homogeneous system of equations Ax = 0 is always consistent.

S. Crisci
Solving a linear system of equations

A linear system Ax = b is said to be consistent if it admits at least

one solution; otherwise, if it has no solution, it is inconsistent.

A homogeneous system of equations Ax = 0 is always consistent.

A special case
Given a square (m = n) linear system Ax = b, if the columns of A are
linear independent then the system has a unique solution.

S. Crisci
Cramer’s rule
Cramer’s rule provides an explicit formula for the solution of a
system of linear equations
Example 

 3x + 2y − z =1
x+z =3

 2x − y − 2z =4
det(A) = 12
1 2 −1 3 1 −1
3 0 1 1 3 1
4 −1 −2 24 2 4 −2 −24
x= = = 2, y= = = −2
12 12 12 12
3 2 1
1 0 3
2 −1 4 12
z= = =1
12 12

S. Crisci
Solving linear equations with the inverse

A square (n = m) matrix A is invertible if there exists a n × n matrix

B such that
AB = BA = In
B is said inverse of A and is denoted by A−1 .

Given a square system of n linear equations with n variables Ax = b,

if A is invertible (det(A) ̸= 0) then for any n-vector b, we can write

x = In x = (A−1 A)x = A−1 Ax = A−1 b

The square system of linear equations Ax = b, with A invertible, has

the unique solution x = A−1 b, for any n-vector b.
Remark. For n very large, this method can be costly!

S. Crisci
Rank of a matrix

The rank of a matrix A is the maximal number of linearly

independent columns (or, equivalently, rows) of A
It is denoted by rank(A)
If A is a square matrix of order n such that det(A) ̸= 0 (i.e. A is
nonsingular), then rank(A) = n

S. Crisci
Rouchè-Capelli theorem

Rouchè-Capelli theorem
A system of m linear equations with n variables is consistent (i.e.
admits a solution) if and only if

rank(A) = rank([A|b]),

i.e. the rank of its coefficient matrix A is equal to the rank of its
augmented matrix [A|b].
If there are solutions, they form an affine subspace of Rn of
dimension n − rank(A). In particular:

• if n = rank(A), the solution is unique,

• otherwise there are infinitely many solutions.

S. Crisci
Recap

Let Ax = b be a system of m linear equations in n variables

• if rank(A) ̸= rank([A|b]), the system is inconsistent (no

solutions!) (impossible or over-determined system)

• if rank(A) = rank([A|b]) = k, the system is consistent;

if k = n the solution is unique, if k < n the system has ∞n−k
solutions (under-determined system)

S. Crisci
Exercise

Solve the following systems

 of linear equations
 2x + y − z
 =3
x − 3y + 2z =2

 5x + 13y − 10z = 6


 x−y+z =1
2x − 3y + 4z = 3

 3x + 4y + 5z = 0


 x − y + 2z = 3
x+y+z =2

 x+y−z =0

S. Crisci
Exercise

Set up and solve the following problems

• A 2% saline solution is to be combined and mixed with a 5%
saline solution to produce 72 ounces of a 2.5% saline solution.
How much of each is needed?
• A town’s population has been growing linearly. In 2013 the
population was 6.200. By 2018 the population had grown to
8.100. Assume this trend continues.
Predict the population in 2022. Identify the year in which the
population will reach 15.000.
(Hint. Define the input x as number of years since 2013, i.e. x = 0
would correspond to 2013...)

S. Crisci
Complexity of vector operations

Real numbers → floating point notation: representing a real number

using a block of 64 bits (0s and 1s), or 8 bytes (groups of 8 bits).
Each of the 264 possible sequences of bits corresponds to a specific
real number.

Vectors are stored as arrays of floating point numbers (or integers,

when the entries are all integers).

Storing an n-vector requires 8n bytes to store.

Current memory and storage devices, with capacities measured in many
gigabytes (109 bytes), can easily store vectors with dimensions in the
millions or billions. Sparse vectors are stored in a more efficient way that
keeps track of indices and values of the nonzero entries.

S. Crisci
Complexity of vector operations

When computers carry out operations (addition, subtraction,

multiplication, division, or other arithmetic operations) on numbers
represented in floating point format, the result is rounded to the
nearest floating point number.

These operations are called floating point operations.

The very small error in the computed result is called round−off

error.

S. Crisci
Complexity of vector operations

Let x, y n-vectors, α ∈ R

• αx −→ n scalar multiplications
• x + y −→ n additions
• xT y −→ n multiplications and n − 1 additions, then the
complexity is 2n − 1 flops

In all these cases we say that the computation has order n, denoted
by O(n)

S. Crisci
Complexity of sparse vector operations

Let x, y be sparse n-vectors, α ∈ R

• αx −→ nnz(x) flops
• x + y −→ no more than min{nnz(x), nnz(y)}
• xT y −→ no more than 2 min{nnz(x), nnz(y)} flops

Remark. If the sparsity patterns of x and y do not overlap, then

computing x + y and xT y requires 0 flops.

S. Crisci
Complexity of matrix operations

Given m × n matrices A, B, n × p matrix C, n-vector x, α ∈ R

• αA −→ mn flops
• A + B −→ mn flops
• Ax −→ m(2n − 1) flops
• AC −→ mp(2n − 1) flops

S. Crisci
Complexity of sparse matrix operations

Let m × n sparse matrix A, B, n × p matrix C

• αA −→ nnz(A) flops
• A + B −→ no more than min{nnz(A), nnz(B)} flops
• Ax −→ between nnz(A) and 2nnz(A) flops
• AC −→ no more than 2 min{nnz(A)p, nnz(C)m}

S. Crisci
Reference:

• Introduction to Applied Linear Algebra - Vectors, Matrices, and

Least Squares, S. Boyd and L. Vandenberghe, Cambridge
University Press ([Link]

S. Crisci