5

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
    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$)?

     –  Dec 12 '15 at 21:49

1 Answers1

3

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$

Daniel
  • 5,872