6
$\begingroup$

Are somewhere existed a method for solving a linear equations over matrices? For example, I have a task that is similar to next: find $l \times l$ - matrix $A \in M_{l \times l}(\mathbf{F}_q)$ over $\mathbf{F}_q$ that vanishes $B_0 + B_1 X + B_2 X^2 + B_3 X^3 + ... + B_m X^m$ where $B_i \in M_{l \times l}(\mathbf{F}_q)$.

I have found nothing about this by Google. Thank you!

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Your title, and your example, deal with polynomials. Your second sentence, and your tag, refer to linear equations. Which one do you mean? $\endgroup$
    – Yemon Choi
    Commented Aug 19, 2011 at 21:53
  • $\begingroup$ You are right. But matrices are from linear algebra and polynomials are from algebra. So I suppose that linear algebra is the case. $\endgroup$
    – spk
    Commented Aug 20, 2011 at 17:47
  • $\begingroup$ In this context, the $X$ that solves your matrix equation would be called a solvent. $\endgroup$
    – J. M. isn't a mathematician
    Commented Aug 21, 2011 at 12:56
  • 1
    $\begingroup$ Is A and X the same? $\endgroup$
    – Zsbán Ambrus
    Commented May 5, 2013 at 11:57
  • $\begingroup$ It is a mistake to call these "linear" equations. Even if they are related to linear algebra. $\endgroup$
    – Daniel Asimov
    Commented Aug 10, 2023 at 3:03

6 Answers 6

Reset to default
6
$\begingroup$

Yes, there a number of numerical methods for finding the solvents of a polynomial with matrix coefficients. Dennis, Traub, and Weber in this article give some of the relevant theory, as well as some algorithms for finding so-called "dominant solvents" for your matrix polynomial (see also their earlier article). This article presents the use of Newton's method for solving matrix polynomials.

As a tiny aside on the "companion" formulation mentioned by Federico: make sure that whatever software you're using is the version that uses the QZ algorithm, without the preliminary application of the inverse of the leading coefficient to "monicize" the matrix polynomial. It can happen that the leading coefficient is an ill-conditioned matrix, and the "monicization" leads to a degradation of accuracy in the solvents returned.

Improve this answer
$\endgroup$
1
3
$\begingroup$

I'd like to provide a reference for this question. You can see the book "Matrix Polynomials", of which the authors are I. Gohberg, P. Lancaster and L. Rodman. I hope it will be helpful.

Improve this answer
$\endgroup$
2
$\begingroup$

If you are looking for information about roots of polynomials with matrix coefficients try checking out this set of notes created by Robert L. Wilson (at Rutgers University):

http://www.math.rutgers.edu/~rwilson/polynomial_equations.pdf

Wilson has mentored a series of undergraduates who have made some small contributions to this area. Try searching for something like "DIMACS REU polynomials with matrix coefficients" and you should be able to dig up a few project summaries.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for the reference! But this is about only the quadratic case. But I have an equation of arbitrary degree. And it is a big problem. $\endgroup$
    – spk
    Commented Aug 20, 2011 at 17:49
2
$\begingroup$

You can consider this as a system of $l^2$ polynomial equations in the $l^2$ matrix entries of $X$. I doubt that you can do much better in general. Even the quadratic case is not trivial. For $2 \times 2$ matrices that is likely to "reduce" to solving a polynomial of degree 6 in one variable.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the answer! As for me it is a known fact that for any field $\mathbf{F}_q$ $M_{l \times l}(\mathbf{F}_q)[x] \sim (\mathbf{F}_q[x])^{l \times l}$. But how it could help me? $\endgroup$
    – spk
    Commented Aug 20, 2011 at 17:54
  • $\begingroup$ What I mean is something like this. Consider e.g. the case $m=2$, $l=2$ with $B_0=\pmatrix{0 & 1\cr 0 & 0\cr}$, $B_1=\pmatrix{0& 1\cr 1 & 0\cr}$, $B_2=\pmatrix{1 & 0\cr 0 & 1\cr}$. If $X= \pmatrix{x_{11} & x_{21}\cr x_{12} & x_{22}\cr}$, the system of equations is $$\begin {array}{c} x_{{2,1}}+{x_{{1,1}}}^{2}+x_{{1,2}}x_{{2,1}}=0\\ x_{{1,1}}+x_{{2,1}}x_{{1,1}}+x_{{2,2}}x_{{2,1}} =0\\ 1+x_{{2,2}}+x_{{1,1}}x_{{1,2}}+x_{{1,2}}x_{{2,2 }}=0\\ x_{{1,2}}+x_{{1,2}}x_{{2,1}}+{x_{{2,2}}}^{2}=0 \end {array}$$ You could use Groebner basis techniques to solve this system. $\endgroup$
    – Robert Israel
    Commented Aug 21, 2011 at 6:28
  • $\begingroup$ Thank you for your answer! But this approach becomes very hard if $m >> 1$ and $l >> 1$. So I understood, that common technique does not exist. $\endgroup$
    – spk
    Commented Aug 21, 2011 at 8:32
2
$\begingroup$

It's essentially finding $l$ solutions of a polynomial eigenvalue problem (i.e., find a vector $v$ s.t. $(\sum x^i B_i)v=0$. Existing methods to solve it are usually based on linearization (a matrix version of the "companion matrix"); Matlab has a function polyeig that does all the work for you. Check Chapter 9 of Templates for the solution of algebraic eigenvalue problems by Zhaojun Bai.

In alternative, there are iterative methods to solve directly the matrix equation, such as Cyclic Reduction for the quadratic case - you find something in Numerical methods for structured Markov chains, Bini, Latouche, Meini, and in the article Solving matrix polynomial equations arising in queueing problems by the same authors.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Thank you for the answer! But I have to solve not an eigenvalue problem, but find roots of polynomial with matrix coefficients. For example, for polynomial $B_0 + B_1 X + B_2 X^2 + B_3 x^3 + \ldots + B_m X^m$ I have to find a square $l \times l$-matrix $X$ that makes equation vanished.I suppose that it is not analogous to eigenvalue problem you have stated above. $\endgroup$
    – spk
    Commented Aug 20, 2011 at 17:57
  • $\begingroup$ $X^n$ states for matrix power... $\endgroup$
    – spk
    Commented Aug 20, 2011 at 17:58
  • 1
    $\begingroup$ If you diagonalize $X$, you get a generalized eigenvalue problem. If you wish to go for the direct solution, though, check the references I listed in the second part. $\endgroup$
    – Federico Poloni
    Commented Aug 21, 2011 at 19:20
  • $\begingroup$ An interesting approach. But did you miss the ${\bf F}_q$? Numerical methods are not likely to be useful over a finite field. $\endgroup$
    – Robert Israel
    Commented Aug 22, 2011 at 0:26
  • 1
    $\begingroup$ Yes, this is a very promising approach. Note that the diagonalization may require an extension field, if $\det(\sum_i B_i x^i)$ does not have all its roots in ${\mathbb F}_q$. Also you may need to look at cases where $X$ has nontrivial Jordan form. $\endgroup$
    – Robert Israel
    Commented Aug 23, 2011 at 17:44
0
$\begingroup$

see

International Mathematical Forum, 3, 2008, no. 17, 829 - 836

A Note on a Generalization of an Extension of the Cayley-Hamilton Theorem this will reply your request best issam

Improve this answer
$\endgroup$

You must log in to answer this question.