\section*{5. For ALL APPLICANTS.}
An $n \times n$ square array contains 0 s and 1 s. Such a square is given below with $n = 3$.

\begin{center}
\begin{tabular}{ l l l }
0 & 0 & 1 \\
1 & 0 & 0 \\
1 & 1 & 0 \\
\end{tabular}
\end{center}

Two types of operation $C$ and $R$ may be performed on such an array.

\begin{itemize}
  \item The first operation $C$ takes the first and second columns (on the left) and replaces them with a single column by comparing the two elements in each row as follows; if the two elements are the same the $C$ replaces them with a 1 , and if they differ $C$ replaces them with a 0 .
  \item The second operation $R$ takes the first and second rows (from the top) and replaces them with a single row by comparing the two elements in each column as follows; if the two elements are the same the $R$ replaces them with a 1 , and if they differ $R$ replaces them with a 0 .
\end{itemize}

By way of example, the effects of performing $R$ then $C$ on the square above are given below.

$$\begin{array} { c c c } 
0 & 0 & 1 \\
1 & 0 & 0 \\
1 & 1 & 0
\end{array} \xrightarrow { R } \begin{array} { c c c } 
0 & 1 & 0 \\
1 & 1 & 0
\end{array} \xrightarrow { C } \begin{array} { c c } 
0 & 0 \\
1 & 0
\end{array}$$

(a) If $R$ then $C$ are performed on a $2 \times 2$ array then only a single number ( 0 or 1 ) remains.\\
(i) Write down in the grids on the next page the eight $2 \times 2$ arrays which, when $R$ then $C$ are performed, produce a 1 .\\
(ii) By grouping your answers accordingly, show that if $\begin{array} { l l } a & b \\ c & d \end{array}$ is amongst your answers to part (i) then so is $\begin{array} { l l } a & c \\ b & d \end{array}$.\\
Explain why this means that doing $R$ then $C$ on a $2 \times 2$ array produces the same answer as doing $C$ first then $R$.\\
(b) Consider now a $n \times n$ square array containing 0 s and 1 s , and the effects of performing $R$ then $C$ or $C$ then $R$ on the square.\\
(i) Explain why the effect on the right $n - 2$ columns is the same whether the order is $R$ then $C$ or $C$ then $R$. [This then also applies to the bottom $n - 2$ rows.]\\
(ii) Deduce that performing $R$ then $C$ on an $n \times n$ square produces the same result as performing $C$ then $R$.\\
\includegraphics[max width=\textwidth, alt={}, center]{43f3ba53-7486-4997-ada9-58d9009d4293-15_202_204_413_452}\\
\includegraphics[max width=\textwidth, alt={}, center]{43f3ba53-7486-4997-ada9-58d9009d4293-15_204_204_708_452}\\
\includegraphics[max width=\textwidth, alt={}, center]{43f3ba53-7486-4997-ada9-58d9009d4293-15_204_204_411_790}\\
\includegraphics[max width=\textwidth, alt={}, center]{43f3ba53-7486-4997-ada9-58d9009d4293-15_204_204_708_790}\\
\includegraphics[max width=\textwidth, alt={}, center]{43f3ba53-7486-4997-ada9-58d9009d4293-15_204_204_411_1128}\\
\includegraphics[max width=\textwidth, alt={}, center]{43f3ba53-7486-4997-ada9-58d9009d4293-15_204_204_708_1128}\\
\includegraphics[max width=\textwidth, alt={}, center]{43f3ba53-7486-4997-ada9-58d9009d4293-15_202_200_413_1466}\\
\includegraphics[max width=\textwidth, alt={}, center]{43f3ba53-7486-4997-ada9-58d9009d4293-15_202_204_708_1466}