Re: Transitive Order of a Relation

On 9 May 2007 02:52:43 -0700, DGoncz@xxxxxxxxxxxx wrote:

On May 9, 4:58 am, quasi <q...@xxxxxxxx> wrote:
On 8 May 2007 19:30:30 -0700, DGo...@xxxxxxxxxxxx wrote:





On May 6, 8:33 am, DGo...@xxxxxxxxxxxx wrote:
Given a relation R, which is a subset of the power set P of the
Cartesian product SxS of a set S with itself, R is either transitive
or it is not. The transitive closure of R is well defined and is
conventionally noted R^t, where t is not an integer, but indicates
"transitive".

Matrix multiplication may be used to find the transitive closure of a
graph. The mth power of an ajacency matrix is the number of paths of
length m between the relevant vertices. Each time the adjacency matrix
A of a graph G of a relation R is squared, new paths of length two may
appear. For large graphs this is easier using computer methods than
looking for potential closures in the graph by inspection. When none
appear, we are done; we have found the transitive closure of the
relation.

By defining 0/0 = 0, we may normalize any power of an adjacency matrix
simply to directly represent the transitive closure of a graph. We may
write (piecewise) (R / |R|) to normalize a matrix if 0/0 = 0. Then,
the transitive order of a relation R is

the minimial power n such the normalized adjacency matrices

(piecewise)
( (R^(2^n)) / | R^(2^n)) | ) = ( (R^(2^(n+1))) / | R^(2^(n+1)))
| ).

The transitive order of a transitive relation is 1.

The transitive closure of a relation with transitive order n is
therefore

( (R^(2^n)) / | R^(2^n)) | ).

Is this known?

Doug Goncz
Replikon Research
Seven Corners, VA 22044-0394

Hello? Is anybody listening?

Doug

Please define the term "relation of transitive order n"

At first glance, it appears you are defining the order of a relation
to be the least positive integer n power such that your sequence of
matrices stabilizes. If so your claim is true by definition -- there's
nothing to prove.

Yes, thank you for replying, quasi.

OK, it's true by definition.

Is it of any use and might a journal article be of interest to others?
Or perhaps a letter to the editor of a journal?

Is there a standard method to find the transitive closure of a
complicated relation, say of order > 10, other than matrix powers.

I'll let other more knowledgeable people respond to this last
question, but I think it's this question that you should have asked
initially.

Also, I asked you a question which you never really answered, so I'll
ask it again. How are you defining the transitive order of a relation?
Can you give some simple examples to illustrate?

Is it a standard terminology? If so, are you using a standard
definition?

I would have assumed the term transitive order to mean this ...

Start with a relation R, regarded R as a graph. For two elements a,b
in the same connected component of R, define the distance from a to b,
in the usual way, as the length of the shortest path from a to b. Then
define the transitive order of R to be the maximum distance for all
such pairs a,b. In other words, the transitive order of R is just the
maximum diameter of the components of R.

With the definition I proposed above, a relation is transitive iff it
has transitive order 1, which I think agrees with your interpretation.
However, using this definition, starting with any positive integer n,
it's easy to create a relation with transitive order exactly n. How
would the method of successive squaring distinguish between a relation
of transitive order 3 and one of order 4?

Some examples would be helpful.

quasi
.

Relevant Pages

  • Re: Transitive Order of a Relation
    ... The transitive closure of R is well defined and is ... A of a graph G of a relation R is squared, new paths of length two may ... we may normalize any power of an adjacency matrix ... The transitive order of a transitive relation is 1. ...
    (sci.math)
  • Re: Transitive Order of a Relation
    ... The transitive closure of R is well defined and is ... The mth power of an ajacency matrix is the number of paths of ... A of a graph G of a relation R is squared, new paths of length two may ... Please define the term "relation of transitive order n" ...
    (sci.math)
  • Re: Transitive Order of a Relation
    ... The transitive closure of R is well defined and is ... A of a graph G of a relation R is squared, new paths of length two may ... we may normalize any power of an adjacency matrix ... The transitive order of a transitive relation is 1. ...
    (sci.math)
  • Re: Transitive Order of a Relation
    ... The transitive closure of R is well defined and is ... A of a graph G of a relation R is squared, new paths of length two may ... we may normalize any power of an adjacency matrix ... The transitive order of a transitive relation is 1. ...
    (sci.math)