Re: Transitive Order of a Relation

On May 9, 2:04 pm, quasi <q...@xxxxxxxx> wrote:
On 9 May 2007 02:52:43 -0700, DGo...@xxxxxxxxxxxx wrote:

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.

Oh. I see. You're forming the convex hull of G? I'm not doing that.

What I believe is that I have invented OR discovered a parameter
applicable to all relations R which are subsets of AxA. I'd like to
determine if I have invented this or discovered some other person's
work product perhaps from long ago.

For all x, y in A, for any directed graph of a relation R, a subset of
the Cartesisan product of arbitrary set A with itself (AxA), form a
(square) adjacency matrix of ones and zeroes with one indicating a
relation from element x to element y (that is, xRy) of AxA and a zero
indicating no such relation.

Square this matrix. Piecewise (element by element) divide each element
this new matrix by its magnitude, defining 0/0 = 0. We now have a new
matrix. Continue squaring and "normalizing" the matrix until, on
interation n, it is found (inevitably) that

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

Call this n the transitive order of the relation. The question is:

Is this n OF use (and new), or perhaps IN use (and old)?

I have an example in Mathcad from our Discrete Math exam to post soon
as I can find the paper.

Doug



.