# Binary matrices with rank $n$

I'm stuck doing this problem

Let $A$ be a matrix of order $n \times n$ with entries in $\{0,1\}$, which has exactly two $1$'s on each row and on each column. Which conditions are necessary and sufficient to make $\mbox{rank} (A) = n$?

and the only things I got are that:

• The determinant of $A$ must be non-zero (equivalent to saying that the columns mustn't repeat or be linearly dependent)
• If the column vector $(a_1\ a_2\ \dots \ a_n)^T$ with $1$'s in the entries $a_i,a_j$ with $i-j$ odd, the vectors $(0\ 0\ 1 \ 1\dots 0)^T$ with $1$'s in $a_m$ and $a_{m+1}$ ($i \leq m < j$).

But I can't see more to solve it. Anyone can tell me how to solve it?

Edit:

The last condition is only valid for matrices with $n$ even.

• The range couldn't be a single integer $n$, because 0 would be there too. Do you mean something else?? – rschwieb Jun 22 '16 at 1:29
• You're right. A mistake. (Python user) – iam_agf Jun 22 '16 at 1:30
• And "in 0,1" is talking about the field of two elements? Or integers ? – rschwieb Jun 22 '16 at 1:31
• @rschwieb Integers. – iam_agf Jun 22 '16 at 1:31
• I think that a circulant matrix would work, but I have to pull out a pencil and paper to check. Let me try this out when I'm home in a few minutes. – Chris Harshaw Jun 22 '16 at 1:34

Thm: If A is a matrix of order n with entries in ${0,1}$, which has exactly two 1's on each row and on each column then $A=P_1+P_2$, where $P_i\ (i =1,2)$ is a permutation matrix.
Proof of thm: Since each row and column of $A$ has exactly two 1's, choose one 1 on each column and row in order to obtain a permutation $P_1$. Notice that $A-P_1$ has exactly one 1 on each row and column, so $A-P_1=P_2$ is a permutation matrix. $\square$
Now, $P_1+P_2$ is invertible iff $-1$ is not an eigenvalue of $P_1^{-1}P_2$. Notice that $P_1^{-1}P_2$ is also a permutation matrix. Thus, $P_1+P_2$ is invertible iff $P_1+P_2=P_1(I+P_3)$, where $P_3$ is a permutation matrix such that $-1$ is not an eigenvalue of $P_3$.