Si $N = K$ todas las filas se suman a una, y todas las columnas se suman a una, así que las matrices son las matrices doblemente estocásticas que forma un conjunto convexo conocido como el Politopo de Birkhoff . El teorema de Birkhoff-von Neumann establece que los vértices del politopo de Birkhoff son los matrices de permutación .
Una generalización más amplia del politopo de Birkhoff es la politópico de transporte en el que las columnas y filas se suman a valores arbitrarios, y dos filas (o columnas) diferentes pueden sumar a valores diferentes.
La respuesta a la nueva pregunta
Calentamiento: Un caso especial
Puede expresar sus necesidades como una ecuación matricial, por ejemplo, para la $2 \times 3$ caso $$A = \begin {pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \end {pmatrix}$$
puedes ver que cada matriz $A$ satisfacer sus condiciones debe satisfacer $$ \underbrace { \begin {pmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \end {pmatrix}}_{C} \begin {pmatrix} a_{11} \\ a_{12} \\ a_{13} \\ a_{21} \\ a_{22} \\ a_{23} \end {pmatrix} = \underbrace { \begin {pmatrix} \frac {3}{2} \\ \frac {3}{2} \\ 1 \\ 1 \\ 1 \end {pmatrix} }_{b} $$
He eliminado aquí la última fila que correspondería a la última restricción de la columna, la razón es que depende linealmente de las otras filas, y por lo tanto se satisfará si se satisfacen automáticamente las otras restricciones. Para que el resto de esto funcione, es importante que las filas de $C$ son linealmente independientes.
Quieres encontrar los vértices del simplex definidos por $$ \begin {align} Ca &= b \\ a & \geq 0 \end {align}$$
Un algoritmo que utiliza los vértices de un simplex como se define arriba es el algoritmo simplex para la programación lineal, pero en nuestro caso no tenemos una función objetivo a optimizar; sólo queremos los vértices, pero podría ser una buena fuente de inspiración a la hora de resolver este problema. Me gusta bastante Las notas de Robert Fourers sobre el algoritmo simplex .
En el contexto del algoritmo simplex, un vector $a$ que es un vértice del simplex se llama solución básica factible . La caracterización algebraica de una solución básica factible es que $a \geq 0$ (este es el factible parte) y si $i_1, \dots , i_k$ son todas las posiciones de $a$ donde $a$ no es cero, entonces las columnas $C_{i_1}, \dots C_{i_k}$ son linealmente independientes (esta es la básico parte).
Un ejemplo. De la $C$ arriba, podemos elegir las columnas 1, 2, 4 y 6, para formar $ \tilde C$ . Para que esto forme una solución básica, debemos tener $a_3 = a_5 = 0$ para que podamos eliminarlos de nuestro sistema y formar $ \tilde a$ . Entonces podemos resolver el sistema $ \tilde C \tilde a = b$ : $$ \begin {pmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end {pmatrix} \begin {pmatrix} a_{11} \\ a_{12} \\ a_{21} \\ a_{23} \end {pmatrix} = \begin {pmatrix} \frac {3}{2} \\ \frac {3}{2} \\ 1 \\ 1 \\ 1 \end {pmatrix} $$
que se convierte en un solucionador para los sistemas lineales:
$$ \begin {pmatrix} a_{11} \\ a_{12} \\ a_{21} \\ a_{23} \end {pmatrix} = \begin {pmatrix} \frac {1}{2} \\ 1 \\ \frac {1}{2} \\ 1 \end {pmatrix} \Rightarrow \begin {pmatrix} a_{11} \\ a_{12} \\ a_{13} \\ a_{21} \\ a_{22} \\ a_{23} \end {pmatrix} = \begin {pmatrix} \frac {1}{2} \\ 1 \\ 0 \\ \frac {1}{2} \\ 0 \\ 1 \end {pmatrix} $$ y esta solución es básica y factible, así que este es uno de los vértices.
Así que, ahora hemos encontrado un vértice del simplex. ¿Cómo encontramos los otros? Podemos hacerlo encontrando todos los conjuntos de columnas linealmente independientes en $C$ y asegurarse de que las soluciones son factibles. Podríamos en cambio, una vez que hayamos encontrado un vértice, hacer lo que el método simplex hace; pasar a otro vértice directamente desde otro vértice.
En el algoritmo simplex, se elige un borde para moverse a lo largo del cual aumenta (o disminuye) el valor objetivo. Como esto no es relevante para nosotros, tendremos que hacer algún tipo de búsqueda para encontrar los vértices. La forma en que uno se mueve a lo largo de un borde es tal vez un poco demasiado para entrar en detalles aquí, comprueba el enlace para las notas de arriba.
Pasé a través de los conjuntos de columnas linealmente independientes que forman un $4 \times 4$ matriz $ \tilde C$ y tiene los siguientes vértices: $$ \begin {pmatrix} \frac {1}{2} \\ 1 \\ 0 \\ \frac {1}{2} \\ 0 \\ 1 \end {pmatrix} , \begin {pmatrix} 1 \\ \frac {1}{2} \\ 0 \\ 0 \\ \frac {1}{2} \\ 1 \end {pmatrix} , \begin {pmatrix} \frac {1}{2} \\ 0 \\ 1 \\ \frac {1}{2} \\ 1 \\ 0 \end {pmatrix} , \begin {pmatrix} 1 \\ 0 \\ \frac {1}{2} \\ 0 \\ 1 \\ \frac {1}{2} \end {pmatrix} , \begin {pmatrix} 0 \\ \frac {1}{2} \\ 1 \\ 1 \\ \frac {1}{2} \\ 0 \end {pmatrix} , \begin {pmatrix} 0 \\ 1 \\ \frac {1}{2} \\ 1 \\ 0 \\ \frac {1}{2} \end {pmatrix} $$
En general
Para el general $N \times K$ matrices, la matriz $C$ es bastante fácil de construir: La primera $K$ Las filas se corresponderán con las condiciones de las filas y tendrán una secuencia de $N$ los que empiezan en la posición $K(i-1) + 1$ donde $i$ es el número de fila. El último $N$ las filas serán las condiciones de la columna, probablemente es más fácil pensar en ellas como una secuencia de matrices de identidad de tamaño $N \times N$ es decir..: $$ \begin {pmatrix} I_N & I_N & \cdots & I_N \end {pmatrix}$$ las filas siempre serán linealmente dependientes, yo Piensa en basta con quitar la última fila para que las filas sean linealmente independientes.
Hice un programa para resolver este problema en general; rápidamente se obtienen muchos vértices. Para el $3 \times 5$ en el caso de que consigas 360 vértices y para el $4 \times 5$ en el caso de que tengas 3000 vértices, así que puede que no sea una forma muy rápida de generar matrices aleatorias.
La respuesta a la pregunta original
Puede expresar sus necesidades como una ecuación matricial, por ejemplo, para la $2 \times 3$ caso $$A = \begin {pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \end {pmatrix}$$
puedes ver que cada matriz $A$ satisfacer sus condiciones debe satisfacer $$ \begin {pmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end {pmatrix} \begin {pmatrix} a_{11} \\ a_{12} \\ a_{13} \\ a_{21} \\ a_{22} \\ a_{23} \end {pmatrix} = \begin {pmatrix} \frac {2}{3} \\ \frac {2}{3} \\ 1 \\ 1 \\ 1 \end {pmatrix} $$ y este sistema en realidad no tiene solución . Podemos ver esto haciendo algunas operaciones de fila en la matriz. Restar la primera y segunda fila de la última, y luego sumar la tercera y cuarta fila. Obtienes:
$$ \begin {pmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end {pmatrix} \begin {pmatrix} a_{11} \\ a_{12} \\ a_{13} \\ a_{21} \\ a_{22} \\ a_{23} \end {pmatrix} = \begin {pmatrix} \frac {2}{3} \\ \frac {2}{3} \\ 1 \\ 1 \\ \frac {5}{3} \end {pmatrix} $$ así que la última fila exhibe la condición insatisfactoria $0 = \frac {5}{3}$ .
Y parece que en general, se obtiene algo como esto. Si sumas toda tu matriz de dos maneras, los resultados deberían ser los mismos. Dejemos que $A$ ser un $N \times K$ matriz como la que usted ha descrito. Si se suman todos los elementos se obtiene la suma de las columnas (es decir, 1) por el número de columnas ( $K$ ): $$ \sum a_{ij} = K$$ y deberías obtener la suma de la fila (es decir. $N/K$ ) multiplicado por el número de filas ( $N$ ): $$ \sum a_{ij} = N^2/K$$ que lleva a la condición necesaria $$N^2/K = K \Leftrightarrow N^2 = K^2 \Leftrightarrow N = K$$ desde $N, K > 0$ . Así que sus matrices tienen que ser cuadradas, y mi primer párrafo es la respuesta.
