¿Es cada entero positivo el permanente de alguna matriz 0-1?

Question

En el curso de la discusión de otro MO pregunta nos dimos cuenta de que no sabe la respuesta a una pregunta básica, a saber:

Es cierto que para cada entero positivo $k$ existe un equilibrio gráfico bipartito con exactamente $k$ perfecto elecciones?

De forma equivalente, como se indica en el título, es cada entero positivo permanente de algunos 0-1 de la matriz?

La respuesta es seguramente sí, pero no me queda claro cómo demostrarlo. La entrada A089479 de la OEIS informa del número de $T(n,k)$ de los tiempos de la permanente de un real $n\times n$ cero de una matriz toma el valor de $k$ pero no aborda la cuestión de si, para cada $k$ existe $n$ tal que $T(n,k)\ne 0$. Suponiendo que la respuesta es sí, el seguimiento, la pregunta es, ¿qué más podemos decir acerca de los valores de $n$ para que $T(n,k)\ne 0$ (por ejemplo, los límites superior e inferior)?

Answer 1

La respuesta a la pregunta es sí. Dado $k$, el 0-1 de la matriz dada por

$1$ $1$ $\dotsc$ $1$ $0$ $0$ $\dotsc$ $0$ $0$ $0$ $0$

$0$ $1$ $1$ $0$ $\dotsc$ $0$ $0$ $\dotsc$ $0$ $0$ $0$

$0$ $0$ $1$ $1$ $0$ $\dotsc$ $0$ $\dotsc$ $0$ $0$ $0$

$\dotsc$

$1$ $0$ $0$ $0$ $0$ $\dotsc$ $\dotsc$ $0$ $0$ $0$ $1$

donde la primera fila tiene, precisamente, $k$ entradas igual a $1$, evidentemente permanente igual a $k$.

Para $k=1$ la matriz es ($1$). Para $k=2$ la matriz es

$1$ $1$

$1$ $1$

Para $k=3$ la matriz es

$1$ $1$ $1$

$0$ $1$ $1$

$1$ $0$ $1$.

Para $k=4$ la matriz es

$1$ $1$ $1$ $1$

$0$ $1$ $1$ $0$

$0$ $0$ $1$ $1$

$1$ $0$ $0$ $1$

que evidentemente tiene permanente igual a $4$.

Por favor, tenga en cuenta que, por cada $k$ e $1\leq \ell \leq k$, esta construcción puede ser ajustado para dar una explícita $k\times k$ tamaño $0$-$1$-matriz de tener una permanente, precisamente,$\ell$, sólo por la realización de la primera fila, tienen exactamente $\ell$ entradas igual a $1$.

Por favor, también tenga en cuenta que mi construcción no tiene ninguna influencia sobre el interesante y aparentemente difícil pregunta que fue citado en el presente OP: mi construcción es demasiado derrochador: se utiliza un $k\times k$ matriz, que es demasiado grande cuando se trata de satisfacer las demandas de la OP en dicha pregunta.

Answer 2

Para el registro, aquí es la construcción de Kim, Lee, y Seol que he mencionado en mi comentario a Pedro Heinig la respuesta.

Escribir $k-1$ en binario, y deje $n$ 1 más el número de dígitos binarios de $k-1$.

Empezar con un $n\times n$ matriz con todos los $1$'s en o por encima de la diagonal principal y todos los $0$'s por debajo de la diagonal. A continuación, reemplace el primer $n-1$ entradas de la fila inferior de la matriz con la representación binaria de $k-1$ (un bit por cada entrada).

Por ejemplo, si $k=389$,, a continuación, $k-1$ en binario es $110000100$. A continuación, $n=1+9=10$ y la matriz es $$\matriz{ 1&1&1&1&1&1&1&1&1&1\cr 0&1&1&1&1&1&1&1&1&1\cr 0&0&1&1&1&1&1&1&1&1\cr 0&0&0&1&1&1&1&1&1&1\cr 0&0&0&0&1&1&1&1&1&1\cr 0&0&0&0&0&1&1&1&1&1\cr 0&0&0&0&0&0&1&1&1&1\cr 0&0&0&0&0&0&0&1&1&1\cr 0&0&0&0&0&0&0&0&1&1\cr 1&1&0&0&0&0&1&0&0&1\cr }$$

Answer 3

Si un pedido n (0,1) de la matriz tiene r filas con todos aquellos, de su permanente es un múltiplo de r! por un argumento fácil. De ello se desprende que el mayor número impar que es un permanente de orden n de la matriz es q = der(n) + der(n-1), que es una suma de números de alteraciones, y es un poco más grande que $n!/e$. Sospecho que el número positivo menor que no se pueden expresar como una permanente de este tamaño de la matriz es un número entero impar, que no es mucho más pequeño, tal vez cerca de la mitad, de q. Si es así, entonces podemos afeitarse un poco fuera de n=log(k) en la construcción de Timoteo Chow del post. Para algunos la motivación para este problema, vea Orrick a hablar mencionados (por determinantes) en https://mathoverflow.net/a/271273 .

Gerhard "También Un Potencial Proyecto Polymath" Paseman, 2017.08.29.