Description

General Instructions

The following document contains the solutions to the theory-based questions for
Question 2

a) In an adjacency matrix, each entry is either 0 or 1, depending on whether an edge exists or not between two nodes(vertices). Hence, we can say that the field of the matrix is {0,1}.
It is a Binary Field.
b) If there are no self-loops in the graph, all the diagonal terms in the adjacency matrix willbe zero. Hence, the trace of the matrix will also be zero. This condition is violated in the presence of one or more self-loops.
c) The primary difference between the adjacency matrix of a directed and an undirectedgraph is that the adjacency matrix of a undirected graph is always symmetric whereas this is not necesarily true for a directed graph. The reason being, in an undirected graph, the edge between the vertices is in both directions, which is reflected in the graph i.e. Aij = Aji. This is not true for a directed graph.
d) The degree of a vertex of a graph refers to the number of edges incident to that vertex.Thus, in an adjacency matrix, we can find this value by calculating the sum of all the entries in a column or a row. Since the entries for non-connected vertices are 0, the answer will be equal to the number of connected vertices. Mathematically,
n
deg(v) = ∑Avi
i=0
n
= ∑Ajv
j=0
where n is the number of vertices and aij denotes the value of the entry at the ith row and jth column of the adjacency matrix.
Alternatively, this can also be achieved by finding the dot product of a row or column vector with itself.
e) Given that there are no self loops, each value in A2 corresponds to Aii i.e. the diagonal values will be equal to the degree of the corresponding vertex. Hence, the summation of the diagonal values is equal to twice the total number of edges in the graph.
⟹ trace(A2) = 2m
Please note that this is valid for simple graphs only.
f) Claim: The number of walks of length k between vi and vj is given by (AK)ij i.e. the ijth entry of the matrix AK.
Proving the above claim by induction:
For k = 1, the number of walks between the vi and vj is given by Aij because Aij = 1 implies that there is an edge between the two vertices, which is a walk of length 1, and Aij = 0 means that no such walk exists.
Assuming the claim to be true for all k ∈ {1,⋯,k0}
We attempt to prove it for k = k0 + 1. Any walk of length k0 + 1 from vi to vj consists of a walk of length k from vi to a neighbour of vj.
For vp ∈ N(vj) i.e. vp is a neighbour of vj, the number of walks of length k between vi and vp is given by (Ak0)ip.
W(vi,vj,k + 1) = ∑ W(vi,vp,k)
vp∈N(j)
= ∑ AKip
vp∈N(j)
n
= ∑ AKimAmj
m=1 = AKij+1
where W(vi,vj,k) denotes the number of walks of length k between vi and vj. The summation obtained is the ijth entry of the matrix obtained by multiplying AK with A.
Hence, the claim is true for k = k0 + 1.
Note
The ijth entry of the matrix Z ∈ Rm×p obtained by multiplying the matrices X ∈ Rm×n and
Y ∈ Rn×p is given by
n
Zij = xikykj
Question 3
The adjacency matrix for a graph with n nodes A (A ∈ Rn×n) validates the existence of a connection between 2 points in a graph. For an undirected graph,
∃ a link between i and j
Aij
erwise ⎡⎤

A ⎣ ⎦
The incidence matrix for a graph with m edges and n nodes B (B ∈ Rm×n) checks for the incidence of vertex j upon edge i in a graph. For an undirected graph,
1 if vertex j lies on the edge i
Bij = {
0 otherwise
⎡
1 1 0 0 0 0⎤
1 0 1 0 0 0
0 1 1 0 0 0
0 1 0 1 0 0
B =
0 1 0 0 1 0
0 0 0 1 1 0
⎣
0 1 0 0 0 1
0 0 0 0 1 1⎦
Question 4
The output of a system ( say y[n] ) is given by the convolution of the input with the impulse response of the system. We can write this as:
y[n] = x[n] ∗ h[n]
The linear convolution sum can be written as a matrix-vector product with help of the Toeplitz matrix.
The Toeplitz matrix of the impulse response is given by:
⎡
1 0 0 0⎤
1 1 0 0
0 1 1 0
0 0 1 1
1 0 0 1
H = 0 1 0 0 1 0 1 0
0 1 0 1
0 0 1 0
⎣
0 0 0 0⎦ 0 0 0 1
Now, we can write the convolution sum as:
y[n] = H[n] x[n]
⎡
1 0 0 0⎤
1 1 0 0
0 1 1 0
0 0 1 1
1
1 0 0 1 ⎡ ⎤
2
= 0 1 0 0
3
1 0 1 0 ⎣ ⎦
4
0 1 0 1
0 0 1 0
⎣
0 0 0 1
0 0 0 0⎦
= [1 3 5 7 5 2 4 6 3 4 0]T
Question 5
a) Consider the given circuit.
As the inductor has a reading of 2Ω, you can consider the impedance to be j2Ω. Else, considering the inductance as 2H, the impedance is jω × 2 = j100 × 2 = j200Ω. The other inductor has an inductance of 0.02H. Hence, the impedance is jω × 0.02 = j100 × 0.02 = j2Ω
.
This solution has been made assuming j2Ω.
Consider that the matrix-vector product is to be made wrt VA and VB. This means that the resistance 10Ω and impedance j2Ω can be considered to be in series. The effective impedance thus becomes (10 + 2j)Ω

From the circuit,
VA − VB = Vs = 10sin(100t + )
If written directly as a matrix-vector product, we have
[1 −1]VA] = 10sin(100t +) VB
Perform nodal analysis at Node A:
is = VA j−2VB + V1A0−+Vj2B
= VA ( + ) − VB ( + )
= [ j12 + 10+1j2 − j12 − 10+1j2 ][VA]
VB
Another possibility would be combining these equations into a common matrix-vector product.
⟹ [ s] = [ j2 + 10+1j2 − j12 − 10+1j2 ][VA] i 1
0 1 −1 VB
One solution can be made without considering VA and VB too. Consider the following circuit and notations.

At Node 1,
is = Vj21 + V − V
At Node 2,
V + V21−0V1 = 0
Also,
V1 = Vs
Substituting the third equation in the second,
V2 + V21−0Vs = 0 j2
⟹ V2 ( j12 − 110 ) = 1V0s ⟹ j12 − ][V2] = [ V10s ]
b) Consider the given circuit.

This solution too can be made using various methods. The one that has been followed here is using the notation below. Assume that ω of the current source = 100s−1.

From the circuit, V5 = −2V . At Node 1,
is = V11−0V2
= V1 − V2
10 10
At Node 2,
V + V21−0V1 + V2−−j2V3 = 0
⟹ −V1 + V2 ( 1 + 1 + 1 ) − V = 0
At Node 3,
V V
= 0
⟹ V + V3 + − V54 = 0
At Node 4,
+ V4 j−1V5 = 0
⟹ + V4 ( + ) = −j12
These four final euqations can be written as a matrix-vector product. i.e.,
j 0 0 ⎤⎡V1⎤ ⎡ is ⎤
−1 1 ++0 V20
10 2 j1 1 + −1j2 15 V3 =0
⎣ 0 0+ j11 ⎦⎣V4⎦ ⎣ −j12 ⎦ 0 2 5

Note
As there are multiple correct approaches to each part of this question, marks will be awarded regardless of the method chosen if a correct matrix vector product is formed.