Mayor $n\times m$ matriz con el no $n\times (n+1)$ submatriz tener $n$-sabio independiente columnas

Question

¿Cuál es el mayor $m$ para que un $n \times m$ matriz con la propiedad de que cualquier subconjunto de a $n+1$ columnas tiene rango $n$, puede contener ningún subconjunto de $n+1$ columnas en las que las columnas se $n$-sabio independiente?

En general se puede ver que la hipótesis implica que $m \leq 2n$, pero creo que debería ser posible determinar el $m$ exactamente. Si $n = 3$ I puede verificar por que el valor máximo del $m$$5$. Lo que debe ser en general?

Editar:

Como algunas personas han señalado, la pregunta puede ser generalizado a matroids. Sin embargo, en el interés de mantener las cosas concretas, estoy dispuesto en este punto a aceptar cualquier respuesta que presenta una matriz con entradas sobre cualquier campo que mejora el general vinculado $n+2 \leq m \leq 2n$. Si el ejemplo de Heptagon puede ser extendido para arbitrario $n$, este sería, por ejemplo, muestran que la $2n-1 \leq m \leq 2n$ sobre el conjunto de realizable matroids.

Answer 1

Aquí es una respuesta parcial que termina con una buena caracterización de admisible de las familias en la cardinalidad $n+2$. Mi conjetura es que el $m$ no es siempre igual a $n+2$, y que los resultados a continuación será útil en la construcción de un contraejemplo.

La notación En la secuela, la admisibilidad de una familia de vectores es aquel que satisface sus condiciones y ${\cal B}=\lbrace e_1,e_2,\ldots,e_n \rbrace $ denota una base del espacio vectorial. También se $x,y,z$ son vectores arbitrarios, con las coordenadas $(x_k),(y_k),(z_k)$ $\cal B$ (por ejemplo $x=\sum_{i=k}^n x_k e_k$, etc). Los apoyos $X,Y,Z$ para los vectores $x,y,z$ son definidos por $X=\lbrace k | x_k\neq 0 \rbrace$, etc. Tenga en cuenta que para un número finito de la familia de vectores es admisible iff cada $(n+1)$-subconjunto tiene tanto independiente $n$-subconjunto (que llamamos un $n$-base) y una variable dependiente $n$-subconjunto (que llamamos un $n$-nonbase). Así que una familia es admisible el fib tiene suficiente $n$-bases y suficiente $n$-nonbases.

Para $t\in \lbrace 1,2,\ldots, n\rbrace$, tenemos

$$ {\sf span}(({\cal B}\setminus \lbrace e_t \rbrace)\cup \lbrace x \rbrace)= \left\lbrace\begin{array}{lcll} {\sf span}(({\cal B}\setminus \lbrace e_t \rbrace) &\text{if} \ t\not\in X& \text{so it's a nonbase in this case} \\ {\mathbb K}^n &\text{if} \ t\in X& \text{so it's a base in this case} \\ \end{array}\right.\la etiqueta{1} $$

donde la segunda línea se sigue del hecho de que $e_t$ es una combinación lineal de $x$ e las $e_k$ $k\neq t$ ($e_t=\frac{x-\sum_{k\in X,k\neq t}x_ke_k}{x_t}$). tener un $n$-nonbase en $\cal B\cup\lbrace x \rbrace$ necesitamos al menos un $t\not\in X$. De ello se deduce inmediatamente que

Lema 1 : criterio de Admisibilidad para $n+1$-a las familias La familia $F_{n+1}=\cal B\cup\lbrace x \rbrace $ es admisible el fib $X\neq \lbrace 1,2,\ldots, n\rbrace$.

A continuación, tenemos :

Teorema : la Admisibilidad criterio para $n+2$-a las familias de La la familia $F_{n+2}=\lbrace e_1,e_2,\ldots,e_n,x,y \rbrace$ es admisible el fib $X\neq \lbrace 1,2,\ldots, n\rbrace$,$Y\neq \lbrace 1,2,\ldots, n\rbrace$, $X\cup Y=\lbrace 1,2,\ldots, n\rbrace$, e $X\cap Y$ está vacío o se puede dividir en piezas de tamaño, al menos, $2$ en el que la relación $\frac{y_k}{x_k}$ es constante.

La prueba del teorema. Vamos a mostrar el "sólo si" dirección : supongamos que $F_{n+2}$ es admisible. Argumentando como en el lema 1, para tener un $n$-nonbase en $\cal B\cup\lbrace x \rbrace$ necesitamos $X'=\lbrace 1,2,\ldots, n\rbrace \setminus X$ a ser no vacío. Del mismo modo $Y'=\lbrace 1,2,\ldots, n\rbrace \setminus Y$ es no vacío. Ahora si $X'\cap Y'$ fueron de vacío, decir $i\in X'\cap Y'$, a continuación, el $n+1$familia $({\cal B})\setminus \lbrace e_i \rbrace)\cup \lbrace x,y \rbrace$ no abarcan $e_i$, y para que no pudo contener cualquier base, contradiciendo la admisibilidad. Por lo $X'\cap Y'=\emptyset$, en otras palabras $X\cup Y=\lbrace 1,2,\ldots, n\rbrace$. Si $X\cap Y=\emptyset$, hemos terminado. Así que supongo $X\cap Y\neq \emptyset$ y deje $i\in X\cap Y$. Deje $G=F_{n+2}\setminus \lbrace e_i \rbrace$. Por la admisibilidad hipótesis, tenemos un $g\in G$ tal que $H=G\setminus \lbrace g \rbrace$ $n$- nonbase. A causa de la segunda línea en (1), tenemos $g\not\in\lbrace x,y\rbrace$. Por lo $g=e_j$ algunos $j\in\lbrace 1,2,\ldots, n\rbrace, j \neq i$. Si $j\not\in Y$, $e_i=\frac{y-\sum{k\in Y,k\neq i}y_ke_k}{y_i}\in {\sf span}(H)$ y y, por tanto, $e_j=\frac{x-\sum{k\in X,k\neq j}x_ke_k}{x_j}\in {\sf span}(H)$ contradiciendo el hecho de que $H$ es un nonbase. Así que debemos tener $j\in Y$. Intercambiando los papeles de $X$$Y$, tenemos $j\in X$ también. A continuación, ${\sf span}(H)$ contiene todas las $e_k$$k\not\in\lbrace i,j\rbrace$, pero también se $x^{\sim}=x_ie_i+x_je_j=x-\sum_{k\in X,k\neq i,k\neq j}x_ke_k$ y $y^{\sim}=y_ie_i+y_je_j=y-\sum_{k\in Y,k\neq i,k\neq j}y_ke_k$. Como $H$ es un nonbase, $x^{\sim}$ y $y^{\sim}$ son proporcionales vectores, por lo $\frac{y_j}{x_j}=\frac{y_i}{x_i}$. Ya que para cualquier $i$ podemos encontrar un adecuado $j$, esto es claramente la condición de partición formulada anteriormente.

El "si", la dirección es sólo una verificación "in reverse" el trabajo que hemos hecho en el "sólo si" de dirección.

Answer 2

Esta es una observación que muestra que $m=n+3$ es posible. Considere la matriz $$\begin{pmatrix}0&1&1&1&0&0&0\\1&0&1&0&1&0&0\\1&1&0&0&0&1&0\\1&1&1&0&0&0&1\\\end{pmatrix}$$ over the field with two elements $\mathbb{F}_2$.

Tiene rango de cuatro, y se puede comprobar directamente que cualquier familia de cinco columnas que contiene una subfamilia de cuatro linealmente dependiente de las columnas y una subfamilia de cuatro columnas linealmente independientes. (Por cierto, esta matriz surge como una realización del doble de la de Fano matroid.)

---

UPD. Varias observaciones adicionales. El equivalente a las transformaciones de las filas de las matrices de no cambiar las propiedades mencionadas en la pregunta. Por lo tanto, podemos suponer sin pérdida de generalidad que, si $A$ es una matriz, como en la pregunta, a continuación, $A=(I|A')$ $I$ la identidad de $n\times n$ matriz. Tenga en cuenta que cada columna de $A'$ debe contener un cero, ya que de lo contrario la matriz formada de esta columna y de las columnas de a $I$ tiene todos sus $n\times n$ submatrices no-singular.

Si sucede que $A'$ contiene un $k\times(k+1)$ submatrix (con índices de fila en el conjunto de $R$ e índices de columna en el conjunto de $C$, por ejemplo) de rango inferior a $k$, entonces la matriz formada por los $(n+1)$ columnas de $A$ con índices en $\{1,\ldots,n\}\cup C\setminus R$ tiene rango menor que $n$, una contradicción. Por lo tanto, todos los $k\times(k+1)$ submatriz de a $A'$ rango $k$.

Sobre el campo $\mathbb{F}_2$, la última condición (aplicado con $k=1,2$) dice que, si $m\geqslant n+3$, entonces cada columna de $A'$ contiene a lo sumo un cero, y en realidad contiene exactamente un cero si usamos el resultado de la anterior párrafo. Esto significa que $A$ debe seguir el patrón como en la inicial de la respuesta anterior, y vemos que $m\leqslant n+2$ si $n=4$.

Finalmente, se obtiene una respuesta completa para este problema en el $\mathbb{F}_2$. (Aquí, yo denotar por $m_i$ el máximo valor posible de $m$ correspondiente a $n=i$.) El análisis de los valores pequeños de a $n$ por separado y teniendo en cuenta lo dicho anteriormente, obtenemos $m_1=2$, $m_2=3$, $m_3=5$, $m_4=7$, y $m_i=i+2$$i>4$.

Mi conjetura es que la respuesta es la misma en todos los campos, excepto en que $m_4=6$ en el carácter diferente de los dos. (En otras palabras, el ejemplo con $m=n+3$ es posible sólo para $n=4$ y en el carácter de los dos.) Pero una prueba de esta conjetura parece requerir mucho más complicado análisis combinatorio si es posible en absoluto.