Una matriz lógica , matriz binaria , matriz de relación , la matriz booleana , o (0,1) de la matriz es una matriz con entradas de la dominio Boolean B = {0, 1}. Esta matriz se puede utilizar para representar una relación binaria entre un par de conjuntos finitos .
Representación matricial de una relación
Si R es una relación binaria entre los conjuntos indexados finitos X e Y (entonces R ⊆ X × Y ), entonces R puede ser representado por la matriz lógica M cuyos índices de fila y columna indexan los elementos de X e Y , respectivamente, de manera que las entradas de M están definidas por:
Con el fin de designar los números de fila y columna de la matriz, los conjuntos de X y de Y se indexan con números enteros positivos: i varía de 1 a la cardinalidad (tamaño) de X y j varía de 1 a la cardinalidad de Y . Consulte la entrada sobre conjuntos indexados para obtener más detalles.
Ejemplo
La relación binaria R en el conjunto {1, 2, 3, 4} se define de modo que aRb se cumple si y solo si a divide a b uniformemente, sin resto. Por ejemplo, 2 R 4 se cumple porque 2 divide 4 sin dejar un resto, pero 3 R 4 no se cumple porque cuando 3 divide 4 hay un resto de 1. El siguiente conjunto es el conjunto de pares para los que se cumple la relación R.
- {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.
La representación correspondiente como matriz lógica es:
- que incluye una diagonal de unos ya que cada número se divide.
Otros ejemplos
- Una matriz de permutación es una matriz (0,1), cuyas columnas y filas tienen cada una exactamente un elemento distinto de cero.
- Una matriz de Costas es un caso especial de una matriz de permutación
- Una matriz de incidencia en combinatoria y geometría finita tiene unas para indicar la incidencia entre puntos (o vértices) y líneas de una geometría, bloques de un diseño de bloque o aristas de un gráfico (matemáticas discretas)
- Una matriz de diseño en análisis de varianza es una matriz (0,1) con sumas de fila constantes.
- Una matriz lógica puede representar una matriz de adyacencia en la teoría de grafos : las matrices no simétricas corresponden a gráficos dirigidos , las matrices simétricas a gráficos ordinarios y un 1 en la diagonal corresponde a un bucle en el vértice correspondiente.
- La matriz de biadjacencia de un grafo bipartito simple, no dirigido es una matriz (0,1), y cualquier matriz (0,1) surge de esta manera.
- Los factores primos de una lista de m -cuadrados libres , n -smooth números pueden ser descritos como una m × π ( n ) (0,1) -matrix, donde π es la función contador de números primos y un ij es 1 si y sólo si el j- ésimo primo divide al i- ésimo número. Esta representación es útil en el algoritmo de factorización cuadrática de tamices .
- Una imagen de mapa de bits que contiene píxeles en solo dos colores se puede representar como una matriz (0,1) en la que los 0 representan píxeles de un color y los 1 representan píxeles del otro color.
- Se puede utilizar una matriz binaria para comprobar las reglas del juego en el juego de Go [1]
Algunas propiedades
La representación matricial de la relación de igualdad en un conjunto finito es la matriz identidad I, es decir, la matriz cuyas entradas en la diagonal son todas 1, mientras que las demás son todas 0. De manera más general, si la relación R satisface I ⊂ R , entonces R es una relación reflexiva .
Si el dominio booleano se ve como un semiring , donde la suma corresponde al OR lógico y la multiplicación al AND lógico , la representación matricial de la composición de dos relaciones es igual al producto matricial de las representaciones matriciales de estas relaciones. Este producto se puede calcular en el tiempo esperado O ( n 2 ). [2]
Con frecuencia, las operaciones en matrices binarias se definen en términos de aritmética modular mod 2, es decir, los elementos se tratan como elementos del campo de Galois GF (2) = ℤ 2 . Surgen en una variedad de representaciones y tienen varias formas especiales más restringidas. Se aplican, por ejemplo, en satisfacibilidad XOR .
El número de matrices binarias m- por- n distintas es igual a 2 mn y, por lo tanto, es finito.
Enrejado
Deje que n y m ser dada y dejar que T denota el conjunto de todos lógico m × n matrices. Entonces U tiene un orden parcial dado por
De hecho, U forma un álgebra booleana con las operaciones y & o entre dos matrices aplicadas por componentes. El complemento de una matriz lógica se obtiene intercambiando todos los ceros y unos por su opuesto.
Toda matriz lógica a = (a ij ) tiene una transpuesta a T = (a ji ). Suponga que a es una matriz lógica sin columnas o filas idénticas a cero. Luego, el producto de la matriz, usando aritmética booleana, a T a contiene la matriz de identidad m × m , y el producto aa T contiene la identidad n × n .
Como estructura matemática, el álgebra de Boole U forma un retículo ordenado por inclusión ; además, es un retículo multiplicativo debido a la multiplicación de matrices.
Toda matriz lógica en U corresponde a una relación binaria. Estas operaciones enumeradas en U , y el ordenamiento, corresponden a un cálculo de relaciones , donde la multiplicación de matrices representa la composición de relaciones . [3]
Vectores lógicos
Estructuras de tipo grupal | |||||
---|---|---|---|---|---|
Totalidad α | Asociatividad | Identidad | Invertibilidad | Conmutatividad | |
Semigropoide | Innecesario | Requerido | Innecesario | Innecesario | Innecesario |
Categoría pequeña | Innecesario | Requerido | Requerido | Innecesario | Innecesario |
Groupoid | Innecesario | Requerido | Requerido | Requerido | Innecesario |
Magma | Requerido | Innecesario | Innecesario | Innecesario | Innecesario |
Cuasigrupo | Requerido | Innecesario | Innecesario | Requerido | Innecesario |
Magma unital | Requerido | Innecesario | Requerido | Innecesario | Innecesario |
Círculo | Requerido | Innecesario | Requerido | Requerido | Innecesario |
Semigroup | Requerido | Requerido | Innecesario | Innecesario | Innecesario |
Semigroup inverso | Requerido | Requerido | Innecesario | Requerido | Innecesario |
Monoide | Requerido | Requerido | Requerido | Innecesario | Innecesario |
Monoide conmutativo | Requerido | Requerido | Requerido | Innecesario | Requerido |
Grupo | Requerido | Requerido | Requerido | Requerido | Innecesario |
Grupo abeliano | Requerido | Requerido | Requerido | Requerido | Requerido |
^ α El cierre, que se utiliza en muchas fuentes, es un axioma equivalente a la totalidad, aunque se define de manera diferente. |
Si m o n es igual a uno, entonces la matriz lógica m × n (M i j ) es un vector lógico. Si m = 1 el vector es un vector de fila, y si n = 1 es un vector de columna. En cualquier caso, el índice igual a uno se elimina de la denotación del vector.
Suponer y son dos vectores lógicos. El producto externo de P y Q da como resultado una relación rectangular m × n :
- Un reordenamiento de las filas y columnas de dicha matriz puede ensamblar todas en una parte rectangular de la matriz. [4]
Sea h el vector de todos unos. Entonces, si v es un vector lógico arbitrario, la relación R = vh T tiene filas constantes determinadas por v . En el cálculo de relaciones, tal R se llama vector . [4] Un ejemplo particular es la relación universal hh T .
Para una relación dada R , una máxima, relación rectangular contenida en R se llama un concepto en R . Las relaciones se pueden estudiar descomponiendo en conceptos y luego observando el entramado de conceptos inducido .
Considere la tabla de grupo-como las estructuras, donde "innecesaria" pueden designarse 0, y "necesario" indicados por 1, formando una matriz lógica R . Para calcular elementos de RR T es necesario utilizar el producto interno lógico de pares de vectores lógicos en filas de esta matriz. Si este producto interno es 0, entonces las filas son ortogonales. De hecho, el semigrupo es ortogonal al bucle, la categoría pequeña es ortogonal al cuasigrupo y el grupoide es ortogonal al magma. En consecuencia, hay ceros en RR T y no es una relación universal .
Sumas de filas y columnas
Sumar todos los 1 en una matriz lógica se puede lograr de dos maneras, primero sumando las filas o primero sumando las columnas. Cuando se suman las sumas de las filas, la suma es la misma que cuando se suman las sumas de las columnas. En geometría de incidencia , la matriz se interpreta como una matriz de incidencia con las filas correspondientes a "puntos" y las columnas como "bloques" (líneas de generalización formadas por puntos). Una suma de filas se denomina grado de punto y una suma de columnas es el grado de bloque . La Proposición 1.6 de la Teoría del Diseño [5] dice que la suma de los grados de los puntos es igual a la suma de los grados del bloque.
Un problema temprano en el área fue "encontrar las condiciones necesarias y suficientes para la existencia de una estructura de incidencia con grados puntuales y grados de bloque dados (o en lenguaje matricial, para la existencia de una (0,1) -matriz de tipo v × b con sumas de filas y columnas dadas. " [5] Tal estructura es un diseño de bloque .
Ver también
- Lista de matrices
- Binatorix (un toro binario de De Bruijn)
- Matriz de bits
- Matriz de Redheffer
Notas
- ^ Petersen, Kjeld (8 de febrero de 2013). "Binmatrix" . Consultado el 11 de agosto de 2017 .
- ^ Patrick E. O'Neil; Elizabeth J. O'Neil (1973). "Un algoritmo de tiempo esperado rápido para la multiplicación de matrices booleanas y el cierre transitivo" . Información y control . 22 (2): 132-138. doi : 10.1016 / s0019-9958 (73) 90228-3 .- El algoritmo se basa en que la suma es idempotente , cf. p.134 (abajo).
- ^ Irving Copilowish (diciembre de 1948). "Desarrollo matricial del cálculo de relaciones", Journal of Symbolic Logic 13 (4): 193-203 Jstor link
- ^ a b Gunther Schmidt (2013). "6: Relaciones y Vectores". Matemáticas relacionales . Prensa de la Universidad de Cambridge. pag. 91. doi : 10.1017 / CBO9780511778810 . ISBN 9780511778810.
- ^ a b Beth, Thomas; Jungnickel, Dieter ; Lenz, Hanfried (1986). Teoría del diseño . Prensa de la Universidad de Cambridge . pag. 18.. 2ª ed. (1999) ISBN 978-0-521-44432-3
Referencias
- Hogben, Leslie (2006), Manual de álgebra lineal (Matemáticas discretas y sus aplicaciones) , Boca Raton: Chapman & Hall / CRC, ISBN 978-1-58488-510-8, § 31.3, Matrices binarias
- Kim, Ki Hang (1982), Teoría y aplicaciones de la matriz booleana , ISBN 978-0-8247-1788-9
- HJ Ryser (1957) "Propiedades combinatorias de matrices de ceros y unos", Canadian Journal of Mathematics 9: 371–7.
- Ryser, HJ (1960) "Rastros de matrices de ceros y unos", Canadian Journal of Mathematics 12: 463–76.
- Ryser, HJ (1960) "Matrices of Zeros and Ones", Boletín de la American Mathematical Society 66: 442–64.
- DR Fulkerson (1960) "Matrices cero-uno con traza cero", Pacific Journal of Mathematics 10; 831–6
- DR Fulkerson y HJ Ryser (1961) "Anchuras y alturas de (0, 1) -matrices", Canadian Journal of Mathematics 13: 239–55.
- LR Ford Jr. y DR Fulkerson (1962) § 2.12 "Matrices compuestas de ceros y unos", páginas 79 a 91 en Flows in Networks , Princeton University Press MR0159700
enlaces externos
- "Matriz lógica" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]