FA-15381 / Numerics / Open access

Rational row reduction: other row elimination · case 01

The exact rational row reduction result violates the stated contract at other row elimination.

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

ROOT CAUSE

The other row elimination step uses a[i][j]+va[r][j] instead of a[i][j]-va[r][j].

VERIFIED REPAIR

Use a[i][j]-v*a[r][j] at the other row elimination step.

Unsuccessful approach: The partial repair a[i][j]-a[r][j] still violates the other row elimination 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 = [[([[1, 0], [2, -2]], [[[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]]]), ([[2, -1]], [[[1, 1], [-1, 2]]]), ([[1, 1]], [[[1, 1], [1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[-2, 0]], [[[1, 1], [0, 1]]]), ([[0, 1]], [[[0, 1], [1, 1]]])], [([[2, 1], [-2, 0]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[2, 0], [-2, 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, 1]], [[[0, 1], [1, 1]]]), ([[-2, -1]], [[[1, 1], [1, 2]]]), ([[-2, -1]], [[[1, 1], [1, 2]]]), ([[0, -1]], [[[0, 1], [1, 1]]])], [([[2, 0], [-2, 1]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[-1, -1], [-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]]]), ([[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, -2], [-1, 0]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[1, 0], [2, -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]]]), ([[-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, -2]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[0, 0], [-1, 2]], [[[1, 1], [-2, 1]], [[0, 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]]]), ([[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 fixture	Actual	Expected	Outcome
explicit oracle 0	`[[[1, 1], [0, 1]], [[-2, 1], [1, 1]]]`	`[[[1, 1], [0, 1]], [[0, 1], [1, 1]]]`	Failed
explicit oracle 1	`[[[0, 1], [0, 1]]]`	`[[[0, 1], [0, 1]]]`	Passed
explicit oracle 2	`[[[3, 1], [-6, 1], [-1, 1], [3, 2]], [[0, 1], [1, 1], [0, 1], [-1, 2]], [[-4, 1], [10, 1], [1, 1], [-1, 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]]]`	Failed
explicit oracle 3	`[[[1, 1], [-1, 2]]]`	`[[[1, 1], [-1, 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	`[[[1, 1], [0, 1]]]`	`[[[1, 1], [0, 1]]]`	Passed
explicit oracle 7	`[[[0, 1], [1, 1]]]`	`[[[0, 1], [1, 1]]]`	Passed

SHA-256 / 798d2a812c0a01841a4c619dd7923dacb053f42ed72fb9a980cf5b56be42a698

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/d for v in a[r]]
     for i in range(rows):
      if i==r:continue
      v=a[i][c]
      a[i]=[a[i][j]-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 = [[([[1, 0], [2, -2]], [[[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]]]), ([[2, -1]], [[[1, 1], [-1, 2]]]), ([[1, 1]], [[[1, 1], [1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[-2, 0]], [[[1, 1], [0, 1]]]), ([[0, 1]], [[[0, 1], [1, 1]]])], [([[2, 1], [-2, 0]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[2, 0], [-2, 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, 1]], [[[0, 1], [1, 1]]]), ([[-2, -1]], [[[1, 1], [1, 2]]]), ([[-2, -1]], [[[1, 1], [1, 2]]]), ([[0, -1]], [[[0, 1], [1, 1]]])], [([[2, 0], [-2, 1]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[-1, -1], [-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]]]), ([[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, -2], [-1, 0]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[1, 0], [2, -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]]]), ([[-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, -2]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[0, 0], [-1, 2]], [[[1, 1], [-2, 1]], [[0, 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]]]), ([[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 fixture	Actual	Expected	Outcome
explicit oracle 0	`[[[3, 2], [-1, 1]], [[-1, 2], [1, 1]]]`	`[[[1, 1], [0, 1]], [[0, 1], [1, 1]]]`	Failed
explicit oracle 1	`[[[0, 1], [0, 1]]]`	`[[[0, 1], [0, 1]]]`	Passed
explicit oracle 2	`[[[1, 15], [41, 6], [-17, 10], [137, 15]], [[-26, 15], [28, 3], [-4, 5], [98, 15]], [[4, 3], [-25, 3], [1, 1], [-22, 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]]]`	Failed
explicit oracle 3	`[[[1, 1], [-1, 2]]]`	`[[[1, 1], [-1, 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	`[[[1, 1], [0, 1]]]`	`[[[1, 1], [0, 1]]]`	Passed
explicit oracle 7	`[[[0, 1], [1, 1]]]`	`[[[0, 1], [1, 1]]]`	Passed

SHA-256 / 9c9a4adaed5d140adaaeaf78c3906a95e32d12a6697e7f7f44581beedb341ffe

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 = [[([[1, 0], [2, -2]], [[[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]]]), ([[2, -1]], [[[1, 1], [-1, 2]]]), ([[1, 1]], [[[1, 1], [1, 1]]]), ([[0, 0]], [[[0, 1], [0, 1]]]), ([[-2, 0]], [[[1, 1], [0, 1]]]), ([[0, 1]], [[[0, 1], [1, 1]]])], [([[2, 1], [-2, 0]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[2, 0], [-2, 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, 1]], [[[0, 1], [1, 1]]]), ([[-2, -1]], [[[1, 1], [1, 2]]]), ([[-2, -1]], [[[1, 1], [1, 2]]]), ([[0, -1]], [[[0, 1], [1, 1]]])], [([[2, 0], [-2, 1]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[-1, -1], [-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]]]), ([[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, -2], [-1, 0]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[1, 0], [2, -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]]]), ([[-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, -2]], [[[1, 1], [0, 1]], [[0, 1], [1, 1]]]), ([[0, 0], [-1, 2]], [[[1, 1], [-2, 1]], [[0, 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]]]), ([[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 fixture	Actual	Expected	Outcome
explicit oracle 0	`[[[1, 1], [0, 1]], [[0, 1], [1, 1]]]`	`[[[1, 1], [0, 1]], [[0, 1], [1, 1]]]`	Passed
explicit oracle 1	`[[[0, 1], [0, 1]]]`	`[[[0, 1], [0, 1]]]`	Passed
explicit oracle 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], [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 3	`[[[1, 1], [-1, 2]]]`	`[[[1, 1], [-1, 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	`[[[1, 1], [0, 1]]]`	`[[[1, 1], [0, 1]]]`	Passed
explicit oracle 7	`[[[0, 1], [1, 1]]]`	`[[[0, 1], [1, 1]]]`	Passed

SHA-256 / bca184fac01fd928b6f543e12362ff4a244011cbfd35ade40a4c284825df5526

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.114896+00:00.

Case digest / bfb41b2b84de601d3e65e2f0e797c47deb453107c2de205f94423ce17d641557