Question

Linear Algebra
Graph and Matricies

Introduction One of the most interesting applications of linear algebra is to the problem on network analysis. The system of highways or city roads constitutes a network, as does a telephone communication network, or even the World Wide Web. In order to analyze highly complex networks, it is necessary to use fast computers and advanced methods, but the journey must begin somewhere and I hope that for you it starts here today, by analyzing some simple networks and discovering how matrix methods can help. A useful tool to analyze a network is a graph, not in the familiar sense of the graph of a function, but in the sense of a diagram consisting of points, called vertices or nodes, and directed arrows, each representing a connection from one node to another. For instance, this graph represents a network consisting of four nodes connected through each of the drawn arrows: In this network there is one way to go from N, to N,, one way to go from N, back to N, (yes, that option is available too!), two ways to go from N, to N,, but no way to go from N, to N, or to N2, or to go from N, to N, etc. The link between these graphs and linear algebra is obtained through an adjacency matrix, that is, a matrix M in which entry M, represents the number of options available to go from N, to N,. For instance, the adjacency matrix for the above graph is the 4x4 matrix: In this seminar you will start exploring how matrix operations can produce information about the network. As usual, this is just an introduction, but it will give you a taste for the application and will offer you another opportunity to play with matrices and their properties. Please check the additional file available on BB with some examples on this application.

Answer 1

M = Aro 10 oo CI 0 0 1 0 0 oooo EO 1 0 1 0 1 Floo ooo AFF In this network there is one way from A to B , B to C, one way to go C to D and back to C and so on... There is no way from D to E t to E, B to A, (to B (2) The given Matrix M is not symmetric because its diagonal entries are zero. To make M symmetric it should have every verten has its own way that is There is one way to go from and back to itself and every element hes go and back way to every verten oor not anyway. (that is it is comected both way ar not connected)

To o - 0 0 0 - 0 ooooo A AS 1 B 1 co 0 2 B C e f 0 1 0 1 0 1 0 2 0 1 1 1 0 0 2 0 0 1 oo 1 (a) By Multiplication many verticies get two ways like B to D, (tof, a to A, EtoC and many Verticies disconnected like Atof, stof etc. (6) If A is adjacency Matrix of the directed graph then the Matrix An Ele the Matrix product of nopies of A) Les an intresting interpretation, the element (1, 1 gives the number of walks of length n from verten i to verten y ffn is the smallest nou - negative integer such that fur sense (1, 1) the element (ij) of an is positive. (9 M² = M² M = rololol roloool 1 0 201 o 0 2 0 0 1 0 - - 0 1 1 0 0 0 دم ITO 2 0 1 1 Lolo vol J Ari î ó ? BI I30 13 c/3 olio olo 2 1 0 0 3 B3 2 o 3 0 2 191 1 0 1 0 1 0 تما م

Therefore there is a way from A to D in three steps as discribed above
As the policy i can do only four parts