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

<p>A more recent reference on the subject of actually computing the transitive closure is Marius Bozga, Radu Iosif and Filip Konečný, <em>Fast Acceleration of Ultimately Periodic Relations</em>, in CAV 2010 (Computer Aided Verification), Lecture Notes in Computer Science 6174, pages 227--242, <a href="http://dx.doi.org/10.1007/978-3-642-14295-6_23" rel="nofollow">DOI: 10.1007/978-3-642-14295-6_23</a>, 2010.</p>

CC BY-SA 2.5
2011-01-11T12:54:27.033Z
2011-01-11T12:54:27.033Z
Sylvain
<p>I am looking for work on computing the transitive closure
of an affine relation in the following sense:</p>

<p>Let $R(x_1,\dots,x_n,x&#39;_1,\dots,x&#39;_n)$
be the relation defined by a system of linear inequalities over real variables
$x_1,\dots,x_n,x&#39;_1,\dots,x&#39;_n$,
i.e.</p>

<p>$R(x_1,\dots,x_n,x&#39;_1,\dots,x&#39;_n)$ iff
$A x_1\dots x_n x&#39;_1\dots x&#39;_n \leq b$</p>

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

<p>I am looking for a symbolic representation of $R^k$,
where</p>

<p>$R^k(x_1,\dots,x_n,x&#39;_1,\dots,x&#39;_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&#39;_1,\dots,x&#39;_n)$.</p>

<p>As a very simple example, consider</p>

<p>$R(x,x&#39;)$ iff $x&#39;\leq x+1$ and $x&#39;\geq \frac{1}{2} x$</p>

<p>In this case, $R^k(x,x&#39;)$ iff $x&#39;\leq x+k$ and $x&#39;\geq \frac{1}{2^k} x$</p>

<p>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&#39;_j$ and compute its $k$th power.
But of course in general, $R$ will not be functional.</p>

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

<p>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.</p>

CC BY-SA 2.5
2011-01-06T14:04:45.217Z
(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
CC BY-SA 2.5
2011-01-06T14:37:59.210Z
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
CC BY-SA 2.5
2011-01-06T14:45:49.893Z
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
CC BY-SA 2.5
2011-01-06T15:02:55.097Z
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
<ds.algorithms><linear-algebra><matrices>
Transitive closure of an affine relation
warakawa
# Transitive closure of an affine relation

(Asked by: username_0 on 2011-01-06)

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.

**Tags:** ds.algorithms, linear-algebra, matrices

> **Comments:**
> **username_1**: (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?  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-01-11. Score: 4 | Accepted answer

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](http://dx.doi.org/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.

A more recent reference on the subject of actually computing the transitive closure is Marius Bozga, Radu Iosif and Filip Konečný, *Fast Acceleration of Ultimately Periodic Relations*, in CAV 2010 (Computer Aided Verification), Lecture Notes in Computer Science 6174, pages 227--242, [DOI: 10.1007/978-3-642-14295-6\_23](http://dx.doi.org/10.1007/978-3-642-14295-6_23), 2010.


---

