Let $n$ be a fixed positive integer. I would like to know for what values of $k$ there exists an $n$ by $n$ $0/1$ matrix that is non-singular with exactly $k$ ones per row.

Clearly if $k=1$ then the identity matrix is non-singular. Also if $k=n$ there are no non-singular matrices.

What can one say about $1 < k < n$?

If $n$ is large, is it true for almost all $k$ in the range?

  • 1
    $\begingroup$ For $k = 2$, $n\ge 3$, consider the matrix $M^{(n)}_e$ given by $$M^{(n)}_e = \left[\begin{array}{ccccccc}1 & 1 & 0 & 0 & \cdots & 0 &0\\ 0 & 1 & 1 & 0 & \cdots & 0 & 0\\ 0 & 0 & 1 & 1 & \cdots & 0 &0\\ & & & \vdots & & \\ e & 1-e &0 & 0 &\cdots & 0 & 1\end{array}\right]$$ When $e = 0,1$, $M_e$ will be of the desired form. When $n$ is odd, $M^{(n)}_1$ is nonsingular, and when $n$ is even, $M^{(n)}_0$ is nonsingular (as can be seen by cofactor expansion on the last row). Maybe this technique can be generalized to other $k$ (with some bound $n \ge n_k$)? $\endgroup$ – Strants Dec 12 '15 at 21:49

I edited my answer because this new proof is much simpler.

Thm: For every $k<n$ there is a non singular $(0,1)-$matrix of order $n$ with exactly $k$ ones on each row.

Proof: If the order is two, consider the identity. Assume the result is true for matrices with order $n-1$.

Now if $k<n-1$, by induction hypothesis, we can find $(0,1)-$matrix $A$ with exactly $k$ ones per row of order $n-1$.

Let $B$ be a matrix of order $n$ defined by

$B=\left[\begin{array}{cc}A_{n-1\times n-1} & 0_{n-1\times 1} \\ u_{1\times n-1} & 1_{1 \times 1} \end{array}\right]$, where $u$ is any $(0,1)$ vector with $k-1$ ones.

Notice that $\det(B)=\det(A)\neq 0$.

If $k=n-1$ consider the matrix of order $n$ with diagonal equal to zero and the other entries equal to 1. $\square$

  • $\begingroup$ Thank you! This is a great answer. $\endgroup$ – dorothy Dec 13 '15 at 5:56

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.