Supongamos que $A$ es un $m\times n$ matriz y $b$ es un $m\times 1$ vector (donde $m,n\geq 3$ ) tal que cada uno de los vectores columna de $A$ y el vector $b$ tiene una entrada igual a $1$ otra entrada igual a $-1$ y el resto de las entradas son cero.
Ahora bien, si el sistema $Ax=b$ tiene una solución ( donde $x$ es $n\times 1$ ) entonces siempre existe una solución $x$ tal que cada una de las entradas de $x$ son $1,-1$ o $0$ ? Si no es en general, ¿es cierto cuando el rango de $A$ es $m-1$ ?
Cualquier $A$ puede verse como la matriz de incidencia de un grafo dirigido. Si el rango es menor que $m-1$ entonces el gráfico correspondiente sólo tendrá más de una componente conectada.
El sistema $Ax=b$ puede verse como $b$ cantidad de flujo que se inyecta en los nodos y $x$ es entonces un flujo válido a lo largo de las aristas que satisface la conservación del flujo en cada nodo. Se puede demostrar que $Ax=b$ tiene solución si los valores de $b$ correspondientes a cada componente conectado suman cero.
Su exigencia de que debe existir una solución con sólo $1$ , $-1$ y $0$ no siempre es cierto para la arbitrariedad $b$ . Pero para su caso particular, puede ver que existe una solución para $Ax=b$ si los nodos correspondientes a $1$ y $-1$ en $b$ están en el mismo componente conectado. Y si están en el mismo componente conectado, podemos encontrar un camino (ignorando las direcciones) entre esos dos nodos y enviar un flujo unitario a lo largo de este camino. Esto da una solución $x$ con sólo $1$ , $-1$ y $0$ .
Esto se puede ampliar a un nivel más general $b$ también, con algunas condiciones sobre el corte mínimo del gráfico.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
