What is the determinant of a binary matrix with exactly two ones in each row and column?

775 Views Asked by At

Consider a binary matrix $A \in \{0,1\}^{n \times n}$. If it has exactly one $1$ in each row and column, is is called a permutation matrix and its determinant is $\pm 1$. What if I have a binary matrix with exactly two ones in each row and column? What is its determinant?

2

There are 2 best solutions below

0
On

(Playing at 4am)

If 2x2, 0.

If 3x3, $ 1 1 0\\ 1 0 1\\ 0 1 1 $ is -2.

An expansion by minors should help, but I can't think clearly now.

1
On

The $1$s form loops in the matrix. Start with any $1$, go to the other $1$ in the same row, then the other $1$ in the same column, then same row, and so on.

Suppose they form one loop. Then expanding along any row, it can be seen the determinant will be $\pm1\pm1$. I think, it will be $0$ if there is an even number of rows, and $\pm2$ if there is an odd number.

Suppose they form several loops. The determinant of the combination is the product of the $0$ and $\pm2$ from each individual loop.

So I think it will be $\pm2^k$, where $n$ can be written as the sum of $k$ odd numbers (each $3$ or more) and no even numbers; or it may be $0$.