4

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.

Hans Parshall
  • 6,246

2 Answers2

3

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.

Algebraic Pavel
  • 22,928
2

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.

N. S.
  • 132,525