ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 13 Sep 2024 08:26:08 +0200- Splitting of a (1,-1) square matrix into (0,1) and (0,-1) summands satisfying certain conditionshttps://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/
Given a (-1,1) square matrix A, to find all possible summands A1,A2,A3…..such that:
(i)each Ai is either a (0,1) or (0,-1) matrix which add upto A forming a sort of “partition” of A .
(By “partition” I mean that if a Ai has a non-zero entry at a particular position , then other Ai’s have to have zero at that position)
(ii) their pairwise products are linear combinations of A1,A2,A3,…with integer coefficients.
Note that the same problem(without the “partition” condition) was discussed at:
https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/
(That approach won’t be useful here because of
“partition” condition, things have simplified)
I have written a code below(with example of a 4th order matrix).
A= matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
#Given matrix
n=4
#Enter the order of the matrix
def mat_to_vector(m):
return vector( sum(map(list,m.rows()), []), immutable=True )
#Defining a function which converts matrix to vector
def p(x):
if x==1:
return 1
else:
return 0
#Defining a function which converts any non 1 entry to 0
l=A.apply_map(p)
#applying function p on the given matrix A
MTVP=mat_to_vector(l)
def j(x):
if x==-1:
return 1
else:
return 0
#Defining a function which converts (-1) entry to 1 and non (-1) entry to 0
k=A.apply_map(j)
#applying function j on the given matrix A
MTVN=mat_to_vector(k)
VP=VectorPartitions(MTVP)
VN=VectorPartitions(MTVN)
s = 4
#("Enter no.(>1) of (0,1) matrices u want")
P=[]
for a in VP:
if len(a)==s :
P.append(a)
t = 1
#("Enter no.(>1) of (0,-1) matrices u want")
TN=[]
for a in VN:
if len(a)==t :
TN.append(a)
N = [[[(-1) * x for x in y]for y in z]for z in TN]
# Multiplication by (-1) over the List
R=[]
for a in P:
for b in N:
r=a+b
R.append(r)
M=[[matrix(n,n,v) for v in t] for t in R]
test_sum=s+t
VVV = ZZ^(n^2)
Counter=0
for test in M:
VV = VVV.submodule(mat_to_vector(test[i]) for i in range(len(test)))
flag = 0
for i in range(test_sum):
for j in range(test_sum):
if(mat_to_vector(test[i]*test[j]) not in VV):
flag = 1
if(flag==0):
Counter+=1
show("(",Counter,").",test)
print("\n")
B=matrix([mat_to_vector(test[i]) for i in range(len(test))]);B
C=B.transpose();C
for i in range(test_sum):
for j in range(test_sum):
b=vector(mat_to_vector(test[i]*test[j]))
show('A',i+1, 'A',j+1, '=', C.solve_right(b))
#Showing the respective coefficients of A1,A2,A3....in the matrix products
How to improve upon it to make it run faster for higher orders?
Sat, 07 Sep 2024 18:35:38 +0200https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/
- Answer by Max Alekseyev for <p>Given a (-1,1) square matrix A, to find all possible summands A1,A2,A3…..such that:</p>
<p>(i)each Ai is either a (0,1) or (0,-1) matrix which add upto A forming a sort of “partition” of A .</p>
<p>(By “partition” I mean that if a Ai has a non-zero entry at a particular position , then other Ai’s have to have zero at that position)</p>
<p>(ii) their pairwise products are linear combinations of A1,A2,A3,…with integer coefficients.</p>
<p>Note that the same problem(without the “partition” condition) was discussed at:
<a href="https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/">https://ask.sagemath.org/question/642...</a></p>
<p>(That approach won’t be useful here because of
“partition” condition, things have simplified)</p>
<p>I have written a code below(with example of a 4th order matrix). </p>
<pre><code>A= matrix(ZZ, [[1, 1, 1, 1], [1, 1, -1, -1], [1, -1, 1, -1], [1, -1, -1, 1]])
#Given matrix
n=4
#Enter the order of the matrix
def mat_to_vector(m):
return vector( sum(map(list,m.rows()), []), immutable=True )
#Defining a function which converts matrix to vector
def p(x):
if x==1:
return 1
else:
return 0
#Defining a function which converts any non 1 entry to 0
l=A.apply_map(p)
#applying function p on the given matrix A
MTVP=mat_to_vector(l)
def j(x):
if x==-1:
return 1
else:
return 0
#Defining a function which converts (-1) entry to 1 and non (-1) entry to 0
k=A.apply_map(j)
#applying function j on the given matrix A
MTVN=mat_to_vector(k)
VP=VectorPartitions(MTVP)
VN=VectorPartitions(MTVN)
s = 4
#("Enter no.(>1) of (0,1) matrices u want")
P=[]
for a in VP:
if len(a)==s :
P.append(a)
t = 1
#("Enter no.(>1) of (0,-1) matrices u want")
TN=[]
for a in VN:
if len(a)==t :
TN.append(a)
N = [[[(-1) * x for x in y]for y in z]for z in TN]
# Multiplication by (-1) over the List
R=[]
for a in P:
for b in N:
r=a+b
R.append(r)
M=[[matrix(n,n,v) for v in t] for t in R]
test_sum=s+t
VVV = ZZ^(n^2)
Counter=0
for test in M:
VV = VVV.submodule(mat_to_vector(test[i]) for i in range(len(test)))
flag = 0
for i in range(test_sum):
for j in range(test_sum):
if(mat_to_vector(test[i]*test[j]) not in VV):
flag = 1
if(flag==0):
Counter+=1
show("(",Counter,").",test)
print("\n")
B=matrix([mat_to_vector(test[i]) for i in range(len(test))]);B
C=B.transpose();C
for i in range(test_sum):
for j in range(test_sum):
b=vector(mat_to_vector(test[i]*test[j]))
show('A',i+1, 'A',j+1, '=', C.solve_right(b))
#Showing the respective coefficients of A1,A2,A3....in the matrix products
</code></pre>
<p>How to improve upon it to make it run faster for higher orders?</p>
https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/?answer=79128#post-id-79128I'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](https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/?answer=64305#post-id-64305) 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:
https://gist.github.com/maxale/9ebcf95a4bf3c8dff86caffbf65bac00
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: 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: 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]
]]Mon, 09 Sep 2024 03:11:23 +0200https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/?answer=79128#post-id-79128
- Comment by sgmth for <p>I'm not sure if it is possible to get <em>all</em> solutions, but I can show below how to get at least <em>some</em> of them.</p>
<p>Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:</p>
<pre><code># 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) )
</code></pre>
<p>Now, to reduce the search space we will follow the same idea from <a href="https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/?answer=64305#post-id-64305">my previous answer</a>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:
<a href="https://gist.github.com/maxale/9ebcf95a4bf3c8dff86caffbf65bac00">https://gist.github.com/maxale/9ebcf9...</a></p>
<p>It turns out that for a given matrix, there are no solutions if <code>target_dim</code> is less than 5. However, with <code>target_dim = 5</code> we get a unique solution:</p>
<pre><code>sage: 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]
]]
</code></pre>
<p>For <code>target_dim = 6</code>, there is also a unique solution:</p>
<pre><code>sage: 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]
]]
</code></pre>
<p>For <code>target_dim</code> in $\{ 7,8,9,11 \}$ there are no solutions, while for <code>target_dim = 10</code>, there are 3 solutions:</p>
<pre><code>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]
]]
</code></pre>
https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/?comment=79188#post-id-79188Okay Sir. Many things have become clearer now. As of now, no further questions. Thanks again.Fri, 13 Sep 2024 08:26:08 +0200https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/?comment=79188#post-id-79188
- Comment by Max Alekseyev for <p>I'm not sure if it is possible to get <em>all</em> solutions, but I can show below how to get at least <em>some</em> of them.</p>
<p>Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:</p>
<pre><code># 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) )
</code></pre>
<p>Now, to reduce the search space we will follow the same idea from <a href="https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/?answer=64305#post-id-64305">my previous answer</a>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:
<a href="https://gist.github.com/maxale/9ebcf95a4bf3c8dff86caffbf65bac00">https://gist.github.com/maxale/9ebcf9...</a></p>
<p>It turns out that for a given matrix, there are no solutions if <code>target_dim</code> is less than 5. However, with <code>target_dim = 5</code> we get a unique solution:</p>
<pre><code>sage: 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]
]]
</code></pre>
<p>For <code>target_dim = 6</code>, there is also a unique solution:</p>
<pre><code>sage: 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]
]]
</code></pre>
<p>For <code>target_dim</code> in $\{ 7,8,9,11 \}$ there are no solutions, while for <code>target_dim = 10</code>, there are 3 solutions:</p>
<pre><code>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]
]]
</code></pre>
https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/?comment=79164#post-id-79164It was an artifact from multiple revisions of my code. I've moved the up-to-date code to gist and gave a link here. Let me know if there are any questions.Wed, 11 Sep 2024 20:39:09 +0200https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/?comment=79164#post-id-79164
- Comment by sgmth for <p>I'm not sure if it is possible to get <em>all</em> solutions, but I can show below how to get at least <em>some</em> of them.</p>
<p>Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:</p>
<pre><code># 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) )
</code></pre>
<p>Now, to reduce the search space we will follow the same idea from <a href="https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/?answer=64305#post-id-64305">my previous answer</a>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:
<a href="https://gist.github.com/maxale/9ebcf95a4bf3c8dff86caffbf65bac00">https://gist.github.com/maxale/9ebcf9...</a></p>
<p>It turns out that for a given matrix, there are no solutions if <code>target_dim</code> is less than 5. However, with <code>target_dim = 5</code> we get a unique solution:</p>
<pre><code>sage: 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]
]]
</code></pre>
<p>For <code>target_dim = 6</code>, there is also a unique solution:</p>
<pre><code>sage: 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]
]]
</code></pre>
<p>For <code>target_dim</code> in $\{ 7,8,9,11 \}$ there are no solutions, while for <code>target_dim = 10</code>, there are 3 solutions:</p>
<pre><code>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]
]]
</code></pre>
https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/?comment=79163#post-id-79163Thanks a lot again Sir for working so much on my question. Btw I think there is a typo error :
Instead of “def extend_span” in the first line it should be “def extend_subring”.
Well, here’s the background for my work. “Association Schemes” (via matrices) have been known to generate important matrices(like Hadamard matrices etc.). So, starting with a known matrix(Hadamard matrix in our case) , we are trying to find the “Association Schemes”(with relaxed conditions) which generate this Hadamard matrix. Then study the outputs obtained to gain insight and to see if they can be generalized to higher ordersWed, 11 Sep 2024 19:24:49 +0200https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/?comment=79163#post-id-79163
- Comment by Max Alekseyev for <p>I'm not sure if it is possible to get <em>all</em> solutions, but I can show below how to get at least <em>some</em> of them.</p>
<p>Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:</p>
<pre><code># 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) )
</code></pre>
<p>Now, to reduce the search space we will follow the same idea from <a href="https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/?answer=64305#post-id-64305">my previous answer</a>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:
<a href="https://gist.github.com/maxale/9ebcf95a4bf3c8dff86caffbf65bac00">https://gist.github.com/maxale/9ebcf9...</a></p>
<p>It turns out that for a given matrix, there are no solutions if <code>target_dim</code> is less than 5. However, with <code>target_dim = 5</code> we get a unique solution:</p>
<pre><code>sage: 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]
]]
</code></pre>
<p>For <code>target_dim = 6</code>, there is also a unique solution:</p>
<pre><code>sage: 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]
]]
</code></pre>
<p>For <code>target_dim</code> in $\{ 7,8,9,11 \}$ there are no solutions, while for <code>target_dim = 10</code>, there are 3 solutions:</p>
<pre><code>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]
]]
</code></pre>
https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/?comment=79151#post-id-79151No, they are not supposed to be candidates, but actual solutions. However, there was a bug in my code, which led to producing incomplete solutions. Now it's fixed, and with `target_dim = 5` we get a single solution.
Btw, since you *"have just elementary knowledge"*, while the problem is rather involved, it would be helpful if you provide the source and/or context of your problem.Tue, 10 Sep 2024 22:05:57 +0200https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/?comment=79151#post-id-79151
- Comment by sgmth for <p>I'm not sure if it is possible to get <em>all</em> solutions, but I can show below how to get at least <em>some</em> of them.</p>
<p>Let us start with set up, where we create a list of candidate $(0,+1)$ or $(0,-1)$ matrices $A$:</p>
<pre><code># 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) )
</code></pre>
<p>Now, to reduce the search space we will follow the same idea from <a href="https://ask.sagemath.org/question/64286/cant-find-error-in-my-code/?answer=64305#post-id-64305">my previous answer</a>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:
<a href="https://gist.github.com/maxale/9ebcf95a4bf3c8dff86caffbf65bac00">https://gist.github.com/maxale/9ebcf9...</a></p>
<p>It turns out that for a given matrix, there are no solutions if <code>target_dim</code> is less than 5. However, with <code>target_dim = 5</code> we get a unique solution:</p>
<pre><code>sage: 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]
]]
</code></pre>
<p>For <code>target_dim = 6</code>, there is also a unique solution:</p>
<pre><code>sage: 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]
]]
</code></pre>
<p>For <code>target_dim</code> in $\{ 7,8,9,11 \}$ there are no solutions, while for <code>target_dim = 10</code>, there are 3 solutions:</p>
<pre><code>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]
]]
</code></pre>
https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/?comment=79141#post-id-79141Thanks a lot Sir for your time and effort. I need to really go deeper into the background theory mentioned by you and also the code as I have just elementary knowledge of both, to fully grasp the thing done by you. The outputs obtained as per your code are the candidates for the desired output, and we need to further only check the second condition to get the desired output, right?Tue, 10 Sep 2024 05:43:50 +0200https://ask.sagemath.org/question/79111/splitting-of-a-1-1-square-matrix-into-01-and-0-1-summands-satisfying-certain-conditions/?comment=79141#post-id-79141