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


*

*Every column has a nonzero entry

*Every row has a nonzero entry

*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.
 A: 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.
A: 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.
