1 | initial version |

I'm not sure if it is possible to get *all* solutions, but I can show below how to get at least some of them.

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

Now, to reduce the search space we will follow the same idea from my previous answer of fixing the dimension of the matrix span, which, in fact, should be a matrix subring closed under multiplication, and first selecting the basis matrices to fix a subring, and then filter the rest of the matrices based on whether they belong to the subring. Here is implementation of this idea:

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early if the span dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, start_index=0):
'''
Generator for lists of matrices.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
* technical arguments:
* `A_span` - initial span to cover
* `start_index` - starting index in the universe
'''
if M.is_zero():
yield []
if disjoint:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
else:
myU = universe
if A_span is None:
A_span = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
assert A_span.dimension() <= target_dim
if A_span.dimension() == target_dim:
CAND = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) in A_span ]
# print('|CAND|:',len(CAND))
for C in Subsets(CAND): # TODO: use Normaliz
if sum(C) == M:
T = A_span
for c in C:
T = extend_span(T,c)
if T.dimension() > target_dim:
break
else:
yield list(C)
return
for i in range(start_index,len(myU)):
T = extend_span(A_span,myU[i],target_dim)
if T.dimension() > target_dim:
continue
elif T.dimension() <= target_dim: # there is still room for growing dimension
for L in gen_As(M-myU[i], myU, target_dim, disjoint, T, i+1):
yield [myU[i]] + L
```

It turns out that for a given matrix, there are no solutions if target_dim is less than 5. However, for `target_dim = 5`

, we do get solutions:

```
sage: list( gen_As(M, U, 5, disjoint=True) )
[[
[1 0 0 0] [ 0 0 0 0] [0 1 1 1]
[0 0 0 0] [ 0 0 -1 -1] [1 1 0 0]
[0 0 0 0] [ 0 -1 0 -1] [1 0 1 0]
[0 0 0 0], [ 0 -1 -1 0], [1 0 0 1]
],
[
[1 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 1 1 1]
[0 0 0 0] [ 0 0 -1 -1] [1 1 0 0] [0 0 0 0]
[0 0 0 0] [ 0 -1 0 -1] [1 0 1 0] [0 0 0 0]
[0 0 0 0], [ 0 -1 -1 0], [1 0 0 1], [0 0 0 0]
],
[
[1 0 0 0] [0 0 0 0] [ 0 0 0 0] [0 1 1 1]
[0 0 0 0] [1 0 0 0] [ 0 0 -1 -1] [0 1 0 0]
[0 0 0 0] [1 0 0 0] [ 0 -1 0 -1] [0 0 1 0]
[0 0 0 0], [1 0 0 0], [ 0 -1 -1 0], [0 0 0 1]
],
[
[1 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 1 1 1]
[0 0 0 0] [ 0 0 -1 -1] [0 1 0 0] [1 0 0 0]
[0 0 0 0] [ 0 -1 0 -1] [0 0 1 0] [1 0 0 0]
[0 0 0 0], [ 0 -1 -1 0], [0 0 0 1], [1 0 0 0]
],
[
[1 0 0 0] [0 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 1 1 1]
[0 0 0 0] [1 0 0 0] [ 0 0 -1 -1] [0 1 0 0] [0 0 0 0]
[0 0 0 0] [1 0 0 0] [ 0 -1 0 -1] [0 0 1 0] [0 0 0 0]
[0 0 0 0], [1 0 0 0], [ 0 -1 -1 0], [0 0 0 1], [0 0 0 0]
],
[
[0 0 0 0] [ 0 0 0 0] [1 1 1 1]
[0 1 0 0] [ 0 0 -1 -1] [1 0 0 0]
[0 0 1 0] [ 0 -1 0 -1] [1 0 0 0]
[0 0 0 1], [ 0 -1 -1 0], [1 0 0 0]
],
[
[1 0 0 0] [0 1 1 1] [ 0 0 0 0]
[0 1 0 0] [1 0 0 0] [ 0 0 -1 -1]
[0 0 1 0] [1 0 0 0] [ 0 -1 0 -1]
[0 0 0 1], [1 0 0 0], [ 0 -1 -1 0]
],
[
[1 1 1 1] [ 0 0 0 0]
[1 1 0 0] [ 0 0 -1 -1]
[1 0 1 0] [ 0 -1 0 -1]
[1 0 0 1], [ 0 -1 -1 0]
]]
```

2 | No.2 Revision |

I'm not sure if it is possible to get *all* solutions, but I can show below how to get at least some of them.

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

Now, to reduce the search space we will follow the same idea from my previous answer of fixing the dimension of the matrix span, which, in fact, should be a matrix subring closed under multiplication, and first selecting the basis matrices to fix a subring, and then filter the rest of the matrices based on whether they belong to the subring. Here is implementation of this idea:

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early if the span dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, start_index=0):
'''
Generator for lists of matrices.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
* technical arguments:
* `A_span` - initial span to cover
* `start_index` - starting index in the universe
'''
if M.is_zero():
yield []
if disjoint:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
else:
myU = universe
if A_span is None:
A_span = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
assert A_span.dimension() <= target_dim
if A_span.dimension() == target_dim:
CAND = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) in A_span ]
# print('|CAND|:',len(CAND))
for C in Subsets(CAND): # TODO: use Normaliz
if sum(C) == M:
T = A_span
for c in C:
T = extend_span(T,c)
if T.dimension() > target_dim:
break
else:
yield list(C)
return
for i in range(start_index,len(myU)):
T = extend_span(A_span,myU[i],target_dim)
if T.dimension() > target_dim:
continue
elif T.dimension() <= target_dim:
```~~ # there is still room for growing dimension
~~ for L in gen_As(M-myU[i], myU, target_dim, disjoint, T, i+1):
yield [myU[i]] + L

It turns out that for a given matrix, there are no solutions if target_dim is less than 5. However, for `target_dim = 5`

, we do get solutions:

```
sage: list( gen_As(M, U, 5, disjoint=True) )
[[
[1 0 0 0] [ 0 0 0 0] [0 1 1 1]
[0 0 0 0] [ 0 0 -1 -1] [1 1 0 0]
[0 0 0 0] [ 0 -1 0 -1] [1 0 1 0]
[0 0 0 0], [ 0 -1 -1 0], [1 0 0 1]
],
[
[1 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 1 1 1]
[0 0 0 0] [ 0 0 -1 -1] [1 1 0 0] [0 0 0 0]
[0 0 0 0] [ 0 -1 0 -1] [1 0 1 0] [0 0 0 0]
[0 0 0 0], [ 0 -1 -1 0], [1 0 0 1], [0 0 0 0]
],
[
[1 0 0 0] [0 0 0 0] [ 0 0 0 0] [0 1 1 1]
[0 0 0 0] [1 0 0 0] [ 0 0 -1 -1] [0 1 0 0]
[0 0 0 0] [1 0 0 0] [ 0 -1 0 -1] [0 0 1 0]
[0 0 0 0], [1 0 0 0], [ 0 -1 -1 0], [0 0 0 1]
],
[
[1 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 1 1 1]
[0 0 0 0] [ 0 0 -1 -1] [0 1 0 0] [1 0 0 0]
[0 0 0 0] [ 0 -1 0 -1] [0 0 1 0] [1 0 0 0]
[0 0 0 0], [ 0 -1 -1 0], [0 0 0 1], [1 0 0 0]
],
[
[1 0 0 0] [0 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 1 1 1]
[0 0 0 0] [1 0 0 0] [ 0 0 -1 -1] [0 1 0 0] [0 0 0 0]
[0 0 0 0] [1 0 0 0] [ 0 -1 0 -1] [0 0 1 0] [0 0 0 0]
[0 0 0 0], [1 0 0 0], [ 0 -1 -1 0], [0 0 0 1], [0 0 0 0]
],
[
[0 0 0 0] [ 0 0 0 0] [1 1 1 1]
[0 1 0 0] [ 0 0 -1 -1] [1 0 0 0]
[0 0 1 0] [ 0 -1 0 -1] [1 0 0 0]
[0 0 0 1], [ 0 -1 -1 0], [1 0 0 0]
],
[
[1 0 0 0] [0 1 1 1] [ 0 0 0 0]
[0 1 0 0] [1 0 0 0] [ 0 0 -1 -1]
[0 0 1 0] [1 0 0 0] [ 0 -1 0 -1]
[0 0 0 1], [1 0 0 0], [ 0 -1 -1 0]
],
[
[1 1 1 1] [ 0 0 0 0]
[1 1 0 0] [ 0 0 -1 -1]
[1 0 1 0] [ 0 -1 0 -1]
[1 0 0 1], [ 0 -1 -1 0]
]]
```

3 | No.3 Revision |

Below I show a somewhat promising approach to this problem, although I'm still not sure if ~~it is ~~it's possible to ~~get ~~solve it in reasonable time.*all* solutions, but I can show below how to get at least some of them.

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

Now, to reduce the search space we will follow the same idea from my previous answer of fixing the dimension of the matrix span, which, in fact, should be a matrix subring closed under ~~multiplication, and first selecting ~~multiplication. First we select the basis matrices ~~to ~~and thus fix a subring, and then filter the rest of the matrices based on whether they belong to the subring. Here is implementation of this idea:

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early
```~~if the span ~~when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of ~~matrices.
~~matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
~~* ~~ technical arguments:
* `A_span` - ~~initial ~~span ~~to cover
~~of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span( [M.parent().zero()] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() == A_subring.dimension():
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if ~~A_span is None:
A_span = span( mat_to_vector(M^i) ~~A_subring.dimension() == target_dim:
myU = [ w for i in ~~range(M.minpoly().degree()) )
assert A_span.dimension() <= target_dim
~~range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == ~~target_dim:
CAND = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) in A_span ]
~~target_dim: # ~~print('|CAND|:',len(CAND))
~~that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in ~~Subsets(CAND): ~~Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
T = ~~A_span
~~A_subring
for c in C:
T = ~~extend_span(T,c)
~~extend_subring(T,c,target_dim)
if T.dimension() > target_dim:
break
else:
yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in ~~range(start_index,len(myU)):
~~range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = ~~extend_span(A_span,myU[i],target_dim)
~~extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > ~~target_dim:
~~target_dim:
continue
~~ elif T.dimension() <= target_dim:
~~ for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + span(myU[i]), T, i+1):
~~ ~~ yield [myU[i]] + L

It turns out that for a given matrix, there are no solutions if ~~target_dim ~~`target_dim`

is less than ~~5. However, for ~~10.`target_dim = 5`

, we do get solutions:

```
sage: list( gen_As(M, U, 5, disjoint=True) )
[[
[1 0 0 0] [ 0 0 0 0] [0 1 1 1]
[0 0 0 0] [ 0 0 -1 -1] [1 1 0 0]
[0 0 0 0] [ 0 -1 0 -1] [1 0 1 0]
[0 0 0 0], [ 0 -1 -1 0], [1 0 0 1]
],
[
[1 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 1 1 1]
[0 0 0 0] [ 0 0 -1 -1] [1 1 0 0] [0 0 0 0]
[0 0 0 0] [ 0 -1 0 -1] [1 0 1 0] [0 0 0 0]
[0 0 0 0], [ 0 -1 -1 0], [1 0 0 1], [0 0 0 0]
],
[
[1 0 0 0] [0 0 0 0] [ 0 0 0 0] [0 1 1 1]
[0 0 0 0] [1 0 0 0] [ 0 0 -1 -1] [0 1 0 0]
[0 0 0 0] [1 0 0 0] [ 0 -1 0 -1] [0 0 1 0]
[0 0 0 0], [1 0 0 0], [ 0 -1 -1 0], [0 0 0 1]
],
[
[1 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 1 1 1]
[0 0 0 0] [ 0 0 -1 -1] [0 1 0 0] [1 0 0 0]
[0 0 0 0] [ 0 -1 0 -1] [0 0 1 0] [1 0 0 0]
[0 0 0 0], [ 0 -1 -1 0], [0 0 0 1], [1 0 0 0]
],
[
[1 0 0 0] [0 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 1 1 1]
[0 0 0 0] [1 0 0 0] [ 0 0 -1 -1] [0 1 0 0] [0 0 0 0]
[0 0 0 0] [1 0 0 0] [ 0 -1 0 -1] [0 0 1 0] [0 0 0 0]
[0 0 0 0], [1 0 0 0], [ 0 -1 -1 0], [0 0 0 1], [0 0 0 0]
],
[
[0 0 0 0] [ 0 0 0 0] [1 1 1 1]
[0 1 0 0] [ 0 0 -1 -1] [1 0 0 0]
[0 0 1 0] [ 0 -1 0 -1] [1 0 0 0]
[0 0 0 1], [ 0 -1 -1 0], [1 0 0 0]
],
[
[1 0 0 0] [0 1 1 1] [ 0 0 0 0]
[0 1 0 0] [1 0 0 0] [ 0 0 -1 -1]
[0 0 1 0] [1 0 0 0] [ 0 -1 0 -1]
[0 0 0 1], [1 0 0 0], [ 0 -1 -1 0]
],
[
[1 1 1 1] [ 0 0 0 0]
[1 1 0 0] [ 0 0 -1 -1]
[1 0 1 0] [ 0 -1 0 -1]
[1 0 0 1], [ 0 -1 -1 0]
]]
```

4 | No.4 Revision |

Below I show a somewhat promising approach to this problem, although I'm still not sure if it's possible to solve it in reasonable time.

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

Now, to reduce the search space we will follow the same idea from my previous answer of fixing the dimension of the matrix span, which, in fact, should be a matrix subring closed under multiplication. First we select the basis matrices and thus fix a subring, and then filter the rest of the matrices based on whether they belong to the subring. Here is implementation of this idea:

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
technical arguments:
* `A_span` - span of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span( [M.parent().zero()] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() == A_subring.dimension():
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if A_subring.dimension() == target_dim:
myU = [ w for i in range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == target_dim: # that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
T = A_subring
for c in C:
T = extend_subring(T,c,target_dim)
if T.dimension() > target_dim:
break
else:
yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > target_dim:
continue
for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + span(myU[i]), T, i+1):
yield [myU[i]] + L
```

It turns out that for a given matrix, there are no solutions if `target_dim`

is less than ~~10.~~11, which indicates that in any solution there should be at least 11 summands.

5 | No.5 Revision |

Below I show a somewhat promising approach to this problem, although I'm still not sure if it's possible to solve it in reasonable time.

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

Now, to reduce the search space we will follow the same idea from my previous answer of fixing the dimension of the matrix span, which, in fact, should be a matrix subring closed under multiplication. First we select the basis matrices and thus fix a subring, and then filter the rest of the matrices based on whether they belong to the subring. Here is implementation of this idea:

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
technical arguments:
* `A_span` - span of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span( [M.parent().zero()] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() == A_subring.dimension():
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if A_subring.dimension() == target_dim:
myU = [ w for i in range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == target_dim: # that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
T = A_subring
for c in C:
T = extend_subring(T,c,target_dim)
if T.dimension() > target_dim:
break
else:
yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > target_dim:
continue
for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + span(myU[i]), T, i+1):
yield [myU[i]] + L
```

It turns out that for a given matrix, there are no solutions if `target_dim`

is less than 11, which indicates that in any solution there should be at least 11 linearly-independent summands.

6 | No.6 Revision |

Below I show a somewhat promising approach to this problem, although I'm still not sure if it's possible to solve it in reasonable time.

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

Now, to reduce the search space we will follow the same idea from my previous answer of fixing the dimension of the matrix span, which, in fact, should be a matrix subring closed under multiplication. First we select the basis matrices and thus fix a subring, and then filter the rest of the matrices based on whether they belong to the subring. Here is implementation of this idea:

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
technical arguments:
* `A_span` - span of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span(
```~~[M.parent().zero()] ~~[mat_to_vector(M.parent().zero())] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() == A_subring.dimension():
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if A_subring.dimension() == target_dim:
myU = [ w for i in range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == target_dim: # that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
T = A_subring
for c in C:
T = extend_subring(T,c,target_dim)
if T.dimension() > target_dim:
break
else:
yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > target_dim:
continue
for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + ~~span(myU[i]), ~~span([mat_to_vector(myU[i])]), T, i+1):
yield [myU[i]] + L

It turns out that for a given matrix, there are no solutions if `target_dim`

is less than ~~11, which indicates that in any solution there should be at least 11 linearly-independent summands.~~5. However, with `target_dim = 5`

we get a unique solution:

```
sage: list( gen_As(M,U,5) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 -1 0 -1]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 -1 0]
]]
```

7 | No.7 Revision |

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
technical arguments:
* `A_span` - span of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span( [mat_to_vector(M.parent().zero())] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() == A_subring.dimension():
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if A_subring.dimension() == target_dim:
myU = [ w for i in range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == target_dim: # that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
T = A_subring
for c in C:
T = extend_subring(T,c,target_dim)
if T.dimension() > target_dim:
break
else:
yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > target_dim:
continue
for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + span([mat_to_vector(myU[i])]), T, i+1):
yield [myU[i]] + L
```

It turns out that for a given matrix, there are no solutions if `target_dim`

is less than 5. However, with `target_dim = 5`

we get a unique solution:

`sage: list( `~~gen_As(M,U,5) ~~gen_As(M,U,5,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 -1 0 -1]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 -1 0]
]]

8 | No.8 Revision |

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
technical arguments:
* `A_span` - span of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span( [mat_to_vector(M.parent().zero())] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() == A_subring.dimension():
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if A_subring.dimension() == target_dim:
myU = [ w for i in range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == target_dim: # that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
T = A_subring
for c in C:
T = extend_subring(T,c,target_dim)
if T.dimension() > target_dim:
break
else:
yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > target_dim:
continue
for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + span([mat_to_vector(myU[i])]), T, i+1):
yield [myU[i]] + L
```

It turns out that for a given matrix, there are no solutions if `target_dim`

is less than 5. However, with `target_dim = 5`

we get a unique solution:

```
sage: list( gen_As(M,U,5,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 -1 0 -1]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 -1 0]
]]
```

For `targer_dim = 6`

, we get two solutions:

```
sage: list( gen_As(M,U,6,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 0] [ 0 0 0 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 0 0 -1] [ 0 -1 0 0]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 0 0], [ 0 0 -1 0]
],
[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 -1 0 -1]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 -1 0]
]]
```

9 | No.9 Revision |

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
technical arguments:
* `A_span` - span of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span( [mat_to_vector(M.parent().zero())] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() == A_subring.dimension():
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if A_subring.dimension() == target_dim:
myU = [ w for i in range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == target_dim: # that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
T = A_subring
for c in C:
T = extend_subring(T,c,target_dim)
if T.dimension() > target_dim:
break
else:
yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > target_dim:
continue
for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + span([mat_to_vector(myU[i])]), T, i+1):
yield [myU[i]] + L
```

It turns out that for a given matrix, there are no solutions if `target_dim`

is less than 5. However, with `target_dim = 5`

we get a unique solution:

```
sage: list( gen_As(M,U,5,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 -1 0 -1]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 -1 0]
]]
```

For `targer_dim = 6`

, we get two solutions:

```
sage: list( gen_As(M,U,6,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 0] [ 0 0 0 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 0 0 -1] [ 0 -1 0 0]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 0 0], [ 0 0 -1 0]
],
[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 -1 0 -1]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 -1 0]
]]
```

10 | No.10 Revision |

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
technical arguments:
* `A_span` - span of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span( [mat_to_vector(M.parent().zero())] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() ==
```~~A_subring.dimension():
~~A_subring.dimension() == target_dim:
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if A_subring.dimension() == target_dim:
myU = [ w for i in range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == target_dim: # that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
T = A_subring
for c in C:
T = extend_subring(T,c,target_dim)
if T.dimension() > target_dim:
break
else:
yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > target_dim:
continue
for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + span([mat_to_vector(myU[i])]), T, i+1):
yield [myU[i]] + L

`target_dim`

is less than 5. However, with `target_dim = 5`

we get a unique solution:

```
sage: list( gen_As(M,U,5,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 -1 0 -1]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 -1 0]
]]
```

For `target_dim = 6`

, there is also a unique solution:

```
sage: list( gen_As(M,U,5,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 0] [ 0 0 0 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 0 0 -1] [ 0 -1 0 0]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 0 0], [ 0 0 -1 0]
]]
```

11 | No.11 Revision |

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
technical arguments:
* `A_span` - span of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span( [mat_to_vector(M.parent().zero())] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() == A_subring.dimension() == target_dim:
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if A_subring.dimension() == target_dim:
myU = [ w for i in range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == target_dim: # that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
T = A_subring
for c in C:
T = extend_subring(T,c,target_dim)
if T.dimension() > target_dim:
break
else:
yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > target_dim:
continue
for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + span([mat_to_vector(myU[i])]), T, i+1):
yield [myU[i]] + L
```

`target_dim`

is less than 5. However, with `target_dim = 5`

we get a unique solution:

```
sage: list( gen_As(M,U,5,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 -1 0 -1]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 -1 0]
]]
```

For `target_dim = 6`

, there is also a unique solution:

`sage: list( `~~gen_As(M,U,5,disjoint=True) ~~gen_As(M,U,6,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 0] [ 0 0 0 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 0 0 -1] [ 0 -1 0 0]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 0 0], [ 0 0 -1 0]
]]

12 | No.12 Revision |

~~Below I show a somewhat promising approach to this problem, although ~~I'm ~~still ~~not sure if ~~it's ~~it is possible to ~~solve it in reasonable time.~~get *all* solutions, but I can show below how to get at least *some* of them.

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
technical arguments:
* `A_span` - span of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span( [mat_to_vector(M.parent().zero())] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() == A_subring.dimension() == target_dim:
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if A_subring.dimension() == target_dim:
myU = [ w for i in range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == target_dim: # that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
T = A_subring
for c in C:
T = extend_subring(T,c,target_dim)
if T.dimension() > target_dim:
break
else:
yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > target_dim:
continue
for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + span([mat_to_vector(myU[i])]), T, i+1):
yield [myU[i]] + L
```

`target_dim`

is less than 5. However, with `target_dim = 5`

we get a unique solution:

```
sage: list( gen_As(M,U,5,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 -1 0 -1]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 -1 0]
]]
```

For `target_dim = 6`

, there is also a unique solution:

```
sage: list( gen_As(M,U,6,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 0] [ 0 0 0 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 0 0 -1] [ 0 -1 0 0]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 0 0], [ 0 0 -1 0]
]]
```

For `target_dim = 7`

, there are no solutions.

13 | No.13 Revision |

I'm not sure if it is possible to get *all* solutions, but I can show below how to get at least *some* of them.

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
technical arguments:
* `A_span` - span of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span( [mat_to_vector(M.parent().zero())] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() == A_subring.dimension() == target_dim:
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if A_subring.dimension() == target_dim:
myU = [ w for i in range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == target_dim: # that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
```~~T = A_subring
for c in C:
T = extend_subring(T,c,target_dim)
if T.dimension() > target_dim:
break
else:
~~yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > target_dim:
continue
for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + span([mat_to_vector(myU[i])]), T, i+1):
yield [myU[i]] + L

`target_dim`

is less than 5. However, with `target_dim = 5`

we get a unique solution:

```
sage: list( gen_As(M,U,5,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 -1 0 -1]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 -1 0]
]]
```

For `target_dim = 6`

, there is also a unique solution:

```
sage: list( gen_As(M,U,6,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 0] [ 0 0 0 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 0 0 -1] [ 0 -1 0 0]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 0 0], [ 0 0 -1 0]
]]
```

For `target_dim`

in $\{ 7,8,9,11 \}$ there are no solutions, while for `target_dim = `

, there are ~~7~~10~~no solutions.~~3 solutions:

```
[[[ 0 0 0 0]
[ 0 0 0 0]
[ 0 0 0 -1]
[ 0 0 -1 0],
[0 1 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[ 0 0 0 0]
[ 0 0 -1 -1]
[ 0 0 0 0]
[ 0 0 0 0],
[ 0 0 0 0]
[ 0 0 0 0]
[ 0 -1 0 0]
[ 0 -1 0 0],
[0 0 0 0]
[0 0 0 0]
[1 0 0 0]
[1 0 0 0],
[0 0 1 1]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[1 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[0 0 0 0]
[0 0 0 0]
[0 0 1 0]
[0 0 0 1],
[0 0 0 0]
[1 0 0 0]
[0 0 0 0]
[0 0 0 0],
[0 0 0 0]
[0 1 0 0]
[0 0 0 0]
[0 0 0 0]],
[[ 0 0 0 0]
[ 0 0 0 0]
[ 0 -1 0 -1]
[ 0 0 0 0],
[ 0 0 0 0]
[ 0 0 -1 0]
[ 0 0 0 0]
[ 0 0 -1 0],
[0 0 0 0]
[1 0 0 0]
[0 0 0 0]
[1 0 0 0],
[0 0 1 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[0 1 0 1]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[1 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[0 0 0 0]
[0 1 0 0]
[0 0 0 0]
[0 0 0 1],
[ 0 0 0 0]
[ 0 0 0 -1]
[ 0 0 0 0]
[ 0 -1 0 0],
[0 0 0 0]
[0 0 0 0]
[0 0 1 0]
[0 0 0 0],
[0 0 0 0]
[0 0 0 0]
[1 0 0 0]
[0 0 0 0]],
[[0 0 0 1]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[ 0 0 0 0]
[ 0 0 -1 0]
[ 0 -1 0 0]
[ 0 0 0 0],
[ 0 0 0 0]
[ 0 0 0 -1]
[ 0 0 0 -1]
[ 0 0 0 0],
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 1],
[ 0 0 0 0]
[ 0 0 0 0]
[ 0 0 0 0]
[ 0 -1 -1 0],
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[1 0 0 0],
[0 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 0],
[1 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[0 0 0 0]
[1 0 0 0]
[1 0 0 0]
[0 0 0 0],
[0 1 1 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]]
]
```

14 | No.14 Revision |

*all* solutions, but I can show below how to get at least *some* of them.

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
technical arguments:
* `A_span` - span of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span( [mat_to_vector(M.parent().zero())] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() == A_subring.dimension() == target_dim:
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if A_subring.dimension() == target_dim:
myU = [ w for i in range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == target_dim: # that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > target_dim:
continue
for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + span([mat_to_vector(myU[i])]), T, i+1):
yield [myU[i]] + L
```

`target_dim`

is less than 5. However, with `target_dim = 5`

we get a unique solution:

```
sage: list( gen_As(M,U,5,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 -1 0 -1]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 -1 0]
]]
```

For `target_dim = 6`

, there is also a unique solution:

```
sage: list( gen_As(M,U,6,disjoint=True) )
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 0] [ 0 0 0 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 0 0 -1] [ 0 -1 0 0]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 0 0], [ 0 0 -1 0]
]]
```

For `target_dim`

in $\{ 7,8,9,11 \}$ there are no solutions, while for `target_dim = 10`

, there are 3 solutions:

~~[[[ 0 0 0 0]
[ 0 0 0 0]
[ 0 0 0 -1]
~~[[
[ 0 0 0 0] [ 0 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 0 -1 ~~ 0],
[0 ~~-1] [ 0 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 0 0 0] [ 0 -1 0 0] [ 0 0 0 -1] [0 0 1 ~~0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[ 0 0 0 0]
[ 0 ~~0] [1 0 0 0]
[ 0 0 0 0], [ 0 -1 ~~-1]
[ 0 0 0 0]
[ 0 0 0 0],
[ 0 0 0 0]
[ 0 0 0 0]
[ ~~ 0 0], [ 0 0 -1 ~~0 0]
[ ~~0], [0 0 0 1], [1 0 0 0],
[0 0 0 0] [0 0 0 0] [0 0 1 1] [0 1 0 0] [1 0 0 0]
[0 1 0 0] [1 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
[0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0]
],
[
[ 0 0 0 0] [ 0 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 0 -1 ~~0 0],
[0 0 0 0]
[0 0 0 0]
~~0] [ 0 0 0 -1] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 0 0 0] [ 0 0 0 0] [ 0 -1 0 -1] [0 0 1 0] [1 0 0 0]
[ 0 0 -1 0], [ 0 -1 0 0], [ 0 0 0 0], [0 0 0 0], [0 0 0 0],
[0 0 0 0] [0 0 0 0] [0 0 1 0] [0 1 0 1] [1 0 0 ~~0],
[0 0 ~~0]
[0 1 ~~1]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
~~0 0] [1 0 0 ~~0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[0 0 0 0]
[0 0 0 0]
[0 0 1 ~~0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
[0 0 0 1], ~~
[0 0 0 0]
~~[1 0 0 ~~0]
[0 0 0 0]
[0 0 0 0],
[0 0 0 0]
[0 1 0 0]
[0 0 0 0]
[0 0 0 0]],
[[ 0 0 0 0]
[ 0 0 0 0]
[ ~~0], [0 0 0 0], [0 0 0 0], [0 0 0 0]
],
[
[ 0 0 0 0] [ 0 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 0 -1 ~~0 -1]
[ 0 0 0 0],
[ 0 0 0 0]
[ 0 ~~0] [ 0 0 0 -1] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 -1 ~~0]
[ 0 0 0 0]
[ 0 0 -1 0],
[0 0 0 0]
[1 0 0 0]
[0 0 0 0]
[1 0 0 0],
[0 0 1 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[0 1 0 1]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[1 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[0 0 0 0]
[0 1 0 0]
[0 0 0 0]
[0 0 0 1],
[ 0 0 0 0]
[ 0 0 0 -1]
[ 0 0 0 0]
[ 0 -1 0 0],
[0 0 0 0]
[0 0 0 0]
[0 0 1 0]
[0 0 0 0],
[0 0 0 0]
[0 0 0 0]
[1 0 0 0]
[0 0 0 0]],
[[0 0 0 1]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[ 0 0 0 0]
[ 0 0 -1 0]
[ 0 -1 0 0]
[ 0 0 0 0],
[ 0 0 0 0]
[ 0 0 0 -1]
[ 0 0 0 -1]
[ 0 0 0 0],
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 1],
[ 0 0 0 0]
[ 0 0 0 0]
[ 0 0 0 0]
~~0 0] [ 0 0 0 -1] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 0 0 0], [ 0 0 0 0], [ 0 -1 -1 0], ~~
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
~~[0 0 0 1], [1 0 0 ~~0],
[0 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 0],
[1 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0],
[0 0 0 0]
[1 0 0 0]
[1 0 0 0]
[0 0 0 0],
~~0],
[0 0 0 0] [0 0 0 0] [0 0 0 1] [0 1 1 ~~0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]]
]
~~0] [1 0 0 0]
[0 1 0 0] [1 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
[0 0 1 0] [1 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
[0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0]
]]

15 | No.15 Revision |

*all* solutions, but I can show below how to get at least *some* of them.

Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:

```
# given matrix
M = matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
def mat_to_vector(m):
return vector( m.list(), immutable=True )
pos_p = [i for i,e in enumerate(mat_to_vector(M)) if e==1]
pos_n = [i for i,e in enumerate(mat_to_vector(M)) if e==-1]
U = []
for S in Subsets(pos_p):
if S:
U.append( Matrix(ZZ,n,n,[int(i in S) for i in range(n^2)], immutable=True) )
for S in Subsets(pos_n):
if S:
U.append( Matrix(ZZ,n,n,[-int(i in S) for i in range(n^2)], immutable=True) )
```

Now, to reduce the search space we will follow the same idea from my previous answer of fixing the dimension of the matrix span, which, in fact, should be a matrix subring closed under multiplication. First we select the basis matrices and thus fix a subring, and then filter the rest of the matrices based on whether they belong to the subring. Here is implementation of this ~~idea:~~idea:
https://gist.github.com/maxale/9ebcf95a4bf3c8dff86caffbf65bac00

```
# extend a given span (module) with a matrix A into a subring (closed under multiplication)
# breaks early when dimension becomes > max_dim
def extend_span(S,A,max_dim=+oo):
n = A.nrows()
S += span( mat_to_vector(A^i) for i in range(A.minpoly().degree()) )
while S.dimension() <= max_dim:
T = S + span( mat_to_vector(Matrix(n,n,u)*Matrix(n,n,v)) for u,v in Tuples(S.basis(),2) )
if T.dimension() == S.dimension():
break
S = T
return S
def gen_As(M, universe, target_dim, disjoint=True, A_span=None, A_subring=None, start_index=0):
'''
Generator for lists of matrices summing to `M`.
Input:
* `M` - matrix to decompose
* `universe` - universe of matrices to select As from
* `target_dim` - target dimension of the span of As
* `disjoint` - should nonzero elements of As form a disjoint partition of nonzero elements of M
technical arguments:
* `A_span` - span of selected As
* `A_subring` - span of the subring generated by selected As
* `start_index` - starting index in the universe
'''
if A_span is None:
A_span = span( [mat_to_vector(M.parent().zero())] )
A_subring = span( mat_to_vector(M^i) for i in range(M.minpoly().degree()) )
if M.is_zero():
if A_span.dimension() == A_subring.dimension() == target_dim:
yield []
if disjoint:
return
if A_subring.dimension() > target_dim:
return
if disjoint:
myU = [universe[i] for i in range(start_index,len(universe)) if all(a!=0 or b==0 for a,b in zip(M.list(),universe[i].list()))]
start_index = 0
if len(myU) < target_dim - A_span.dimension():
return
else:
myU = universe
if A_subring.dimension() == target_dim:
myU = [ w for i in range(start_index,len(myU)) if (v:=mat_to_vector(w:=myU[i])) in A_subring ]
start_index = 0
if A_span.dimension() == target_dim: # that is, A_subring == A_span
print('|CAND|:',len(myU))
for C in Subsets(myU): # TODO: use Normaliz
if sum(C) == M:
yield list(C)
return
# here we have dim(A_span) <= dim(A_subring) < target_dim
myU = [ w for i in range(start_index,len(myU)) if mat_to_vector(w:=myU[i]) not in A_span ]
if len(myU) < target_dim - A_span.dimension():
return
for i in range(len(myU)):
T = extend_subring(A_subring,myU[i],target_dim)
if T.dimension() > target_dim:
continue
for L in gen_As(M-myU[i], myU, target_dim, disjoint, A_span + span([mat_to_vector(myU[i])]), T, i+1):
yield [myU[i]] + L
```

`target_dim`

is less than 5. However, with `target_dim = 5`

we get a unique solution:

`sage: `~~list( gen_As(M,U,5,disjoint=True) )
~~all_As_dim(M,U,5,True)
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 -1 0 -1]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 -1 0]
]]

For `target_dim = 6`

, there is also a unique solution:

`sage: `~~list( gen_As(M,U,6,disjoint=True) )
~~all_As_dim(M,U,6,True)
[[
[1 0 0 0] [0 1 1 1] [0 0 0 0] [0 0 0 0] [ 0 0 0 0] [ 0 0 0 0]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 1 0 0] [ 0 0 -1 0] [ 0 0 0 -1]
[0 0 0 0] [0 0 0 0] [1 0 0 0] [0 0 1 0] [ 0 0 0 -1] [ 0 -1 0 0]
[0 0 0 0], [0 0 0 0], [1 0 0 0], [0 0 0 1], [ 0 -1 0 0], [ 0 0 -1 0]
]]

For `target_dim`

in $\{ 7,8,9,11 \}$ there are no solutions, while for `target_dim = 10`

, there are 3 solutions:

```
sage: all_As_dim(M,U,10,True)
[[
[ 0 0 0 0] [ 0 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 0 -1 -1] [ 0 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 0 0 0] [ 0 -1 0 0] [ 0 0 0 -1] [0 0 1 0] [1 0 0 0]
[ 0 0 0 0], [ 0 -1 0 0], [ 0 0 -1 0], [0 0 0 1], [1 0 0 0],
[0 0 0 0] [0 0 0 0] [0 0 1 1] [0 1 0 0] [1 0 0 0]
[0 1 0 0] [1 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
[0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0]
],
[
[ 0 0 0 0] [ 0 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 0 -1 0] [ 0 0 0 -1] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 0 0 0] [ 0 0 0 0] [ 0 -1 0 -1] [0 0 1 0] [1 0 0 0]
[ 0 0 -1 0], [ 0 -1 0 0], [ 0 0 0 0], [0 0 0 0], [0 0 0 0],
[0 0 0 0] [0 0 0 0] [0 0 1 0] [0 1 0 1] [1 0 0 0]
[0 1 0 0] [1 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
[0 0 0 1], [1 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0]
],
[
[ 0 0 0 0] [ 0 0 0 0] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 0 -1 0] [ 0 0 0 -1] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 -1 0 0] [ 0 0 0 -1] [ 0 0 0 0] [0 0 0 0] [0 0 0 0]
[ 0 0 0 0], [ 0 0 0 0], [ 0 -1 -1 0], [0 0 0 1], [1 0 0 0],
[0 0 0 0] [0 0 0 0] [0 0 0 1] [0 1 1 0] [1 0 0 0]
[0 1 0 0] [1 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
[0 0 1 0] [1 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]
[0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0]
]]
```

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.