TIFR CSE 2023 | Part A | Question: 15

Question

Consider the $n \times n$ matrix $M$ defined as follows:
$$M=\left(\begin{array}{cccc}
1 & 2 & \ldots & n \\
n+1 & n+2 & \ldots & 2 n \\
2 n+1 & 2 n+2 & \ldots & 3 n \\
\vdots & \vdots & \ldots & \vdots \\
(n-1) n+1 & (n-1) n+2 & \ldots & n^{2}
\end{array}\right).$$
Let $M_{i, j}$ denote the entry present in the $i$-th row and the $j$-th column of $M$ for each $1 \leq i, j \leq n$. Define a set $S$ as
\[
S=\left\{M_{i_{1}, j_{1}}+M_{i_{2}, j_{2}}+\cdots+M_{i_{n}, j_{n}} \mid\left(i_{1}, \ldots, i_{n}\right) \text { and }\left(j_{1}, \ldots, j_{n}\right)\right.
\]
are permutations of $[n]\}$.

(Here, $[n]$ denotes the set $\{1,2, \ldots, n\}$ of positive integers from $1$ to $n.)$ How many elements does $S$ have?

• A. $1$
• B. $\left(\begin{array}{l}n \\ 2\end{array}\right)$
• C. $n$ !
• D. $(n !)^{2}$
• E. $n$

Answer 1

Given definition $S = \{ M_{i_1,j_1} + M_{i_2,j_2} + … + M_{i_n,j_n} \: | \: (i_1,…,i_n) \text{ and } (j_1, …, j_n) \text{ are permutations of } [n] \} $

$\implies (1)$ Each element of $S$ is sum of $n$ terms, such that NO two terms belong to the same row or column of Matrix $M$.

Now each element of the Matrix $M$ can be broken into two parts – (a) $n$ part and (b) constant part.

Example – $M_{1,1} = 1 = 0n + 1 \implies$ (a) $n$ part is $0n$ and (b) constant part is $1$.

$M_{n, 2} = 1 = (n-1)n + 2 \implies$ (a) $n$ part is $(n-1)n$ and (b) constant part is $2$.

Now observe $(2)$ constant part of each column of Matrix $M$ is same and $n$ part of each row of Matrix $M$ is same.

From $(1) \text{ and } (2)$, we can conclude that all the summation

$M_{i_1,j_1} + M_{i_2,j_2} + … + M_{i_n,j_n} \text{ such that } (i_1,…,i_n) \text{ and } (j_1, …, j_n) \text{ are permutations of } [n]$

are same and they are equal to summation of all constant parts plus summation of all $n$ parts.

Element of $S = \sum_{i=0}^{(n-1)} i \times n + \sum_{i=1}^n i = n * \frac{(n)(n-1)}{2} + \frac{n(n+1)}{2} = \frac{n}{2} * \{ n^2-n + n + 1 \} = \frac{n}{2} * (n^2 + 1)$

Therefore, $S = \{ \frac{n}{2} * (n^2 + 1) \} $

Answer :- A