Exercise 2.5.12. Let be a 12 by 7 incidence matrix for a connected graph. What are the following values?

• the rank of
• the number of free variables in the solution for the system
• the number of free variables in the solution for the system
• the number of edges that must be removed in order to convert the graph into a spanning tree

Answer: Each row in the incidence matrix corresponds to an edge of the graph and each column of corresponds to a node of the graph. Since is a 12 by 7 matrix the graph has 12 edges and 7 nodes. Since the graph is connected each node has at least one edge into or out of it.

Per the discussion on page 106, for a connected graph with 7 nodes all spanning trees contain 6 edges. (A example of such a spanning tree is a graph with an edge from node 1 to each of nodes 2 through 7.) We must therefore remove 6 of the 12 edges to form a spanning tree.

The rank of is 6, the number of edges in the spanning tree.

The system is a system of 12 equations in 7 unknowns. Since the rank of is 6 there are 6 pivots and 1 free variable in the solution.

The system is a system of 7 equations in 12 unknowns. Since the rank of is 6 (same as the rank of ) there are 6 pivots and 6 free variables in the solution.

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!