Supnick matrix

From Wikipedia, the free encyclopedia

A Supnick matrix or Supnick array – named after Fred Supnick of the City College of New York, who introduced the notion in 1957 – is a Monge array which is also a symmetric matrix.

[edit] Mathematical definition

A Supnick matrix is a square Monge array that is symmetric around the main diagonal.

An n-by-n matrix is a Supnick matrix if, for all i, j, k, l such that if

1\le i < k\le n and 1\le j < l\le n

then

a_{ij} + a_{kl} \le a_{il} + a_{kj}\,

and also

a_{ij} = a_{ji}. \,

A logically equivalent definition is given by Rudolf & Woeginger who in 1995 proved that

A matrix is a Supnick matrix iff it can be written as the sum of a sum matrix S and a non-negative linear combination of LL-UR block matrices.

The sum matrix is defined in terms of a sequence of n real numbers {αi}:

S = [s_{ij}] = [\alpha_i + \alpha_j]; \,

and an LL-UR block matrix consists of two symmetrically placed rectangles in the lower-left and upper right corners for which aij = 1, with all the rest of the matrix elements equal to zero.

[edit] Properties

Adding two Supnick matrices together will result in a new Supnick matrix (Deineko and Woeginger 2006).

Multiplying a Supnick matrix by a non-negative real number produces a new Supnick matrix (Deineko and Woeginger 2006).

If the distance matrix in a traveling salesman problem can be written as a Supnick matrix, that particular instance of the problem admits an easy solution (even though the problem is, in general, NP hard).

[edit] References

  • Supnick, Fred (July 1957). "Extreme Hamiltonian Lines". The Annals of Mathematics (2nd series) 66 (1): 179–201. 
  • Woeginger, Gerhard J. (June 2003). "Computational Problems without Computation". Nieuwarchief 5 (4): 140–147. 
  • Vladimir G. Deineko and Gerhard J. Woeginger (2006): 'Some problems around travelling salesmen, dart boards, and euro-coins', appeared in the Bulletin of the European Association for Theoretical Computer Science (EATCS), Number 90, October 2006, ISSN 0252-9742, pages 43 - 52. See online edition (PDF).