# Rowspan of 0-1 Matrix

Let $A$ be an $n \times n$ matrix with entries 0 or 1 with the following properties:

1. Every column has a nonzero entry
2. Every row has a nonzero entry
3. No rows are repeated

Is it true that the vector $(1, \ldots, 1)$ lies in the span of the rows of $A$?

I'm unsure if I'm expecting a proof that this is true, or an example that shows that it's false.

If $n = 2$ or $3$, then $\det(A) \neq 0$, so the answer is yes in these cases. For $n = 4$, however, the matrix \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} has the required properties and a zero determinant. Still, $(1, 1, 1, 1)$ is in the span of its rows, so this doesn't provide a counterexample.

What about $$A = \begin{bmatrix}0&0&1&0\\ 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 1 \end{bmatrix}?$$

EDIT: Oh actually it's the transpose, I was not reading that you want it to lie in the row span. Anyway, the transpose satisfies the aforementioned conditions too.

This Octave/Matlab script could help to find more examples :-)

n = 4;
rho = 0.5;

e = ones(n, 1);

for k = 1 : 10
A = full(double(sprand(n,n,rho) ~= 0));
if all(A * e) & all(A' * e)
x = pinv(A') * e;
f = A' * x;
residual = f - e;
if norm(residual) > 1e-8
fprintf('found one!!!\n');
fprintf('this should be vector of ones:\n');
disp(f);
fprintf('least squares solution:\n');
disp(x);
break;
end
end
end


It actually does not check for uniqueness of the rows but it can be checked visually.

• This seems to settle that the answer is no, thanks. – Hans Parshall Oct 4 '13 at 13:33

If $n=3$ it is not necessarily true that $\det(A) \neq 0$. For example,

$$A = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \\ \end{bmatrix}$$

It is true that the problem is true in that case, but the argument is a little more complicated. Just split the problem in three cases:

• a row with 3 ones (trivial)
• a row with 1 one (with a little work reduces the problem to $2 \times 2$ case, just be careful after removing that row/column you don't know anymore that the rows are distinct.)
• every row has two ones (there are only 3 possible rows, and the rows are distinct, so you know the rows up to permutation).

I think you can prove that $\det(A) \neq0$ if the columns are also pairwise distinct , but you don't know that.

• Sure, good point. I wasn't considering the trivial case. – Hans Parshall Oct 3 '13 at 21:48