Linear Control Summary Notes
Chapter 1
directed graph: a triple (𝑉, 𝐸, 𝛼) where V is the finite set of vertices, E is the finite
set of edges, and 𝛼: 𝐸 → {(𝑥, 𝑦)𝜖 𝑉 × 𝑉: 𝑥 ≠ 𝑦} is the incidence function
example 1: 𝑉 = {0,1,2,3} of n=4 elements, 𝐸 = {i, ii, iii, iv, v} of m=5 elements and
𝛼(i) = (1,2), 𝛼(ii) = (3,2), 𝛼(iii) = (1,0), 𝛼(iv) = (2,0), 𝛼(v) = (3,0)
incidence matrix M: M of a graph has n rows
and m columns. Mij equals 1 if the edge j
starts at vertex i, -1 if j ends at i, and 0
otherwise i ii iii iv v
0 0 0 −1 −1 −1
1 1 0 1 0 0
ex.2: M = [ ]
2 −1 −1 0 1 0
3 0 1 0 0 1
walk: a finite sequence of edges which joins a sequence of vertices (direction
unimportant)
connected graph: every pair of vertices has a walk between them
trail: a walk in which all edges are distinct (can only be used once)
circuit: a non-empty trail where the first vertex is equal to the last vertex
cycle: a circuit in which the first vertex is the only repeated vertex
cycle matrix 𝒄̃: a matrix of all cycles of a row, where |𝑐̃𝑖𝑗 | = 1 if edge j is part of the
cycle i, and 0 if not. If edge j is traversed by the cycle in the direction it has an
edge, then 𝑐̃𝑖𝑗 = 1. If the opposite direction, 𝑐̃𝑖𝑗 = −1
circuit rank: the number of linearly independent rows of 𝒄̃ for a connected graph
equals (m – n + 1), the circuit rank of the graph
cycle basis matrix: a matrix C formed from (m – n + 1) L.I rows of 𝒄̃
1 0 −1 1 0
ex.3: C = [ ]
0 −1 0 −1 1
The Dual Graph
face: for a graph embedded in a plane, a face is the region of the plane bounded
by the edges [Euler: there are m - n + 1 bounded
faces]
ex.4: 3 faces: 𝛼, 𝛽, 𝛾
,For each face we have a corresponding cycle that traverses the edges. We take
the orientations so that the face is on the right
cycle basis matrix: the matrix formed from the bounded face cycles
face cycle matrix F: the cycle basis matrix including the cycle corresponding to
the exterior face as well [this is the incidence matrix of a directed graph]
dual graph: the above graph (with incidence matrix F)
1 0 −1 1 0 (𝛼)
ex.5: C = [ ]
0 −1 0 −1 1 (𝛽)
1 0 −1 1 0 𝛼
F = [ 0 −1 0 −1 1 ] 𝛽 the dual graph
−1 1 1 0 −1 𝛾
Example 8:
1 1 1 1
𝑀= [ ]
−1 −1 −1 2
dual graph from matrix
1 −1 0 𝛼
𝐹= [ 0 1 −1 ] 𝛽 dual graph from
−1 0 1 𝛾 picture
Functions on Graphs
𝒇: 𝑬 → 𝑹 function on the edges, to which we can associate a vector (if we order the
edges) 2
5
𝑣𝑒𝑐𝑡𝑜𝑟 = −3
7
(−6)
a vector in Rm defines a function on the edges 𝑓: 𝐸 → 𝑅, so the function in the
above picture is equal to:
−4
∅: 𝑽 → 𝑹 function on vertices 5
𝑣𝑒𝑐𝑡𝑜𝑟 = ( )
corresponds to an element of Rn 7
3
, incompressible: an edge function is incompressible if 𝑀𝑓 = 0, where M is the
incidence matrix
irrotational: an edge function is irrotational if 𝑐̃ 𝑓 = 0, where 𝑐̃ is the cycle matrix
[𝑐𝑓 = 0 for c a cycle basis matrix, 𝐹𝑓 = 0 for F a face cycle matrix]
for a connected graph: 𝑓 𝑖𝑠 𝑖𝑟𝑟𝑜𝑡𝑎𝑡𝑖𝑜𝑛𝑎𝑙 ↔ 𝑓 = 𝑀𝑇 ∅, for a vertex function ∅ called
the potential
ground vertex: a vertex where the potential ∅ has the value 0, in which the
potential is unique. We use // for this vertex (we may draw several // in a diagram,
but they are all the same vertex)
example 9: for the usual graph, 0 is the // (ground)
example 10: a potential and its corresponding edge function
check with matrix and vector:
0 1 −1 0 −2
0 −1 1 1 0
0 4
𝑇
𝑀 ∅ = −1 1 0 0 [3] = 1
−1 0 1 0 3
[−1 ] 7 [
0 0 1 7]
this edge function is irrotational, not incompressible: net outflow from top left
vertex is: 1 + -2 = -1 ≠ 0
example 11: this is incompressible
5 + -5 = 0 1
-5 + 8 + -3 = 0 0
5 + 3 + -8 = 0 2
3 + -3 = 0 3
an edge function is incompressible ↔ 𝒇 = 𝑭𝑻 𝝋 𝒇𝒐𝒓 𝝋 a function on faces
[A function on a graph induces an edge function on the dual graph. If irrotational for the graph,
incompressible for the dual graph. If incompressible for the graph, it is irrotational for the dual graph.]
time dependent: 𝒇: 𝑹 × 𝑬 → 𝑹, which we identify with 𝑓: 𝑅 → 𝑅𝑚 . This is
irrotational/incompressible if 𝑓(𝑡, ∙ ) is for each fixed 𝑡 ∈ 𝑅
Edge Equations
time dependent edge functions:
• 𝑓𝑟 : 𝑅 → 𝑅𝑚 (irrotational)
• 𝑓𝑐 : 𝑅 → 𝑅𝑚 (incompressible)
𝒅
the pointwise product 𝑓𝑟 𝑓𝑐 : 𝑅 → 𝑅𝑚 has the interpretation of power [ (𝒆𝒏𝒆𝒓𝒈𝒚)]
𝒅𝒕
Chapter 1
directed graph: a triple (𝑉, 𝐸, 𝛼) where V is the finite set of vertices, E is the finite
set of edges, and 𝛼: 𝐸 → {(𝑥, 𝑦)𝜖 𝑉 × 𝑉: 𝑥 ≠ 𝑦} is the incidence function
example 1: 𝑉 = {0,1,2,3} of n=4 elements, 𝐸 = {i, ii, iii, iv, v} of m=5 elements and
𝛼(i) = (1,2), 𝛼(ii) = (3,2), 𝛼(iii) = (1,0), 𝛼(iv) = (2,0), 𝛼(v) = (3,0)
incidence matrix M: M of a graph has n rows
and m columns. Mij equals 1 if the edge j
starts at vertex i, -1 if j ends at i, and 0
otherwise i ii iii iv v
0 0 0 −1 −1 −1
1 1 0 1 0 0
ex.2: M = [ ]
2 −1 −1 0 1 0
3 0 1 0 0 1
walk: a finite sequence of edges which joins a sequence of vertices (direction
unimportant)
connected graph: every pair of vertices has a walk between them
trail: a walk in which all edges are distinct (can only be used once)
circuit: a non-empty trail where the first vertex is equal to the last vertex
cycle: a circuit in which the first vertex is the only repeated vertex
cycle matrix 𝒄̃: a matrix of all cycles of a row, where |𝑐̃𝑖𝑗 | = 1 if edge j is part of the
cycle i, and 0 if not. If edge j is traversed by the cycle in the direction it has an
edge, then 𝑐̃𝑖𝑗 = 1. If the opposite direction, 𝑐̃𝑖𝑗 = −1
circuit rank: the number of linearly independent rows of 𝒄̃ for a connected graph
equals (m – n + 1), the circuit rank of the graph
cycle basis matrix: a matrix C formed from (m – n + 1) L.I rows of 𝒄̃
1 0 −1 1 0
ex.3: C = [ ]
0 −1 0 −1 1
The Dual Graph
face: for a graph embedded in a plane, a face is the region of the plane bounded
by the edges [Euler: there are m - n + 1 bounded
faces]
ex.4: 3 faces: 𝛼, 𝛽, 𝛾
,For each face we have a corresponding cycle that traverses the edges. We take
the orientations so that the face is on the right
cycle basis matrix: the matrix formed from the bounded face cycles
face cycle matrix F: the cycle basis matrix including the cycle corresponding to
the exterior face as well [this is the incidence matrix of a directed graph]
dual graph: the above graph (with incidence matrix F)
1 0 −1 1 0 (𝛼)
ex.5: C = [ ]
0 −1 0 −1 1 (𝛽)
1 0 −1 1 0 𝛼
F = [ 0 −1 0 −1 1 ] 𝛽 the dual graph
−1 1 1 0 −1 𝛾
Example 8:
1 1 1 1
𝑀= [ ]
−1 −1 −1 2
dual graph from matrix
1 −1 0 𝛼
𝐹= [ 0 1 −1 ] 𝛽 dual graph from
−1 0 1 𝛾 picture
Functions on Graphs
𝒇: 𝑬 → 𝑹 function on the edges, to which we can associate a vector (if we order the
edges) 2
5
𝑣𝑒𝑐𝑡𝑜𝑟 = −3
7
(−6)
a vector in Rm defines a function on the edges 𝑓: 𝐸 → 𝑅, so the function in the
above picture is equal to:
−4
∅: 𝑽 → 𝑹 function on vertices 5
𝑣𝑒𝑐𝑡𝑜𝑟 = ( )
corresponds to an element of Rn 7
3
, incompressible: an edge function is incompressible if 𝑀𝑓 = 0, where M is the
incidence matrix
irrotational: an edge function is irrotational if 𝑐̃ 𝑓 = 0, where 𝑐̃ is the cycle matrix
[𝑐𝑓 = 0 for c a cycle basis matrix, 𝐹𝑓 = 0 for F a face cycle matrix]
for a connected graph: 𝑓 𝑖𝑠 𝑖𝑟𝑟𝑜𝑡𝑎𝑡𝑖𝑜𝑛𝑎𝑙 ↔ 𝑓 = 𝑀𝑇 ∅, for a vertex function ∅ called
the potential
ground vertex: a vertex where the potential ∅ has the value 0, in which the
potential is unique. We use // for this vertex (we may draw several // in a diagram,
but they are all the same vertex)
example 9: for the usual graph, 0 is the // (ground)
example 10: a potential and its corresponding edge function
check with matrix and vector:
0 1 −1 0 −2
0 −1 1 1 0
0 4
𝑇
𝑀 ∅ = −1 1 0 0 [3] = 1
−1 0 1 0 3
[−1 ] 7 [
0 0 1 7]
this edge function is irrotational, not incompressible: net outflow from top left
vertex is: 1 + -2 = -1 ≠ 0
example 11: this is incompressible
5 + -5 = 0 1
-5 + 8 + -3 = 0 0
5 + 3 + -8 = 0 2
3 + -3 = 0 3
an edge function is incompressible ↔ 𝒇 = 𝑭𝑻 𝝋 𝒇𝒐𝒓 𝝋 a function on faces
[A function on a graph induces an edge function on the dual graph. If irrotational for the graph,
incompressible for the dual graph. If incompressible for the graph, it is irrotational for the dual graph.]
time dependent: 𝒇: 𝑹 × 𝑬 → 𝑹, which we identify with 𝑓: 𝑅 → 𝑅𝑚 . This is
irrotational/incompressible if 𝑓(𝑡, ∙ ) is for each fixed 𝑡 ∈ 𝑅
Edge Equations
time dependent edge functions:
• 𝑓𝑟 : 𝑅 → 𝑅𝑚 (irrotational)
• 𝑓𝑐 : 𝑅 → 𝑅𝑚 (incompressible)
𝒅
the pointwise product 𝑓𝑟 𝑓𝑐 : 𝑅 → 𝑅𝑚 has the interpretation of power [ (𝒆𝒏𝒆𝒓𝒈𝒚)]
𝒅𝒕
