Supnick matrix

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 symmetrical across its main diagonal.

Mathematical definition

A Supnick matrix must satisfy the requirements of a Monge array plus the requirements of symmetric arrays.

A Supnick matrix is an m-by-n matrix if, for all i, j, k, l such that if

$1\leq i<k\leq m$ and $1\leq j<l\leq n$

then, one obtains

$A[i,j]+A[k,l]\leq A[i,l]+A[k,j]$

and

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

Another definition is that of Rudolf & Woeginger who, in 1995, proposed (Deineko and Woeginger 2006) 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.

Properties

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

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

References

• Supnick, Fred (July 1957). "Extreme Hamiltonian Lines". The Annals of Mathematics (2nd series). 66 (1): 179–201.
• 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).