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!

2 Responses to Linear Algebra and Its Applications, Exercise 2.5.9

Filipe says:

December 2, 2012 at 8:53 pm

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:
  
  March 5, 2013 at 6:11 pm
  
  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.