1
$\begingroup$

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.

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

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!$$

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.