(How can you use Euler's theorem in these proofs?)

The PRDG has no self loops. They can be eliminated in a simple way.

---------------------------------------------------------

====================

**Alg1: Algorithm to construct G**

====================

For every row of the block matrix, there is a node in the hypergaph /*There are total n+d nodes in G*/

for all columns of A, do the following:

If there is a +1 in a column of G, then we make them the tail of a hyperedge. If there is a -1 in the row, we make that corresponding node a head of a hyperedge (A 0 does nothing. By a restriction in the input PRDG, a 0 in the incidence matrix of input PRDG corresponds to nothing).

---------------------------------------------------------

We can construct another graph G' in the following way:

---------------------------------------------------------

====================

**Algorithm to construct hypergraph G'**

====================

Notation:

The input PRDG is unitarized by step A_1 of the algorithm (given above). So in the rest of the paper, we refer to the unitarized-PRDG G_u simply as a PRDG. We also refer to it as a graph when the context is clear (In such instances, we refer to the other graph as a hypergraph). We also refer to the PRDG in terms of its block matrix. The block matrix is a (n+d)*m matrix, with the columns corresponding to its edges. Also, the top n rows corresponding to the incidence matrix of the PRDG, which is but a directed graph. The bottom d rows of the block matrix contain the d-dimensional dependence vectors associated with that corresponding edge.

G': A hypergraph constructed from the PRDG. Specifically, it has

**node**for each column of the block matrix A (or, a node for each edge of the PRDG)

**hyperedge**for a row of the matrix A. This also means a hyperedge which for a vertex of the PRDG and a hyperedge for each component of the dependence vector. The tail of the hyperedge is all the rows of A that have an entry equal to -1. The head of the hyperedge is all the rows of A that have an entry of +1.

**hypernode**per hyperedge of the hypergraph G': These are the additional nodes that comeup in the analysis. Refer to section ... for additional notes on types of hypernodes.

---------------------------------------------------------

**Lemma 1: G'=COMP(UNDIRECT(G))**G' is the graph obtained by the complementing the underlying undirected graph for G(see proof below).

**Lemma 2:**In graph G, all the hypernodes are either sources (all outgoing nodes) or sinks (all incoming nodes).

**Proof (by construction):**

**Corollary:**in graph G', for v \in hypernode, indegree(v) = outdegree(v)

**Theorem:**The given system of equations has a solution iff the orientation of G is a transitive orientation.

**Proof(if):**The orientation of G is a transitive orientation

**Corollary:**The given system of equations has a zero cycle iff the orientation of G' is a transitive orientation.

--

What is a separating hyperplane? How to do decomposition?

--

the given PRDG has atleast one alternating sign in every row and column.

--

Dependence analysis of unitarized PRDGs