Rowspan de 0-1 Matriz

Question

Deje $A$ $n \times n$ matriz con entradas de 0 o 1 con las siguientes propiedades:

1. Cada columna tiene un valor distinto de cero de la entrada
2. Cada fila tiene un valor distinto de cero de la entrada
3. No hay filas se repiten

Es cierto que el vector $(1, \ldots, 1)$ se encuentra en el lapso de las filas de $A$?

No estoy seguro de si estoy esperando una prueba de que esto es cierto, o un ejemplo que demuestra que es falsa.

Si $n = 2$ o $3$,$\det(A) \neq 0$, así que la respuesta es sí en estos casos. Para $n = 4$, sin embargo, la matriz de \begin{bmatrix} 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} tiene las propiedades necesarias y un cero determinante. Todavía, $(1, 1, 1, 1)$ está en el intervalo de sus filas, por lo que esto no proporcione un contraejemplo.

Answer 1

¿Qué acerca de $$ A = \begin{bmatrix}0&0&1&0\\ 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 1\\ 0 & 1 & 1 & 1 \end{bmatrix}? $$

EDIT: Oh, en realidad es la transpuesta, yo no estaba leyendo que usted quiere que se encuentran en el tamaño de fila. De todos modos, la transposición satisface las condiciones antes mencionadas.

Este Octave/Matlab script podría ayudar a encontrar más ejemplos :-)

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

Realmente no comprobar la unicidad de las filas, pero se puede comprobar visualmente.

Answer 2

Si $n=3$ no es necesariamente cierto que $\det(A) \neq 0$. Por ejemplo,

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

Es cierto que el problema es de cierto en ese caso, pero el argumento es un poco más complicado. Simplemente dividir el problema en tres casos:

• una fila con 3 (trivial)
• una fila con 1 uno (con un poco de trabajo reduce el problema a $2 \times 2$ de los casos, solo tienes que tener cuidado después de la eliminación de la fila/columna no sabe ya que las filas son distintos.)
• cada fila tiene dos (sólo hay 3 posibles filas y las filas son distintos, así que usted sabe las filas hasta permutación).

Creo que se puede demostrar que $\det(A) \neq0$ si las columnas son también de a pares distintos , pero no sabemos que.