proving a transpose times its original equals to $I_n$?

Question

Let $P = [p_{ij}] \in \mathsf{M}_n (\{0,1\})$ (i.e., $p_{ij} = 0$ or $p_{ij} = 1)$ and suppose that $$ \sum_{i=1}^n p_{ij} = 1,~i=1,\dots,n $$ and $$ \sum_{j=1}^n p_{ij} = 1,~j=1,\dots,n. $$ Prove that $ P^\top P = I_n $.

I have no idea how to prove this. I always just considered that $ P^\top P = I_n $ was true so I am coming up with no idea on how do do this.

so my question how do I prove this question?

I don't know if the title is accurate, but it you have a better one feel free to change it.

Answer 1

$$ \sum_{i=1}^n p_{ij} = 1,~i=1,\dots,n $$

means each column sums to $1$, since $P$ is a binary matrix, there is exactly one $1$ in each column.

and $$ \sum_{j=1}^n p_{ij} = 1,~j=1,\dots,n. $$

means each row sum to $1$, similarly, there is exactly one $1$ in each row.

Hence $P$ is a permutation matrix.

Hence $P^T=P^{-1}$.

Answer 2

The product $PP^T$ has it's $(i,j)$th entry as $\sum_{k=1}^n P_{ik}P^T_{kj} = \sum_{k=1}^n P_{ik}P_{jk}$.

Now, note that there is precisely one $k_i$ for which $P_{ik_i} \neq 0$. If $j \neq i$, then naturally the product will be zero, since $k_i \neq k_j$, otherwise the vector containing $(i,j)$ and $(i,k)$ would have sum greater than $1$.

If $i = j$, then the above sum is clearly $1$, since the sum is just $\sum_{k=1}^n P_{ik}^2 = 1$.

Hence, the entries are $1$ if $i=j$, and $0$ otherwise. This is clearly a description of the identity matrix.