A Supnick matrix or Supnick array – named after Fred Supnick of the

City College of New York The City College of the City University of New York (also known as the City College of New York, or simply City College or CCNY) is a Public university, public research university within the City University of New York (CUNY) system in New York ...

, who introduced the notion in 1957 – is a

Monge array In mathematics applied to computer science, Monge arrays, or Monge matrices, are mathematical objects named for their discoverer, the French mathematician Gaspard Monge. An ''m''-by-''n'' matrix is said to be a ''Monge array'' if, for all \script ...

which is also a

symmetric matrix In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally, Because equal matrices have equal dimensions, only square matrices can be symmetric. The entries of a symmetric matrix are symmetric with ...

Mathematical definition

A Supnick matrix is a square

that is symmetric around the

main diagonal In linear algebra, the main diagonal (sometimes principal diagonal, primary diagonal, leading diagonal, major diagonal, or good diagonal) of a matrix A is the list of entries a_ where i = j. All off-diagonal elements are zero in a diagonal matrix ...

. An ''n''-by-''n''

matrix Matrix (: matrices or matrixes) or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the m ...

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_ + a_ \le a_ + a_\,

and also :

a_ = a_. \,

A logically equivalent definition is given by Rudolf & Woeginger who in 1995 proved that :''A matrix is a Supnick matrix

iff In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either both ...

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 : :

S =_= 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 In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...

produces a new Supnick matrix (Deineko and Woeginger 2006). If the distance matrix in a

traveling salesman problem In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exac ...

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 NP may refer to: Arts and entertainment * NP (novel), ''NP'' (novel), by Japanese author Banana Yoshimoto Organizations * Nashua-Plainfield Community School District, Iowa, United States * National Party (disambiguation), various political parti ...

References

* * * {{cite journal , title = Some problems around travelling salesmen, dart boards, and euro-coins , first1 = Vladimir G. , last1 = Deineko , first2 = Gerhard J. , last2 = Woeginger , author2-link = Gerhard J. Woeginger , journal = Bulletin of the European Association for Theoretical Computer Science , publisher = EATCS , volume = 90 , date=October 2006 , issn = 0252-9742 , pages = 43–52 , url = http://alexandria.tue.nl/openaccess/Metis211810.pdf Travelling salesman problem Matrices (mathematics)