Representación de matroid

En la teoría matemática de los matroides , una representación matroide es una familia de vectores cuya relación de independencia lineal es la misma que la de un matroide dado. Las representaciones matroidales son análogas a las representaciones de grupos ; ambos tipos de representación proporcionan estructuras algebraicas abstractas (matroides y grupos, respectivamente) con descripciones concretas en términos de álgebra lineal .

Un matroide lineal es un matroide que posee una representación, y un matroide lineal sobre F (para un cuerpo F ) es un matroide cuya representación se realiza mediante un espacio vectorial sobre F. La teoría de la representación de matroides estudia la existencia de representaciones y las propiedades de los matroides lineales .

Un matroide (finito)${\displaystyle (E,{\mathcal {I}})}$se define mediante un conjunto finito${\displaystyle E}$(los elementos del matroide) y una familia no vacía${\displaystyle {\mathcal {I}}}$de los subconjuntos de${\displaystyle E}$, llamados conjuntos independientes del matroide. Se requiere que satisfagan las propiedades de que cada subconjunto de un conjunto independiente es a su vez independiente, y que si un conjunto independiente${\displaystyle A}$es mayor que un segundo conjunto independiente${\displaystyle B}$entonces existe un elemento${\displaystyle x\in A\setminus B}$que se puede agregar a${\displaystyle B}$para formar un conjunto independiente más grande. Uno de los ejemplos clave que motivaron la formulación de los matroides fue la noción de independencia lineal de los vectores en un espacio vectorial : si${\displaystyle E}$es un conjunto finito o multiconjunto de vectores, y${\displaystyle {\mathcal {I}}}$es la familia de subconjuntos linealmente independientes de${\displaystyle E}$, entonces${\displaystyle (E,{\mathcal {I}})}$es un matroide. ^{[ 1 ] [ 2 ]}

En términos más generales, si${\displaystyle (E,{\mathcal {I}})}$es cualquier matroide, entonces una representación de${\displaystyle (E,{\mathcal {I}})}$puede definirse como una función${\displaystyle f}$que mapas${\displaystyle E}$a un espacio vectorial${\displaystyle V}$, con la propiedad de que un subconjunto${\displaystyle A}$de${\displaystyle E}$es independiente si y solo si${\displaystyle f|_{A}}$es inyectivo y${\displaystyle f(A)}$es linealmente independiente. Un matroide con una representación se llama matroide lineal, y si${\displaystyle V}$Si es un espacio vectorial sobre el cuerpo F , entonces el matroide se llama matroide lineal F. Por lo tanto, los matroides lineales son precisamente los matroides que son isomorfos a los matroides definidos a partir de conjuntos o multiconjuntos de vectores. La función${\displaystyle f}$Será biyectivo si y solo si el matroide subyacente es simple (no tiene conjuntos dependientes de dos elementos). Las representaciones de matroides también pueden describirse de forma más concreta utilizando matrices sobre un cuerpo F , con una columna por elemento del matroide y con un conjunto de elementos que son independientes en el matroide si y solo si el conjunto correspondiente de columnas de la matriz es linealmente independiente. La función de rango de un matroide lineal viene dada por el rango matricial de las submatrices de esta matriz, o equivalentemente por la dimensión del espacio vectorial generado por subconjuntos de vectores. ^{[ 3 ]}

No todos los matroides son lineales; el matroide de Vámos de ocho elementos es uno de los matroides más pequeños que no se puede representar sobre ningún cuerpo. ^{[ 4 ]} Si un matroide es lineal, puede representarse sobre algunos cuerpos, pero no sobre todos. Por ejemplo, el matroide de rango tres de nueve elementos definido por la configuración de Perles se puede representar sobre los números reales , pero no sobre los números racionales .

Los matroides binarios son los matroides que pueden representarse sobre el cuerpo finito GF(2) ; son precisamente los matroides que no tienen el matroide uniforme.${\displaystyle U{}_{4}^{2}}$como un menor . ^{[ 5 ]} Los matroides unimodulares o regulares son los matroides que pueden representarse sobre todos los cuerpos; ^{[ 6 ]} pueden caracterizarse como los matroides que no tienen ninguno de${\displaystyle U{}_{4}^{2}}$, el plano de Fano (un matroide binario con siete elementos), o el matroide dual del plano de Fano como menores. ^{[ 5 ] [ 7 ]} Alternativamente, un matroide es regular si y solo si puede representarse mediante una matriz totalmente unimodular . ^{[ 8 ]}

La conjetura de Rota afirma que, para todo cuerpo finito F , los matroides F -lineales pueden caracterizarse mediante un conjunto finito de menores prohibidos, similar a las caracterizaciones descritas anteriormente para los matroides binarios y regulares. ^{[ 9 ]} Hasta 2012, solo se había demostrado para cuerpos de cuatro o menos elementos. ^{[ 5 ] [ 10 ] [ 11 ] [ 12 ]} Para cuerpos infinitos (como el cuerpo de los números reales ) no es posible tal caracterización. ^{[ 13 ]}

Para cada cuerpo numérico algebraico y cada cuerpo finito F existe un matroide M para el cual F es el subcuerpo mínimo de su clausura algebraica sobre el cual M puede ser representado: M puede tomarse como de rango 3. ^{[ 14 ]}

El conjunto característico de un matroide lineal se define como el conjunto de características de los campos sobre los que es lineal. ^{[ 15 ]} Para cada número primo p existen infinitos matroides cuyo conjunto característico es el conjunto unitario { p }, ^{[ 16 ]} y para cada conjunto finito de números primos existe un matroide cuyo conjunto característico es el conjunto finito dado. ^{[ 17 ]}

Si el conjunto característico de un matroide es infinito, contiene el cero; y si contiene el cero, entonces contiene todos los primos excepto un número finito. ^{[ 18 ]} Por lo tanto, los únicos conjuntos característicos posibles son conjuntos finitos que no contienen el cero y conjuntos cofinitos que contienen el cero. ^{[ 19 ]} De hecho, todos estos conjuntos existen. ^{[ 20 ]}

Un matroide uniforme${\displaystyle U{}_{n}^{r}}$tiene${\displaystyle n}$elementos, y sus conjuntos independientes consisten en todos los subconjuntos de hasta${\displaystyle r}$de los elementos. Los matroides uniformes pueden representarse mediante conjuntos de vectores en posición general en un${\displaystyle r}$Espacio vectorial de dimensión . El campo de representación debe ser lo suficientemente grande para que exista${\displaystyle n}$vectores en posición general en este espacio vectorial, por lo que los matroides uniformes son F -lineales para todos los campos F excepto un número finito de ellos . ^{[ 21 ]} Lo mismo es cierto para los matroides de partición , las sumas directas de los matroides uniformes, ya que la suma directa de cualesquiera dos matroides F -lineales es también F -lineal.

Un matroide gráfico es el matroide definido a partir de las aristas de un grafo no dirigido, definiendo un conjunto de aristas como independientes si y solo si no contiene un ciclo . Todo matroide gráfico es regular y, por lo tanto, es F -lineal para todo cuerpo F. ^{[ 8 ]}

Los matroides de rigidez describen los grados de libertad de los mecanismos mecánicos formados por barras rígidas conectadas en sus extremos por bisagras flexibles. Un mecanismo de este tipo puede describirse como un grafo, con una arista para cada barra y un vértice para cada bisagra, y para mecanismos unidimensionales los matroides de rigidez son exactamente los matroides gráficos. Los matroides de rigidez de dimensiones superiores pueden definirse utilizando matrices de números reales con una estructura similar a la de la matriz de incidencia del grafo subyacente, y por lo tanto son${\displaystyle \mathbb {R} }$-lineal. ^{[ 22 ] [ 23 ]}

Al igual que los matroides uniformes y los matroides de partición, los gammoides , matroides que representan la alcanzabilidad en grafos dirigidos , son lineales sobre todo campo suficientemente grande. Más específicamente, un gammoide con${\displaystyle n}$Los elementos pueden estar representados en cada campo que tenga al menos${\displaystyle 2^{n}}$elementos. ^{[ 24 ]}

Los matroides algebraicos son matroides definidos a partir de conjuntos de elementos de una extensión de cuerpo utilizando la noción de independencia algebraica . Todo matroide lineal es algebraico, y para cuerpos de característica cero (como los números reales) los matroides lineales y algebraicos coinciden, pero para otros cuerpos pueden existir matroides algebraicos que no sean lineales. ^{[ 25 ]}