4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

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

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.

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

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.