FAILURE MAP
← Case archive

FA-15376 / Numerics / Open access

Rational row reduction: pivot row normalization · case 01

The exact rational row reduction result violates the stated contract at pivot row normalization.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The pivot row normalization step uses v*d instead of v/d.

VERIFIED REPAIR

Use v/d at the pivot row normalization step.

Unsuccessful approach: The partial repair v/abs(d) still violates the pivot row normalization invariant.

Case contract

Input nonempty rectangular integer matrix; return RREF with each rational entry [p,q].

Why this case matters

Exact discrete arithmetic with observable algorithmic state; no floating point approximation is used.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    a=[list(map(Fraction,r)) for r in x];rows=len(a);cols=len(a[0]);r=0
    for c in range(cols):
     if r==rows:break
     pivot=next((i for i in range(r,rows) if a[i][c]!=0),None)
     if pivot is None:continue
     a[r],a[pivot]=a[pivot],a[r]
     d=a[r][c]
     if not d:return None
     a[r]=[v*d for v in a[r]]
     for i in range(rows):
      if i==r:continue
      v=a[i][c]
      a[i]=[a[i][j]-v*a[r][j] for j in range(cols)]
     r=r+1
    return [[[v.numerator,v.denominator] for v in row] for row in a]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[2, -1]], [[[1, 1], [-1, 2]]]), ([[-2, 0]], [[[1, 1], [0, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[1, 1]], [[[1, 1], [1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 1]], [[[0, 1], [1, 1]]]), ([[2, 1]], [[[1, 1], [1, 2]]])], [([[-2, 0]], [[[1, 1], [0, 1]]]), ([[-1, 1]], [[[1, 1], [-1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[0, 1]], [[[0, 1], [1, 1]]]), ([[-2, -1]], [[[1, 1], [1, 2]]]), ([[-2, -1]], [[[1, 1], [1, 2]]]), ([[0, -1]], [[[0, 1], [1, 1]]])], [([[2, 1]], [[[1, 1], [1, 2]]]), ([[0, -1]], [[[0, 1], [1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[2, 2]], [[[1, 1], [1, 1]]]), ([[2, -1]], [[[1, 1], [-1, 2]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[1, -1]], [[[1, 1], [-1, 1]]])], [([[-2, -1]], [[[1, 1], [1, 2]]]), ([[-1, 0]], [[[1, 1], [0, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[-1, 1], [-1, 0]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[0, 0], [-1, 2]], [[[1, 1], [-2, 1]], [[0, 1], [0, 1]]]), ([[-2, 1], [1, -2]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[-1, 0], [0, 0]], [[[1, 1], [0, 1]], [[0, 1], [0, 1]]])], [([[2, -2]], [[[1, 1], [-1, 1]]]), ([[0, -1]], [[[0, 1], [1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[0, -2], [2, 0]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[-1, -2], [0, 1]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[-2, 0], [-2, 0]], [[[1, 1], [0, 1]], [[0, 1], [0, 1]]]), ([[0, 0], [0, -1]], [[[0, 1], [1, 1]], [[0, 1], [0, 1]]])]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
explicit oracle 0[[[4, 1], [-2, 1]]][[[1, 1], [-1, 2]]]Failed
explicit oracle 1[[[4, 1], [0, 1]]][[[1, 1], [0, 1]]]Failed
explicit oracle 2[[[0, 1], [0, 1]]][[[0, 1], [0, 1]]]Passed
explicit oracle 3[[[-8, 1], [6, 1], [6, 1], [-24, 1]], [[0, 1], [4, 1], [0, 1], [-2, 1]], [[-6, 1], [0, 1], [4, 1], [-12, 1]]][[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]Failed
explicit oracle 4[[[1, 1], [1, 1]]][[[1, 1], [1, 1]]]Passed
explicit oracle 5[[[0, 1], [0, 1]]][[[0, 1], [0, 1]]]Passed
explicit oracle 6[[[0, 1], [1, 1]]][[[0, 1], [1, 1]]]Passed
explicit oracle 7[[[4, 1], [2, 1]]][[[1, 1], [1, 2]]]Failed

SHA-256 / 0fa4fc2860911394d507af821493ccf20a5076ba18f5f74f2dc35d01e5b5df65

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    a=[list(map(Fraction,r)) for r in x];rows=len(a);cols=len(a[0]);r=0
    for c in range(cols):
     if r==rows:break
     pivot=next((i for i in range(r,rows) if a[i][c]!=0),None)
     if pivot is None:continue
     a[r],a[pivot]=a[pivot],a[r]
     d=a[r][c]
     if not d:return None
     a[r]=[v/abs(d) for v in a[r]]
     for i in range(rows):
      if i==r:continue
      v=a[i][c]
      a[i]=[a[i][j]-v*a[r][j] for j in range(cols)]
     r=r+1
    return [[[v.numerator,v.denominator] for v in row] for row in a]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[2, -1]], [[[1, 1], [-1, 2]]]), ([[-2, 0]], [[[1, 1], [0, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[1, 1]], [[[1, 1], [1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 1]], [[[0, 1], [1, 1]]]), ([[2, 1]], [[[1, 1], [1, 2]]])], [([[-2, 0]], [[[1, 1], [0, 1]]]), ([[-1, 1]], [[[1, 1], [-1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[0, 1]], [[[0, 1], [1, 1]]]), ([[-2, -1]], [[[1, 1], [1, 2]]]), ([[-2, -1]], [[[1, 1], [1, 2]]]), ([[0, -1]], [[[0, 1], [1, 1]]])], [([[2, 1]], [[[1, 1], [1, 2]]]), ([[0, -1]], [[[0, 1], [1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[2, 2]], [[[1, 1], [1, 1]]]), ([[2, -1]], [[[1, 1], [-1, 2]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[1, -1]], [[[1, 1], [-1, 1]]])], [([[-2, -1]], [[[1, 1], [1, 2]]]), ([[-1, 0]], [[[1, 1], [0, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[-1, 1], [-1, 0]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[0, 0], [-1, 2]], [[[1, 1], [-2, 1]], [[0, 1], [0, 1]]]), ([[-2, 1], [1, -2]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[-1, 0], [0, 0]], [[[1, 1], [0, 1]], [[0, 1], [0, 1]]])], [([[2, -2]], [[[1, 1], [-1, 1]]]), ([[0, -1]], [[[0, 1], [1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[0, -2], [2, 0]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[-1, -2], [0, 1]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[-2, 0], [-2, 0]], [[[1, 1], [0, 1]], [[0, 1], [0, 1]]]), ([[0, 0], [0, -1]], [[[0, 1], [1, 1]], [[0, 1], [0, 1]]])]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
explicit oracle 0[[[1, 1], [-1, 2]]][[[1, 1], [-1, 2]]]Passed
explicit oracle 1[[[-1, 1], [0, 1]]][[[1, 1], [0, 1]]]Failed
explicit oracle 2[[[0, 1], [0, 1]]][[[0, 1], [0, 1]]]Passed
explicit oracle 3[[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]][[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]Passed
explicit oracle 4[[[1, 1], [1, 1]]][[[1, 1], [1, 1]]]Passed
explicit oracle 5[[[0, 1], [0, 1]]][[[0, 1], [0, 1]]]Passed
explicit oracle 6[[[0, 1], [1, 1]]][[[0, 1], [1, 1]]]Passed
explicit oracle 7[[[1, 1], [1, 2]]][[[1, 1], [1, 2]]]Passed

SHA-256 / 7f000db00ea3cd0c6d23695d445a1ec1e0f91d6c9bc84fb4700f96696db45f4b

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    a=[list(map(Fraction,r)) for r in x];rows=len(a);cols=len(a[0]);r=0
    for c in range(cols):
     if r==rows:break
     pivot=next((i for i in range(r,rows) if a[i][c]!=0),None)
     if pivot is None:continue
     a[r],a[pivot]=a[pivot],a[r]
     d=a[r][c]
     if not d:return None
     a[r]=[v/d for v in a[r]]
     for i in range(rows):
      if i==r:continue
      v=a[i][c]
      a[i]=[a[i][j]-v*a[r][j] for j in range(cols)]
     r=r+1
    return [[[v.numerator,v.denominator] for v in row] for row in a]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[2, -1]], [[[1, 1], [-1, 2]]]), ([[-2, 0]], [[[1, 1], [0, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[1, 1]], [[[1, 1], [1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 1]], [[[0, 1], [1, 1]]]), ([[2, 1]], [[[1, 1], [1, 2]]])], [([[-2, 0]], [[[1, 1], [0, 1]]]), ([[-1, 1]], [[[1, 1], [-1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[0, 1]], [[[0, 1], [1, 1]]]), ([[-2, -1]], [[[1, 1], [1, 2]]]), ([[-2, -1]], [[[1, 1], [1, 2]]]), ([[0, -1]], [[[0, 1], [1, 1]]])], [([[2, 1]], [[[1, 1], [1, 2]]]), ([[0, -1]], [[[0, 1], [1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[2, 2]], [[[1, 1], [1, 1]]]), ([[2, -1]], [[[1, 1], [-1, 2]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[1, -1]], [[[1, 1], [-1, 1]]])], [([[-2, -1]], [[[1, 1], [1, 2]]]), ([[-1, 0]], [[[1, 1], [0, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[-1, 1], [-1, 0]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[0, 0], [-1, 2]], [[[1, 1], [-2, 1]], [[0, 1], [0, 1]]]), ([[-2, 1], [1, -2]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[-1, 0], [0, 0]], [[[1, 1], [0, 1]], [[0, 1], [0, 1]]])], [([[2, -2]], [[[1, 1], [-1, 1]]]), ([[0, -1]], [[[0, 1], [1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[0, 2, 0, -1], [2, -1, -1, 2], [1, -2, 0, -2]], [[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]), ([[0, -2], [2, 0]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[-1, -2], [0, 1]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[-2, 0], [-2, 0]], [[[1, 1], [0, 1]], [[0, 1], [0, 1]]]), ([[0, 0], [0, -1]], [[[0, 1], [1, 1]], [[0, 1], [0, 1]]])]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
explicit oracle 0[[[1, 1], [-1, 2]]][[[1, 1], [-1, 2]]]Passed
explicit oracle 1[[[1, 1], [0, 1]]][[[1, 1], [0, 1]]]Passed
explicit oracle 2[[[0, 1], [0, 1]]][[[0, 1], [0, 1]]]Passed
explicit oracle 3[[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]][[[1, 1], [0, 1], [0, 1], [-3, 1]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[0, 1], [0, 1], [1, 1], [-15, 2]]]Passed
explicit oracle 4[[[1, 1], [1, 1]]][[[1, 1], [1, 1]]]Passed
explicit oracle 5[[[0, 1], [0, 1]]][[[0, 1], [0, 1]]]Passed
explicit oracle 6[[[0, 1], [1, 1]]][[[0, 1], [1, 1]]]Passed
explicit oracle 7[[[1, 1], [1, 2]]][[[1, 1], [1, 2]]]Passed

SHA-256 / 89bc258b4d57e6027f90ffdd7355b643ea329c4a933a538c5cbda764d6f2f14d

Verification & scope

A deterministic bounded teaching model. Inputs are restricted to the explicit contract; this is not a production algebra library. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:39:26.038967+00:00.

Case digest / d9b9c4243309ba174f676cc9d7e059269ebca1c319342ca7362ba1a329725f00