Welcome to MathOverflow

Question

3

1

Is there some algorithms for solving non-linear matrix equations on field $\mathbb{C}$?

Especially, solving polynomial nonlinear matrix equations.

For instance, let $X$ be some matrix satisfying

$X=A+BXC+DXEXF,$

where $A,B,C,D,E,F$ are given matrices.

Of course, the equation could be in higher degree, such as

$X=X^n+X^{n-1}+A$.

Is there a algorithm can solve this kind equations by provide one solution $X$.

edited Nov 21 2011 at 12:26

asked Nov 18 2011 at 0:04

gondolf
281●5

6

Is there any additional information you can provide on this problem (in terms of $A,B,C,D.E,F$) - is there any reason to expect unique solutions for this system? Trivially, one would interpret this question as a system of $N^2$ equations for the entries of the $N\times N$ matrix $X$. One could then use a host of algorithms including the family of Newton methods. Which algorithm to use will depend on the structure of the equations. – Nilima Nigam Nov 18 2011 at 0:25

2

Are you on $\mathbb{R}/\mathbb{C}$ or on a finite field? Do you really need the generic case, or can you get away with a simpler structure? As noted by Suvrit, the cases $AX+XD=B+XCX$ and $AX^2+BX+C=0$ are well-studied; if some of your matrices are invertible you can reduce some more cases to this form. The more general problem "here's a bunch of quadratic equations, give me a solution" is known to be NP-hard on a finite field, so you may have little luck in the generic case. – Federico Poloni Nov 18 2011 at 12:42

@Nilima Nigam, any solution is fine. – gondolf Nov 21 2011 at 12:20

@Federico Poloni, thank you, I prefer to consider complex field case. – gondolf Nov 21 2011 at 12:21

S. Sra · Answer 1 · 2011-11-18 10:14:04Z UTC

4

You could solve your equations by suitably extending the methods for solving Nonsymmetric Riccati equations, see e.g.,

Nonsymmetric algebraic Riccati equations and Wiener-Hopf Factorization for M-Matrices by C.-H. Guo

answered Nov 18 2011 at 10:14

S. Sra
10k●1●16●44

	@Thank you. What if the degree is greater than 2? – gondolf Nov 21 2011 at 12:28
	@gondolf: One can always derive a Newton-type method (don't know how easy it is to ensure convergence though). The recipe is essentially as for the scalar case. Suppose we are solving $R(X)=0$. First, compute the Fréchet derivative by checking what $R(X+E)$ looks like (expand out $R(X+E)$, keep only the terms linear in $E$, throw away the rest). Then, you'll have a map involving $R'(X)$, which could possibly be used to have a Newton-type iteration. Maybe there exists a more precise reference somewhere though! – S. Sra Nov 21 2011 at 13:18

Mark Sapir · Answer 2 · 2011-11-18 01:59:49Z UTC

2

These are systems of polynomial equations (in entries of $X$). So use Groebner bases.

answered Nov 18 2011 at 1:59

Mark Sapir
27.5k●2●57●118

A question regarding complexity from a user not used to Groebner bases methods. How does the efficiency of this approach compare to that of the following naive method?: 1) Transform original equation into a system of many-variable polynomial equations (I guess this can be lengthy unless the coefficients of the equation are sparse matrices). 2) Use standard algorithm to solve polynomial equations. Thanks. – Juan Bermejo Vega Nov 21 2011 at 15:09

1

@Juan: What is "the standard algorithm to solve polynomial equations". The only one I know uses Groebner bases (it is essentially a generalization of the Gauss-Jordan method of solving systems of linear equations). Perhaps you meant finding approximate solutions? The complexity depends on the system of equations, order of variables, and other things (even Gauss-Jordan is not as easy as it seems). In fact it is a kind of art to make this algorithm working faster. There are many books on that subject. – Mark Sapir Nov 21 2011 at 15:56

Yes, I meant numerical methods. I thought that was the original question. Thanks. en.wikipedia.org/wiki/… – Juan Bermejo Vega Nov 21 2011 at 16:04

I guess we interpreted the question differently. There is no word "numeric" in it. Also he/she specifies that the field is $\mathbb{C}$ which is usual for the exact solutions and not quite usual for numeric solutions. On the other hand the OP's comments for the other answer seem to indicate that, indeed, he/she meant "numeric solutions". – Mark Sapir Nov 21 2011 at 17:51

Also the Groebner basis method is sometimes good for numeric solutions too especially if there is only finitely many solutions because it reduces the problem to one polynomial equation in one variable. One can also use it in combination with numeric methods: first you simplify the system of equations using the Groebner procedure (possibly not to the very end), then use a numeric method. – Mark Sapir Nov 21 2011 at 17:55

Is there some algorithms for solving non-linear matrix equations?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.