India_2017

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{array}{ll}1& \text{if }j=\sigma (i)\\ 0& \text{if otherwise.}\end{array}\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.