number of reflexive relations

Question

I don't understand Why the number of reflexive relations is $2^{n^2-n}$ instead of $2^n$

I thought reflexive relations are elements in form of (a,a). So I understand that there are $2^{n^2}$ Relations in total. But the reflexive ones should only be on the main diagonal right? Why are they excluding those and including only the ones that are not reflexive? The textbook didn't explain this

Answer 1

If $\{x_1, x_2, \ldots, x_n\}$ is your $n$-element set, then things get really simple when you represent a relation $R$ with a matrix $(a_{ij})$, in the sense that $(x_i, x_j) \in R$ if $a_{ij} = 1$, and $(x_i, x_j) \notin R$ if $a_{ij} = 0$.

A relation $R$ is reflexive if and only if $a_{ii} = 1$ for all $i = 1, \ldots, n$. Other $n^2 - n$ elements can be either $0$ or $1$.

$$\begin{array}{ccc} & & \begin{array}{ccc} \, x_1 & \!\! x_2 & \!\! x_3 & \!\!\cdots & x_n \end{array}\\ & \begin{array}{c} x_1\\ x_2\\ x_3 \\ \vdots \\ x_n\end{array} & \left(\begin{array}{ccccc} 1 & * & * & \cdots & *\\ * & 1 & * & \cdots & *\\ * & * & 1 & \cdots & *\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ * & * & * & \cdots & 1\\ \end{array}\right) \end{array}$$

Therefore, we make $n^2 - n$ binary choices, which amounts to $2^{n^2 - n}$ different matrices, i.e. reflexive relations.

Answer 2

Note that the number of reflexive relations is $2^{n^2-n}$.

By definition, a binary relation ~ over a set $X$ is reflexive if for all $x \in X$, we have $x$ ~ $x$.

The example give below should clear your doubt on which relations are reflexive.

Let $X=\{1,2,3,4\}$ and define binary relations $R_1,R_2$ and $R_3$ on $X$ as follows:-

$R_1=\{(1,1),(2,2),(3,3),(4,4)\}$

$R_2=\{(1,1),(2,2),(3,3),(4,4),(1,4),(2,3)\}$

$R_3=\{(1,1),(2,2),(4,4),(1,4),(2,3)\}$

Note that $R_1$ and $R_2$ are both reflexive by definition.

But $R_3$ is not reflexive since $(3,3) \notin R_3$.

From this example for your relation matrix, we observe the following:-

$(1)$ A reflexive relation may contain elements which are not on the diagonal in relation matrix.

$(2)$ If a relation does not contain a diagonal element in the relation matrix, then it can't be reflexive.

With these two facts, it is easy to calculate the number of reflexive relations.

Sketch: Fix all the diagonal entries in the $n \times n$ relation matrix. For the remaining $n^2 – n$ entries, choose whether to put the elements corresponding to these entries in your relation. In the end, the relations obtained are reflexive by definition and there are $2^{n^2-n}$ of them.