This is a question from CLRS 3E, 16-3a.
Argue that a set of columns of an incident Matrix M is linearly independent over the field of integers modulo 2 if and only if the corresponding set of edges is acyclic.
Graph used in this question is undirected. What really bugs me in this question is that, Let's say I have a graph with 3 vertices A, B & C with 3 edges x, y & z such that A--x--B, B--y--C & C--z--A. Which gives me the following Incidence Matrix:
| x | y | z | |
|---|---|---|---|
| A | 1 | 0 | 1 |
| B | 1 | 1 | 0 |
| C | 0 | 1 | 1 |
The columns of this matrix are linearly independent too since x=0 is the only solution to Mx=0. The questions asks the reader to prove that linear independence should only be possible when there is no cycle but in this case there is a cycle and it's still independent?
I have seen the answer posted at: Prove that columns of incidence matrix of tree are linearly independent but that doesn't clear my doubt. Since the question uses the phrase if and only if, shouldn't it also imply that in case of a cycle it will always be dependent?