Thread: Symmetric relation v.s. symmetric matrix

Here's the LONG question...

------------------------------------


A graph is a finite set of vertices V along with a relation E on V. The elements of the relation E are called edges (and the vertices are sometimes called nodes). We think of the edges as linking the vertices, that is if we draw points on a piece of paper, each point representing a vertex, then we would draw an arrow from vertex i to vertex j if and only if the pair (i, j) is an element of the relation E. Graphs can be used to represent communication networks where each person is represented by a vertex, and an edge links vertex i to vertex j if and only if person i communicates with person j.

The relation E can also be used to define the adjacency matrix of a graph. Simply define the adjacency matrix to be A = [aij] where aij= 1 iff (i, j) belongs to E, and 0 otherwise.

1. Given an arbitrary graph with edge-set E and adjacency matrix A, prove that E is symmetric as a relation iff A is symmetric as a matrix. (Hint 1: Start first with the assumption that E is symmetric, and deduce that A is symmetric. Then, assume that A is symmetric, and deduce that E is symmetric. Hint 2: This is a very easy problem. Don't make it harder than it is.)




----- ----------------------------------------
Here's Here's how I deal with it. Is that making any sense?
----------------------------------------------



------

i. Let A be symmetric matrix A=(aij). then aij=aji=1 which means in the graph, vertex i and vertex j are linked by E => iEj = jEi. Therefore, E is a symmetric relation.


ii. Let E be a symmetric relation. iEj => jEi , Which will be shown in the graph as an arrow from vertex i to vertex j and an arrow from vertex j to vertex i. => aij=aji=1 => A is a symmetric matrix.

The idea is right, and perhaps your thinking is perfectly sound. Let me mention a few details anyway.

Remember that for a symmetric relation , it holds by definition that if , then . So to prove the direction that you label as "i", you assume that is a symmetric matrix, and to prove that the relation is then symmetric, you need to assume that for some . From this assumption, you need to prove that . For this purpose, your argument works fine: Since , we have . Since the matrix is symmetric, we have also , which proves that .

Similarly for the second part. Does your proof show (assuming is symmetric) that if , then ?