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

1 Answer 1

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$
4
  • $\begingroup$ Please explain how it's a derangement $\endgroup$
    – Archer
    Commented Apr 3, 2019 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
    Commented Apr 3, 2019 at 8:47
  • $\begingroup$ How does that ensure that only one 1 is there in each row and column $\endgroup$
    – Archer
    Commented Apr 3, 2019 at 9:46
  • $\begingroup$ The only one in row 1 is $a_{1a}$. The only one in column $a$ is $a_{1a}$. $\endgroup$
    – Empy2
    Commented Apr 3, 2019 at 9:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .