Summary
Matrices, Graphs and Convexity summary
- Course
- Institution
Summary of all chapters of the lecture notes provided by dr. Romeinders
[Show more]
Seller
Follow
woutervoskuilen
Content preview
Matrices, Graphs & ConvexitySummary
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller woutervoskuilen. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $11.39. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67232 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now