Accession Number : AD0657611

Title :   ON INCIDENCE MATRICES,

Corporate Author : MICHIGAN STATE UNIV EAST LANSING DEPT OF STATISTICS

Personal Author(s) : Wang,Peter C. C.

Report Date : 31 AUG 1967

Pagination or Media Count : 14

Abstract : Given an m x n incidence matrix A(m,n), it is desired to 'squeeze' as many of its 1's as possible into its upper left-hand corner by a sequence of row and column permutations. Such problem arised in designing switches for computers. To establish criteria for the optimal matrix of matrix of the class of row and column permutations, we assign a weight W sub ij to each position in the original matrix where W sub ij is the weight assigned to the i-th row, j-th column position. The weight of matrix A(m,n) = (a sub ij) is taken to be summation, 1 = or < i = or < m, 1 = or < j = or < n, of (A sub ij W sub ij). Suppose W sub ij A(m,n) are given, then denote P(A) the permutation derived matrices of A, then the problem is to find max (A epsilon P(A)) summation, 1 = or < i = or < m, 1 = or < j = or <n, of (A sub ij W sub ij). In particular, when W matrix is square and A is the identity matrix, then this problem is reduced to the well-known assignment problem. (Author)

Descriptors :   (*MATRICES(MATHEMATICS), PERMUTATIONS), INEQUALITIES, OPTIMIZATION, COMPUTERS, MATHEMATICS

Subject Categories : Theoretical Mathematics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE