TUMity of gray and degray matrices

The matrices which are used to convert from a "real" to gray and back again are total-unimodular. What does this mean in a linear algebraic way? What does this mean in a graph theoretic way?
--
Postscript: The paper by Conforti et. al is a very interesting one.

It classifies a set of SAT problems that can be solved in polynomial time (I noticed this property from the dense book by the second author).

For a JACM paper, it is very short, mainly consisting of one main proof.

What are its implications on a search algorithm? In specific, how does this property help solving SAT using GA or the more general problem of GRAY/BINARY representations?

--
Postscript: Consider a deterministic algorithm. randomize it, and call it a GA. If we define a new space which the GA looks at, it is working like a simplex algorithm by doing a neighbourhood search.