15 votos

Extremal pregunta sobre matrices

La siguiente pregunta fue planteada a mí hace un tiempo. No conozco una manera satisfactoria (o incluso un completo) prueba:

Supongamos que $M$ $n$ x $n$ matriz de enteros no negativos. Además, suponga que si una coordenada de $M$ es cero, entonces la suma de las entradas en su fila y su columna es, al menos,$n$.

¿Cuál es la menor que la suma de todas las entradas en $M$ puede ser?

La conjetura de que se me planteó fue que se trataba de $\frac{n^2}{2}$ que se obtiene por la matriz diagonal con $\frac{n}{2}$ en todas las entradas de la diagonal.

[Supongo que debe haber un "supongamos que" en la descripción de M. -- GJK]

47voto

Nikos Steiakakis Puntos 2651

El siguiente parece demasiado simple, así que tal vez hay un error, pero aquí va.

Deje $m$ ser la más pequeña entre todas las sumas de fila y columna de sumas. Si $m\geq n/2$, hemos terminado.

De lo contrario, $m=cn$$c\lt 1/2$. Supongamos que se trata de una columna que tiene suma $m$. Esta columna tiene al menos $n-m$ ceros, y cada una de las correspondientes en las filas de la suma de $\geq n-m$. El resto de los $m$ filas, cada una tiene suma $\geq m$.

En total tenemos una suma de al menos $(n-m)^2+m^2 = ((1-c)^2+c^2)n^2$. Por último, tenga en cuenta que $(1-c)^2+c^2\gt 1/2$ al $c\lt 1/2$.

Así que esto le da un límite inferior de $n^2/2$, y la igualdad requiere que cualquier fila y de una columna de sumas exactamente $n/2$, por lo que la matriz es una suma de $n/2$ permutación de las matrices del Teorema de König.

Ahora lo que sobre el caso al $n$ es impar?

Edit: Ya que la suma es un número entero, el límite inferior $n^2/2$ da $(n^2+1)/2$, que se puede lograr, por ejemplo, tomando la suma directa de una $m\times m$ matriz de $1$s con $(n-m)\times (n-m)$ matriz de $1$ donde $m=(n-1)/2$. Al $n$ es raro, esta es la única extremal ejemplo hasta la columna y la fila de permutaciones. Aquí es una prueba.

Deje $m$ ahora, originalmente, denota el mínimo sobre todos los de la fila y la columna de sumas. Si $m\geq (n+1)/2$, el total de la suma es demasiado grande: al menos $nm\geq n(n+1)/2$. Por lo tanto, $m\leq(n-1)/2$, y el $(n-m)^2+m^2$ límite inferior ahora da una suma total de, al menos, $(n-n(n-1)/2)^2+((n-1)/2)^2 = (n^2+1)/2$ (utilizando el hecho de que $(1-c)^2+c^2$ es decreciente cuando se $c\lt 1/2$). Así que hasta ahora sólo hemos volvió a deducir el límite inferior de $n$ impar.

Sin embargo, si la igualdad ocupa, tenemos que $m=(n-1)/2$, que en cada fila se agrega hasta $m$ ($m$ veces) o $n-m$ ($n-m$ veces), y que en una columna que se suma a $m$, hay exactamente $n-m$ $0$s, por lo que todas las entradas se $0$ o $1$ (y declaraciones similares con columnas y filas intercambiados). Por permuting las filas y columnas podemos suponer que la primera $m$ filas [columnas] cada agregar a a $m$.No puede haber un $0$ en la parte superior izquierda $m\times m$ submatriz, desde entonces, la suma de la fila y la columna que contiene la $0$ se suma a sólo $2m\lt n$. Hemos encontrado una suma directa de una $m\times m$ e una $(n-m)\times(n-m)$ $1$ matriz.

5voto

skfd Puntos 463

De nuevo, muy buena pregunta!

Edit: puedo obtener un límite inferior de $\frac{3 - \sqrt{5}}{2} n^2$ como sigue: Set $c = \frac{3 - \sqrt{5}}{2}$ por la concisión. Asignar un (no necesariamente simple) gráfico bipartito a $M$ en la forma obvia. Ahora bien, si la suma de algunos de fila es menor que $cn$, debe haber al menos $(1-c)n$ vértices en el otro partita conjunto de la gráfica que no son adyacentes a la correspondiente vértice, que por lo tanto debe cada uno tienen un grado mínimo de $(1-c)n$ total grado, al menos,$(1-c)^2n^2 \geq cn^2$.

Desafortunadamente c es sólo acerca de 0.38, y ese es el mayor constante de este argumento nos puede dar. Pero tal vez puede ser modificado un poco para darnos 0.5.

Edit 2: Este problema realmente contraataca! Estoy empezando a pensar que hay algún tipo de dicotomía en juego aquí, para que podamos acabar necesidad de algún tipo de estructura teorema... yo he pensado de esta manera, más de lo que debería, y todavía no he conseguido mejorar sensiblemente la anterior encadenado (en realidad creo que tengo la constante a a $\frac{3 - \sqrt{2}}{2}$, que es un poquito debajo de 0.4, por un argumento similar) pero creo que un registro de lo que he tratado de que podría ser útil.

  1. Mi plan original de ataque fue el uso de la existencia de un vértice de grado < n/2 para realizar algunas inteligente contando argumento que muestra que hay por lo menos $n^2/2$ bordes. Por supuesto, no hay ninguna garantía de que esto no iba a funcionar, pero parece que tienes que ser muy cuidadoso con el recuento: la inconexión de la unión completa de la grafos bipartitos $K_{m-1, m-1}$ $K_{m+1, m+1}$ satisface la propiedad deseada y tiene el máximo número permitido de bajo grado de los vértices, pero sólo ha $n^2/2 + 2$ bordes! No es claro para mí cómo construir un recuento de argumento que puede manejar la situación anterior y más "típico" en el que los vértices tienen una amplia gama de grados, por lo que este enfoque se puso al lado.

  2. Sin embargo, no puede ser una solución: que en realidad no tiene que demostrar que $n^2/2$ es un límite inferior! De hecho, si nos puede mostrar un límite inferior de la forma $(0.5-o(1))n^2$ entonces, el obligado de la siguiente manera. Por qué? Porque si tenemos una matriz con la propiedad deseada y la densidad de menos de 1/2, podríamos meter un montón de copias de la misma para obtener arbitrariamente grandes matrices con la misma densidad. Esto significa que podemos sacrificio, por ejemplo, O(n) los factores que en nuestra recuento de los argumentos.

  3. Por cierto, aquí una dicotomía que creo que podría tener una oportunidad de conducir a una prueba. Considere la posibilidad de un multigraph con la propiedad deseada; sea G denotar el bipartito complemento de su subyacente simple gráfico. Si G tiene un "gran" matching, es decir, una de tamaño n-o(n), obtenemos nuestra débil límite inferior por un simple recuento de argumento. Si G no tiene gran coincidencia, entonces tal vez podemos utilizar esta propiedad para forzar algún tipo de estructura en el original multigraph, lo cual muestra que tiene una densidad de al menos 1/2.

4voto

ninegrid Puntos 213

[Edit: en un principio, me dio la cota de $\frac{5-\sqrt{17}}{2}n^2$, pero el resto de la holgura en el problema era fácil de eliminar mediante la consideración de la fila con el mínimo de la suma. Si mis cálculos son correctos, esto resuelve el problema. ]

Esta es la modificación de Harrison Brown argumento.

Supongamos que el total es menos de $cn^2$. Deje $r_1$ ser una fila con una mínima suma $sn\leq cn$. Digamos que $r_1$ $tn$ cero entradas. Por supuesto, $t\leq s$. Considere la posibilidad de cualquier otra fila $r$, lo que ha $c_r n$ ceros en los lugares que $r_1$ no, y cuya suma es $s_r n$. A continuación, la suma total es de al menos $c_r(1-s_r)n^2+(1-s)(1-t)n^2$. Por otro lado, la suma de $r$ restringido a las columnas donde $r_1$ es no-cero es, al menos,$(t-c_r) n$. Por lo tanto la suma total es de al menos $\sum_r (t-c_r) n + (1-s)(1-t) n^2$. Para resumir $$\begin{align*} cn^2&\geq (1-s)(1-t)n^2+\max_r c_r(1-s_r)n^2\\\\ cn^2&\geq (1-s)(1-t)n^2+\sum_r (t-c_r)n\\\\ cn^2&\geq \sum_r s_r n \end{align*} $$ Para un valor fijo de $\sum c_r$ $T=\max c_r(1-s_r)$ el mínimo de $\sum s_r$ se logra cuando todos pero uno de los $c_r$ son igual a $T/(1-s)$ o $c$ (que sigue a través de la optimización de una suma de dos términos de la forma $\max(s,1-T/c_r)$ ). Deje $p$ la proporción de filas $r$ tal que $c_r=c$. Entonces $$\begin{align*} c&\geq (1-c)(1-t)+T\\\\ c&\geq (1-c)(1-t)+(1-p)(c-T)\\\\ c&\geq p(1-T/c)+(1-p)s\\\\ t&\leq s\leq c \end{align*}$$ Afirmo que el mínimo de $c$ bajo estas restricciones se produce cuando la primera de estas desigualdades son igualdades. En efecto, si la primera desigualdad es estricta, aumentar el $T$. Si la segunda desigualdad es estricta, disminución del $p$. Por otra parte, si $s\neq t$, se puede disminuir el $s$. Así $$\begin{align*} c&= (1-c)(1-s)+T\\\\ c&= (1-c)(1-s)+(1-p)(c-T)\\\\ c&\geq p(1-T/c)+(1-p)s\\\\ s&\leq c \end{align*}$$ La eliminación de $T$ obtenemos $$\begin{align*} c&=(2-p)(1-c)(1-s), \end{align*}$$ La resolución de la ecuación de $s$ y sustituyendo en la desigualdad de $s\leq c$, obtenemos (verifique por favor!) $$\begin{align*} p(1-c)^2\geq 2c^2-5c+2 \end{align*}$$ La sustitución de esta desigualdad por $p$ a $c\geq p(1-T/c)+(1-p)s$ y el uso de los expresando para $s$ $T$ que tenemos, por fin llegamos (compruebe por favor!) a $$(1-2c)(2-c)(2c^3-6c^2+3c-1)\geq 0$$. Since $2c^3-6c)^2+3c-1$ is negative for $c<1$, the inequality $c\geq 1/2$ de la siguiente manera.

[Antes de la edición, la respuesta fue que concluyó con la siguiente frase, para que el comentario se refiere]. En general es tentador considerar arbitraria de conjuntos de $k$ filas, y si la unión de sus cero conjuntos es grande, el uso que decir que la suma de las columnas correspondientes es grande.

2voto

Eric Puntos 246

Cabe señalar que, tal vez, que la diagonal de la matriz no es el único extremal de la matriz. Un patrón de tablero de ajedrez de 1's y 0's también consigue $n^2/2$.

Hay ciertas transformaciones que conservan las propiedades especificadas y simplificar la matriz. Por ejemplo, podemos transponer la matriz, el intercambio de cualquier par de filas, el intercambio de cualquier par de columnas.

Hay otra transformación, cuyo efecto es más sutil. Supongamos $m_{ij}\ge2$. Si alguna de las $m_{i'j'}\ge2$$i'\le i+1$$j'\ge j+1$, entonces podemos reemplazar$m_{ij},m_{i',j'},m_{i',j},m_{i,j'}$$m_{ij}-1,m_{i'j'}-1,m_{i',j}+1,m_{i,j'}+1$, respectivamente. Esto conserva todos los de la fila y la columna de sumas de dinero, y se mueve la masa de distancia de la parte inferior izquierda y superior derecha de las curvas, y hacia la diagonal. La única razón por la que necesitamos $m_{ij}\ge1$ es que tenemos que ser cuidadosos acerca de la creación de 0 en la matriz.

Se siente como este es tan sólo uno o dos WOLOGs dice que podemos suponer que la matriz es diagonal, en cuyo caso el problema es fácil (la suma es $n^2/2$ o $(n^2+n-2)/2$ dependiendo de la paridad de $n$).

1voto

ConroyP Puntos 24021

El extraño caso.

Improvisar algunos posts que ya han aparecido, obtenemos:

Reclamo: Para $n$ impar, el mínimo es de $\frac{n^2 + 1}{2}$.

Pf: Como Harrison Brown puntos, ya que el $\frac{n^2}{2}$ es un límite inferior para $n$, incluso, es un límite inferior para $n$ impar. Por lo tanto, $\lceil\frac{n^2}{2}\rceil = \frac{n^2 + 1}{2}$ es así.

El patrón de tablero de ajedrez (con aquellas en las esquinas) logra esta obligado.

Lo que hace el conjunto de todos los extremal matrices?

i-Ciencias.com

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.

Powered by: