Directed Graphs

Math 790-92

Brian D. Fitzpatrick

Duke University

August 8, 2019

MATH
Overview

Directed Graphs Transposition

Definition Incidence Matrices
Basic Terminology General Matrices
Applications The Involution Property
Invariants Net Flow
Incidence Vectors Definition
Definition Via Incidence Vectors
General Vectors Summing General Vectors
Incidence Matrices Weighted Digraphs
Definition Definition
General Matrices Weighted Incidence Vectors
Scaling General Vectors
Weighted Net Flow
Linear Combinations
Directed Graphs
Definition

A directed graph is a collection of

Directed Graphs
Definition

A directed graph is a collection of nodes

Directed Graphs
Definition

A directed graph is a collection of nodes

v3

v1 v2 v5

v4 v6
Directed Graphs
Definition

A directed graph is a collection of nodes and arrows.

v3

v1 v2 v5

v4 v6
Directed Graphs
Definition

A directed graph is a collection of nodes and arrows.

v3

a2 a4

v1 a1 v2 v5

a3 a5 a6

v4 v6
Directed Graphs
Basic Terminology

Other terms for ”directed graph”

“digraph” “directed network” “quiver”=

Directed Graphs
Basic Terminology

Other terms for ”directed graph”

“digraph” “directed network” “quiver”=

Other terms for “node”

“vertex” “object” “point”
Directed Graphs
Basic Terminology

Other terms for ”directed graph”

“digraph” “directed network” “quiver”=

Other terms for “node”

“vertex” “object” “point”

Other terms for “arrow”

“directed edge” “directed arc” “directed line”
Directed Graphs
Basic Terminology

v3

a2 a5

v1 a1 v2 a4 v5

a3 a6 a7

v4 v6

digraph on six vertices and seven directed edges

Directed Graphs
Basic Terminology

v1

a1 a3

v2 a2 v3

a4 a5
a6
v4

quiver on four nodes and six arrows

Directed Graphs
Applications

Digraphs are often used to describe relationships between objects.

Directed Graphs
Applications

In finance, digraphs can be used to model transactional data.

Directed Graphs
Applications

In finance, digraphs can be used to model transactional data.

nodes financial institutions arrows transactions

Directed Graphs
Applications

In finance, digraphs can be used to model transactional data.

nodes financial institutions arrows transactions

Directed Graphs
Applications

In finance, digraphs can be used to model transactional data.

nodes financial institutions arrows transactions

t3

t2 t4

t1 t5
Directed Graphs
Applications

The internet can be modeled by a digraph organizing hyperlink

data.
Directed Graphs
Applications

The internet can be modeled by a digraph organizing hyperlink

data.

nodes webpages arrows hyperlinks

Directed Graphs
Applications

The internet can be modeled by a digraph organizing hyperlink

data.

nodes webpages arrows hyperlinks

Directed Graphs
Applications

The internet can be modeled by a digraph organizing hyperlink

data.

nodes webpages arrows hyperlinks

l1 l9

l2 l8
l5
l3
l6

l4 l7
Directed Graphs
Applications

Family trees are digraphs organizing parental relationships.

Directed Graphs
Applications

Family trees are digraphs organizing parental relationships.

nodes people arrows parental relationships

Directed Graphs
Applications

Family trees are digraphs organizing parental relationships.

nodes people arrows parental relationships

Directed Graphs
Applications

Family trees are digraphs organizing parental relationships.

nodes people arrows parental relationships

Directed Graphs
Applications
Facebook can be modeled by a digraph organizing friendships.
nodes user accounts arrows friendships

[Link]
Directed Graphs
Applications
Uber can be modeled by a digraph organizing routes.
nodes locations arrows routes

[Link]
Directed Graphs
Applications

Logical arguments can be modeled by digraphs organizing logical

implications.
Directed Graphs
Applications

Logical arguments can be modeled by digraphs organizing logical

implications.

nodes statements arrows logical implications

Directed Graphs
Applications

Logical arguments can be modeled by digraphs organizing logical

implications.

nodes statements arrows logical implications

Axiom 1 Axiom 2

Lemma 1 Lemma 2 Lemma 3

Theorem 1 Theorem 2
Directed Graphs
Applications

Logical arguments can be modeled by digraphs organizing logical

implications.

nodes statements arrows logical implications

Axiom 1 Axiom 2

Lemma 1 Lemma 2 Lemma 3

Theorem 1 Theorem 2
Directed Graphs
Applications

A neural network is a type of digraph used to solve artificial

intelligence problems.

nodes “artificial neurons” arrows “connections”

Directed Graphs
Applications

Transportation

nodes street intersections arrows one-way streets

Directed Graphs
Applications

Transportation

nodes street intersections arrows one-way streets

Communication
nodes cell phone numbers arrows text messages
Directed Graphs
Applications

Transportation

nodes street intersections arrows one-way streets

Communication
nodes cell phone numbers arrows text messages

Food Chain
nodes species arrows predator-prey relationships
Directed Graphs
Applications

Transportation

nodes street intersections arrows one-way streets

Communication
nodes cell phone numbers arrows text messages

Food Chain
nodes species arrows predator-prey relationships

Game Theory

nodes board positions arrows legal moves

Directed Graphs
Invariants

Interesting properties of digraphs are often referred to as invariants.

Directed Graphs
Invariants

Connectedness
How can we determine if a digraph is connected?
Directed Graphs
Invariants

Connectedness
How can we determine if a digraph is connected?

connected
Directed Graphs
Invariants

Connectedness
How can we determine if a digraph is connected?

connected not connected

Directed Graphs
Invariants

Connected Components
How can we determine the number of connected components of a
digraph?
Directed Graphs
Invariants

Connected Components
How can we determine the number of connected components of a
digraph?

one connected component

Directed Graphs
Invariants

Connected Components
How can we determine the number of connected components of a
digraph?

one connected component two connected components

Directed Graphs
Invariants

Trees
How can we determine if a digraph is a tree (connected and no
cycles)?
Directed Graphs
Invariants

Trees
How can we determine if a digraph is a tree (connected and no
cycles)?

tree
Directed Graphs
Invariants

Trees
How can we determine if a digraph is a tree (connected and no
cycles)?

tree not a tree

Directed Graphs
Invariants
Girth
What is the length of a shortest cycle?
Directed Graphs
Invariants
Girth
What is the length of a shortest cycle?

girth =
Directed Graphs
Invariants
Girth
What is the length of a shortest cycle?

girth = 5
Directed Graphs
Invariants

How can we use mathematics to solve problems involving digraphs?

Incidence Vectors
Definition

Each arrow in a digraph is associated to an incidence vector.

Incidence Vectors
Definition

Each arrow in a digraph is associated to an incidence vector.

v1

a1 a2

v2 a3 v3
Incidence Vectors
Definition

Each arrow in a digraph is associated to an incidence vector.

v1 a1
v1 −1
" #
#»
a 1 = v2
a1 a2 1
v3 0
v2 a3 v3
Incidence Vectors
Definition

Each arrow in a digraph is associated to an incidence vector.

v1 a1
v1 −1
" #
#»
a 1 = v2
a1 a2 1
v3 0
v2 a3 v3

The incidence vector associates nodes to scalars (“scalar” means

“number”).
Incidence Vectors
Definition

Each arrow in a digraph is associated to an incidence vector.

v1 a1
v1 −1
" #
#»
a 1 = v2
a1 a2 1
v3 0
v2 a3 v3

The incidence vector associates nodes to scalars (“scalar” means

“number”).

“source” node → −1 “target” node → 1 other nodes → 0

Incidence Vectors
Definition

v3
a2
v1 a1 v2
a3
v4

The incidence vectors are

a1 a2 a3
v1 v1 v1
     
#»
a 1 = v2   #»
a 2 = v2   #»
a 3 = v2  
v3 v3 v3
     
v4 v4 v4
Incidence Vectors
Definition

v3
a2
v1 a1 v2
a3
v4

The incidence vectors are

a1 a2 a3
v1
 − 1 v1
  v1
 
#»
a 1 = v2  1 #»
a 2 = v2   #»
a 3 = v2  
v3 0 v3 v3
     
v4 0 v4 v4
Incidence Vectors
Definition

v3
a2
v1 a1 v2
a3
v4

The incidence vectors are

a1 a2 a3
v1
 − 1 v1
 0 v1
 
#»
a 1 = v2  1 #»
a 2 = v2  − 1 #»
a 3 = v2  
v3 0 v3 1 v3
     
v4 0 v4 0 v4
Incidence Vectors
Definition

v3
a2
v1 a1 v2
a3
v4

The incidence vectors are

a1 a2 a3
v1
 − 1 v1
 0 v1 0
#»
a 1 = v2  1 #»
a 2 = v2  − 1 #»
a 3 = v2  1
v3 0 v3 1 v3 0
     
v4 0 v4 0 v4 −1
Incidence Vectors
General Vectors

Question
Suppose our digraph has m nodes and n arrows. How many scalars
are stored inside a given incidence vector?
Incidence Vectors
General Vectors

Question
Suppose our digraph has m nodes and n arrows. How many scalars
are stored inside a given incidence vector?

Answer
Each incidence vector is of the form
a
v1
∗

#» v2 ∗
a = . .
..  .. 
vm ∗
Incidence Vectors
General Vectors

Question
Suppose our digraph has m nodes and n arrows. How many scalars
are stored inside a given incidence vector?

Answer
Each incidence vector is of the form
a
v1
∗

#» v2 ∗
a = . .
..  .. 
vm ∗

There are
Incidence Vectors
General Vectors

Question
Suppose our digraph has m nodes and n arrows. How many scalars
are stored inside a given incidence vector?

Answer
Each incidence vector is of the form
a
v1
∗

#» v2 ∗
a = . .
..  .. 
vm ∗

There are m scalars stored inside #»

a.
Incidence Vectors
General Vectors

Question
Suppose our digraph has m nodes and n arrows. How many scalars
are stored inside a given incidence vector?

Answer
Each incidence vector is of the form
a
v1
∗

#» v2 ∗
a = . .
..  .. 
vm ∗

There are m scalars stored inside #»

a . To indicate this, we write
#»
a ∈ Rm .
Incidence Vectors
General Vectors

Definition
A vector in Rm is a list of m scalars.
Incidence Vectors
General Vectors

Set-Membership Notation
We use the symbol ∈ to indicate membership.
Incidence Vectors
General Vectors

Set-Membership Notation
We use the symbol ∈ to indicate membership.
#»
v ∈ Rm means #» v is a vector in Rm
Incidence Vectors
General Vectors

Set-Membership Notation
We use the symbol ∈ to indicate membership.
#»
v ∈ Rm means #» v is a vector in Rm
#»
v ∈/ Rm means #»
v is not a vector in Rm
Incidence Vectors
General Vectors

Set-Membership Notation
We use the symbol ∈ to indicate membership.
#»
v ∈ Rm means #» v is a vector in Rm
#»
v ∈/ Rm means #»
v is not a vector in Rm

Horizontal and Vertical Notation

Two ways to indicate that #»
v ∈ Rm .

#»
 
v = hx1 , x2 , . . . , xm i x1
#»
 x2 
v =
 
Horizontal Notation .. 
 . 
xm
Vertical Notation
Incidence Vectors
General Vectors

Set-Membership Notation
We use the symbol ∈ to indicate membership.
#»
v ∈ Rm means #» v is a vector in Rm
#»
v ∈/ Rm means #»
v is not a vector in Rm

Horizontal and Vertical Notation

Two ways to indicate that #»
v ∈ Rm .

#»
 
v = hx1 , x2 , . . . , xm i x1
#»
 x2 
v =
 
Horizontal Notation .. 
 . 
xm
Vertical Notation
The scalars x1 , x2 , . . . , xm are called the coordinates of #»
v.
Incidence Vectors
General Vectors

Example
Consider the vector #»
v = h3, −2, 4, 9i .
Incidence Vectors
General Vectors

Example
v = h3, −2, 4, 9i . Then #»
Consider the vector #» v ∈
Incidence Vectors
General Vectors

Example
v = h3, −2, 4, 9i . Then #»
Consider the vector #» v ∈ R4 .
Incidence Vectors
General Vectors

Example
Consider the vector #»
v = h3, −2, 4, 9i . Then #»
v ∈ R4 . In vertical
and horizontal notation, we have
 
3
#»  −2 
v = h3, −2, 4, 9i =   4


9
Incidence Vectors
General Vectors

Example
Consider the vector #»
v = h3, −2, 4, 9i . Then #»
v ∈ R4 . In vertical
and horizontal notation, we have
 
3
#»  −2 
v = h3, −2, 4, 9i =   4


9

The coordinates of #»
v are

first coordinate is 3
Incidence Vectors
General Vectors

Example
Consider the vector #»
v = h3, −2, 4, 9i . Then #»
v ∈ R4 . In vertical
and horizontal notation, we have
 
3
#»  −2 
v = h3, −2, 4, 9i =   4


9

The coordinates of #»
v are

first coordinate is 3
second coordinate is −2
Incidence Vectors
General Vectors

Example
Consider the vector #»
v = h3, −2, 4, 9i . Then #»
v ∈ R4 . In vertical
and horizontal notation, we have
 
3
#»  −2 
v = h3, −2, 4, 9i =   4


9

The coordinates of #»
v are

first coordinate is 3 third coordinate is 4

second coordinate is −2
Incidence Vectors
General Vectors

Example
Consider the vector #»
v = h3, −2, 4, 9i . Then #»
v ∈ R4 . In vertical
and horizontal notation, we have
 
3
#»  −2 
v = h3, −2, 4, 9i =   4


9

The coordinates of #»
v are

first coordinate is 3 third coordinate is 4

second coordinate is −2 fourth coordinate is 9
Incidence Vectors
General Vectors

Example
Consider the vectors
 
  1/2
0
#»
v = h1, 1i #» = h−6, −2, 0i
w #»
x = 2  #» 
y =
2 

 0 
−2
0
Incidence Vectors
General Vectors

Example
Consider the vectors
 
  1/2
0
#»
v = h1, 1i #» = h−6, −2, 0i
w #»
x = 2  #» 
y =
2 

 0 
−2
0

These vectors satisfy

Incidence Vectors
General Vectors

Example
Consider the vectors
 
  1/2
0
#»
v = h1, 1i #» = h−6, −2, 0i
w #»
x = 2  #» 
y =
2 

 0 
−2
0

These vectors satisfy

#»
v ∈ R2 #» ∈ R3
w #»
x ∈ R3 #»
y ∈ R4
Incidence Vectors
General Vectors

Example
Consider the vectors
 
  1/2
0
#»
v = h1, 1i #» = h−6, −2, 0i
w #»
x = 2  #» 
y =
2 

 0 
−2
0

These vectors satisfy

#»
v ∈ R2 #» ∈ R3
w #»
x ∈ R3 #»
y ∈ R4
#»
v ∈/ R3 #» ∈
w / R2 #»
x ∈/ R5 #»
y ∈/ R2
Incidence Vectors
General Vectors

a4
v3
a2
v1 a1 v2
a3
v4
a5

The incidence vector associated to the arrow a4 is

 
−1
#»  0  4
a4 =  1  = h−1, 0, 1, 0i ∈ R


0
Incidence Vectors
General Vectors

Our Convention
We will typically use the “arrow” or “harpoon” notation #»
v to refer
to vectors.
Incidence Vectors
General Vectors

Our Convention
We will typically use the “arrow” or “harpoon” notation #»
v to refer
to vectors.

Other Common Notation

You might also encounter

v v v v
Incidence Matrices
Definition

Question
How can we use a computer to analyze a digraph?
Incidence Matrices
Definition

Question
How can we use a computer to analyze a digraph?

Answer
Feed the computer all of the incidence vectors!
Incidence Matrices
Definition
Every digraph is associated to an incidence matrix.

v1

A = #» #» #»
 
a1 a2 a1 a2 a3

v2 a3 v3
Incidence Matrices
Definition
Every digraph is associated to an incidence matrix.

v1

A = #» #» #»
 
a1 a2 a1 a2 a3

v2 a3 v3
The incidence matrix is an array of numbers obtained by inserting
each incidence vector into a column.
a1 a2 a3
v1
"−1 −1 0#
A = v2 1 0 −1
v3 0 1 1
Incidence Matrices
Definition
Every digraph is associated to an incidence matrix.

v1

A = #» #» #»
 
a1 a2 a1 a2 a3

v2 a3 v3
The incidence matrix is an array of numbers obtained by inserting
each incidence vector into a column.
a1 a2 a3
v1
"−1 −1 0#
A = v2 1 0 −1
v3 0 1 1

Here, A has three rows and three columns.

Incidence Matrices
Definition

v3
a2
v1 a1 v2
a3
v4

The incidence matrix is

a1 a2 a3
v1
 

A = v2  
v3
 
v4
Incidence Matrices
Definition

v3
a2
v1 a1 v2
a3
v4

The incidence matrix is

a1 a2 a3
v1
−1 

A = v2  1 
v3 0
 
v4 0
Incidence Matrices
Definition

v3
a2
v1 a1 v2
a3
v4

The incidence matrix is

a1 a2 a3
v1
−1 0 

A = v2  1 −1 
v3 0 1
 
v4 0 0
Incidence Matrices
Definition

v3
a2
v1 a1 v2
a3
v4

The incidence matrix is

a1 a2 a3
v1
−1 0 0
A = v2  1 −1 1
v3 0 1 0
 
v4 0 0 −1
Incidence Matrices
Definition

v3
a2
v1 a1 v2
a3
v4

The incidence matrix is

a1 a2 a3
v1
−1 0 0
A = v2  1 −1 1
v3 0 1 0
 
v4 0 0 −1

Here, A has four rows and three columns.

Incidence Matrices
Definition

Every digraph is defined by its incidence matrix.

Incidence Matrices
Definition

Every digraph is defined by its incidence matrix.

a1 a2 a3 a4
v1 −1 0 −1 1#
"
A = v2 1 −1 0 −1
v3 0 1 1 0
Incidence Matrices
Definition

Every digraph is defined by its incidence matrix.

v2
a4
a1 a2 a3 a4
v1
"−1 0 −1 1# a1
A = v2 1 −1 0 −1 v1 a2
v3 0 1 1 0
a3
v3
Incidence Matrices
Definition

Question
Suppose our digraph has m nodes and n arrows. How many rows
and columns does its incidence matrix have?
Incidence Matrices
Definition

Question
Suppose our digraph has m nodes and n arrows. How many rows
and columns does its incidence matrix have?

Answer
The incidence matrix is of the form
a1 a2 ··· an
v1
∗ ∗ ··· ∗
v2  ∗ ∗ ··· ∗
A= .  .. .. .. 
..  ∗ . . .
vm ∗ ∗ ··· ∗
Incidence Matrices
Definition

Question
Suppose our digraph has m nodes and n arrows. How many rows
and columns does its incidence matrix have?

Answer
The incidence matrix is of the form
a1 a2 ··· an
v1
∗ ∗ ··· ∗
v2  ∗ ∗ ··· ∗
A= .  .. .. .. 
..  ∗ . . .
vm ∗ ∗ ··· ∗

The incidence matrix has m rows and n columns.

Incidence Matrices
Definition

Question
Suppose our digraph has m nodes and n arrows. How many rows
and columns does its incidence matrix have?

Answer
The incidence matrix is of the form
a1 a2 ··· an
v1
∗ ∗ ··· ∗
v2  ∗ ∗ ··· ∗
A= .  .. .. .. 
..  ∗ . . .
vm ∗ ∗ ··· ∗

The incidence matrix has m rows and n columns.

nodes ↔ rows arrows ↔ columns

Incidence Matrices
General Matrices

Definition
A m × n matrix is an array of numbers with m rows and n columns.
Incidence Matrices
General Matrices

Definition
A m × n matrix is an array of numbers with m rows and n columns.

Note
We often represent matrices as
 
a11 a12 ··· a1n
 a21 a22 ··· a2n 
A= .
 
.. .. .. 
 .. . . . 
am1 am2 · · · amn
Incidence Matrices
General Matrices

Definition
A m × n matrix is an array of numbers with m rows and n columns.

Note
We often represent matrices as
 
a11 a12 ··· a1n
 a21 a22 ··· a2n 
A= .
 
.. .. .. 
 .. . . . 
am1 am2 · · · amn

We use the notation aij to refer to the element of A in the ith row
and jth column.
Incidence Matrices
General Matrices

Example
Consider the matrix A given by
 
−5 2 9 9 −1
A =  −8 −10 −6 −6 6 
7 −3 9 −1 −7
Incidence Matrices
General Matrices

Example
Consider the matrix A given by
 
−5 2 9 9 −1
A =  −8 −10 −6 −6 6 
7 −3 9 −1 −7

Then A is a 3 × 5 matrix with

a11 = −5 a12 = 2 a13 = 9 a14 = 9 a15 = −1

a21 = −8 a22 = −10 a23 = −6 a24 = −6 a25 = 6
a31 = 7 a32 = −3 a33 = 9 a34 = −1 a35 = −7
Incidence Matrices
General Matrices

Convention
We typically use capital letters to denote matrices.
Incidence Matrices
General Matrices

Convention
We typically use capital letters to denote matrices.

Definition
The collection of m × n matrices is denoted by Mm×n (R) or Rm×n .
Incidence Matrices
General Matrices

Convention
We typically use capital letters to denote matrices.

Definition
The collection of m × n matrices is denoted by Mm×n (R) or Rm×n .

Example
The incidence matrix A of a digraph on 4 nodes and 10 arrows
satisfies A ∈ R4×10 .
Incidence Matrices
General Matrices

Example
Consider the matrices A, B, and C given by
 
  −1 −1  
1 7 −7 0 1  0 0
1 
A =  2 −1 0 1 2  B=  1 −1/2

 C = 2 
−2 2 0 25 2 0
1 2
Incidence Matrices
General Matrices

Example
Consider the matrices A, B, and C given by
 
  −1 −1  
1 7 −7 0 1  0 0
1 
A =  2 −1 0 1 2  B=  1 −1/2

 C = 2 
−2 2 0 25 2 0
1 2

These matrices satisfy

Incidence Matrices
General Matrices

Example
Consider the matrices A, B, and C given by
 
  −1 −1  
1 7 −7 0 1  0 0
1 
A =  2 −1 0 1 2  B=  1 −1/2

 C = 2 
−2 2 0 25 2 0
1 2

These matrices satisfy

A ∈ R3×5 / R5×3
A∈
Incidence Matrices
General Matrices

Example
Consider the matrices A, B, and C given by
 
  −1 −1  
1 7 −7 0 1  0 0
1 
A =  2 −1 0 1 2  B=  1 −1/2

 C = 2 
−2 2 0 25 2 0
1 2

These matrices satisfy

A ∈ R3×5 / R5×3
A∈
B ∈ M4×2 (R) B∈
/ M2×4 (R)
Incidence Matrices
General Matrices

Example
Consider the matrices A, B, and C given by
 
  −1 −1  
1 7 −7 0 1  0 0
1 
A =  2 −1 0 1 2  B=  1 −1/2

 C = 2 
−2 2 0 25 2 0
1 2

These matrices satisfy

A ∈ R3×5 / R5×3
A∈
B ∈ M4×2 (R) B∈
/ M2×4 (R)
3×1
C ∈R / R1×3
C∈
Incidence Matrices
General Matrices

Observation
Each row and each column of a matrix A is a vector.
Incidence Matrices
General Matrices

Observation
Each row and each column of a matrix A is a vector.

Row and Column Extraction

Let A be a m × n matrix. We write
 #» 
r1
 #»
 r 2 
A =  .  = #»a 1 #» #»
 
a2 ··· an
 .. 
#»
r m

to define the rows of A as the vectors { #» r 1 , #»

r 2 , . . . , #»
r m } and the
#» #» #»
columns of A as the vectors { a 1 , a 2 , . . . , a n }.
Incidence Matrices
General Matrices

Example
By writing
   #» 
4 1 0 0 r1
2 −1  =  #»
r 2  = #» #» #» #»
 
A= 2 0 a1 a2 a3 a4
−2 0 −1 1 #»
r3

we define the rows and columns of A as

#»
r 1 = h4, 1, 0, 0i #»
a 1 = h4, 2, −2i
#»
r 2 = h2, 0, 2, −1i #»
a 2 = h1, 0, 0i
#»
r = h−2, 0, −1, 1i #»
a 3 = h0, 2, −1i
3
#»
a = h0, −1, 1i
4
Transposition
Incidence Matrices
The choice to organize “node data” in rows and “arrow data” in
columns is, of course, arbitrary.
Transposition
Incidence Matrices
The choice to organize “node data” in rows and “arrow data” in
columns is, of course, arbitrary.

v1 a1 a2 a3
v1
"−1 −1 0#
a1 a2 A = v2 1 0 −1
v3 0 1 1
v2 a3 v3
Transposition
Incidence Matrices
The choice to organize “node data” in rows and “arrow data” in
columns is, of course, arbitrary.

v1 a1 a2 a3
v1
"−1 −1 0#
a1 a2 A = v2 1 0 −1
v3 0 1 1
v2 a3 v3
The same information is stored in the transpose of the incidence
matrix.
v1 v2 v3
"−1
a1 1 0#
|
A = a2 −1 0 1
a3 0 −1 1
Transposition
Incidence Matrices

v3
a2
v1 a1 v2
a3
v4

The incidence matrix A and its transpose A| are given by

Transposition
Incidence Matrices

v3
a2
v1 a1 v2
a3
v4

The incidence matrix A and its transpose A| are given by

a1 a2 a3
−1 v1 v2 v3 v4
v1 0 0 "−1
a1 1 0 0#
A= v2  1 −1 1 |
A = a2 0 −1 1 0
v3 0 1 0
 
a3 0 1 0 −1
v4 0 0 −1
Transposition
Incidence Matrices

v3
a2
v1 a1 v2
a3
v4

The incidence matrix A and its transpose A| are given by

a1 a2 a3
−1 v1 v2 v3 v4
v1 0 0 "−1
a1 1 0 0#
A= v2  1 −1 1 |
A = a2 0 −1 1 0
v3 0 1 0
 
a3 0 1 0 −1
v4 0 0 −1

Note that A is 4 × 3 while A| is 3 × 4.

Transposition
Incidence Matrices

Since the incidence matrix A and its transpose A| contain the same
information, some mathematicians call A| the incidence matrix!
Transposition
General Matrices

Definition
The transpose of a m × n matrix A is the n × m matrix A| formed
by interchanging the rows and columns of A.
Transposition
General Matrices

Definition
The transpose of a m × n matrix A is the n × m matrix A| formed
by interchanging the rows and columns of A.
Cool animation: [Link]
Transposition
General Matrices

Example
Consider the matrices A and B given by
 
  1 −11 −1
6 −10 1  1 2 0 
A= B= 
2 1 −2  −4 0 1 
2×3 −1 1 1
4×3
Transposition
General Matrices

Example
Consider the matrices A and B given by
 
  1 −11 −1
6 −10 1  1 2 0 
A= B= 
2 1 −2  −4 0 1 
2×3 −1 1 1
4×3

The transposes of these matrices are given by

   
6 2 1 1 −4 −1
A| =  −10 1  B | =  −11 2 0 1 
1 −2 −1 0 1 1
3×2 3×4
Transposition
The Involution Property

Question
What happens if we transpose twice?
Transposition
The Involution Property

Question
What happens if we transpose twice?

Example 
1 −28 3
For A = we have
1 −1 1
 
1 1  
1 −28 3
A| =  −28 −1  | |
(A ) =
1 −1 1
3 1

So (A| )| = A.
Transposition
The Involution Property

Question
What happens if we transpose twice?

Example 
1 −28 3
For A = we have
1 −1 1
 
1 1  
1 −28 3
A| =  −28 −1  | |
(A ) =
1 −1 1
3 1

So (A| )| = A.

Answer
Transposing twice results in the original matrix.
Transposition
The Involution Property

Involution Property of Transposition

The transpose operation is an involution, meaning (A| )| = A.
Net Flow
Definition

v1
a4
a1 a2 Question
What is the “net flow” through
each node?
v2 a3 v3
a5
Net Flow
Definition

v1
a4
a1 a2 Question
What is the “net flow” through
each node?
v2 a3 v3
a5
Answer
For each node, take the difference of the number of “target
arrows” and the number of “source arrows.”
through v1 1 − 1 − 1 = −1
a4 a1 a2
Net Flow
Definition

v1
a4
a1 a2 Question
What is the “net flow” through
each node?
v2 a3 v3
a5
Answer
For each node, take the difference of the number of “target
arrows” and the number of “source arrows.”
through v1 1 − 1 − 1 = −1
a4 a1 a2
through v2 1 + 1 − 1 − 1 = 0
a1 a5 a3 a4
Net Flow
Definition

v1
a4
a1 a2 Question
What is the “net flow” through
each node?
v2 a3 v3
a5
Answer
For each node, take the difference of the number of “target
arrows” and the number of “source arrows.”
through v1 1 − 1 − 1 = −1
a4 a1 a2
through v2 1 + 1 − 1 − 1 = 0
a1 a5 a3 a4
through v3 1 + 1 − 1 = 1
a2 a3 a5
Net Flow
Via Incidence Vectors

v1
a4 Note
a1 a2 The net flows can be computed
by summing the incidence
v2 a3 v3 vectors.

a5
Net Flow
Via Incidence Vectors

v1
a4 Note
a1 a2 The net flows can be computed
by summing the incidence
v2 a3 v3 vectors.

a5
           
v1 −1 −1 0 1 0
 v2  =  1  +  0  +  −1  +  −1  +  1 
v3 0 1 1 0 −1
   
−1 − 1 + 0 + 1 + 0 −1
= 1+0−1−1+1 = 0 
0+1+1+0−1 1
Net Flow
Summing General Vectors

Definition
Let #»
v,w#» ∈ Rn be vectors. The sum of #»v and w #» is
     
v1 w1 v1 + w1
v2  w2  v2 + w2 
#»
v +w #» = 
 ..  +  ..  = 
    
.. 
.  .   . 
vn wn vn + wn
Net Flow
Summing General Vectors

Definition
Let #»
v,w#» ∈ Rn be vectors. The sum of #»v and w #» is
     
v1 w1 v1 + w1
v2  w2  v2 + w2 
#»
v +w #» = 
 ..  +  ..  = 
    
.. 
.  .   . 
vn wn vn + wn

Example
       
−1 5 −1 + 5 4
 −8   −1   −8 + (−1)   −9 
 9  +  −1  =  9 + (−1)
     = 
  8 
1 −3 1 + (−3) −2
Net Flow
Summing General Vectors

Note
If #» #» are vectors in Rn , then #»
v and w #» is a vector in Rn .
v +w
Net Flow
Summing General Vectors

Note
If #» #» are vectors in Rn , then #»
v and w #» is a vector in Rn .
v +w

Note
The sum #» #» is only defined if #»
v +w #» have the same
v and w
dimension.
Net Flow
Summing General Vectors

Note
If #» #» are vectors in Rn , then #»
v and w #» is a vector in Rn .
v +w

Note
The sum #» #» is only defined if #»
v +w #» have the same
v and w
dimension.

Example 
  1
3  1 
The sum  −1  + 
 −1  is nonsensical!

2
−15
Weighted Digraphs
Definition

Arrows in digraphs are often associated to scalars. These scalars

are called weights and these digraphs are called weighted digraphs.
Weighted Digraphs
Definition

Financial transactions are measured in dollars.

t3
$30 000.00

t2 t4
$20.00 $22.00

t1 t5
$40.00 $3245.00
Weighted Digraphs
Definition

When modeling road networks, one might use speed limits as

weights.
v1 a1 v2
45 mph

a3 a2 a4
25 mph 30 mph 40 mph

v3 a5 v4
50 mph
Weighted Digraphs
Weighted Incidence Vectors

v3
The weighted incidence vectors
of a weighted digraph are
a3 a2 obtained by “scaling” the original
−2 11
incidence vectors by the
corresponding weights.
v1 a1 v2
4
Weighted Digraphs
Weighted Incidence Vectors

v3
The weighted incidence vectors
of a weighted digraph are
a3 a2 obtained by “scaling” the original
−2 11
incidence vectors by the
corresponding weights.
v1 a1 v2
4

     
−4 0 2
4 · #»
a1 =  4  11 · #»
a 2 =  −11  −2 · #»
a3 =  0 
0 11 −2
Weighted Digraphs
Scaling General Vectors

Definition (Algebraic)
Let #»
v ∈ Rn be a vector and let c ∈ R be a scalar. The scalar
product of c and #»
v is
   
v1 c · v1
v2  c · v2 
c · #»
v =c · . = . 
   
.
.  .  .
vn c · vn
Weighted Digraphs
Scaling General Vectors

Definition (Algebraic)
Let #»
v ∈ Rn be a vector and let c ∈ R be a scalar. The scalar
product of c and #»
v is
   
v1 c · v1
v2  c · v2 
c · #»
v =c · . = . 
   
.
.  .  .
vn c · vn

Example
     
3 (−4) · 3 −12
 2   (−4) · 2   −8 
(−4) · 
 1 =
  = 
(−4) · 1   −4 
−1 (−4) · (−1) 4
Weighted Digraphs
Weighted Net Flow

v3
We can determine the weighted
net flow through each node by
a3 a2
7 2 summing the weighted incidence
vectors.

v1 a1 v2
5
Weighted Digraphs
Weighted Net Flow

v3
We can determine the weighted
net flow through each node by
a3 a2
7 2 summing the weighted incidence
vectors.

v1 a1 v2
5

hv1 , v2 , v3 i = 5 · #»
a 1 + 2 · #»
a 2 + 7 · #»
a3
Weighted Digraphs
Weighted Net Flow

v3
We can determine the weighted
net flow through each node by
a3 a2
7 2 summing the weighted incidence
vectors.

v1 a1 v2
5

hv1 , v2 , v3 i = 5 · #»
a 1 + 2 · #»
a 2 + 7 · #»
a3
= 5 · h−1, 1, 0i + 2 · h0, −1, 1i + 7 · h−1, 0, 1i
Weighted Digraphs
Weighted Net Flow

v3
We can determine the weighted
net flow through each node by
a3 a2
7 2 summing the weighted incidence
vectors.

v1 a1 v2
5

hv1 , v2 , v3 i = 5 · #»
a 1 + 2 · #»
a 2 + 7 · #»
a3
= 5 · h−1, 1, 0i + 2 · h0, −1, 1i + 7 · h−1, 0, 1i
= h−5, 5, 0i + h0, −2, 2i + h−7, 0, 7i
Weighted Digraphs
Weighted Net Flow

v3
We can determine the weighted
net flow through each node by
a3 a2
7 2 summing the weighted incidence
vectors.

v1 a1 v2
5

hv1 , v2 , v3 i = 5 · #»
a 1 + 2 · #»
a 2 + 7 · #»
a3
= 5 · h−1, 1, 0i + 2 · h0, −1, 1i + 7 · h−1, 0, 1i
= h−5, 5, 0i + h0, −2, 2i + h−7, 0, 7i
= h−12, 3, 9i
Weighted Digraphs
Linear Combinations

Definition
A linear combination of vectors { #»v 1 , #»
v 2 , . . . , #»
v n } is a sum of the
form
c1 · #»
v 1 + c2 · #»
v 2 + · · · + cn · #» vn
where c1 , c2 , . . . , cn are scalars.
Weighted Digraphs
Linear Combinations

Example
Consider the vectors #»
v 1 , #»
v 2 , and #»
v 3 given by
#»
v 1 = h−1, −1, 1i #»
v 2 = h2, 0, 1i #»
v 3 = h−1, −4, 5i
Weighted Digraphs
Linear Combinations

Example
Consider the vectors #»
v 1 , #»
v 2 , and #»
v 3 given by
#»
v 1 = h−1, −1, 1i #»
v 2 = h2, 0, 1i #»
v 3 = h−1, −4, 5i

By choosing c1 = 3, c2 = −2, and c3 = 4, we may form the linear

combination
Weighted Digraphs
Linear Combinations

Example
Consider the vectors #»
v 1 , #»
v 2 , and #»
v 3 given by
#»
v 1 = h−1, −1, 1i #»
v 2 = h2, 0, 1i #»
v 3 = h−1, −4, 5i

By choosing c1 = 3, c2 = −2, and c3 = 4, we may form the linear

combination

c1 · #»
v 1 +c2 · #»
v 2 + c3 · #»
v3
Weighted Digraphs
Linear Combinations

Example
Consider the vectors #»
v 1 , #»
v 2 , and #»
v 3 given by
#»
v 1 = h−1, −1, 1i #»
v 2 = h2, 0, 1i #»
v 3 = h−1, −4, 5i

By choosing c1 = 3, c2 = −2, and c3 = 4, we may form the linear

combination

c1 · #»
v 1 +c2 · #»
v 2 + c3 · #»
v3
= 3 · h−1, −1, 1i + (−2) · h2, 0, 1i + 4 · h−1, −4, 5i
Weighted Digraphs
Linear Combinations

Example
Consider the vectors #»
v 1 , #»
v 2 , and #»
v 3 given by
#»
v 1 = h−1, −1, 1i #»
v 2 = h2, 0, 1i #»
v 3 = h−1, −4, 5i

By choosing c1 = 3, c2 = −2, and c3 = 4, we may form the linear

combination

c1 · #»
v 1 +c2 · #»
v 2 + c3 · #»
v3
= 3 · h−1, −1, 1i + (−2) · h2, 0, 1i + 4 · h−1, −4, 5i
= h−3, −3, 3i + h−4, 0, −2i + h−4, −16, 20i
Weighted Digraphs
Linear Combinations

Example
Consider the vectors #»
v 1 , #»
v 2 , and #»
v 3 given by
#»
v 1 = h−1, −1, 1i #»
v 2 = h2, 0, 1i #»
v 3 = h−1, −4, 5i

By choosing c1 = 3, c2 = −2, and c3 = 4, we may form the linear

combination

c1 · #»
v 1 +c2 · #»
v 2 + c3 · #»
v3
= 3 · h−1, −1, 1i + (−2) · h2, 0, 1i + 4 · h−1, −4, 5i
= h−3, −3, 3i + h−4, 0, −2i + h−4, −16, 20i
= h−11, −19, 21i
Weighted Digraphs
Linear Combinations

Example
Consider the vectors #»
v 1 , #»
v 2 , and #»
v 3 given by
#»
v 1 = h−1, −1, 1i #»
v 2 = h2, 0, 1i #»
v 3 = h−1, −4, 5i

By choosing c1 = 3, c2 = −2, and c3 = 4, we may form the linear

combination

c1 · #»
v 1 +c2 · #»
v 2 + c3 · #»
v3
= 3 · h−1, −1, 1i + (−2) · h2, 0, 1i + 4 · h−1, −4, 5i
= h−3, −3, 3i + h−4, 0, −2i + h−4, −16, 20i
= h−11, −19, 21i

We say “h−11, −19, 21i is a linear combination of { #»

v 1 , #»
v 2 , #»
v 3 }.”
Weighted Digraphs
Linear Combinations

v3
Question
Is it possible to set weights so a3 a2
that the net flow through the
#»
nodes is b = h3, −1, 0i ?
v1 a1 v2
Weighted Digraphs
Linear Combinations

v3
Question
Is it possible to set weights so a3 a2
that the net flow through the
#»
nodes is b = h3, −1, 0i ?
v1 a1 v2

Answer
#»
We want to determine if b = h3, −1, 0i is a linear combination of
the incidence vectors.
Weighted Digraphs
Linear Combinations

v3
Question
Is it possible to set weights so a3 a2
that the net flow through the
#»
nodes is b = h3, −1, 0i ?
v1 a1 v2

Answer
#»
We want to determine if b = h3, −1, 0i is a linear combination of
the incidence vectors. This means that we need to solve
Weighted Digraphs
Linear Combinations

v3
Question
Is it possible to set weights so a3 a2
that the net flow through the
#»
nodes is b = h3, −1, 0i ?
v1 a1 v2

Answer
#»
We want to determine if b = h3, −1, 0i is a linear combination of
the incidence vectors. This means that we need to solve

h3, −1, 0i = c1 · #»
a 1 + c2 · #»
a 2 + c3 · #»
a3
= c1 · h−1, 1, 0i + c2 · h0, −1, 1i + c3 · h−1, 0, 1i
= h−c1 − c3 , c1 − c2 , c2 + c3 i
Weighted Digraphs
Linear Combinations

v3
Question
Is it possible to set weights so a3 a2
that the net flow through the
#»
nodes is b = h3, −1, 0i ?
v1 a1 v2

Answer
#»
We want to determine if b = h3, −1, 0i is a linear combination of
the incidence vectors. This means that we need to solve

h3, −1, 0i = c1 · #»
a 1 + c2 · #»
a 2 + c3 · #»
a3
= c1 · h−1, 1, 0i + c2 · h0, −1, 1i + c3 · h−1, 0, 1i
= h−c1 − c3 , c1 − c2 , c2 + c3 i

for the “unknown” weights c1 , c2 , and c3 .