Linear Algebra and Its Applications, Exercise 2.5.9

Exercise 2.5.9. Given the incidence matrix A from exercise 2.5.6 (for the graph on page 113 with six edges and four nodes) and the diagonal matrix

C = \begin{bmatrix} c_1&0&0&0&0&0 \\ 0&c_2&0&0&0&0 \\ 0&0&c_3&0&0&0 \\ 0&0&0&c_4&0&0 \\ 0&0&0&0&c_5&0 \\ 0&0&0&0&0&c_6 \end{bmatrix}

compute A^TA and A^TCA. Describe how the diagonal and other entries in A^TA can be predicted from looking at the graph to which A corresponds.

Answer: We have

A^TA = \begin{bmatrix} -1&-1&0&0&-1&0 \\ 1&0&-1&-1&0&0 \\ 0&1&1&0&0&-1 \\ 0&0&0&1&1&1 \end{bmatrix} \begin{bmatrix} -1&1&0&0 \\ -1&0&1&0 \\ 0&-1&1&0 \\ 0&-1&0&1 \\ -1&0&0&1 \\ 0&0&-1&1 \end{bmatrix}

= \begin{bmatrix} 3&-1&-1&-1 \\ -1&3&-1&-1 \\ -1&-1&3&-1 \\ -1&-1&-1&3 \end{bmatrix}

and

A^TCA = \begin{bmatrix} -1&-1&0&0&-1&0 \\ 1&0&-1&-1&0&0 \\ 0&1&1&0&0&-1 \\ 0&0&0&1&1&1 \end{bmatrix} \begin{bmatrix} c_1&0&0&0&0&0 \\ 0&c_2&0&0&0&0 \\ 0&0&c_3&0&0&0 \\ 0&0&0&c_4&0&0 \\ 0&0&0&0&c_5&0 \\ 0&0&0&0&0&c_6 \end{bmatrix} \begin{bmatrix} -1&1&0&0 \\ -1&0&1&0 \\ 0&-1&1&0 \\ 0&-1&0&1 \\ -1&0&0&1 \\ 0&0&-1&1 \end{bmatrix}

= \begin{bmatrix} -c_1&-c_2&0&0&-c_5&0 \\ c_1&0&-c_3&-c_4&0&0 \\ 0&c_2&c_3&0&0&-c_6 \\ 0&0&0&c_4&c_5&c_6 \end{bmatrix} \begin{bmatrix} -1&1&0&0 \\ -1&0&1&0 \\ 0&-1&1&0 \\ 0&-1&0&1 \\ -1&0&0&1 \\ 0&0&-1&1 \end{bmatrix}

= \begin{bmatrix} c_1+c_2+c_5&-c_1&-c_2&-c_5 \\ -c_1&c_1+c_3+c_4&-c_3&-c_4 \\ -c_2&-c_3&c_2+c_3+c_6&-c_6 \\ -c_5&-c_4&-c_6&c_4+c_5+c_6 \end{bmatrix}

Note that c_1 through c_6 in C can be associated with edges 1 through 6 respectively. Each row of the product A^TCA 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 A^TCA corresponds to node 1. The value of c_1+c_2+c_5 for the (1, 1) entry reflects the fact that edges 1, 2, and 5 all have node 1 as an endpoint. The value of -c_1 for the (1, 2) entry reflects the fact that edge 1 connects node 1 to node 2, the value of -c_2 for the (1, 3) entry reflects the fact that edge 2 connects node 1 to node 3, and the value of -c_5 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 A^TCA is symmetric because if a given edge connects node i to node j and thus produces an (i, j) entry of the matrix then that same edge also connects node j to node i 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.

 Buy me a snack to sponsor more posts like this!

This entry was posted in linear algebra. Bookmark the permalink.

2 Responses to Linear Algebra and Its Applications, Exercise 2.5.9

  1. Filipe says:

    I’m learning a lot by your blog. I wish you resolve some questions Strang: 2.5.12, 2.5.16 and 2.6.4, 2.6.10, 2.6.16.
    Keep up the good, fun work!
    Thanks

    • hecker says:

      My apologies–for some reason your comment got held up in moderation and I didn’t notice it. I’ve posted the answers for 2.5.12 and 2.5.16, and will post answers for the other ones in the coming months as I have time.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s