ON INCIDENCE MATRICES,
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 31, 1967
- Accession Number
- AD0657611
Entities
People
- Peter C. C. Wang
Organizations
- Michigan State University