Skip to content

Supnick Matrix

A symmetric square Monge matrix, under a stated diagonal convention, with ordered quadrangle inequalities.

Version
v1 · 2026-09-28 · History
Domain-specific #
12383
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomains
Matrix Theory, Monge Properties → Mathematics

Core Idea

A Supnick matrix, in the complete-matrix convention used here, combines symmetry with the Monge quadrangle inequality on a common ordering of rows and columns. For every earlier row i and later row r, and earlier column j and later column s, the aligned-entry sum c(i,j)+c(r,s) is no larger than the cross sum c(i,s)+c(r,j). This is a testable matrix class, not simply a distance table with a memorable name.

The class has an additive structure: sum matrices and nonnegative combinations of paired corner blocks generate it. In traveling-salesperson problems whose cost matrix qualifies, an optimal tour can be chosen in a fixed order of odd indices upward followed by even indices downward. The benefit is conditional on the matrix property and on the declared diagonal convention, not a shortcut for arbitrary TSP instances.

Structural Signature

Sig role-phrases:

  • Ordered index set — Supplies a common order 1,...,n for rows and columns; arbitrary relabeling need not preserve the inequalities. It is constitutive. Counterfactual: The test is not invariant under every city permutation.
  • Real square matrix — Holds the numeric entries c(i,j), including diagonal under this convention. It is constitutive. Counterfactual: A rectangular non-symmetric Monge array is not the same named class.
  • Symmetry constraint — Requires c(i,j)=c(j,i) for all indices. It is constitutive. Counterfactual: Monge inequality alone does not imply symmetry.
  • Monge quadrangle constraint — Requires c(i,j)+c(r,s) ≤ c(i,s)+c(r,j) for every i<r and j<s. It is constitutive. Counterfactual: One violated ordered 2-by-2 inequality excludes the matrix.
  • Cone decomposition — Represents class members as sum matrices plus nonnegative LL-UR block combinations. It is central. Counterfactual: A negative block coefficient is not licensed by this characterization.
  • Structured optimization consequence — Connects a qualifying TSP cost matrix to a fixed optimal tour order. It is derived. Counterfactual: The theorem does not solve unrestricted TSP instances.

What It Is Not

  • Not any symmetric matrix. It must also pass all ordered quadrangle inequalities.
  • Not any Monge matrix. Symmetry on the square index set is required.
  • Not permutation-invariant without qualification. The row/column order matters.
  • Not a general TSP solution. The fixed-tour theorem applies to structured cost instances.
  • Closest near-miss. The diagonal may be omitted or completed in some later TSP formulations; whether that relaxed variant is intended must be declared before comparing theorems or examples.

Scope of Application

  • Combinatorial optimization. Identify TSP instances for which a fixed optimal-tour order is justified.
  • Matrix-cone analysis. Decompose a qualifying matrix into sum and LL-UR generators.
  • Algorithm testing. Construct positive and negative cases for symmetric-Monge recognition.
  • Mathematical exposition. Keep complete and unspecified-diagonal variants separate.

Clarity

Symmetry says c(i,j)=c(j,i); Monge says an inequality holds on each ordered two-row, two-column selection. Neither condition alone suffices. A sum matrix has all inequalities tight, while a corner-block generator can make some strict. State whether the diagonal is a tested entry or a free completion.

Manages Complexity

An n-by-n cost table appears to contain n-squared unrelated numbers. The ordered inequalities and cone generators compress it into a structured class with theorem-backed optimization consequences. That compression is invalid if one reorders cities silently, skips a required inequality, or imports a theorem from a different diagonal convention.

Abstract Reasoning

  1. Fix a common index order and whether diagonal entries are specified.
  2. Check square real entries and c(i,j)=c(j,i).
  3. Test ordered Monge inequalities, including every required 2-by-2 selection.
  4. If useful, express the matrix as sum component plus nonnegative corner blocks.
  5. Only then invoke a theorem for a TSP instance whose cost matrix satisfies those conditions.
  6. Distinguish the result from the general unrestricted traveling-salesperson problem.

Knowledge Transfer

The quadrangle structure can guide other array algorithms and decomposition arguments, while a TSP cost table is one domain of use. A spreadsheet grid or arbitrary graph distance does not become a Supnick matrix by being square; the exact numerical inequalities and order remain necessary. The general idea of exploiting structure transfers, but the named theorem does not cross that boundary.

Examples

Canonical

Woeginger gives sum matrices c(i,j)=alpha_i+alpha_j as a generator of the Supnick cone. Taking alpha=(0,1,2) yields [[0,1,2],[1,2,3],[2,3,4]]. It is symmetric; for every ordered i<r and j<s, both sides of c(i,j)+c(r,s)≤c(i,s)+c(r,j) equal the same four-alpha sum. Thus every required inequality is tight, and the matrix is a pure sum component with zero LL-UR coefficients. The numbers are an explicit checked construction from Woeginger's family, not a table claimed to be printed in his paper.

Mapped back: Ordered index set → indices 1<2<3; Real square matrix → 3-by-3 numeric array including diagonal; Symmetry constraint → alpha_i+alpha_j equals alpha_j+alpha_i; Monge quadrangle constraint → every ordered comparison is equality; Cone decomposition → pure sum-matrix component, zero block coefficients; Structured optimization consequence → the class admits a fixed-order TSP result under the theorem's hypotheses.

Applied / In Practice

Rudolf and Woeginger's 1995 research applied their extremal-ray/cone decomposition of Monge matrices to derive a new proof of Supnick's fixed optimal-tour result for qualifying traveling-salesperson cost matrices. The matrix is a symmetric ordered Monge cost array represented through sum and nonnegative LL-UR components; the tour theorem is the derived consequence. This is an attested proof application of the class, not a numeric matrix printed by the authors or a claim of real transport deployment.

Mapped back: Ordered index set → common city order required by the theorem; Real square matrix → symmetric square TSP cost matrix in the studied class; Symmetry constraint → matrix equals its transpose; Monge quadrangle constraint → ordered inequality defining the studied matrix class; Cone decomposition → sum-matrix plus nonnegative LL-UR generators used in the proof; Structured optimization consequence → Supnick fixed optimal-tour result rederived by the authors.

Structural Tensions

T1 — Complete-Matrix Test versus Tour-Cost Diagonal Freedom. Testing a fully specified matrix gives an unambiguous algebraic class, but a TSP tour never traverses diagonal costs; leaving them free can broaden useful data while demanding an explicit completion or different theorem hypothesis.

Diagnostic: Is the diagonal tested as data or treated as irrelevant tour bookkeeping?

T2 — Structural Restriction versus Broader Instance Coverage. Strong symmetry-plus-Monge restrictions yield a fixed optimal tour but exclude many cost tables; weakening them covers more instances while forfeiting this simple guarantee.

Diagnostic: Is the gain in solvability worth the restrictive hypothesis for this application?

Structural–Framed Character

Supnick Matrix is structural-leaning within formal mathematics: membership is checked by numerical shape, symmetry, order, and quadrangle inequalities rather than an empirical substrate. Evaluative weight: satisfying the inequalities is a formal fact, not a judgment that the matrix or a resulting algorithm is universally better. Human-practice-bound: mathematicians choose the order and diagonal convention; once those are fixed, the inequalities and consequences do not depend on a user's preference. Institutional origin: the named class and theorem come from mathematical research, not an agency's cataloging decision that could make a violating array qualify. Vocabulary travels: matrix, constraint, and structural exploitation appear widely, but the real square carrier and ordered Monge relation must be checked literally. Import versus recognize: a different matrix satisfying the same convention and inequalities is another instance; a merely square table or visually regular graph is analogy.

The portable skeleton is a structured carrier whose declared constraints enable deductions, a future-prime candidate at this level; the live prime Constraint is a related comparison, not an asserted parent. The actual strict parent is the domain-specific Matrix kind. Symmetry, ordered entries, and the complete-matrix Monge condition narrow that parent. Its character: an exact matrix subclass whose algorithmic uses depend on its full numerical conditions.

Structural Core vs. Domain Accent

What is skeletal. A carrier is restricted by explicit relations so that properties or algorithms can be derived from the restriction rather than from arbitrary instances. This constraint-to-consequence move is portable, but it is thinner than the named matrix class and is not a new asserted DAG parent.

What is domain-bound. Supnick membership requires a real square matrix under a fixed index order, symmetry, and the relevant Monge quadrangle inequalities, with a stated diagonal convention. Those numerical conditions make its TSP theorem and cone decomposition applicable in their own setting; a square table without them fails the type test.

Why this does not clear the prime bar. The exact inequality and ordered matrix carrier do not travel to every constrained system. The current strict parent is domain-specific Matrix; broader reasoning about constraints can be recognized elsewhere only after its carrier and consequences are re-established. Calling any conveniently structured array “Supnick” would import the name by analogy and lose the test that defines it.

This entry is a kind of Matrix.

  • Proposed strict parent. The live domain-specific Matrix node is a rectangular numeric array with arithmetic and representational roles. A Supnick matrix is exactly a square real numeric instance with added symmetry and Monge restrictions; thus child→Matrix holds, while generic matrices need not be Supnick.

  • Neighbor. A non-symmetric Monge matrix shares the inequality but fails the symmetry condition; a relaxed unspecified-diagonal Supnick convention needs explicit qualification.

Relationships to Other Abstractions

Local relationship map for Supnick MatrixParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Supnick MatrixDOMAINDomain-specific abstraction: Matrix — is a kind ofMatrixDOMAIN

Current abstraction Supnick Matrix Domain-specific

Parents (1) — more general patterns this builds on

  • Supnick Matrix is a kind of Matrix Domain-specific

    A Supnick matrix is a square real matrix with additional symmetry and Monge constraints.

Hierarchy paths (5) — routes to 5 parentless roots

Neighborhood in Abstraction Space

Supnick Matrix sits in a moderately populated region (54th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Cryptographic & Combinatorial Hardness Problems (5 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • Symmetric matrix. Tell: Does not by itself satisfy ordered Monge inequalities.
  • Monge array. Tell: May be rectangular or asymmetric.
  • Kalmanson matrix. Tell: A distinct indexed TSP cost class with different inequalities and tour theorem.
  • Arbitrary TSP distance matrix. Tell: Does not automatically admit the fixed Supnick tour.

References

The frozen Wikipedia plaintext loses formula symbols. This entry states Woeginger's complete-matrix convention; its small numeric matrices instantiate his sourced generator families. A diagonal-free relaxed convention is noted as a boundary, not silently identified with the same theorem hypotheses. - Rudolf and Woeginger (1995), The cone of Monge matrices: extremal rays and applications — original published cone characterization and proof application to Supnick's TSP result, not a numeric transport deployment.