mathematics

Supnick matrix

Supnick matrix is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Supnick matrix rather than just read about it. In short: 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. Mathematical definition A Supnick matrix is a square Monge array that is symmetric around the main diagonal.

Key takeaways

Supnick matrix belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Supnick matrix to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Supnick matrix from memory before moving on to harder problems.

Reference excerpt

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.

Mathematical definition A Supnick matrix is a square Monge array 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

1 ≤ i < k ≤ n {\displaystyle 1\leq i<k\leq n} and 1 ≤ j < l ≤ n {\displaystyle 1\leq j<l\leq n}

then

a i j + a k l ≤ a i l + a k j {\displaystyle a_{ij}+a_{kl}\leq a_{il}+a_{kj}\,}

and also

a i j = a j i . {\displaystyle 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. The sum matrix is defined in terms of a sequence of n real numbers {αi}:

S = [ s i j ] = [ α i + α j ] ; {\displaystyle 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 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 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).

References Supnick, Fred (July 1957). "Extreme Hamiltonian Lines". Annals of Mathematics. Second Series. 66 (1): 179–201. doi:10.2307/1970124. JSTOR 1970124. Woeginger, Gerhard J. (June 2003). "Computational Problems without Computation" (PDF). Nieuwarchief. 5 (4): 140–147. Deineko, Vladimir G.; Woeginger, Gerhard J. (October 2006). "Some problems around travelling salesmen, dart boards, and euro-coins" (PDF). Bulletin of the European Association for Theoretical Computer Science. 90. EATCS: 43–52. ISSN 0252-9742.

Worked examples

Example 1 — a first encounter with Supnick matrix

Start with the simplest possible case. Write down what Supnick matrix claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Supnick matrix before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Supnick matrix ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Supnick matrix

In research: Supnick matrix appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Supnick matrix in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Supnick matrix is common in secondary-school and first-year university syllabi. It links to neighbouring topics Matrices (mathematics), Travelling salesman problem, so understanding it makes those chapters shorter.
In everyday life: Look for Supnick matrix outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Supnick matrix in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Supnick matrix means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Supnick matrix out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Supnick matrix in simple terms?

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. Mathematical definition A Supnick matrix is a square Monge array that is symmetric around the main diagonal.

Why does Supnick matrix matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Supnick matrix?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Supnick matrix.