Exercise 2.5.9. Given the incidence matrix from exercise 2.5.6 (for the graph on page 113 with six edges and four nodes) and the diagonal matrix
compute and . Describe how the diagonal and other entries in can be predicted from looking at the graph to which corresponds.
Answer: We have
Note that through in can be associated with edges 1 through 6 respectively. Each row of the product then corresponds to a given node, and the entries in the row reflect the edges connected to that node and the nodes connected to the given node by those edges.
For example, the first row of corresponds to node 1. The value of for the (1, 1) entry reflects the fact that edges 1, 2, and 5 all have node 1 as an endpoint. The value of for the (1, 2) entry reflects the fact that edge 1 connects node 1 to node 2, the value of for the (1, 3) entry reflects the fact that edge 2 connects node 1 to node 3, and the value of for the (1, 4) entry reflects the fact that edge 5 connects node 1 to node 4.
Similar interpretations apply to rows 2 through 4, which represent the connections for nodes 2 through 4 respectively. The matrix is symmetric because if a given edge connects node to node and thus produces an (i, j) entry of the matrix then that same edge also connects node to node to produce a (j, i) entry of the same value.
NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.
If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.