1

Consider the following matrix: \begin{bmatrix}1&0&0&1\\0&1&0&0\\0&0&1&0\\1&0&0&1\end{bmatrix}

Does this matrix represent any of the relations in 2.9(a)–(c)?

$$(a) {(2, 2),(2, 3),(2, 4),(3, 2),(3, 3),(3, 4)}$$ $$(b) {(1, 1),(1, 2),(2, 1),(2, 2),(3, 3),(4, 4)}$$ $$(c) {(2, 4),(4, 2)}$$

Well I know that it cannot be (c) as there are 6 1's in the matrix so it must be be (a) or (b) if any. Then I figure out it can't be (a) because the matrix shows that the relation must be reflexive as there are a diagonal of 1's so that leaves us (b) which is indeed reflexive.

I do some playing around to figure out what way the elements must be listed as it can't be a 1,2,3,4 matrix as that wouldn't match (b). I come up with 1,4,3,2 but the answer says this:

Yes, it represents the relation in 2.9(b), with the elements of {1, 2, 3, 4} listed as 2, 3, 4, 1

Is my version of listing the elements correct? It seems so to me but the answer only has one ordering of elements 2,3,4,1.

And how are you supposed to go about these questions because it seems tedious having to do trial and error, is there a process to go about finding out which way the elements must be listed in the matrix?

Thanks in advance

computerscienceisapain
  • 238
  • 1
    both answers are correct – Exodd Sep 01 '21 at 19:59
  • So how would you go about these questions in general? Do you just need to trial and error and use intuition? How would you go about this question @Exodd – computerscienceisapain Sep 01 '21 at 20:01
  • 1
    @Exodd (a) is false because there is no row with three $1$s in the matrix, while the relation contains (2,2),(2,3),(2,4) (similarly with 3 as the first element) – user376343 Sep 01 '21 at 20:01
  • 1
    @user376343 by 'both answers' I meant the OP's answer and the book's answer – Exodd Sep 01 '21 at 20:05
  • In general, this is the graph isomorphism problem. Trial and error and intuition is a good way to described doing it with a pencil for a small graph (matrix). There are computer programs that will solve this problem quickly in practice, but it's still unknown, so far as I know, whether there is an algorithm that will solve all possible problems of this type efficiently. – saulspatz Sep 01 '21 at 20:29

0 Answers0