Combinatorial equivalence of (0, 1) circulant matrices

摘要

In this paper various properties of (0, 1) square matrices are investigated, and in particular, circulant matrices are considered. If r is a (0, 1) vector or code word of length n and contains exactly K one elements, then let A(r) be the corresponding circulant matrix having r as its first row. In particular, if in r the K one elements are in the first K positions, then we say that A(r) is a canonical matrix with parameters (K, n). Two matrices A and A′ are said to be in the same equivalence class if there exist permutation matrices P and P′ such that A′=PAP′, and we write A≡A′. We assume that no matrix A being considered is equivalent to a matrix A′ of the form Download : Download full-size imageThe main results of this paper deal with obtaining necessary and sufficient conditions on A in order to ensure the existence of P and P′ so that A is equivalent to the canonical matrix with parameters (K, n), where A need not be circulant. These conditions are very simple to check for. If A is equivalent to the canonical matrix with parameters (K, n), we say it has property (C, K, n). One elementary but important result is that there is only one equivalence class of (0, 1)n×n matrices A in which each row and column is unique and has exactly two one elements. From the results we can construct all those r such that A(r) has property (C, K, n), for any given K and n. If A(r) has property (C, K, n), then r cannot be a periodically repeating vector. We can therefore count the number of distinct matrices having property (C, K, n), and in some cases we can determine the number of equivalent classes of circulant matrices for a given K and n.The results obtained have applications to coding theory and in particular to cycliccodes and shift registers. The particular matrices studied were chosen because they are encountered in many engineering problems, such as the Quine matrix found in the simplification of Boolean functions and in the general formulation of the covering problem as a linear program.