Supnick matrix
Encyclopedia
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.
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
and also
A logically equivalent definition is given by Rudolf & Woeginger who in 1995 proved that
The sum matrix is defined in terms of a sequence of n real numbers {αi}:
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.
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).
City College of New York
The City College of the City University of New York is a senior college of the City University of New York , in New York City. It is also the oldest of the City University's twenty-three institutions of higher learning...
, who introduced the notion in 1957 – is a Monge array
Monge array
In computer science, Monge arrays, or Monge matrices, are mathematical objects named for their discoverer, the French mathematician Gaspard Monge....
which is also a symmetric matrix.
Mathematical definition
A Supnick matrix is a square Monge arrayMonge array
In computer science, Monge arrays, or Monge matrices, are mathematical objects named for their discoverer, the French mathematician Gaspard Monge....
that is symmetric around the main diagonal.
An n-by-n matrix
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
is a Supnick matrix if, for all i, j, k, l such that if
and then
and also
A logically equivalent definition is given by Rudolf & Woeginger who in 1995 proved that
- A matrix is a Supnick matrix iffIFFIFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...
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}:
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
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
produces a new Supnick matrix (Deineko and Woeginger 2006).
If the distance matrix
Distance matrix
In mathematics, computer science and graph theory, a distance matrix is a matrix containing the distances, taken pairwise, of a set of points...
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).
Further reading
- 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).