# Transitive closure of an affine relation

I am looking for work on computing the transitive closure of an affine relation in the following sense:

Let $R(x_1,\dots,x_n,x'_1,\dots,x'_n)$ be the relation defined by a system of linear inequalities over real variables $x_1,\dots,x_n,x'_1,\dots,x'_n$, i.e.

$R(x_1,\dots,x_n,x'_1,\dots,x'_n)$ iff $A x_1\dots x_n x'_1\dots x'_n \leq b$

where $A$ is an $m\times 2n$ matrix and $b$ an $m$-vector.

I am looking for a symbolic representation of $R^k$, where

$R^k(x_1,\dots,x_n,x'_1,\dots,x'_n)$ iff there exists $y_1,\dots,y_n$ such that $R^{k-1}(x_1,\dots,x_n,y_1,\dots,y_n)$ and $R(y_1,\dots,y_n,x'_1,\dots,x'_n)$.

As a very simple example, consider

$R(x,x')$ iff $x'\leq x+1$ and $x'\geq \frac{1}{2} x$

In this case, $R^k(x,x')$ iff $x'\leq x+k$ and $x'\geq \frac{1}{2^k} x$

There is an easy special case where all constraints are equalities: then we can apply Gauss elimination to find the affine transformation that maps the $x_i$ to the (dependent) $x'_j$ and compute its $k$th power. But of course in general, $R$ will not be functional.

The problem also seems to be easier when $R$ describes an open polytope a convex cone, but I can not assume this.

Edit: I'm looking for a parametric form independent of the concrete value of $k$ (as in the toy example). For a given value of $k$, a representation of $R^k$ can always be obtained from $R^{k-1}$ and $R$ by variable elimination.

• (1) “Transitive closure” sounds as if you are looking for something like R∪R^2∪R^3∪…, but I guess that this is not the case and that you are looking for the H-representation of R^k for a given k. Am I right? (2) Sorry for my ignorance, but what is an open polytope? – Tsuyoshi Ito Jan 6 '11 at 14:04
• Assuming that you are looking for an H-representation of R^k for a given k, there is at least an inefficient algorithm. Assume k=2 for simplicity (a general k can be handled in the same way). Let P={(x,x′)|R(x,x′)} be the polyhedron corresponding to the relation R, and consider the Cartesian product P×P={(x,x′,y,y′)|R(x,x′)∧R(y,y′)}. Since we are given an H-representation of P, we have an H-representation of P×P. Add the equation x′=y, and project out the variables x′ and y by the Fourier-Motzkin elimination (this is inefficient). Then we obtain an H-representation of the relation R^2. – Tsuyoshi Ito Jan 6 '11 at 14:37
• Thank you Tsuyoshi, indeed this was also my first idea. This gives an SLI (system of linear inequalities) for any given k. I am looking for a parametric form that is independent of the actual value of k. – warakawa Jan 6 '11 at 14:45
• Interesting. I think that it is better to edit the question so that people can understand that you are looking for a parametric form independent of the value of k without reading the comment. – Tsuyoshi Ito Jan 6 '11 at 15:02

An answer in case the monoid generated by $A$ for matrix multiplication is finite: Alain Finkel and Jérôme Leroux, How to Compose Presburger-accelerations: Applications to Broadcast Protocols, in FSTTCS 2002 (Foundations of Software Technology and Theoretical Computer Science) Lecture Notes in Computer Science 2556, pages 145--156, DOI: 10.1007/3-540-36206-1_14, 2002 (see also the many references there). The relation $R^k$ is represented by an effectively computable Presburger formula.