Witness and separating vector computation from CM-Z

One main feature of CM-Z algorithm is the computation of either a witness vector or a separating vector (are they the same? look for the notes below). The other main feature, is the computation of the partition of the graph, using the witness vector or the separating vector.
Defs(from the paper): The existence of a witness vector proves that a (nontrivial) zero-circulation does not exist. On the other hand, if you conclude that there exists no separating vector, then there exists a zero-circulation. Proposition 6.1 seems to suggest that a separating vector is the same as a witness. Is this true only in the case when the depth of the tree == 1????? All this means the following:

zero circulation exists? There exists no witness vector or a separating vector.

no zero-circulation? There is exists a witness and you will be able to find it. and a separating vector.
This is like trying to find a certificate for the problem (zero-cycle detection) or a certificate for the complement problem (scheduling problem). Can the algorithm be made faster if we reverse the direction of the certificate and complement?
--
According to CM-Z, KMW give an algorithm if and when monodimensional scheduling is possible. Of course, they raise the important issue of computability. Roychowdary and Kailath call the 1-dimensional scheduling as hyperplane scheduling. They give a simple LP formulation, (like DV-KMW: I am not sure who preceeds whom), for the case when a 1-dim schedule exists. They also have series of LP formulations, when the depth of the decomposition tree > 1.
--
The main idea of CM-Z is to find a vector v whose null space is maximal independent subspace. CM-Z say that the zero-cycle detection problem is harder than LP. (They reduce the general LP problem to this problem, which is the same thing. They reduce the problem within the POLY time hierarchy. So its ok, it proves some bounds about hardness, donot worry about it.) Since some rows of the constraint matrix have nicer properties. What can be done better? In specific, CM-Z is a general zero-cycle detection algorithm. Can it be specialized for 1-dimensions? i.e., can a maximal independent subspace be found in faster time?
--
Look up the Megiddo's beautiful paper on LP in linear time when dimension is fixed(this is the link), in which he uses a multi-dimensional median search.
What can be done something similar? like, starting from a partially sorted list and increasing the size of the sorted list????
--
added a strang's linear algebra link to the links. A simple question:

if Ax=0 has one solution x=0, then A is non-singular.

if Ax=0 has infinitely many solutions, then A is singular.
What do these two statements mean when A could be TUM??
--
ideas from notes on linear algebra page: matrix multiplication formulation of 1-dimensional scheduling problem.