22MAT230

Mathematics for Computing – 4

4th Semester AIE

Dr. Sarada Jayan

1/21/2025 Dr. Sarada Jayan 1

 Graph
• A graph consists of a set of nodes and a set of edges between
these nodes
• Graph is an important model for discrete applied mathematics
to make it simple, useful and general
• Complete graph, Tree
• Linear Algebra is used instead of Calculus

1/21/2025 Dr. Sarada Jayan 2

 Incidence Matrix of a Graph
• Graphs can represent current flowing on edges, potential
difference, electrical network, hydraulic network, design of
bridge
• A graph with m edges and n nodes has an m by n Incidence
matrix A.
• Row i of A corresponds to edge i. If that edge is from node j to
node k, then row i in A has -1 in column j and +1 in column k.
• Each row of A adds to zero

1/21/2025 Dr. Sarada Jayan 3

 Incidence Matrix of a Graph
• Each row of Incidence matrix A adds to zero
• If A is a square matrix, One of the eigenvalues of A is zero
• Vector of all ones is an element in Nullspace of A
• Nullspace of A is (c, c, c, …, c)T
• Dim(Nullspace) = 1

1/21/2025 Dr. Sarada Jayan 4

 Incidence Matrix of a Graph
• Each graph could represent:
• Electric network (current flowing on edges)
• Hydraulic network (flow of water or oil on edges)
• Design for a bridge
• If a graph represents the current flow, and if A is it’s incidence matrix, then ATy = 0 will
represent the Kirchhoff’s current law (Flow into each node equals flow out from that
node), where y = (y1, y2, y3, y4, y5) is the current along the five edges
• Hence current flowing along edges will be an element in the left null space of the
incidence matrix, A.

1/21/2025 Dr. Sarada Jayan 6

 Incidence Matrix of a Graph
Incidence matrix for an undirected graph
In an undirected graph, our convention is that -1 comes first
before +1 in each row.

Question: Assuming y1, y2, y3, y4, y5 and y6 to be the currents

flowing along each of the edges 1,2,3,4,5 and 6 respectively, write
the KCL from the Incidence matrix.

1/21/2025 Dr. Sarada Jayan 7

 Incidence Matrix of a Graph
Trees and Loops
• Row vectors of incidence matrix of a graph with loops will be dependent
• Row vectors of incidence matrix of a tree (a graph with no loops) will be
independent

1/21/2025 Dr. Sarada Jayan 8

 Incidence Matrix of a Graph

Question 1: Find the incidence matrix A of this graph and find the
dimensions of all four fundamental subspaces of A.
Question 2: Assuming y1, y2, y3, y4, y5 and y6 to be the currents
flowing along each of the edges 1,2,3,4,5 and 6 respectively, write the
KCL from the Incidence matrix.
Question 3: Draw the loops and trees from this graph and verify that:
(a) Row vectors of incidence matrix of a loop is dependent
(b) Row vectors of incidence matrix of a tree is independent
1/21/2025 Dr. Sarada Jayan 9
 Incidence Matrix of a Graph

Question 4: Draw the graph if the incidence matrix of the graph is

0 −1 1 0 0 0
𝐴 = −1 0 0 1 0 0
0 0 −1 0 1 0
−1 0 0 0 0 1

1/21/2025 Dr. Sarada Jayan 10

 Incidence Matrix of a Graph
For all the given graphs:
(a) Find the incidence matrix A and find the dimensions of all four
fundamental subspaces of A.
(b) Assuming yi’s to be the currents flowing along each of the edges i,
write the KCL from the Incidence matrix.
(c) Draw one loop and one tree from each of these graphs and verify
that: (i)Row vectors of incidence matrix of a loop is dependent and
(ii) Row vectors of incidence matrix of a tree is independent
A B C

1/21/2025 Dr. Sarada Jayan 11

 Adjacency Matrix of a Graph
• The adjacency matrix B of a graph with n nodes is a 0-1 square
matrix of order n, in which Bxy = 1 if there is an edge from node x
to node y in the graph and Bxy = 0 otherwise.

1/21/2025 Dr. Sarada Jayan 12

 Adjacency Matrix of a complete Graph
• The adjacency matrix B of a complete graph (a graph with all edges
present) is a matrix with all ones minus the identity matrix.

1/21/2025 Dr. Sarada Jayan 13

 Degree Matrix of a Graph
• The Degree matrix D of a graph with n nodes is a diagonal matrix
of order n with row sum of adjacency matrix as diagonal elements.
• Degree matrix counts the edges into nodes

1/21/2025 Dr. Sarada Jayan 14

 Degree Matrix of a complete Graph
• The degree matrix D of a complete graph (a graph with all edges
present) is (n-1)I, where I is an n by n identity matrix

1/21/2025 Dr. Sarada Jayan 15

 Homework
For all the given graphs:
(a) Find the adjacency matrix B
(b) Find the degree matrix D

A B

1/21/2025 Dr. Sarada Jayan 16

 Laplacian Matrix of a Graph
• The Laplacian matrix L of a graph with m edges and n nodes is an n
by n square matrix, L=ATA, where A is the incidence matrix.
• The diagonal entry Lii gives the count of the edges meeting at node i.
• The off-diagonal entry Lij = -1 when an edge connects nodes i and j.
• Laplacian matrix is symmetric and positive semidefinite.

1/21/2025 Dr. Sarada Jayan 17

 Laplacian Matrix of a Graph
• The diagonal entry Lii gives the count of the edges meeting at node i.
• The off-diagonal entry Lij = -1 when an edge connects nodes i and j.
• Laplacian matrix is symmetric and positive semidefinite matrix.

Question: Write down the Laplacian matrix for the following graphs

1/21/2025 Dr. Sarada Jayan 18

 Laplacian Matrix of a Graph
• Draw the graph if the Laplacian matrix of it is as given below:

1/21/2025 Dr. Sarada Jayan 19

 Laplacian Matrix of a Graph
• One eigenvalue of Laplacian matrix is zero (row sum of L is zero)
and all other n-1 eigenvalues are positive since L=A’A
• L is a semi positive definite matrix
• Eigenvectors of L are orthogonal vectors
• Vector of all ones is an element in Nullspace of L
• Rank of L is n-1 as rank of A is n-1 (since R(AAT)=R(A)).
• Nullity of L is one and null space of L is [c, c,…, c]T
• Dim(RS of L)=Dim(CS of L)=rank of L = n-1
• Dim (NS of L) = Dim(LNS of L) = 1 (since L is symmetric)

1/21/2025 Dr. Sarada Jayan 20

 Laplacian Matrix of a Graph
• The Laplacian matrix L =ATA = D – B, where D is the degree
matrix and B is the adjacency matrix

1/21/2025 Dr. Sarada Jayan 21

 Laplacian Matrix of a complete Graph

Laplacian matrix for a complete graph with n nodes is

L = nIn – matrix of all ones

Question. Find the Laplacian matrix for the given complete graphs

1/21/2025 Dr. Sarada Jayan 22

 Laplacian Matrix of a Graph
Question. Find the Laplacian matrix for the following graphs and
verify all the properties given in the previous slides

1/21/2025 Dr. Sarada Jayan 23

 Homework
Q1. For both the given graphs:
(a) Find the adjacency matrix B
(b) Find the degree matrix D
(c) Find the incidence matrix A and Laplacian matrix L from the graph.
(d) Verify that L=ATA and L=D-B
A B

1/21/2025 Dr. Sarada Jayan 24

 Homework
Q2. Given the incidence matrix of a graph is:

Find the Laplacian matrix and then draw the graph

Q3. Given the adjacency matrix of a graph is:

Find the Laplacian matrix and then draw the graph

1/21/2025 Dr. Sarada Jayan 25

 Homework
Q4. For a complete graph with 8 nodes, find:
(a) matrices A, B, D and L
(b) Find eigenvalues of B and L

1/21/2025 Dr. Sarada Jayan 26

 Summary of Matrices related to graphs

Self work:
Try all the questions in section IV.6 of the Gilbert Strang’s
textbook, “Linear Algebra: Learning from Data”

1/21/2025 Dr. Sarada Jayan 27