Collision Analysis Matrix¶
Analysis matrix — instantiates Preimage Set Characterization
Cross-tabulates inputs against outputs to expose where distinct inputs collide on the same output and where the mapping's uniqueness fails.
A Collision Analysis Matrix lays inputs along one axis and outputs along the other and marks where each input lands, so the structure of many-to-one behavior becomes visible at a glance. Its defining question is qualitative and positional: which inputs share an output, and does any output have more than one input pointing at it? Wherever a column collects two or more marks, the mapping is non-injective there — uniqueness fails — and the matrix names the specific colliding inputs, not merely their count. It is the mechanism that turns "outputs are probably many-to-one" into a concrete, inspectable map of who collides with whom, which is exactly what you need before assuming an output has a single source.
Example¶
A security team audits a password-hashing scheme by building a Collision Analysis Matrix over a test corpus: candidate passwords down the rows, their truncated hash values across the columns. Most columns hold a single mark — those passwords hash uniquely within the sample. But three columns light up with multiple marks: password1, Password1, and a third unrelated string all land on the same truncated hash. The matrix names them side by side.
That structural finding is the product. It is not "there are collisions" as a headline — it is these specific inputs collide here, which tells the team the truncation is destroying distinctions it was assumed to preserve, and lets them show, concretely, that treating a hash as a unique fingerprint of its input is unsafe for this scheme. The colliding cells are where the injective assumption breaks, made visible input-by-input.
How it works¶
- Lay out the cross-tabulation. Put candidate inputs on one axis and output values on the other; each input contributes a mark in the column of the output it maps to.
- Read the columns for multiplicity. Any column with two or more marks is a collision — an output with a non-singleton preimage; name the inputs that share it.
- Score uniqueness. A mapping is injective over the sample exactly when every column holds at most one mark; the matrix's column profile is the injectivity verdict.
- Cluster the collision patterns. Group columns by how they collide (near-duplicates, structural aliasing, coincidences) so the kind of uniqueness failure, not just its presence, is legible.
Tuning parameters¶
- Output resolution — how finely output values are bucketed into columns. Coarser buckets manufacture collisions (distinct outputs merged); finer buckets hide real ones (near-equal outputs split apart). This dial decides what even counts as a collision.
- Input coverage — which inputs get rows. A matrix over a sample shows the collisions present in that sample; expanding the rows can reveal collisions the sample missed but costs space and compute.
- Marking rule — exact-match cells versus tolerance-banded "near-collision" marks. Bands surface almost-collisions worth worrying about but blur the clean injectivity verdict.
- Ordering / clustering — how rows and columns are sorted. Good ordering makes collision blocks jump out visually; poor ordering scatters them and hides the structure.
When it helps, and when it misleads¶
Its strength is making non-injectivity concrete and located: instead of an abstract warning that a mapping might be many-to-one, it shows the exact inputs that coincide — the pigeonhole reality[n1] that whenever inputs outnumber output buckets, some column must collect more than one.
Its failure mode is that the matrix's verdict is only as honest as its resolution and coverage: choose the output buckets too coarse and you conjure collisions that do not exist at full precision; choose the input rows too sparse and you certify a "unique" mapping whose collisions live entirely among the inputs you left out. The classic misuse is reading a clean matrix over a convenient sample as proof of global injectivity. The guarding discipline is to fix output resolution to the decision's real tolerance and to state the input coverage plainly, so a "no collisions" reading is scoped to the rows and buckets that actually produced it.
How it implements the components¶
collision_and_multiplicity_check— its core: the located record of which distinct inputs share an output, read straight off the columns.inverse_uniqueness_test— the column profile is the injectivity verdict; single-mark columns pass, multi-mark columns fail and name the offenders.
It does not implement uncertainty_and_unknown_region or sampling_or_search_strategy — quantifying the multiplicity as a per-output count and reasoning about the confidence of that number is the job of Fiber Cardinality Count, its nearest twin; the matrix shows which inputs collide, while the count reports how many do. Naming the discarded distinction as a projection_loss_note is Output-to-Input Traceback Map's role.
Related¶
- Instantiates: Preimage Set Characterization — the matrix supplies the honest, located multiplicity check that stops a many-to-one output from being read as single-source.
- Consumes: Inverse Lookup Query or Constraint-Solver Backsolve supplies the candidate inputs the matrix cross-tabulates.
- Sibling mechanisms: Inverse Lookup Query · Constraint-Solver Backsolve · Predicate Satisfaction Filter · Output-to-Input Traceback Map · Fiber Cardinality Count · Sensitivity-to-Mapping-Change Review · Preimage Table · Witness and Counterexample Set
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Cross-tabulates inputs against outputs to expose where distinct inputs collide on the same output and where the mapping's uniqueness fails, making its operative form a computation, comparison, model, or analytic representation used to infer, estimate, or choose.
Independent corroboration: The frozen evidence defines Collision Analysis Matrix as 'Cross-tabulates inputs against outputs to expose where distinct inputs collide on the same output and where the mapping's uniqueness fails', so its operative form is Analysis, Modeling & Optimization.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Mathematics
Origin pattern: Single lineage
Present-day reach: Universal
Rationale: Set theory and function analysis formalized injectivity through preimage sets and distinct inputs mapping to a common output.
Related originating lineages:
- Computer Science & Software Engineering — Data and algorithm analysis operationalize collision tables over finite mappings.
Review resolution: Both reviewers agree on mathematics as primary. Reading the source mechanism confirms that its defining operation belongs to that lineage; the final record retains computer_science only where it materially formed the mechanism and keeps present-day application breadth separate from provenance.
Encyclopedia synthesis: The exact catalogued form synthesizes established practice rather than reproducing a single standard historical label.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] The pigeonhole principle: if more items are placed into fewer containers than there are items, at least one container holds more than one. It is the structural guarantee behind collisions — whenever a mapping's inputs outnumber its output buckets, some output must have a non-singleton preimage. ↩