Home >
Community >
Transitivity using adjacency matrices?
Upvote
18
Downvote
+ Transition
+ Graphs
Posted by
Kaninefat
Transitivity using adjacency matrices?
True, that's why I stipulated 1s on the diagonal and a reflexive relation. That way squaring doesn't lose any links and R2 >= R is forced. The question is whether one gains any new links and R2 <= R stops that. So R2 = R is precisely the condition for transitivity.
Saying that a graph (not a directed graph) represents a relation implies the relation is symmetric (and also reflexive), by the way. But I think that's all probably an oversight. It depends how tricky the question setter was trying to be! I assumed this had some background context that was meant to make it an easy exercise with no tricks, so R2=R is the answer and we just have to imagine how and why.
That phrasing of "no new non-zero elements" is a good idea, but the "and vice versa" is probably a mistake. One can in the most general situation be happy to lose links. Nobody says that if you can get from X to Y in one step, then you must also be able to get to it in two. Only in a reflexive relation ...
True, that's why I stipulated 1s on the diagonal and a reflexive relation. That way squaring doesn't lose any links and R2 >= R is forced. The question is whether one gains any new links and R2 <= R stops that. So R2 = R is precisely the condition for transitivity.
Saying that a graph (not a directed graph) represents a relation implies the relation is symmetric (and also reflexive), by the way. But I think that's all probably an oversight. It depends how tricky the question setter was trying to be! I assumed this had some background context that was meant to make it an easy exercise with no tricks, so R2=R is the answer and we just have to imagine how and why.
That phrasing of "no new non-zero elements" is a good idea, but the "and vice versa" is probably a mistake. One can in the most general situation be happy to lose links. Nobody says that if you can get from X to Y in one step, then you must also be able to get to it in two. Only in a reflexive relation ...
If the matrix A2 does not contain a non-zero element on the position, where A has zero, then is the relation transitive (and vice versa). In a different wording: if there is a two-step path "ax-xc" between vertices a,c then the shortcut ac must belong to the relation. Othervise is the relation not transitive. It is not necessary to have A2=A. Example: Let the relation be R={ab,ac,bc}. Here A2 and A are not equal, but R is transitive.
If the matrix A2 does not contain a non-zero element on the position, where A has zero, then is the relation transitive (and vice versa). In a different wording: if there is a two-step path "ax-xc" between vertices a,c then the shortcut ac must belong to the relation. Othervise is the relation not transitive. It is not necessary to have A2=A. Example: Let the relation be R={ab,ac,bc}. Here A2 and A are not equal, but R is transitive.
A transitive relation has R2 = R, if you take addition of 1/0s as OR in the matrix multiplication. If you prefer ordinary addition, that is f(R2)=R, where f maps matrix entries n>=1 to 1, and 0 to 0. Actually, that first requires 1s on the diagonals in R in order to be exactly defining, i.e. reflexivity. I guess I took that for granted. Replace R by R U I if your definition of adjacency matrix doesn't force 1s on the diagonal.
A transitive relation has R2 = R, if you take addition of 1/0s as OR in the matrix multiplication. If you prefer ordinary addition, that is f(R2)=R, where f maps matrix entries n>=1 to 1, and 0 to 0. Actually, that first requires 1s on the diagonals in R in order to be exactly defining, i.e. reflexivity. I guess I took that for granted. Replace R by R U I if your definition of adjacency matrix doesn't force 1s on the diagonal.
True, that's why I stipulated 1s on the diagonal and a reflexive relation. That way squaring doesn't lose any links and R2 >= R is forced. The question is whether one gains any new links and R2 <= R stops that. So R2 = R is precisely the condition for transitivity.
Saying that a graph (not a directed graph) represents a relation implies the relation is symmetric (and also reflexive), by the way. But I think that's all probably an oversight. It depends how tricky the question setter was trying to be! I assumed this had some background context that was meant to make it an easy exercise with no tricks, so R2=R is the answer and we just have to imagine how and why.
That phrasing of "no new non-zero elements" is a good idea, but the "and vice versa" is probably a mistake. One can in the most general situation be happy to lose links. Nobody says that if you can get from X to Y in one step, then you must also be able to get to it in two. Only in a reflexive relation ...
True, that's why I stipulated 1s on the diagonal and a reflexive relation. That way squaring doesn't lose any links and R2 >= R is forced. The question is whether one gains any new links and R2 <= R stops that. So R2 = R is precisely the condition for transitivity.
Saying that a graph (not a directed graph) represents a relation implies the relation is symmetric (and also reflexive), by the way. But I think that's all probably an oversight. It depends how tricky the question setter was trying to be! I assumed this had some background context that was meant to make it an easy exercise with no tricks, so R2=R is the answer and we just have to imagine how and why.
That phrasing of "no new non-zero elements" is a good idea, but the "and vice versa" is probably a mistake. One can in the most general situation be happy to lose links. Nobody says that if you can get from X to Y in one step, then you must also be able to get to it in two. Only in a reflexive relation ...
More
VOTE
If the matrix A2 does not contain a non-zero element on the position, where A has zero, then is the relation transitive (and vice versa).
In a different wording: if there is a two-step path "ax-xc" between vertices a,c then the shortcut ac must belong to the relation. Othervise is the relation not transitive.
It is not necessary to have A2=A.
Example:
Let the relation be R={ab,ac,bc}. Here A2 and A are not equal, but R is transitive.
If the matrix A2 does not contain a non-zero element on the position, where A has zero, then is the relation transitive (and vice versa).
In a different wording: if there is a two-step path "ax-xc" between vertices a,c then the shortcut ac must belong to the relation. Othervise is the relation not transitive.
It is not necessary to have A2=A.
Example:
Let the relation be R={ab,ac,bc}. Here A2 and A are not equal, but R is transitive.
More
VOTE
Useful. Thank you.
Useful. Thank you.
More
VOTE
A transitive relation has R2 = R, if you take addition of 1/0s as OR in the matrix multiplication.
If you prefer ordinary addition, that is f(R2)=R, where f maps matrix entries n>=1 to 1, and 0 to 0.
Actually, that first requires 1s on the diagonals in R in order to be exactly defining, i.e. reflexivity. I guess I took that for granted. Replace R by R U I if your definition of adjacency matrix doesn't force 1s on the diagonal.
A transitive relation has R2 = R, if you take addition of 1/0s as OR in the matrix multiplication.
If you prefer ordinary addition, that is f(R2)=R, where f maps matrix entries n>=1 to 1, and 0 to 0.
Actually, that first requires 1s on the diagonals in R in order to be exactly defining, i.e. reflexivity. I guess I took that for granted. Replace R by R U I if your definition of adjacency matrix doesn't force 1s on the diagonal.
More
VOTE