3
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ The range couldn't be a single integer $n$, because 0 would be there too. Do you mean something else?? $\endgroup$ – rschwieb Jun 22 '16 at 1:29
  • $\begingroup$ You're right. A mistake. (Python user) $\endgroup$ – iam_agf Jun 22 '16 at 1:30
  • $\begingroup$ And "in 0,1" is talking about the field of two elements? Or integers ? $\endgroup$ – rschwieb Jun 22 '16 at 1:31
  • $\begingroup$ @rschwieb Integers. $\endgroup$ – iam_agf Jun 22 '16 at 1:31
  • $\begingroup$ 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. $\endgroup$ – Chris Harshaw Jun 22 '16 at 1:34
0
$\begingroup$

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

$\endgroup$

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.