## Friendships and Cliques in a Group

The diagram below shows the relationships within a group of people. An arrow from one person to another indicates that the first person is friendly to the second, and a line with arrows at both ends indicates that the two people are friends.The table representing the relationships is:

A | B | C | D | E | |

A | 0 | 1 | 1 | 1 | 1 |

B | 1 | 0 | 1 | 1 | 0 |

C | 1 | 1 | 0 | 1 | 1 |

D | 0 | 1 | 1 | 0 | 1 |

E | 1 | 1 | 1 | 1 | 0 |

A is friendly to D, but A and D are not friends, so there is a one sided arrow from A to D.

The matrix representing the diagram is:

\[M= \left( \begin{array}{ccccc} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \end{array} \right) \]

The table of friends is

A | B | C | D | E | |

A | 0 | 1 | 1 | 0 | 1 |

B | 1 | 0 | 1 | 1 | 0 |

C | 1 | 1 | 0 | 1 | 1 |

D | 0 | 1 | 1 | 0 | 1 |

E | 1 | 0 | 1 | 1 | 0 |

\[S= \left( \begin{array}{ccccc} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 1 & 1 & 0 \end{array} \right) \]

,A clique is the largest collection people, all friends with each other. The entries along the main diagonal of

\[S^3= \left( \begin{array}{ccccc} 4 & 8 & 8 & 4 & 8 \\ 8 & 4 & 8 & 8 & 4 \\ 8 & 8 & 8 & 8 & 8 \\ 4 & 8 & 8 & 4 & 8 \\ 8 & 4 & 8 & 8 & 4 \end{array} \right) \]

gives the number of three step relationships (person - friend - friend of this friend - person) between a person and himself. This means mutual friendships with at least two other people.If

\[(S^3)_{ii}\]

is positive then \[P_i\]

belongs to at least one clique and if \[(S^3)_{ii}=0\]

then \[P_i\]

does not belong to any cliques. All the diagonals entries in \[S^3\]

are positive, so everyone is in at least one clique. If there is only one, the number of individuals \[k\]

in it is the solution to \[(S^3)_{ii}=(k-1)(k-2)\]

. There can only possibly be 3, 4 or 5 individuals in any clique for this group, and none of them fit the above equation, so each person must belong to more than one clique.For A, the diagonal entry is 4=2+2, so A belongs to two cliques each with two other members. Similarly for B, D and E. The diagonal entry for C is also not a solution to the above equation, so C must belong to more than one clique. We could have 8=2+6 but this is impossible since there are only 5 members in the whole group, so we must have 8=2+2+2_2+2, and C is a member of all the cliques.