Transitive reduction of a rectangular Boolean matrix (Q798324)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Transitive reduction of a rectangular Boolean matrix |
scientific article |
Statements
Transitive reduction of a rectangular Boolean matrix (English)
0 references
1984
0 references
This paper deals with simplification of rectangular Boolean matrices of zeros and ones. For x,y whose values are zero or one, the following operations are defined \(x+y=\max (x,y), x\Theta y=\max (0,x-y)\) and for \(m\times n\) Boolean matrices A,B, \(A\Theta\) B and \(A\leq B\) are defined elementwise. An \(n\times n\) Boolean matrix R such that \(R^ 2\leq R\) is said to be transitive and a Boolean matrix, all of whose diagonal elements are zero, is said to be irreflexive. The main result is as follows: Let R, S, P be transitive matrices. If P is irreflexive and \(P\leq R\), then \(S(A\Theta SAP)R=SAR.\) The author also shows some similar relationships and remarks on an application of the results to information retrieval models.
0 references
(0,1)-matrices
0 references
Boolean matrix
0 references