Matrices, Graphs & Convexity
Summary
EBB073A05
Semester IA
Wouter Voskuilen
S4916344
Abstract
This summary mostly contains the relevant definitions, theorems, properties and
explanations of the theory covered in this course (corresponding Lecture Notes
chapters). For extra explanations and examples corresponding to the theory, take
a look at the Lecture Notes and the lecture examples. Exercises are also not covered
in this summary.
1
,Wouter Voskuilen Matrices, Graphs & Convexity
Contents
1 Chapter 1 4
1.1 Matrices and linear maps . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Special matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Similar matrices, congruent matrices and symmetric matrices . . . . . . . 6
1.4 Positive (semi-)definite matrices and idempotent matrices . . . . . . . . . 7
1.5 Submatrices, block matrices and Kronecker products of matrices . . . . . 8
2 Singular value decomposition and generalized inverse 11
2.1 Singular Value Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 One-sided inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Generalized inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 The Moore-Penrose inverse . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Graphs 15
3.1 Definitions and Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Subgraphs, complementary graphs and isomorphic graphs . . . . . . . . . 16
3.3 Euler paths and Euler circuits . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Non-negative matrices 18
4.1 Reducible and irreducible non-negative matrices . . . . . . . . . . . . . . . 18
4.2 Dominant eigenvalue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Primitive matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4 Non-negative matrices and directed graphs . . . . . . . . . . . . . . . . . 20
4.5 Non-negative matrices and M-matrices . . . . . . . . . . . . . . . . . . . . 21
4.6 Stochastic matrices and finite Markov chains . . . . . . . . . . . . . . . . 21
5 Introduction to convexity 22
5.1 convex sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2 Convex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.3 Quasi-convex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6 Hyper-planes and cones 26
6.1 Seperating hyper-planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.2 Supporting hyper-planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.3 Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.4 Combination of seperating hyper-planes and cones . . . . . . . . . . . . . 27
7 Extrema 29
7.1 Extreme points of convex sets . . . . . . . . . . . . . . . . . . . . . . . . . 29
7.2 Convex functions and extreme values . . . . . . . . . . . . . . . . . . . . . 29
2
,Wouter Voskuilen Matrices, Graphs & Convexity
Notations
Notation Meaning Notation Meaning
R collection of real numbers Rn n-dimensional linear space
∅ empty set =⇒ implies
⇐⇒ if and only if ∈ element of
∈
/ no element of ⊂ subset of
∩ intersection ∪ union
P
summation sign ⊗ Kronecker product
⊕ direct sum Rm×n vector-space of all m × n real matrices
In n × n identity matrix diag D, diag(D) diagonal-matrix D
A−1 the inverse of A A⊤ transpose of A
A−1
L a left inverse of A [aij ] a matrix A
[aij ]1≤i≤m m × n matrix A det A, det(A) determinant of A
1≤j≤n
Tr A, Tr(A) trace of A A−1
R a right inverse of A
Ker A, Ker(A) null-space of A Im A, Im(A) image of A
AI generalized inverse of A A+ the Moore-Penrose inverse of A
A≥0 all entries aij > 0 A>0 A ≥ 0 and at least one entry aij > 0
A≫0 all entries aij > 0 λ∗ (A), λ∗A dominant eigenvalue of A
σk (A) kth largest singular value of A GA , G(A) directed graph associated to A
[x1 · · · xn ]⊤ (x1 , · · · , xn ) = x ∈ Rn (x, y) inner product of x and y
∥x∥ norm of x B(x; ε) open ball with radius ε centered at x
{x ∈ V : Px } the set of all x in V with property Px V \D {x ∈ V : x ∈
/ D}
x≥0 all coordinates xk ≥ 0 x>0 x ≥ 0 and at least one coordinate xk > 0
Rn+ {x ∈ Rn : x ≥ 0} x≫0 all coordinates xk > 0
Rn++ {x ∈ Rn : x ≫ 0} Int V , Int(V ) the interior of V
Cl V , Cl(V ), V̄ the closure of V ∂V the boundary of V
Conv V , Conv(V ) the convex hull of V Epi V , Epi(V ) the epi-graph of V
Hypo f , Hypo(f ) the hypo-graph of f Dk f the first order partial derivative of f w.r.t. kth variable
Dij f second order partial derivative of f w.r.t. ith and jth variables ∇f (a) the gradient of f at a
Hf (a) the Hessian matrix of f at a
3
, Wouter Voskuilen Matrices, Graphs & Convexity
1 Chapter 1
1.1 Matrices and linear maps
We denote the vector space of all m × n real matrices by Rm×n , and
a11 · · · a1n
m×n .. .. .
A∈R ⇔ A = [aij ]1≤i≤m = . .
1≤j≤n
am1 · · · amn
Some operations for matrices are:
Addition (Rm×n × Rm×n → Rm×n ) C =A+B cij = aij + bij
Scalar Multiplication (R × Rm×n → Rm×n ) C =α·A cij =Pα · aij
Multiplication (Rm×n × Rn×s → Rm×s ) C = AB cij = nk=1 aik bkj
Transpose (Rm×n → Rn×m ) C = A⊤ cij = aji
A square matrix is a permutation matrix if every row and every column has ex-
actly one entry equal to 1 and all other entries are equal to 0.
If the matrices A and B in Rn×n satisfy AB = BA = In , then the matrix B is the
inverse of A and it is denoted by A−1 . If A−1 exists, then A is regular (non-singular); if
A−1 does not exist then A is singular.
Let A ∈ Rn×n be given. The determinant of A, det(A), is defined as follows: det(A) = a11
if n = 1 and for n > 1,
n
X
det(A) = (−1)j+1 a1j det (A1j ) ,
j=1
where A1j ∈ R(n−1)×(n−1) is the resulting matrix by deleting the 1st row and j th column
from A (1 ≤ j ≤ n).
Some properties of the determinant:
(a) det(AB) = det(A) det(B) A, B ∈ Rn×n
(b) det A⊤ = det(A) A ∈ Rn×n
(c) det(αA) = αn · det(A) α ∈ R, A ∈ Rn×n
(d) det(A) ̸= 0 ⇔ A is regular A ∈ Rn×n
We identify the vector space Rm with the vector space Rm×1 and the column vectors
are usually denoted by small letters, y, and the coordinates are denoted by the same
4
Summary
EBB073A05
Semester IA
Wouter Voskuilen
S4916344
Abstract
This summary mostly contains the relevant definitions, theorems, properties and
explanations of the theory covered in this course (corresponding Lecture Notes
chapters). For extra explanations and examples corresponding to the theory, take
a look at the Lecture Notes and the lecture examples. Exercises are also not covered
in this summary.
1
,Wouter Voskuilen Matrices, Graphs & Convexity
Contents
1 Chapter 1 4
1.1 Matrices and linear maps . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Special matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Similar matrices, congruent matrices and symmetric matrices . . . . . . . 6
1.4 Positive (semi-)definite matrices and idempotent matrices . . . . . . . . . 7
1.5 Submatrices, block matrices and Kronecker products of matrices . . . . . 8
2 Singular value decomposition and generalized inverse 11
2.1 Singular Value Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 One-sided inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Generalized inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 The Moore-Penrose inverse . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 Graphs 15
3.1 Definitions and Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Subgraphs, complementary graphs and isomorphic graphs . . . . . . . . . 16
3.3 Euler paths and Euler circuits . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Non-negative matrices 18
4.1 Reducible and irreducible non-negative matrices . . . . . . . . . . . . . . . 18
4.2 Dominant eigenvalue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Primitive matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4 Non-negative matrices and directed graphs . . . . . . . . . . . . . . . . . 20
4.5 Non-negative matrices and M-matrices . . . . . . . . . . . . . . . . . . . . 21
4.6 Stochastic matrices and finite Markov chains . . . . . . . . . . . . . . . . 21
5 Introduction to convexity 22
5.1 convex sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.2 Convex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.3 Quasi-convex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6 Hyper-planes and cones 26
6.1 Seperating hyper-planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.2 Supporting hyper-planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.3 Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.4 Combination of seperating hyper-planes and cones . . . . . . . . . . . . . 27
7 Extrema 29
7.1 Extreme points of convex sets . . . . . . . . . . . . . . . . . . . . . . . . . 29
7.2 Convex functions and extreme values . . . . . . . . . . . . . . . . . . . . . 29
2
,Wouter Voskuilen Matrices, Graphs & Convexity
Notations
Notation Meaning Notation Meaning
R collection of real numbers Rn n-dimensional linear space
∅ empty set =⇒ implies
⇐⇒ if and only if ∈ element of
∈
/ no element of ⊂ subset of
∩ intersection ∪ union
P
summation sign ⊗ Kronecker product
⊕ direct sum Rm×n vector-space of all m × n real matrices
In n × n identity matrix diag D, diag(D) diagonal-matrix D
A−1 the inverse of A A⊤ transpose of A
A−1
L a left inverse of A [aij ] a matrix A
[aij ]1≤i≤m m × n matrix A det A, det(A) determinant of A
1≤j≤n
Tr A, Tr(A) trace of A A−1
R a right inverse of A
Ker A, Ker(A) null-space of A Im A, Im(A) image of A
AI generalized inverse of A A+ the Moore-Penrose inverse of A
A≥0 all entries aij > 0 A>0 A ≥ 0 and at least one entry aij > 0
A≫0 all entries aij > 0 λ∗ (A), λ∗A dominant eigenvalue of A
σk (A) kth largest singular value of A GA , G(A) directed graph associated to A
[x1 · · · xn ]⊤ (x1 , · · · , xn ) = x ∈ Rn (x, y) inner product of x and y
∥x∥ norm of x B(x; ε) open ball with radius ε centered at x
{x ∈ V : Px } the set of all x in V with property Px V \D {x ∈ V : x ∈
/ D}
x≥0 all coordinates xk ≥ 0 x>0 x ≥ 0 and at least one coordinate xk > 0
Rn+ {x ∈ Rn : x ≥ 0} x≫0 all coordinates xk > 0
Rn++ {x ∈ Rn : x ≫ 0} Int V , Int(V ) the interior of V
Cl V , Cl(V ), V̄ the closure of V ∂V the boundary of V
Conv V , Conv(V ) the convex hull of V Epi V , Epi(V ) the epi-graph of V
Hypo f , Hypo(f ) the hypo-graph of f Dk f the first order partial derivative of f w.r.t. kth variable
Dij f second order partial derivative of f w.r.t. ith and jth variables ∇f (a) the gradient of f at a
Hf (a) the Hessian matrix of f at a
3
, Wouter Voskuilen Matrices, Graphs & Convexity
1 Chapter 1
1.1 Matrices and linear maps
We denote the vector space of all m × n real matrices by Rm×n , and
a11 · · · a1n
m×n .. .. .
A∈R ⇔ A = [aij ]1≤i≤m = . .
1≤j≤n
am1 · · · amn
Some operations for matrices are:
Addition (Rm×n × Rm×n → Rm×n ) C =A+B cij = aij + bij
Scalar Multiplication (R × Rm×n → Rm×n ) C =α·A cij =Pα · aij
Multiplication (Rm×n × Rn×s → Rm×s ) C = AB cij = nk=1 aik bkj
Transpose (Rm×n → Rn×m ) C = A⊤ cij = aji
A square matrix is a permutation matrix if every row and every column has ex-
actly one entry equal to 1 and all other entries are equal to 0.
If the matrices A and B in Rn×n satisfy AB = BA = In , then the matrix B is the
inverse of A and it is denoted by A−1 . If A−1 exists, then A is regular (non-singular); if
A−1 does not exist then A is singular.
Let A ∈ Rn×n be given. The determinant of A, det(A), is defined as follows: det(A) = a11
if n = 1 and for n > 1,
n
X
det(A) = (−1)j+1 a1j det (A1j ) ,
j=1
where A1j ∈ R(n−1)×(n−1) is the resulting matrix by deleting the 1st row and j th column
from A (1 ≤ j ≤ n).
Some properties of the determinant:
(a) det(AB) = det(A) det(B) A, B ∈ Rn×n
(b) det A⊤ = det(A) A ∈ Rn×n
(c) det(αA) = αn · det(A) α ∈ R, A ∈ Rn×n
(d) det(A) ̸= 0 ⇔ A is regular A ∈ Rn×n
We identify the vector space Rm with the vector space Rm×1 and the column vectors
are usually denoted by small letters, y, and the coordinates are denoted by the same
4
