4
$\begingroup$

Consider a square matrix of order $n = 5$ such that $a_{ij} = 0 ~ \forall ~ i+j = n+1; a_{ij} \in \{0,1\}$. In each row as well as in each column there is only one non zero element. Then number of such matrices is?

First we note that right diagonal has only $0$s.

Then I tried it this way: We choose a place for one among each row and mark the other places in that column and same row as forbidden (i.e. no more one's).

So for first column we have 4 choices then 3 choices then 2 then 1 and then 2s.

Thus, Number of ways = $4\times 3 \times 2\times 1\times 2 = 48$

But its erroneous because the number of choices change if we place 1 above 0 in each attempt.

What's the correct way to solve this question?

Answer given is:

44

$\endgroup$
1
$\begingroup$

Flip the array uoside down. Then $a_{ii}=0$, so the positions of the nonzero $a_{ij}$ form a derangement of the numbers from $1$ to $5$.

$\endgroup$
  • $\begingroup$ Please explain how it's a derangement $\endgroup$ – Abcd Apr 3 at 8:43
  • $\begingroup$ Suppose the nonzero cells are $a_{1a},a_{2b},a_{3c},a_{4d}$ and $a_{5e}$. Then $a,b,c,d,e$ are five different numbers, and $1\neq a,2\neq b,3\neq c,4\neq d,5\neq e$. $\endgroup$ – Empy2 Apr 3 at 8:47
  • $\begingroup$ How does that ensure that only one 1 is there in each row and column $\endgroup$ – Abcd Apr 3 at 9:46
  • $\begingroup$ The only one in row 1 is $a_{1a}$. The only one in column $a$ is $a_{1a}$. $\endgroup$ – Empy2 Apr 3 at 9:49

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.