GATE CS 2021 Set 2 Q11 — Sets, Relations and Functions

To determine the relationship between the sets $S_1$ and $S_2$, let us find their cardinalities.

1. Cardinality of $S_1$

The set $S_1$ consists of all $n \times n$ matrices with entries from the set $\{a, b, c\}$.

• An $n \times n$ matrix has exactly $n^2$ positions.
• Each position can be filled with any of the $3$ elements from $\{a, b, c\}$.

Therefore, the total number of such matrices is: $$|S_1| = 3^{n^2}$$

2. Cardinality of $S_2$

The set $S_2$ consists of all functions from the domain $D = \{0, 1, 2, \dots, n^2-1\}$ to the codomain $C = \{0, 1, 2\}$.

• The size of the domain is $|D| = n^2$.
• The size of the codomain is $|C| = 3$.

The total number of functions from $D$ to $C$ is: $$|S_2| = |C|^{|D|} = 3^{n^2}$$

Conclusion

Since both $S_1$ and $S_2$ are finite sets and have the exact same cardinality ($|S_1| = |S_2| = 3^{n^2}$), there exists a bijection between them.

• Since a bijection is always a surjection, there exists a surjection from $S_1$ to $S_2$ (Option B is correct).
• There exists a bijection from $S_1$ to $S_2$ (Option C is correct).
• Options A and D are incorrect because a bijection (and hence an injection) does exist.