Samenvatting
Matrices, Graphs and Convexity summary
Summary of all chapters of the lecture notes provided by dr. Romeinders
[Meer zien]Voorbeeld 4 van de 31 pagina's
Voorbeeld 4 van de 31 pagina's
In winkelwagengesponsord bericht van onze partner
Verkoper
Volgen
Voorbeeld van de inhoud
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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper woutervoskuilen. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €10,48. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 82871 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen