Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello all! 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!

share|improve this question
2  
Your title, and your example, deal with polynomials. Your second sentence, and your tag, refer to linear equations. Which one do you mean? –  Yemon Choi Aug 19 '11 at 21:53
    
You are right. But matrices are from linear algebra and polynomials are from algebra. So I suppose that linear algebra is the case. –  spk Aug 20 '11 at 17:47
    
In this context, the $X$ that solves your matrix equation would be called a solvent. –  J. M. Aug 21 '11 at 12:56
1  
Is A and X the same? –  Zsbán Ambrus May 5 '13 at 11:57
add comment

6 Answers 6

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.

share|improve this answer
    
The quadratic case already quite complicated: see dx.doi.org/10.1145/357456.357463 and the associated FORTRAN code: netlib.org/toms/598 –  J. M. Aug 21 '11 at 13:11
add comment

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.

share|improve this answer
    
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. –  spk Aug 20 '11 at 17:49
add comment

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.

share|improve this answer
    
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? –  spk Aug 20 '11 at 17:54
    
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. –  Robert Israel Aug 21 '11 at 6:28
    
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. –  spk Aug 21 '11 at 8:32
add comment

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.

share|improve this answer
    
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. –  spk Aug 20 '11 at 17:57
    
$X^n$ states for matrix power... –  spk Aug 20 '11 at 17:58
1  
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. –  Federico Poloni Aug 21 '11 at 19:20
    
An interesting approach. But did you miss the ${\bf F}_q$? Numerical methods are not likely to be useful over a finite field. –  Robert Israel Aug 22 '11 at 0:26
1  
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. –  Robert Israel Aug 23 '11 at 17:44
show 4 more comments

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.