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 within the City University of New York (CUNY) system in New York City. Founded in 1847, Cit ...

, 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 \scripts ...

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 most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** '' The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchi ...

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" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicondi ...

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 measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...

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

distance matrix In mathematics, computer science and especially graph theory, a distance matrix is a square matrix In mathematics, a square matrix is a matrix with the same number of rows and columns. An ''n''-by-''n'' matrix is known as a square matrix of orde ...

in a

traveling salesman problem The travelling salesman problem (also called the travelling salesperson problem or 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 cit ...

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 In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

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 The European Association for Theoretical Computer Science (EATCS) is an international organization with a European focus, founded in 1972. Its aim is to facilitate the exchange of ideas and results among theoretical computer scientists as well as ...

, volume = 90 , date=October 2006 , issn = 0252-9742 , pages = 43–52 , url = http://alexandria.tue.nl/openaccess/Metis211810.pdf , format = PDF Travelling salesman problem Matrices