A note on multiplying boolean matrices II

ABSTRACT

In a note by Baker [1], a method is given for getting the limiting connectivity matrix, B, of a matrix whose entries are Boolean 0's and 1's. Harary [2] suggests determining An-1 since An-1 = An = ··· , where n is the order of the matrix. The purpose of this note is to give a method for determining An-1. The method is also applicable to finding the output matrix of a switching network as described in [3] and [4] where again An-1 = An = ··· , but A now has Boolean switching functions as entries instead of 0's and 1's.

REFERENCES

• 1: James J. Baker, A note on multiplying Boolean matrices, Communications of the ACM, v.5 n.2, p.102, Feb. 1962 [doi>10.1145/366792.366825]
• 2: HARARY, F. A graph theoretic method for the complete reduction of a matrix with a view toward finding its eigenvalues. J. Math. Physics 38 (1959-60), 104-111.
• 3: HOHN, F. E., AND SCHISSLER, L. R. Boolean matrices and the design of combinational relay switching circuits. BSTJ 84, 1 (1955), 177-202.
• 4: LUNTZ, A. G. Algebraic methods of analysis and synthesis of contact networks. Izvestia Akad. Nauk SSSR, Ser. Mat. 19 (1952), 405-426.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Performance, Theory