Results 1 to 2 of 2

Math Help - Symmetric relation v.s. symmetric matrix

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    2

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member HappyJoe's Avatar
    Joined
    Sep 2010
    From
    Denmark
    Posts
    234
    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 5th 2013, 08:23 PM
  2. Relation that is 1-1, reflexive, but not symmetric
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2011, 01:13 PM
  3. Symmetric Relation question
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 20th 2010, 02:43 AM
  4. Replies: 2
    Last Post: November 13th 2010, 07:27 AM
  5. Smallest Symmetric Relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 14th 2010, 10:31 AM

Search Tags


/mathhelpforum @mathhelpforum