# Symmetric relation v.s. symmetric matrix

• Oct 14th 2010, 07:10 PM
mrsi
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.
• Oct 15th 2010, 12:37 AM
HappyJoe
The idea is right, and perhaps your thinking is perfectly sound. Let me mention a few details anyway.

Remember that for a symmetric relation $E$, it holds by definition that if $iEj$, then $jEi$. So to prove the direction that you label as "i", you assume that $A$ is a symmetric matrix, and to prove that the relation $E$ is then symmetric, you need to assume that $iEj$ for some $i,j\in V$. From this assumption, you need to prove that $jEi$. For this purpose, your argument works fine: Since $iEj$, we have $a_{ij}=1$. Since the matrix is symmetric, we have also $a_{ji}=1$, which proves that $jEi$.

Similarly for the second part. Does your proof show (assuming $E$ is symmetric) that if $a_{ij}=0$, then $a_{ji}=0$?