## 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.

## Reviews

There are no reviews yet.