Accession Number:

AD0657611

Title:

ON INCIDENCE MATRICES,

Descriptive Note:

Corporate Author:

MICHIGAN STATE UNIV EAST LANSING DEPT OF STATISTICS

Personal Author(s):

Report Date:

1967-08-31

Pagination or Media Count:

14.0

Abstract:

Given an m x n incidence matrix Am,n, it is desired to squeeze as many of its 1s 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 Am,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 Am,n are given, then denote PA the permutation derived matrices of A, then the problem is to find max A epsilon PA 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

Subject Categories:

  • Theoretical Mathematics
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE