# Counting the number of matrices

Kindly help me solve this question.

Let $$S=\left\{A=[a_{ij}]_{5\times 5}\;\middle\vert\;\begin{array}{c} a_{ij}=0\text{ or }1\forall i,j,\\ \textstyle\sum_j a_{ij}=1\forall i,\\ \text{ and }\textstyle\sum_ia_{ij}=1\forall j \end{array}\right\}.$$ Then what is the the number of elements in $S$?

a) $5^2$
b) $5^5$
c) $5!$
d) $55$

My first problem is that I am unable to understand the summation part. I wish somebody could help.

• Are $5^2$, $5^5$, $5!$, and $55$ intended to be multiple choice options? – Zev Chonoles Aug 14 '13 at 6:59
• ya, I'll make it explicit in question. – Ramit Aug 14 '13 at 7:00

The sum of each row and each column is one, meaning that we only have $n=5$ ones, and all the rest zeroes. Choose the first $1$ anywhere in the first row (5 choices), the $1$ in the second row only has four options etc. This leads to $$|S| = 5!$$
Addressing the summation conditions: The number $a_{ij}$ is the entry in the $i^{\text{th}}$ row and $j^{\text{th}}$ column of $A$, so $\sum_{j}a_{ij}$ means the sum over all possible values of $j$ (i.e. $j = 1, 2, 3, 4, 5$) of $a_{ij}$ is $1$. So if you add the entry in the $i^{\text{th}}$ row and first column, to the entry in the $i^{\text{th}}$ row and second column, to the entry in the $i^{\text{th}}$ row and third column, to the entry in the $i^{\text{th}}$ row and fourth column, to the entry in the $i^{\text{th}}$ row and fifth column, you would get one. That is, if you add up all of the entries of the $i^{\text{th}}$ row, you get $1$, and this is true for all possible values of $i$ (i.e. $i = 1, 2, 3, 4, 5$); said differently, for all possible rows.
There is an analogous interpretation for the condition $\sum_i a_{ij} = 1$.