Revision history [back]
 | 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 all solutions, but I can show below how to get at least some of them.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, 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 |
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( [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 |
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( [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 |
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( [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 |
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( [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
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 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 |
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( [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
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 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) )
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( [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
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 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) )
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( [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
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 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 710no 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 |
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. 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( [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
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 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 |
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. 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
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) )
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]
]]
