Para una matriz $X$ de rango $r$ Llamaré al lado derecho de $$X = a_1b_1^T + \dots + a_rb_r^T$$ a $decomposition$ de $X$ . Llamaré $a_ib_i^T$ a término en la descomposición.
Cualquier matriz de rango 1 será una matriz donde a submatriz se compone enteramente de unos y el resto de las entradas son ceros. Una submatriz $B'$ de la matriz $B$ es una matriz en la que elegimos algunas columnas y algunas filas. Por ejemplo, para la matriz $$B = \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 \end{pmatrix}$$ la submatriz $B'$ formado por las filas 1 y 3 y las columnas 2 y 3 es: $$B ' = \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}.$$
Puedes reformular tu problema a otros problemas:
Reformular a un problema de conjunto
Esto se puede reformular a un problema de conjunto. Dado un $M \times N$ matriz binaria $B$ tu universo $U$ es el conjunto de índices $(1,1), (1, 2), \dots, (M,N)$ y tienes un conjunto $\mathfrak B \subseteq U$ formado por los índices donde $B$ es distinto de cero: $$\mathfrak B = \{ (i,j) : B_{ij} = 1 \}$$ Tienes una colección de conjuntos $\mathcal R_1$ donde cada $R \in \mathcal R_1$ corresponde a una matriz de rango 1, el conjunto $R$ formado por los índices en los que la matriz es distinta de cero.
Así que, entonces tu problema es encontrar un mínimo $\mathcal C \subset R$ tal que la unión de todos los conjuntos en $\mathcal C$ es igual a $\mathfrak B$ es decir, el $\mathcal C$ con el tamaño más pequeño $| C |$ tal que $$\bigcup_{C \in \mathcal C} C = \mathfrak B.$$ Esto, creo, es un caso especial de la problema de la base del conjunto .
Reformular a un problema gráfico
También puede, dada una $M \times N$ matriz binaria $B$ Construir un gráfico bipartito $G_B$ formado por dos conjuntos de vértices $V_1, V_2$ de tamaño $M, N$ respectivamente, con un borde entre $v_i \in V_1$ y $w_j \in V_2$ si $B_{ij} = 1$ es decir, los elementos de $V_1$ corresponden a los números de fila y los elementos de $V_2$ corresponden a los números de las columnas.
El rango es entonces el menor número de subgrafos bipartitos completos necesarios para cubrir $G_B$ algo que se conoce como el dimensión bipartita de $G_B$ .
Esto se puede ver considerando a qué corresponde un subgrafo bipartito completo: Digamos que el subgrafo bipartito completo está formado por los conjuntos de vértices $A, B$ . Como el subgrafo es bipartito completo, hay una arista entre cada $a \in A$ y cada $b \in B$ . Esto corresponde a una submatriz llena de unos.
Comentarios
Tanto el problema de decisión para la formulación de conjuntos como el problema de decisión para la formulación de grafos son NP-completos.
Un problema estrechamente relacionado, cómo acercarse a una matriz binaria dada $B$ como sea posible con un número restringido de términos en su descomposición, se estudia en el artículo El problema de la base discreta de Miettinen, Mielikäinen, Gionis, Das y Mannila.
Un límite superior para el rango
Si $B$ es un $M \times N$ matriz booleana, vemos que nunca necesitaremos más de $mn$ términos para descomponerlo. Podemos ver esto utilizando la base estándar. Sea $e_i^n$ sea el $n$ -vector de dimensiones con un uno en la posición $i$ , ceros en otros lugares. Entonces $e_i^n (e_j^m)^T$ es el $n \times m$ matriz booleana en la posición $(i,j)$ . Por lo tanto, siempre podemos descomponer $B$ como $$B = \sum_{i = 1}^N \sum_{j = 1}^M \alpha_{ij} e_i^N (e_j^M)^T$$ donde $\alpha_{ij}$ es cero o uno. Podemos simplificar esto escribiendo: $$B = \sum_{j = 1}^M \left( \sum_{i=1}^N \alpha_{ij} e_i^N \right)(e_j^m)^T$$ que es $B$ expresado como una suma de $M$ matrices de rango uno. Nótese que también podemos tener la $i$ -como la suma externa, por lo que obtenemos que $$\operatorname{rank}(B) \leq \min \{N, M\}.$$
