Límite superior para la mayor parte de la matriz con que no hay dos subconjuntos de columnas con la misma suma de vectores

Question

Más en PPCG está en marcha un concurso que va a encontrar la matriz más grande sin una cierta propiedad, denominada propiedad $X$. La descripción es la siguiente (copiado de la pregunta).

Un circulantes de la matriz se especifica completamente por su primera fila $r$. El resto de filas de cada una de las permutaciones cíclicas de la fila $r$ con desplazamiento igual al índice de fila. Vamos a permitir que circulantes matrices que no son cuadradas, de modo que son simplemente faltan algunas de sus últimas filas. Nosotros, no obstante, siempre hay que asumir que el número de filas no es más que el número de columnas. Por ejemplo, considere el siguiente $3\times5$ circulantes de la matriz.

$$\begin{pmatrix}1&0&1&1&1\\ 1&1&0&1&1\\ 1&1&1&0&1\end{pmatrix}$$

We say a matrix has property $X$ if it contains two non-empty sets of columns with non-identical indices which have the same (vector) sum. The vector sum of two columns is simply an element-wise summation of the two columns. That is the sum of two columns containing $x$ elements each is another column containing $x$ elements.

The matrix above trivially has property $X$ as the first and last columns are the same. The identity matrix never has property $X$.

If we just remove the last column of the matrix above then we get an example which does not have property $X$. The score of a matrix is defined to be the number columns divided by the number of rows. The following matrix therefore does not have property $X$ and gives a score of $4/3$.

$$\begin{pmatrix}1&0&1&1\\ 1&1&0&1\\ 1&1&1&0\end{pmatrix}$$ $$

The task they were given is to find the highest scoring circulant matrix whose entries are all 0 or 1 and which does not have property $X$.

Hasta ahora, la evidencia numérica, apunta hacia una cota superior de a dos.

Hay un límite superior de $2$ de esta calificación?

---

La más alta puntuación de la matriz se encuentran hasta el momento tiene una puntuación de 36/19 por Peter Taylor. Esto ha 000001001010110001000101001111111111 como la primera fila.

Answer 1

Creo que cualquier nxm matrices circulantes (donde m=n+1) de esta forma no tendrá la propiedad X, con todas las entradas 0 o 1

$$\begin{pmatrix}1&0&1&1&\cdots&1\\ 1&1&0&1&\cdots&1\\ 1&1&1&0&\cdots&1\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 1&1&1&1&\cdots&0\end{pmatrix}$$

Por lo tanto el puntaje de una matriz de esta forma es $$S=\frac{n+1}{n}$$

S es mayor cuando n=1, por tanto la máxima puntuación posible es $$S_{max}=\frac{2}{1}=2$$

Sin embargo una de 1x2 de la matriz es sólo un vector de fila $$\begin{pmatrix}1&0\end{pmatrix}$$ y no circulantes matriz

Por lo tanto la puntuación más alta se requiere de la matriz es una matriz de 2x3 de la forma $$\begin{pmatrix}1&0&1\\1&1&0\end{pmatrix}$$

con la máxima puntuación $$S=\frac{3}{2}=1.5$$

================

EDITAR (Intento de arreglar mi respuesta mediante el asesoramiento señalado por Lembik)

De los requisitos de la propiedad X, parece que en cualquier circulantes (0,1) de la matriz no debe tener ningún columnas idénticas

Además, cualquier columna no puede ser la combinación lineal de cualquier otras 2 columnas

Es señalado por Lembik que la siguiente matriz

$$\begin{pmatrix}1&0&1\\1&1&0\end{pmatrix}$$

tiene la propiedad X desde

$$\begin{pmatrix}1\\1\end{pmatrix}=\begin{pmatrix}1\\0\end{pmatrix}+\begin{pmatrix}0\\1\end{pmatrix}$$

Con el fin de construir una matriz B tal que no tiene la propiedad X y no tiene columnas vacías, se deben única no columnas vacías como así (o permultation de los mismos):

$$\begin{pmatrix}1&0&1&1&\cdots&1\\ 1&1&0&1&\cdots&1\\ 1&1&1&0&\cdots&1\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 1&1&1&1&\cdots&0\end{pmatrix}$$

La puntuación de una matriz de esta forma es $$S=\frac{m}{n}$$

S es mayor cuando n=1

Sin embargo, una 1xm matriz es simplemente un vector fila por ejemplo, para 1x2 matriz $$\begin{pmatrix}1&0\end{pmatrix}$$ y no circulantes de la matriz, y dado que 0+1=1 como se ha señalado por la PPCG enlace, que tiene la propiedad X

Para n=2, la única forma en la que podría ser la única de las columnas que no son combinación lineal de cualquiera de los otros dos columnas es cuando m=2, pero esto viola la restricción m>n

Por lo tanto nxm donde m>n, n debe ser > 2

También observamos que para el caso donde n=3, m < 5 ya que, si no existe una columna que va a ser que no único o una combinación lineal de cualquiera de los 2 columnas existentes (ya que todas las entradas están restringidos a 0 o 1)

Así para n=3, m debe = 4

Sabíamos que al encontrar el límite de S como $$n \rightarrow \infty$$ es cero.

Por lo tanto, la más alta puntuación de la matriz debe tener el más mínimo m y n

Por lo tanto, el conjunto de más alta puntuación requerida circulantes matrices son (24)

$$B=\begin{pmatrix}1&0&1&1\\1&1&0&1\\1&1&1&0\end{pmatrix}, \begin{pmatrix}1&0&1&1\\1&1&1&0\\1&1&0&1\end{pmatrix},\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&1&1&0\end{pmatrix},\begin{pmatrix}1&1&0&1\\1&1&1&0\\1&0&1&1\end{pmatrix},\begin{pmatrix}1&1&1&0\\1&0&1&1\\1&1&0&1\end{pmatrix},\begin{pmatrix}1&1&1&0\\1&1&0&1\\1&0&1&1\end{pmatrix}\\\begin{pmatrix}1&1&1&0\\1&1&0&1\\0&1&1&1\end{pmatrix} etc.$$

con la máxima puntuación $$S=\frac{4}{3}=1.3333...$$