Supnick matrix - Citizendia

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. The City College of The City University of New York (known more commonly as the City College of New York or simply City College, CCNY, or colloquially as Monge arrays, or Monge matrices, are mathematical objects used primarily in Computer science. In Linear algebra, a symmetric matrix is a Square matrix, A, that is equal to its Transpose A = A^{T}

Mathematical definition

A Supnick matrix is a square Monge array that is symmetric around the main diagonal. Monge arrays, or Monge matrices, are mathematical objects used primarily in Computer science. In Linear algebra, the main diagonal (sometimes leading diagonal or primary diagonal) of a matrix A is the collection of cells A_{ij}

An n-by-n matrix 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_{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. In Mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries) which may be Numbers or more generally ↔

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). In Mathematics, the real numbers may be described informally in several different ways

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). The Travelling salesman problem ( TSP) in Operations research is a problem in discrete or Combinatorial optimization. NP-hard (nondeterministic Polynomial-time hard in Computational complexity theory, is a class of problems informally "at least as hard as the hardest problems

References

Supnick, Fred (July 1957). "Extreme Hamiltonian Lines". The Annals of Mathematics (2nd series) 66 (1): 179–201.
Woeginger, Gerhard J. (June 2003). "Computational Problems without Computation". Nieuwarchief 5 (4): 140–147.
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).

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |