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.