Una matriz lógica , una matriz binaria , una matriz de relaciones , una matriz booleana o una matriz (0, 1) es una matriz con entradas del dominio booleano B = {0, 1}. Esta matriz se puede utilizar para representar una relación binaria entre un par de conjuntos finitos . Es una herramienta importante en matemáticas combinatorias e informática teórica .
Si R es una relación binaria entre los conjuntos finitos indexados X e Y (por lo que R ⊆ X × Y ), entonces R puede representarse mediante la matriz lógica M cuyos índices de fila y columna indexan los elementos de X e Y , respectivamente, de modo que las entradas de M están definidas por
Para designar los números de fila y columna de la matriz, los conjuntos X e Y están indexados con números enteros positivos : i va de 1 a la cardinalidad (tamaño) de X , y j va de 1 a la cardinalidad de Y. Consulte el artículo sobre conjuntos indexados para obtener más detalles.
La relación binaria R en el conjunto {1, 2, 3, 4} se define de modo que aRb se cumple si y sólo si a divide b uniformemente, sin resto. Por ejemplo, 2 R 4 se cumple porque 2 divide a 4 sin dejar resto, pero 3 R 4 no se cumple porque cuando 3 divide a 4, queda un resto de 1. El siguiente conjunto es el conjunto de pares para los cuales se cumple la relación R .
La representación correspondiente como matriz lógica es
que incluye una diagonal de unos, ya que cada número se divide a sí mismo.
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 sobre 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 . Surgen en una variedad de representaciones y tienen una serie de formas especiales más restringidas. Se aplican, por ejemplo, en satisfacibilidad XOR .
El número de matrices binarias distintas m por n es igual a 2 mn y, por tanto, es finito.
Sean n y m y denotemos por U el conjunto de todas las matrices lógicas m × n . Entonces U tiene un orden parcial dado por
De hecho, U forma un álgebra booleana con las operaciones y & o entre dos matrices aplicadas componente a componente. 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 ). Supongamos que A es una matriz lógica sin columnas ni filas idénticas a cero. Entonces el producto matricial, usando aritmética booleana, contiene la matriz identidad m × m , y el producto contiene la identidad n × n .
Como estructura matemática, el álgebra booleana U forma una red ordenada por inclusión ; además, es una red multiplicativa 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 las relaciones . [3]
Si m o n es igual a uno, entonces la matriz lógica m × n ( m ij ) es un vector lógico o una cadena de bits . 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 1 se elimina de la denotación del vector.
Supongamos que y son dos vectores lógicos. El producto exterior de P y Q da como resultado una relación rectangular m × n
Una reordenación de las filas y columnas de dicha matriz puede ensamblarlas todas en una parte rectangular de la matriz. [4]
Sea h el vector de todos los 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 .
Para una relación dada R , una relación rectangular máxima contenida en R se llama concepto en R. Las relaciones se pueden estudiar descomponiéndolas en conceptos y luego observando la red de conceptos inducida .
Considere la tabla de estructuras tipo grupo, donde "innecesario" puede denotarse por 0 y "requerido" por 1, formando una matriz lógica. Para calcular elementos de , 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, la categoría pequeña es ortogonal al cuasigrupo y el grupoide es ortogonal al magma . En consecuencia, hay ceros y no es una relación universal .
Sumar todos los unos 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 generalizadoras hechas de puntos). Una suma de fila se llama grado de punto y una suma de columna es grado de bloque . La suma de los grados de los puntos es igual a la suma de los grados de los bloques. [5]
Uno de los primeros problemas en el área fue "encontrar las condiciones necesarias y suficientes para la existencia de una estructura de incidencia con grados de puntos y grados de bloque dados; o en lenguaje matricial, para la existencia de una matriz (0, 1) de tipo v × b con sumas de filas y columnas dadas". [5] Este problema se resuelve mediante el teorema de Gale-Ryser .
