Supnick Matrix¶
A symmetric square Monge matrix, under a stated diagonal convention, with ordered quadrangle inequalities.
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.
Scope of Application¶
This entry uses the complete symmetric-Monge convention; diagonal-free TSP variants require explicit qualification.
- 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¶
This is a square matrix with both symmetry and an ordered Monge inequality. Either property alone is insufficient. The numerical sum and corner-block examples instantiate generators described by Woeginger; they are not quoted tables. Some TSP literature omits diagonal costs, so any comparison must state that convention.
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¶
Fix the common index order and diagonal convention, check symmetry, then check every required ordered two-by-two inequality. Only for a qualifying cost matrix use the special fixed-tour or cone-decomposition results.
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.
Relationships to Other Abstractions¶
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
- Supnick Matrix → Matrix → Tensor → Transformation → Function (Mapping)
- Supnick Matrix → Matrix → Linearity
- Supnick Matrix → Matrix → Representation → Abstraction
- Supnick Matrix → Matrix → Tensor → Invariance
- Supnick Matrix → Matrix → Tensor → Vector Space → Set and Membership
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
- Short Integer Solution Problem — 0.86
- Diagonal Matrix — 0.86
- Perfect measure — 0.86
- Number of groups of a given order — 0.86
- Distance Matrix — 0.85
Computed from structural-signature embeddings · 2026-10-08