## 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 and C are friends so there is a '1' in the row corresponding to A , column corresponding to C, and a '1' in the row corresponding to C, column corresponding to A.
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
The corresponding matrix is
$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.