
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 lefthand 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 ith row, jth 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 wellknown assignment problem. (Author)
Descriptors : (*MATRICES(MATHEMATICS), PERMUTATIONS), INEQUALITIES, OPTIMIZATION, COMPUTERS, MATHEMATICS
Subject Categories : Theoretical Mathematics
Computer Hardware
Distribution Statement : APPROVED FOR PUBLIC RELEASE