Hispanopedia Wiki
Articulo de referencia

La desigualdad de Ingleton

En matemáticas , la desigualdad de Ingleton es una desigualdad que satisface la función de rango de cualquier matroide representable . En este sentido, es una condición necesari...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas , la desigualdad de Ingleton es una desigualdad que satisface la función de rango de cualquier matroide representable . En este sentido, es una condición necesaria para la representabilidad de un matroide sobre un cuerpo finito . Para un matroide M y su función de rango ρ , la desigualdad de Ingleton establece que para cualesquiera subconjuntos X 1 , X 2 , X 3 y X 4 en el soporte de M , la desigualdad

ρ ( X 1 ) + ρ ( X 2 ) + ρ ( X 1 ∪ X 2 ∪ X 3 ) + ρ ( X 1 ∪ X 2 ∪ X 4 ) + ρ ( X 3 ∪ X 4 ) ≤ ρ ( X 1 ∪ X 2 ) + ρ ( X 1 ∪ X 3 ) + ρ ( X 1 ∪ X 4 ) + ρ ( X 2 ∪ X 3 ) + ρ ( X 2 ∪ X 4 )

está satisfecho.

Aubrey William Ingleton , matemático inglés, escribió un importante artículo en 1969 [ 1 ] en el que analizó el problema de la representabilidad en matroides. Aunque el artículo es principalmente expositivo, en él Ingleton enunció y demostró la desigualdad de Ingleton, que ha encontrado aplicaciones interesantes en la teoría de la información , la teoría de matroides y la codificación de redes . [ 2 ]

Importancia de la desigualdad

Existen conexiones interesantes entre los matroides, la región de entropía y la teoría de grupos . Algunas de esas conexiones se revelan en la desigualdad de Ingleton.

Quizás, la aplicación más interesante de la desigualdad de Ingleton se refiere al cálculo de las capacidades de codificación de redes . Las soluciones de codificación lineal están restringidas por la desigualdad y esto tiene una consecuencia importante:

La región de tasas alcanzables mediante codificación de red lineal podría ser, en algunos casos, estrictamente menor que la región de tasas alcanzables mediante codificación de red general. [ 3 ] [ 4 ] [ 5 ]

Para definiciones, véase, por ejemplo , [ 6 ].

Prueba

Teorema (desigualdad de Ingleton): [ 7 ] Sea M un matroide representable con función de rango ρ y sean X 1 , X 2 , X 3 y X 4 subconjuntos del conjunto soporte de M , denotados por el símbolo E ( M ). Entonces:

ρ ( X 1 ) + ρ ( X 2 ) + ρ ( X 1 ∪ X 2 ∪ X 3 ) + ρ ( X 1 ∪ X 2 ∪ X 4 ) + ρ ( X 3 ∪ X 4 ) ≤ ρ ( X 1 ∪ X 2 ) + ρ ( X 1 ∪ X 3 ) + ρ ( X 1 ∪ X 4 ) + ρ ( X 2 ∪ X 3 ) + ρ ( X 2 ∪ X 4 ).

Para demostrar la desigualdad debemos mostrar el siguiente resultado:

Proposición : Sean V 1 , V 2 , V 3 y V 4 subespacios de un espacio vectorial V , entonces

  1. tenue( V 1 ∩ V 2 ∩ V 3 ) ≥ tenue( V 1 ∩ V 2 ) + tenue( V 3 ) − tenue( V 1 + V 3 ) − tenue( V 2 + V 3 ) + tenue( V 1 + V 2 + V 3 )
  2. tenue ( V 1 ∩ V 2 ∩ V 3 ∩ V 4 ) ≥ tenue ( V 1 ∩ V 2 ∩ V 3 ) + tenue ( V 1 ∩ V 2 ∩ V 4 ) − tenue ( V 1 ∩ V 2 )
  3. tenue( V 1 ∩ V 2 ∩ V 3 ∩ V 4 ) ≥ tenue( V 1 ∩ V 2 ) + tenue( V 3 ) + tenue( V 4 ) − tenue( V 1 + V 3 ) − tenue( V 2 + V 3 ) − tenue( V 1 + V 4 ) − tenue( V 2 + V 4 ) + tenue( V 1 + V 2 + V 3 ) + tenue ( V 1 + V 2 + V 4 )
  4. tenue ( V 1 ) + tenue ( V 2 ) + tenue ( V 1 + V 2 + V 3 ) + tenue ( V 1 + V 2 + V 4 ) + tenue ( V 3 + V 4 ) ≤ tenue ( V 1 + V 2 ) + tenue ( V 1 + V 3 ) + tenue ( V 1 + V 4 ) + tenue ( V 2 + V 3) ) + tenue( V 2 + V 4 )

Donde V i + V j representan la suma directa de los dos subespacios.

Demostración (proposición) : Usaremos frecuentemente la identidad estándar del espacio vectorial: dim( U ) + dim( W ) = dim( U + W ) + dim( U ∩ W ).

1. Es claro que ( V 1 ∩ V 2 ) + V 3 ⊆ ( V 1 + V 3 ) ∩ ( V 2 + V 3 ), entonces

2. Es evidente que ( V 1 ∩ V 2 ∩ V 3 ) + ( V 1 ∩ V 2 ∩ V 4 ) ⊆ ( V 1 ∩ V 2 ), entonces

3. De (1) y (2) tenemos:

4. De (3) tenemos

Si sumamos (dim( V 1 )+dim( V 2 )+dim( V 3 + V 4 )) a ambos lados de la última desigualdad, obtenemos

Dado que se cumple la desigualdad dim( V 1 ∩ V 2 ∩ V 3 ∩ V 4 ) ≤ dim( V 3 ∩ V 4 ), hemos finalizado la demostración.♣

Demostración (desigualdad de Ingleton) : Supongamos que M es un matroide representable y sea A = [ v 1 v 2 … v n ] una matriz tal que M = M ( A ). Para X , Y ⊆ E( M ) = {1,2, …, n }, definimos U = <{ V i  : i ∈ X }>, como el espacio generado por los vectores en V i , y definimos W = <{ V j  : j ∈ Y }> en consecuencia.

Si suponemos que U = <{ u 1 , u 2 , … , u m }> y W = <{ w 1 , w 2 , … , w r }> entonces claramente tenemos <{ u 1 , u 2 , …, u m , w 1 , w 2 , …, w r }> = U + W .

Por lo tanto: r ( X ∪ Y ) = dim <{ v i  : i ∈ X } ∪ { v j  : j ∈ Y }> = dim( V + W ).

Finalmente, si definimos V i = { v r  : r ∈ X i } para i = 1,2,3,4, entonces por la última desigualdad y el punto (4) de la proposición anterior, obtenemos el resultado.

Referencias

  1. ↑ Ingleton, AW (1971). «Representación de matroides». En Welsh, DJA (ed.). Matemáticas combinatorias y sus aplicaciones. Actas, Oxford, 1969. Academic Press. pp. 149–167 . ISBN  0-12-743350-3. Zbl 0222.05025 . 
  2. ↑ Ahlswede, Rudolf ; N. Cai; Shuo-Yen Robert Li; Raymond Wai-Ho Yeung (2000). "Flujo de información en redes". IEEE Transactions on Information Theory . 46 (4): 1204– 1216. doi : 10.1109/18.850663 .
  3. ↑ Dougherty, R.; C. Freiling ; K. Zeger (2005). "Insuficiencia de los códigos de red lineales". Simposio Internacional IEEE sobre Teoría de la Información, Adelaida, Australia : 264–267 .
  4. ↑ Dougherty, R.; C. Freiling ; K. Zeger (2007). "Redes, matroides y desigualdades de información no-Shannon". IEEE Transactions on Information Theory . 53 (6): 1949– 1969. CiteSeerX 10.1.1.218.3066 . doi : 10.1109/TIT.2007.896862 . S2CID 27096 .  
  5. ↑ Li, S.-YR; Yeung, RW; Ning Cai (2003). "Codificación de red lineal" . IEEE Transactions on Information Theory ( FTP ). p. 371. doi : 10.1109/TIT.2002.807285 . (Para ver los documentos, consulte Ayuda:FTP )
  6. ↑ Bassoli, Riccardo; Marques, Hugo; Rodriguez, Jonathan; Shum, Kenneth W.; Tafazolli, Rahim (2013). "Teoría de la codificación de redes: una revisión". IEEE Communications Surveys & Tutorials . 15 (4): 1950. doi : 10.1109/SURV.2013.013013.00104 . S2CID 691027 . 
  7. ↑ Oxley, James (1992), Matroid Theory, Oxford: Oxford University Press, ISBN 0-19-853563-5, SEÑOR 1207587 , Zbl 0784.05002 .