go-v.orgcodex
Menu
Page tools

codex · Philosophy

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 also a symmetric matrix.

== 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≤i<k≤n and 1≤j<l≤n then

aij+akl≤ail+akj and also

aij=aji. 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=[sij]=[αi+α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.

== 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).

== References == Supnick, Fred (July 1957). "Extreme Hamiltonian Lines". Annals of Mathematics. Second Series. 66 (1): 179–201. doi:10.2307/1970124. JSTOR 1970124. Woeginger, Gerhard J. (June 2003). "Computational Problems without Computation" (PDF). Nieuwarchief. 5 (4): 140–147. Deineko, Vladimir G.; Woeginger, Gerhard J. (October 2006). "Some problems around travelling salesmen, dart boards, and euro-coins" (PDF). Bulletin of the European Association for Theoretical Computer Science. 90. EATCS: 43–52. ISSN 0252-9742.

Wikipedia contributors, "Supnick matrix", Wikipedia, revision 1296009775, retrieved 21 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex