Number of Relations

Question

I was stacked in one question . It was about number of reflexive relations on set with N elements. I know the solution but i don't know the logic behind it . I know we construct nxn matrix and number we find the subset that created by all elements of that matrix except the ones on diagonal. But why do it so why we exclude diagonal , what is the logic behind of it?

Answer 1

The relation $R$ on the set $X$ with $|X| = n$ is a subset of $X \times X$. We can represent this subset by $n \times n$ matrix $A$ which elements are $0$ or $1$, i.e. the pair $(i, j) \in R \subset X \times X$ if and only if $A_{i, j} = 1$.

If $R$ is reflexive, then $A_{i, j} = 1$ for $i = 1, 2, \dots, n$. So the diagonal of it's matrix is fixed. Also we can choose arbitrary values for all other elements. The number of all other elements is $n^2 - n$ which are all the elements of $n \times n$ matrix except $n$ elements on the diagonal.

For each off-diagonal element we have two choices: $0$ and $1$. So the total number of such matrices is $2^{n^2 - n}$.