Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The thing I find the most difficult is the transitive part. The only way that I know of is to see if the relation is transitive, but I have to do check if it is transitive for every relation possible on a given matrices. It gets quite cumbersome when you have a matrix of 5 elements or more. So is there some sort of shortcut?

share|cite|improve this question

closed as not a real question by Chris Eagle, dtldarek, Henry T. Horton, tomasz, Cameron Buie Dec 9 '12 at 3:40

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

What are you actually trying to do? – Chris Eagle Dec 9 '12 at 0:08
Finding the smallest partial order for S={(1,5) (2,3) (2,4) (3,3) (4,3) (5,1)} – xeonphi Dec 9 '12 at 0:09
What on earth does that mean? – Chris Eagle Dec 9 '12 at 0:10
If you are trying to find the smallest partial order containing some relation, look at closure operations. – dtldarek Dec 9 '12 at 0:11
it defines a relation matrix – xeonphi Dec 9 '12 at 0:11

Draw a picture. Make a dot for each of the elements. Whenever you know that $a\prec b$, draw an arrow from $b$ to $a$.

Except that if you know that $a\prec b$ and $b\prec c$, don't bother drawing an arrow for $a\prec c$, because you'll be able to see at a glance that $a\prec c$. Also don't bother to draw the arrow from $a$ to itself, because you'll know they are there anyway.

If you have $a\prec b$ and $b\prec a$ for some $a$ and $b$, this will be apparent, and to make the order into a partial order, you merge $a$ and $b$ into a single dot. Similarly any cycle of arrows $a\prec b\prec c\prec\cdots\prec a$ collapses down to a single point in a partial order.

Then look at the picture. Maximal and minimal elements will be obvious; elements that can't be compared will be obvious; relations implied by transitivity will be obvious.

After you absorb the picture, try drawing it again, and this time when $a\prec b$, instead of drawing an arrow from $b$ to $a$, just try drawing $b$ above $a$ on the paper. For example, here's when we have $a\prec 1, 0\prec c, b\prec 1, c\prec a, 0\prec b$:

some partial order

Clearly 1 is maximal, 0 is minimal, and $b$ is not comparable with $a$ or $c$. Also it's obvious that $0\prec a$ by transitivity.

share|cite|improve this answer
+1. Nice answer, and nice approach! – amWhy Dec 9 '12 at 1:54
@amWhy: I'm not sure it really helps the OP in this case, however. – MJD Dec 9 '12 at 1:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.