## Linear Algebra and Its Applications, Exercise 2.5.12

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

• the rank of $A$
• the number of free variables in the solution for the system $Ax = b$
• the number of free variables in the solution for the system $A^Ty = f$
• 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 $A$ corresponds to an edge of the graph and each column of $A$ corresponds to a node of the graph. Since $A$ 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 $A$ is 6, the number of edges in the spanning tree.

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

The system $A^Ty = f$ is a system of 7 equations in 12 unknowns. Since the rank of $A^T$ is 6 (same as the rank of $A$) 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 .

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