India competition problems

Fix an $n \in \mathbb{N}$. We will prove the following statement by Induction:
$P(m)$ : Every $n$-magic square with common sum $m$ can be written as a sum of $m$ permutation matrices.
For the base case, we verify that $P(1)$ is true. Since all the entries are non-negative integers, the only way possible $n$-magic squares with common sum 1 are exactly $n$-permutation matrices. Hence, every such matrix can be written as a sum of $1$ $n$-permutation matrix, i.e., itself.
For the Induction Hypothesis, assume that the statement $P(k)$ is true for some $k \in \mathbb{N}$. Hence, every $n$-magic square with common sum $k$ can be written as a sum of $k$ $n$-permutation matrices. Consider any $n$-magic square $A_0$ with common sum $k+1$. We will prove that $A_0$ can be written as a sum of an $n$-permutation matrix and an $n$-magic square $A_1$ with common sum $k$.
Consider the graph $\mathcal{G} = (\mathcal{W}, \mathcal{E})$ defined as follows. Let $R_1, R_2, \dots, R_n$ be the rows of $A_0$ and let $C_1, C_2, \dots, C_n$ be the columns of $A_0$. Consider $\mathcal{W} = \{R_1, R_2, \dots, R_n\} \cup \{C_1, C_2, \dots, C_n\}$. Each of the sets $R_i = \{R_1, R_2, \dots, R_n\}$ and $C_i = \{C_1, C_2, \dots, C_n\}$ are independent sets. For every $i, j \in \mathbb{N}_n$, $R_i, C_j$ are connected by an edge if and only if $a_{ij} > 0$, where $a_{ij}$ is the entry of $A_0$ in the $i$-th row and $j$-th column. Observe that from our definition, $\mathcal{G}$ is a bipartite graph.
Consider some $S \subseteq \mathbb{R}$. By $N(S)$, we will denote the set of vertices which are adjacent to some vertex in $S$. We will show that $|N(S)| \ge |S|$.
For every edge having an endpoint in $S$, label that edge with $a_{ij}$. Consider the 'sum' of all such edges. Clearly, for each $R_i \in S$, the edges incident with $R_i$ contribute $m$ to this total. Hence, the total sum is given by $m|S|$. Now these are edges are a subset of all edges with an endpoint in $N(S)$. Hence, if we consider a similar such sum for the set $N(S)$, we get the sum to be $m|N(S)|$. As observed before, we see that $m|S| \le m|N(S)|$. Hence, we get that $|N(S)| \ge |S|$. Since $S$ was any arbitrary subset of $\mathbb{R}$, we that this is true for all subsets of $\mathbb{R}$.
Since the hypothesis for Hall's Matching Theorem is satisfied, an application of it implies that there exists a matching in the above bipartite graph $\mathcal{G}$. Since $|\mathbb{R}| = |\mathbb{C}| = n$, we see that the matching is nothing but a bijective function $\sigma: \mathbb{N}_n \to \mathbb{N}_n$ where $\sigma(i)$ is defined to be the index of the element in $\mathbb{C}$ which is matched with $R_i$. Note that $\sigma$ can also be thought of as a permutation of $\mathbb{N}_n$. We also know that $R_i \cap C_j = \{a_{ij}\}, \forall i, j \in \mathbb{N}_n$. Since $\sigma$ is a matching, we know that $a_{i\sigma(i)} > 0$ for all $i \in \mathbb{N}_n$. Consider the permutation matrix $P_\sigma$ where each entry $p_{ij}$ is given by
$$p_{ij} = \begin{cases} 1 & \text{if } j = \sigma(i) \\ 0 & \text{if otherwise.} \end{cases} \quad \forall i, j \in \mathbb{N}_n$$
Also consider the matrix $A_1 = A_0 - P_\sigma$. Note that since $a_{i\sigma(i)} > 0, \forall i \in \mathbb{N}_n$, every entry of $A_1$ is non-negative. Also observe that since $P_\sigma$ is a permutation matrix, the sum of entries in each row and each column reduces by 1. In effect, $A_1$ is still an $n$-magic square with common sum $k-1$. This completes the inductive step. Hence by Induction, we see that the statement $P(m)$ is true for all $m \in \mathbb{N}$. The proof is now complete.