- #1

- 7,861

- 1,600

My statement of it:

Let M be a N x N symmetric matrix such that N is divisible by 3, all the diagonal entries are 0 and each other entry is either 0 or 1. We think of the matrix entry M

*[j] as representing whether an object i interacts with another object j. Imagine M partitioned into 3x3 submatrices ("tiles"). The "cost" of M is defined as the number of tiles that have at least one non-zero entry. ( I don't undestand the practical reason why the cost is defined that way.)*

The information in M can be arranged differently by changing the order in which the objects are listed. (i.e. let s be a permutation of the numbers 1,2,...n and define a new matrix M' to have entries M'

The information in M can be arranged differently by changing the order in which the objects are listed. (i.e. let s be a permutation of the numbers 1,2,...n and define a new matrix M' to have entries M'

*[j] = M[s(i)][s(j)] ) Find an algorithm with determines a matrix M' that has minimum cost and contains the same information as the matrix M.*