2
$\begingroup$

I am trying to find the fixed point of a dynamical system, which requires solving two coupled eigenvalue-like equations. These equations are, in general, overconstrained. I'd like to have a simple criterion for whether or not there will be a solution.

Assume that there are two given matrices, $A$ and $B$. I want to find a diagonal matrix $X$ and a nonzero vector $y$ such that the following two conditions are satisfied: \begin{align} X A y &= y \\ (A - X B)y &= 2y \end{align} (All matrices are of size $n \times n$, and $y$ is of size $n$.) Please feel free to suggest any reasonable simplifying assumptions if it helps solve the problem.

Here is a hand-wavy argument to suggest that the problem is slightly overconstrained. I have $2n$ free variables, and the two conditions above impose $2n$ constraints, suggesting that there is generally a solution. However, they have the obvious solution $y=0$, which I am excluding, so it's almost as if there are $2n+1$ constraints. Therefore, it seems like solutions to this problem should be possible if one extra condition is satisfied by $A$ and $B$, which would make one of the constraints degenerate. (Yes, this is extremely wishy-washy and possibly wrong.)

I posted a related question here in the hope that it would give me some insight into this problem, but so far I am still stuck. Thanks in advance for any ideas!

$\endgroup$
  • $\begingroup$ maybe you can require the vector $y$ to satisfy $\|y\|=1$; that will exclude the $y=0$ solution... $\endgroup$ – Suvrit Oct 10 '13 at 13:53
  • $\begingroup$ Of course. There are many ways to impose the $f \ne 0$ condition, but the main point is that it makes the system slightly overconstrained. $\endgroup$ – sasquires Oct 10 '13 at 19:43
  • $\begingroup$ Actually, what I was hoping with $\|y\|=1$ is flip it around into a fixed-point iteration so that we can invoke Brouwer's theorem to guarantee existence of $X$ and $y$... $\endgroup$ – Suvrit Oct 10 '13 at 19:54
3
$\begingroup$

I tried the $n=2$ case, using Maple to find a "plex" Groebner basis for the equations. The result is rather complicated, and too large to show here. The first member of the basis, for example, is $y_1$ times an irreducible polynomial of $143$ terms and total degree $8$ in the entries of $A$ and $B$, which must be $0$ in order to have a solution with $y_1 \ne 0$. So I don't think you'll get a "simple" criterion.

EDIT: You want the $2n \times n$ matrix $$ \pmatrix{X A - I\cr A - X B - 2 I\cr}$$ to have rank $< n$. That is equivalent to all its ${2n} \choose n$ $n \times n$ submatrices (obtained by selecting $n$ of the rows) having determinant $0$. Each of those determinants is a polynomial ...

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! I didn't know about Gröbner bases. Somehow this seems like it can't possibly be that complicated, but maybe it is. $\endgroup$ – sasquires Oct 10 '13 at 19:45
  • 1
    $\begingroup$ It's occurs to me that you can construct a scary-looking polynomial in all eight variables just using simple ingredients like $\det(A)$ or $\det(B-I)$ or something, and we could be seeing a complicated result that has a simple origin. But that still doesn't bring us any closer to a solution. $\endgroup$ – sasquires Oct 11 '13 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.