Exercise 1620Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Counting with matrices

#matrices#counting#trace

Statement

Count the $n\times n$ $0$ - $1$ matrices with exactly one $1$ in each row and each column. How many are symmetric?

Hint

Such matrices correspond to permutations. Symmetry means the permutation is an involution.

Show solutionHide solution

Solution

Total. Each matrix corresponds to a permutation: $n!$ .

Symmetric. Symmetric permutation matrices correspond to involutions (permutations with cycle lengths $1$ or $2$ ). The number of involutions $I_n$ satisfies $I_n=I_{n-1}+(n-1)I_{n-2}$ (element $n$ fixed or in a transposition).

Conclusion. $n!$ total; the symmetric count is $I_n$ (involution numbers).

Counting with matrices

Statement

Solution

More problems in Counting principles