Matriz lógica - Logical matrix

Uma matriz lógica , matriz binária , matriz de relação , matriz booleana , ou (0,1) da matriz é uma matriz com as entradas do domínio lógico B = {0, 1}. Essa matriz pode ser usada para representar uma relação binária entre um par de conjuntos finitos .

Representação matricial de uma relação

Se R é uma relação binária entre os conjuntos indexados finitos X e Y (então R ⊆ X × Y ), então R pode ser representado pela matriz lógica M cujos índices de linha e coluna indexam os elementos de X e Y , respectivamente, de modo que as entradas de M são definidas por:

${\ displaystyle M_ {i, j} = {\ begin {cases} 1 & (x_ {i}, y_ {j}) \ in R \\ 0 & (x_ {i}, y_ {j}) \ não \ in R \ end {casos}}}$

De modo a designar os números de linha e coluna da matriz, os conjuntos X e Y são indexados com números inteiros positivos: i varia de 1 a cardinalidade (tamanho) de X e de j varia de 1 a cardinalidade de Y . Veja a entrada em conjuntos indexados para mais detalhes.

Exemplo

A relação binária R no conjunto {1, 2, 3, 4} é definida de modo que aRb se mantenha se e somente se a divide b igualmente, sem resto. Por exemplo, 2 R 4 é válido porque 2 divide 4 sem deixar um resto, mas 3 R 4 não é válido porque quando 3 divide 4 há um resto de 1. O conjunto seguinte é o conjunto de pares para os quais a relação R é válida.

{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

A representação correspondente como uma matriz lógica é:

${\ displaystyle {\ begin {pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \ end {pmatrix}}}$ que inclui uma diagonal de uns, já que cada número se divide.

Outros exemplos

• Uma matriz de permutação é uma matriz (0,1), cujas colunas e linhas têm, cada uma, exatamente um elemento diferente de zero.
  • Uma matriz Costas é um caso especial de uma matriz de permutação
• Uma matriz de incidência em combinatória e geometria finita tem uns para indicar a incidência entre pontos (ou vértices) e linhas de uma geometria, blocos de um desenho de bloco ou arestas de um gráfico (matemática discreta)
• Uma matriz de design em análise de variância é uma matriz (0,1) com somas de linhas constantes.
• Uma matriz lógica pode representar uma matriz de adjacência na teoria dos grafos : matrizes não simétricas correspondem a grafos direcionados , matrizes simétricas a grafos comuns e um 1 na diagonal corresponde a um loop no vértice correspondente.
• A matriz biadjacência de um grafo bipartido simples não direcionado é uma matriz (0,1), e qualquer matriz (0,1) surge dessa maneira.
• Os factores principais de uma lista de m livre-quadrados , n -Smooth números pode ser descrito como um m × π ( n ) (0,1) -matrix, onde π é a principal função de contagem e um _{i j} é 1 se e somente se o j- ésimo primeiro divide o i- ésimo número. Esta representação é útil no algoritmo de fatoração de peneira quadrática .
• Uma imagem de bitmap contendo pixels em apenas duas cores pode ser representada como uma matriz (0,1) em que os 0s representam os pixels de uma cor e os 1s representam os pixels da outra cor.
• Uma matriz binária pode ser usada para verificar as regras do jogo no jogo Go

Algumas propriedades

A representação matricial da relação de igualdade em um conjunto finito é a matriz identidade I, ou seja, a matriz cujas entradas na diagonal são todas 1, enquanto as outras são todas 0. Mais geralmente, se a relação R satisfaz I ⊂ R , então R é uma relação reflexiva .

Se o domínio booleano é visto como um semiramento , onde a adição corresponde ao OR lógico e a multiplicação ao AND lógico , a representação matricial da composição de duas relações é igual ao produto matricial das representações matriciais dessas relações. Este produto pode ser calculado no tempo esperado O ( n ² ).

Freqüentemente, as operações em matrizes binárias são definidas em termos do modo aritmético modular 2 - ou seja, os elementos são tratados como elementos do campo de Galois GF (2) = ℤ ₂ . Eles surgem em uma variedade de representações e têm várias formas especiais mais restritas. Eles são aplicados, por exemplo, na satisfação de XOR .

O número de matrizes binárias m- por- n distintas é igual a 2 ^mn e, portanto, finito.

Malha

Sejam n e m e sejam U o conjunto de todas as matrizes lógicas m × n . Então U tem uma ordem parcial dada por

${\ displaystyle m \ subconjunto n \ quad {\ text {quando}} \ quad \ forall i, j \ quad m_ {ij} = 1 \ implica n_ {ij} = 1.}$

Na verdade, U forma uma álgebra booleana com as operações e & ou entre duas matrizes aplicadas por componentes. O complemento de uma matriz lógica é obtido trocando todos os zeros e uns por seus opostos.

Toda matriz lógica a = (a _ij ) tem uma transposta a ^T = (a _ji ). Suponha que a seja uma matriz lógica sem colunas ou linhas idênticas a zero. Em seguida, o produto de matriz, utilizando aritmética booleana, um ^T um contém o m x m matriz de identidade , e o produto aa ^t contém o n x n identidade.

Como estrutura matemática, a álgebra booleana U forma uma rede ordenada por inclusão ; além disso, é uma rede multiplicativa devido à multiplicação da matriz.

Cada matriz lógica em U corresponde a uma relação binária. Essas operações listadas em U e ordenação correspondem a um cálculo de relações , onde a multiplicação da matriz representa a composição das relações .

Vetores lógicos

Se m ou n for igual a um, então a matriz lógica m × n (M _{i j} ) é um vetor lógico. Se m = 1, o vetor é um vetor linha e se n = 1 é um vetor coluna. Em ambos os casos, o índice igual a um é retirado da denotação do vetor.

Suponha e sejam dois vetores lógicos. O produto externo de P e Q resulta em uma relação retangular m × n : ${\ displaystyle (P_ {i}), \ quad i = 1,2, \ ldots, m}$${\ displaystyle (Q_ {j}), \ quad j = 1,2, \ ldots, n}$

${\ displaystyle M_ {ij} = P_ {i} \ land Q_ {j}.}$ Um reordenamento das linhas e colunas de tal matriz pode reunir todas as outras em uma parte retangular da matriz.

Seja h o vetor de todos os uns. Então, se v é um vetor lógico arbitrário, a relação R = vh ^T tem linhas constantes determinadas por v . No cálculo de relações, tal R é chamado de vetor . Um caso particular é a relação universal hh ^T .

Para uma dada relação R , a máxima, relação retangular contida em R é chamado de conceito em R . As relações podem ser estudadas decompondo-se em conceitos e, em seguida, observando a estrutura do conceito induzido .

Estruturas semelhantes a grupos
	Totalidade	Associatividade	Identidade	Invertibilidade	Comutatividade
Semigroupoide	Desnecessário	Obrigatório	Desnecessário	Desnecessário	Desnecessário
Categoria Pequena	Desnecessário	Obrigatório	Obrigatório	Desnecessário	Desnecessário
Groupoid	Desnecessário	Obrigatório	Obrigatório	Obrigatório	Desnecessário
Magma	Obrigatório	Desnecessário	Desnecessário	Desnecessário	Desnecessário
Quasigroup	Obrigatório	Desnecessário	Desnecessário	Obrigatório	Desnecessário
Magma Unital	Obrigatório	Desnecessário	Obrigatório	Desnecessário	Desnecessário
Ciclo	Obrigatório	Desnecessário	Obrigatório	Obrigatório	Desnecessário
Semigrupo	Obrigatório	Obrigatório	Desnecessário	Desnecessário	Desnecessário
Semigrupo Inverso	Obrigatório	Obrigatório	Desnecessário	Obrigatório	Desnecessário
Monóide	Obrigatório	Obrigatório	Obrigatório	Desnecessário	Desnecessário
Monóide comutativo	Obrigatório	Obrigatório	Obrigatório	Desnecessário	Obrigatório
Grupo	Obrigatório	Obrigatório	Obrigatório	Obrigatório	Desnecessário
Grupo abeliano	Obrigatório	Obrigatório	Obrigatório	Obrigatório	Obrigatório
^ α Fechamento, que é usado em muitas fontes, é um axioma equivalente à totalidade, embora definido de forma diferente.

Considere a tabela de grupo-estruturas semelhantes, onde "desnecessário" pode ser denotado como 0, e "necessário" denotados por um, formando uma matriz lógica R . Para calcular os elementos de RR ^T é necessário usar o produto interno lógico de pares de vetores lógicos em linhas dessa matriz. Se este produto interno for 0, então as linhas são ortogonais. Na verdade, o semigrupo é ortogonal ao loop, a categoria pequena é ortogonal ao quasigrupo e o grupóide é ortogonal ao magma. Conseqüentemente, há 0's em RR ^T e ele deixa de ser uma relação universal .

Soma de linha e coluna

A soma de todos os 1s em uma matriz lógica pode ser realizada de duas maneiras, primeiro somando as linhas ou primeiro as colunas. Quando as somas das linhas são adicionadas, a soma é a mesma de quando as somas das colunas são adicionadas. Na geometria de incidência , a matriz é interpretada como uma matriz de incidência com as linhas correspondentes a "pontos" e as colunas como "blocos" (linhas generalizantes feitas de pontos). Uma soma de linha é chamada de grau de ponto e a soma de coluna é o grau de bloco . A proposição 1.6 na Teoria de Projeto diz que a soma dos graus dos pontos é igual à soma dos graus dos blocos.

Um problema inicial na área foi "encontrar as condições necessárias e suficientes para a existência de uma estrutura de incidência com determinados graus de ponto e de bloco (ou em linguagem de matriz, para a existência de uma (0,1) -matriz do tipo v × b com as somas de linhas e colunas fornecidas. "Essa estrutura é um design de bloco .

Veja também

• Lista de matrizes
• Binatorix (um toro binário De Bruijn)
• Matriz de bits
• Matriz redheffer

Notas

Referências

• Hogben, Leslie (2006), Handbook of Linear Algebra (Discrete Mathematics and Its Applications) , Boca Raton: Chapman & Hall / CRC, ISBN 978-1-58488-510-8, § 31.3, Matrizes binárias
• Kim, Ki Hang (1982), Boolean Matrix Theory and Applications , ISBN 978-0-8247-1788-9
• HJ Ryser (1957) "Propriedades combinatórias de matrizes de zeros e uns", Canadian Journal of Mathematics 9: 371–7.
• Ryser, HJ (1960) "Traços de matrizes de zeros e uns", Canadian Journal of Mathematics 12: 463–76.
• Ryser, HJ (1960) "Matrices of Zeros and Ones", Bulletin of the American Mathematical Society 66: 442–64.
• DR Fulkerson (1960) "Zero-one matrices with zero trace", Pacific Journal of Mathematics 10; 831-6
• DR Fulkerson & HJ Ryser (1961) "Widths and heights of (0, 1) -matrices", Canadian Journal of Mathematics 13: 239–55.
• LR Ford Jr. & DR Fulkerson (1962) § 2.12 "Matrizes compostas por 0's e 1's", páginas 79 a 91 em Flows in Networks , Princeton University Press MR 0159700

links externos

• "Logical matrix" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]