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: and 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 "a_ij" = 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

Further reading

*cite journal|last = Supnick|first = Fred|title = Extreme Hamiltonian Lines|journal = The Annals of Mathematics (2nd series)|volume = 66|issue = 1|date = July 1957|pages = 179–201|url = http://links.jstor.org/sici?sici=0003-486X%28195707%292%3A66%3A1%3C179%3AEHL%3E2.0.CO%3B2-X&size=LARGE
*cite journal|last = Woeginger|first = Gerhard J.|title = Computational Problems without Computation|journal = Nieuwarchief|volume = 5|issue = 4|date = June 2003|pages = 140–147|url = http://www.nieuwarchief.nl/serie5/deel04/jun2003/pdf/woeginger.pdf
* 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 [https://www.eatcs.org/bulletin/beatcs90.pdf online edition] (PDF).