Question

Use Mathematical Induction to show that if MR is the bit matrix representing the relation R, then M^[n]R is the matrix representing R^n. (This was how the question was stated. If you're confused about the terms M^[n]R and R^n, they aren't exponentials, the [n] in the first term is meant to be a superscript and the R a subscript. The n in the second term is a superscript.)

Answer 1

If $R$ is a binary relation on a finite set $A$ , that is $R ⊆ A×A$, then $R$ can be represented by the logical matrix $M_R$ whose row and column indices index the elements of $A$ such that the entries of $M_R$ are defined by:

${\displaystyle m_{i,j}={\begin{cases}1&(x_{i},y_{j})\in R\\0&(x_{i},y_{j})\not \in R\end{cases}}}$

Since $R$ be a symmetric relation on a finite set $A$, $(x,y)\in R$ implies $(y,x)\in R$, and therefore $m_{i,j}=1$ if and only if $m_{j,i}=1$. It follows that $M_R$ is necessarily a symmetric matrix.