0

Given a square matrix A, find all matrices X such that AX = XA. This is a particular case of a Sylvester equation (one of the form AX + XB = Q) when A = B and Q is the zero matrix. I know SciPy has a solver for this type of equations, however, since the zero matrix is always a solution to my equation, this solver just gives me this trivial solution.

There are infinite solutions to the equation AX = XA, so I'm actually looking for a way to find a basis of the space of solutions.

Here's my attempt for a little example I worked on paper:

import numpy as np
import scipy
from sympy import *


A = np.array([[-2, 1, 1],[3, -3, 0], [1, 0, -1]])

X = np.array([["a", "b", "c"], ["d", "e", "f"], ["g", "h", "i"]])

Q = np.zeros_like(L)


var('a b c d e f g h i L S')

A = Matrix([[-2, 1, 1],[3, -3, 0], [1, 0, -1]])

X = Matrix([[a, b, c], [d, e, f], [g, h, i]])


M = A.multiply(X) - X.multiply(A)
M

I can't figure out a way to "extract" the coefficients of the matrix M. If I could do this, then I would have the coefficient matrix of a homogeneous system of linear equations and maybe then I could get a non-trivial solution or all the possible solutions to this problem.

Moony
  • 21
  • 2
  • 3
    Welcome to SO. This isn't a discussion forum or tutorial. Please take the [tour] and take the time to read [ask] and the other links found on that page. Invest some time with [the Tutorial](https://docs.python.org/3/tutorial/index.html) practicing the examples. It will give you an idea of the tools Python offers to help you solve your problem. – wwii Apr 14 '20 at 18:39
  • Probably start with pencil and paper and write down the process to do it by hand - the beginnings of an algorithm. Then once you have learned a bit of Python start trying to turn what you wrote into code. – wwii Apr 14 '20 at 18:43
  • Aren't there infinitely many? B can be an arbitrarily scaled identity matrix, no? – Kelly Bundy Apr 14 '20 at 18:44
  • 2
    Also, this is [not a personal help resource](https://meta.stackoverflow.com/questions/284236/why-is-can-someone-help-me-not-an-actual-question). We deal with *specific* programming questions; "I don't know how to do my homework" is an issue for a local tutor or a review of available educational materials, rather than Stack Overflow. – Prune Apr 14 '20 at 18:44
  • @wwii Than you for the resources and your advice. I made a little example to figure out the steps, although I'm not sure that's what I was meant to do. – Moony Apr 15 '20 at 23:41
  • @HeapOverflow Yes! There are, I edited my question to show how this is part of the problem. – Moony Apr 15 '20 at 23:42
  • @Prune Thank you for your comments. I'm sorry it looked as if I was trying to get my homework done. This is not homework, it is a little project I thought about and wanted to get started with it. Although I understand now that my question was poorly written. I edited and will continue to do so if it's still not good. If this particular problem is simply not the kind that you deal with here, I'll delete. – Moony Apr 15 '20 at 23:47
  • **Much** better! I've reversed my down-vote and voted to reopen. I'm bookmarking this for later consideration. – Prune Apr 16 '20 at 00:34
  • 1
    Like this?: [How to extract all coefficients in sympy](https://stackoverflow.com/questions/22955888/how-to-extract-all-coefficients-in-sympy), [Factor sympy expression to matrix coefficients?](https://stackoverflow.com/questions/30112645/factor-sympy-expression-to-matrix-coefficients), [Extract coefficients and corresponding monomials from a given polynomial in SymPy](https://stackoverflow.com/questions/50563745/extract-coefficients-and-corresponding-monomials-from-a-given-polynomial-in-symp). `Q=M.applyfunc(Poly); for thing in Q: print((thing.gen,thing.coeffs())`? – wwii Apr 16 '20 at 15:37
  • @Prune Thank you again for your feedback. I posted a solution for this example. I don't know if I should've considering it's just a particular case. – Moony Apr 17 '20 at 00:25

2 Answers2

1

I solved it with the help you gave me but there are probably more efficient ways. I post it anyway in case it helps anybody. I hope I can extend this to bigger matrices in a more efficient way.

import numpy as np
import scipy
from sympy import *
from sympy import Matrix, lcm

var('x L S')

#L is the matrix given, I want to find all matrices that commute with it
L = Matrix([[-2, 1, 1],[3, -3, 0], [1, 0, -1]])

#S is a variable matrix
S = Matrix([[x**1, x**2, x**3], [x**4, x**5, x**6], [x**7, x**8, x**9]])

#I need to solve the equation M = 0 (M = LS - SL)
M = L.multiply(S) - S.multiply(L)  

#I convert each entry to a polynomial and extract coefficients
B = []

for i in range(0,9):
    b = poly(M[i]).all_coeffs()
    B.append(b)

# Define a function to add zeros corresponding to missing variables   
def trp(l, n):
    return [0]*(n-len(l)) + l[:n]

# Add zeros at the beginning of every list 
C = []

for i in range(0,9):
    c = trp(B[i],10)
    C.append(c)

#Function to remove last zero corresponding to constant term
def trp2(l,n):
    return l[:n] + [0]*(n-len(l))


#"Good" list: with coefficients for all variables wanted
A = []

for i in range(0,9):
    a = trp2(C[i],9)
    A.append(a)

#Find null space of matrix
A = Matrix(A)
v = A.nullspace()

#one solution matrix
v[0] + v[1] + v[2]

#The matrix found is S = [[1,1,1],[3,0,0],[1,0,2]] which indeed satisfies that SL = LS.
Moony
  • 21
  • 2
0
import sympy as sp

a = sp.Symbol('a')
b =sp.Symbol('b')
c =sp.Symbol('c')
d =sp.Symbol('d')
e =sp.Symbol('e')
f =sp.Symbol('f')
g =sp.Symbol('g')
h =sp.Symbol('h')
i =sp.Symbol('i')


A = sp.Matrix([[-2, 1, 1],[3, -3, 4], [1, 7, -1]])
X = sp.Matrix([[a, b, c], [d, e, f], [g, h, i]])
M = A.multiply(X) - X.multiply(A)

LSG = sp.solve(M)
print(LSG)

LSGM = sp.Matrix([[LSG[a],LSG[b],LSG[c]],[LSG[d],LSG[e],LSG[f]],[0,0,0]])

LSGM - LSGM
Nicola Rohner
  • 65
  • 1
  • 7