Let A,B nxn matrices over finite field F.
One can prove that if the minimal polynomials of A,B are co-prime then the Sylvester equation AX-AB=C has uniqe solution for any given matrix C over F.
Is the opposite also true, i.e. if AX-AB=C has uniqe solution X for any given matrix C over F, does the minimal polynomials of A,B are co-prime ?
The equation is wrong: Sylvester's equation is AX - XB = C. And the necessary and sufficient conditions for the solution to exist are described here: https://elearning.dm.unipi.it/pluginfile.php/6675/mod_resource/content/0/1-Sylvester.pdf for instance. Of course, there are many equivalent ways of stating them.
Dear Stam !
Thank you for your correction ! Indeed I meant AX-XB=C. But note that my question was about the Sylvester equation over finite fields !
The proof over the complex field is useless for finite fields.
Consider the linear map T(X):=AX-XB. The original equation has exactly one solution for each C iff T is injective, iff ker T=0, iff the only solution for AX-XB=0 is X=0. So suppose AX-XB=0, i.e., AX=XB for a fixed solution X. Then A^2X=AAX=AXB=XB^2, and by induction, for any polynomial p(x) we get p(A)X=Xp(B).
Now consider the characteristic polynomial p of B. Then p(A)X=Xp(B)=0 since p(B)=0. Thus p(A)X=0 as a matrix equation. Either p(A) is nonsingular and there is only one solution, or p(A) is singular and there are multiple solutions. But p is the characteristic polynomial of B, which splits over the algebraic closure of the base field as
p(x)=(x-L1·I)...(x-Ln·I),
where I is the identity matrix and the Lk are the eigenvalues of B.
If p(A)=(A-L1·I)...(A-Ln·I) is nonsingular, then A-Lk·I is nonsingular for each k, hence no Lk is an eigenvalue of A. Therefore the minimal polynomials of A and B must be coprime (otherwise they would share at least a linear factor for some eigenvalue over the algebraic closure).
If p(A) is singular, we must have A-Lk·I singular for some k, hence Lk is an eigenvalue of A for some k, so the linear factor x-Lk divides the gcd of the minimal polynomials of A and B over the algebraic closure, therefore the minimal polynomials over the original field have nontrivial gcd.
Dear Jose !
Many thanks for your solution !
Please send me your affiliation details to
I wish to give you the credit and mention you in the proof of this direction in the proof of the theorem below (and please confirm that you are willing that we will mention you in our article). I will send you the copy of the article - when it will be available for publication. The article deals with new post-quantum cryptographic systems.
So, thanks to you, we have the following:
Theorem:
Let F be any field (finite of infinite). Then, the matrix equation AX-XB=C has unique solution X for any given matrix C if and only if the minimal polynomials of A,B are co-prime.
All The Best !
Dear Yossi Peretz ,
I do not deserve the credit, this result is well known (comes already from Sylvester) and is found in textbooks. You can find it for example in
Matrix analysis (second edition) by Horn and Johnson, in Section 2.4.4. They work over the complex numbers, so you don't have there the argument about the gcd, but that is straightforward, the imporant fact is the one about the eigenvalues.
Sorry I didn't put a reference before, I didn't know you wanted the information for a paper. To cite it, I would simply reference Theorem 2.4.4.1 of the aforementioned book, saying that although their proof is stated for the complex numbers, it is equally valid for any field with the obvious changes regarding the minimal polynomials.
Thank you for your kindness!
The paper that deals with matrix equations (among them Sylvester's equation) over finite fields is Article Some matrix equations over a finite field
and can be found by searching for the title in your favorite search engine.
- Badges
- Science topic