Ask Your Question
0

Splitting of a (1,-1) square matrix into (0,1) and (0,-1) summands satisfying certain conditions

asked 2024-09-07 18:35:38 +0100

sgmth gravatar image

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/642...

(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?

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
1

answered 2024-09-09 03:11:23 +0100

Max Alekseyev gravatar image

updated 2024-09-11 20:37:29 +0100

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 answerof 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/9ebcf9...

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]
]]
edit flag offensive delete link more

Comments

Thanks 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?

sgmth gravatar imagesgmth ( 2024-09-10 05:43:50 +0100 )edit

No, 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.

Max Alekseyev gravatar imageMax Alekseyev ( 2024-09-10 22:05:57 +0100 )edit

Thanks 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 orders

sgmth gravatar imagesgmth ( 2024-09-11 19:24:49 +0100 )edit

It 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.

Max Alekseyev gravatar imageMax Alekseyev ( 2024-09-11 20:39:09 +0100 )edit

Okay Sir. Many things have become clearer now. As of now, no further questions. Thanks again.

sgmth gravatar imagesgmth ( 2024-09-13 08:26:08 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2024-09-07 18:35:38 +0100

Seen: 203 times

Last updated: Sep 11