DONE: exact matrix-ring source-insertion criterion for singular demands

[aliromman]

DONE: exact one-insertion feasibility for singular and nonsingular matrix-ring dirty demands.

Let R=Mat_d(F) for any field F and let k>=2 dirty output rows be available. Every nonzero demand list has a one-source-insertion word. More precisely, a specified insertion coefficient B works if and only if its kernel equals the kernel of the vertically stacked demand matrix. This is an exact algebraic interface statement, not a physical cost or kappa claim.

Contract and sources. Use arbitrary independent rows a_i and a preserved source p in R^w. All elementary block-row additions A_i<-A_i+CA_j, i!=j, and insertions A_i<-A_i+Bp are allowed, with coefficients on the left. Every original dirt column must return. There are no extra rows, clearing or observations. Coefficient production and every row addition remain paid.

The noncommutative unit-demand contract is credited to @petalas's PR #4916 and its pinned source, including Ross Richardson's PR #3121 lineage. Lee-phys's PR #5139 supplies the separate finite-commutative principal-ideal criterion. This result changes the ring to a full matrix ring and allows arbitrary singular demands. PR #5171 is neighboring singular matrix-chain-ring work in a different common-update contract. None of those executables is reused.

Base: canonical main ff3cc58e370d0f678e529246f8c73e8094e18fcf, priority revision 7.

Exact criterion. For desired coefficients Lambda_i in Mat_d(F), form the kd-by-d matrix

S = vertical_stack(Lambda_0,...,Lambda_(k-1)).

Assume S!=0. A word with exactly one nonzero insertion P_i(B), and otherwise only the allowed row additions, exists if and only if

ker(B) = ker(S).

Equivalently, B and S have the same row space. All feasible B have rank(S), not merely rank at least rank(S). The insertion can occur at any specified row. Since the row space of S has dimension at most d, put one of its bases in the rows of a d-by-d B and fill the other rows with zero. Such a B always exists. Nonzero demand therefore has source-insertion minimum one. Zero demand has minimum zero.

Necessity. The source column before the insertion is zero. If C is the product of the later block-row additions, the final source matrix is CE_iB, where E_i embeds one d-row block. C is invertible and E_i is injective. Thus its kernel is exactly ker(B). Equality with S proves the condition. This is a kernel invariant, not an argument that independent scalar entries can be inserted for free.

Sufficiency. Suppose ker(B)=ker(S), and put U=E_iB. The rule Ux -> Sx is well-defined and is an isomorphism from im(U) to im(S). Extend it to an invertible map C on F^(kd). Its determinant can be adjusted to one without changing its action on im(U): compose on the output with a map that is identity on im(S) and scales one complementary basis vector. Such a vector exists because rank(S)<=d<kd. Hence choose C in SL_(kd)(F) with CU=S.

Every scalar elementary transvection between coordinates in different blocks is one allowed block-row addition, with a coefficient matrix having a single nonzero entry. For two different coordinates a,b in the same block, choose a coordinate c in another existing block. The identity

[T_ac(t), T_cb(1)] = T_ab(t)

expresses the required within-block transvection using four allowed additions. The commutator here is XYX^(-1)Y^(-1); t=0 needs no call. There is no extra scratch block.

Scalar transvections generate SL_N(F). One elementary proof is Gaussian elimination with row additions, signed swaps and paired diagonal scalings. A signed swap is w(1), where w(t)=T_12(t) T_21(-t^(-1)) T_12(t); and diag(t,t^(-1))=w(t)w(-1). Thus all the elimination operations are products of transvections. The block gates therefore generate the chosen C. Execute a word for C^(-1), then P_i(B), then the word for C. The dirt returns to identity and the source column is S. This proves the criterion over any field. It does not claim a shortest block word.

A singular-demand warning. In two rows over Mat_2(F), take Lambda_0=E_00 and Lambda_1=E_11. Both demands have rank one, but S has rank two. Every one-insertion coefficient B must therefore be invertible. Choosing B=I works: C consists chronologically of E_10(E_11), then E_01(-E_11). Its conjugated insertion has one source call and four row additions.

More generally, with k=d>=2 and Lambda_i=E_ii, all demands have rank one and every one-insertion coefficient must have rank d. A construction uses C made of E_i0(E_ii) for i>0 followed by E_0i(-E_ii) for i>0. Conjugation costs 4(d-1) row additions plus one insertion. Under uniform complete abstract prices mu per insertion and c per row addition, this construction beats d direct insertions exactly when mu>4c. No physical coefficient-independent price assumption is established here.

Exact verification. The checker below independently enumerates the elementary block-column action and reconstructs full restoring words. Its contexts are two and three rows over Mat_2(F_2), and two rows over Mat_2(F_3). It covers every nonzero demand tuple: 10,910 in total. Thirteen representative insertion row spaces seed the searches. Each demand is checked against a separate row-reduction invariant, then its complete original-dirt/source map is replayed. The singular-projector example rejects a rank-one insertion coefficient by the invariant. No predecessor code is imported.

Save as matrix_ring_insertions.py. Both modes passed on CPython 3.12.13:

python3.12 -I -W error -B matrix_ring_insertions.py
python3.12 -I -W error -O -B matrix_ring_insertions.py

Expected output:

PASS_MATRIX_RING_INSERTION contexts=3 nonzero_demands=10910 orbit_roots=13 no_new_kappa

from itertools import product
from collections import deque

def ck(x,s):
 if not x:raise ValueError(s)
def rowspace(rows,q):
 a=[r[:] for r in rows];rank=0
 for j in range(2):
  p=next((i for i in range(rank,len(a)) if a[i][j]),None)
  if p is None:continue
  a[rank],a[p]=a[p],a[rank];u=pow(a[rank][j],-1,q);a[rank]=[u*x%q for x in a[rank]]
  for i in range(len(a)):
   if i!=rank:
    c=a[i][j];a[i]=[(x-c*y)%q for x,y in zip(a[i],a[rank])]
  rank+=1
 return tuple(map(tuple,a[:rank]))
def tables(q):
 elems=list(product(range(q),repeat=4));ids={x:i for i,x in enumerate(elems)}
 add=[[ids[tuple((x+y)%q for x,y in zip(a,b))] for b in elems] for a in elems]
 mul=[[ids[tuple(sum(a[2*i+k]*b[2*k+j] for k in range(2))%q for i in range(2) for j in range(2))] for b in elems] for a in elems]
 neg=[ids[tuple(-x%q for x in a)] for a in elems];one=ids[(1,0,0,1)]
 return elems,add,mul,neg,one
def rows(xs,elems):return [list(elems[x][i:i+2]) for x in xs for i in (0,2)]
def replay(n,b,word,add,mul,neg,one):
 a=[[one if i==j else 0 for j in range(n)]+[0] for i in range(n)]
 for i,j,c in [(i,j,neg[c]) for i,j,c in reversed(word)]:a[i]=[add[x][mul[c][y]] for x,y in zip(a[i],a[j])]
 a[0][-1]=add[a[0][-1]][b]
 for i,j,c in word:a[i]=[add[x][mul[c][y]] for x,y in zip(a[i],a[j])]
 return a
cases=roots=0
for q,n in ((2,2),(2,3),(3,2)):
 elems,add,mul,neg,one=tables(q);size=len(elems);representatives={}
 for b in range(1,size):representatives.setdefault(rowspace(rows((b,),elems),q),b)
 parents={};origins={};todo=deque()
 for key,b in representatives.items():
  x=(b,)+(0,)*(n-1);parents[x]=None;origins[x]=b;todo.append(x);roots+=1
 while todo:
  x=todo.popleft()
  for i in range(n):
   for j in range(n):
    if i==j:continue
    for c in range(1,size):
     y=list(x);y[i]=add[y[i]][mul[c][y[j]]];y=tuple(y)
     if y not in parents:parents[y]=(x,(i,j,c));origins[y]=origins[x];todo.append(y)
 ck(len(parents)==size**n-1,'complete nonzero demand coverage')
 for xs in product(range(size),repeat=n):
  if not any(xs):continue
  b=origins[xs];ck(rowspace(rows(xs,elems),q)==rowspace(rows((b,),elems),q),'exact kernel invariant')
  word=[];x=xs
  while parents[x] is not None:x,g=parents[x];word.append(g)
  word.reverse();out=replay(n,b,word,add,mul,neg,one)
  ck(out==[[one if i==j else 0 for j in range(n)]+[xs[i]] for i in range(n)],'full dirty map')
  cases+=1
 E00=elems.index((1,0,0,0));E11=elems.index((0,0,0,1))
 ck(len(rowspace(rows((E00,E11),elems),q))==2,'singular demands force full rank insertion')
 ck(len(rowspace(rows((E00,),elems),q))==1,'singular coefficient control')
print('PASS_MATRIX_RING_INSERTION contexts=3 nonzero_demands='+str(cases)+' orbit_roots='+str(roots)+' no_new_kappa')

Limits and handoff. The theorem requires all matrix coefficients and all ordered block-row additions. It does not apply to a restricted coefficient alphabet, rank-capped insertions, a general noncommutative ring, or a model with only one output row. It gives feasibility and a rank requirement, not the minimum total tariff. No native coefficient emitter, physical source caller, precision/tape invoice, Lean, Docker or selected cold replay was run. An actual caller must price the potentially full-rank B, the block word and its inverse. The next useful question is whether a named singular-demand caller permits this insertion rank below its direct complete bill.

Overlap checks covered 7,091 current main notes, 328 open PRs and 4,533 Discussion records with complete pagination, plus targeted all-state PR searches. Arbitrary diffs and unpublished work remain outside coverage. Prepared by @aliromman with OpenAI Codex assistance. The linear extension and elementary-matrix facts are classical. No external priority, independent human review or proof-kernel review is claimed. New text and code: Apache-2.0.