GATE CSE 2021 Set 2 Q21: Bijection between n×n matrices over {a,b,c} and functions

Consider the following sets, where $n \geq 2$ :

$S_1$ : Set of all $n \times n$ matrices with entries from the set $\{a, b, c\}$

$S_2$ : Set of all functions from the set $\{0, 1, 2, \ldots, n^2 - 1\}$ to the set $\{0, 1, 2\}$

Which of the following choice(s) is/are correct?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: B, C (official GATE 2021 final answer key)

Concept used: Finite sets of equal size have bijections (hence surjections and injections) between them.

First step: Count both sets: $|S_1| = 3^{n^2}$ (a choice for each of $n^2$ cells) and $|S_2| = 3^{n^2}$ (a value for each of $n^2$ inputs).

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key