Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I wish to solve the following set of coupled eigenvalue equations. How should I do it?

For real matrices $A$,$B$,$D$ and vectors $x \in R^m$, $y \in R^n$ $$ A x + B y = \lambda x $$ $$ B^T x + D y = \mu y $$ where, $A$ and $D$ are symmetric.

Background:

I am trying to solve the following optimization problem:

$$ \min x^T A x + y^T D y + x^T By $$ $$ \textrm{such that } \, x^T x = 1 , y^T y = 1 $$ This leads to the above eigenvalue problem. $\lambda$ and $\mu$ are the Langrangian parameters for the constraints.

EDIT: I need to actually find numerical solutions for these equations given $A$, $B$, $D$

share|improve this question
    
From the optimization, I just realized I want to maximize $\lambda + \mu$ –  Harsh Jun 25 '11 at 12:04

4 Answers 4

If you write $I^m$ for an $m \times m$ identity matrix, you can make a big matrix equation out of it $$\left(\begin {array}{c c}A-\lambda I^m & B\\B^T & D-\mu I^n \end {array}\right)\left(\begin {array}{c}x \\ y \end {array}\right)=0$$ which is a classic eigenvalue problem. Chapter 11 of Numerical Recipes (free for the obsolete versions) or any numerical analysis text can help you.

share|improve this answer
    
Thanks, will look it up –  Harsh Jun 24 '11 at 7:05
    
Can you please explain? AFAIU, This is not the classic Eigenvalue Problem because there are 2 parameters $\lambda$ and $\mu$. Numerical Recipes does not give methods to solve such problems –  Harsh Jun 25 '11 at 12:06
    
This was my first thought, too. But he wants to normalize the $x$ and $y$ parts to unit vectors independently from each other, and I don't see how to factor that in here. –  Jyrki Lahtonen Jun 26 '11 at 20:32

This is not a complete solution... but maybe this will help. Write $u = \begin{pmatrix}x\\y\end{pmatrix}$. Then the objective can be written as $u^TQu$ where $Q = \begin{pmatrix}A & B/2\\B^T/2 & D\end{pmatrix}$. The constraints can be written as $u^TM_1u = 1$ and $u^TM_2u = 1$.

Now, for $\alpha\in(0,1)$, let $M = \alpha M_1 + (1-\alpha)M_2$. Form a constraint as $u^TMu = 1$. It is clear that the minimization with this constraint alone will give a lower bound on the required minimum value. This minimization can be done easily. Let $R = \sqrt{M}$, as $M$ is p.d., and $v = Ru$. Then, the constraint is simply $v^Tv = 1$ and the objective can also be written as $v^TQ'v$, where $Q' = R^{-1}QR^{-1}$. The solution to this is the minimum eigenvalue of $Q'$, which can be obtained by Ritz iterations etc.

Hence the supremum of these lower bounds give a lower bound for for the given minimization problem. The interesting thing to prove is that the supremum of these lower bounds for various $\alpha\in(0,1)$ is the required minimum. This can be shown easily when $B=0$, but I haven't been able to prove it in the general case.

share|improve this answer

Perhaps adding the two equations in order to reeduce it to one equation with eqienvalue (lambda + mu) and Eqienvector x+y is the trick. Then find the inverse using a calculator or standard methods. But there is probably a trick involving the fact that the matrices satisfies the properties they do.

share|improve this answer
    
This does not work –  Harsh Jun 24 '11 at 5:48

Append x and y

form z belonging to R (m+n) by appending y to x

So, now, you will get

m * (m+n) matrix on the left hand side through 1st equation and n*(m+n) matrix on the left hand side through 2nd equation.

your variable is of size m+n.

hence, append the two equations...

now, you get a square matrix on the LHS of size m+n *m+n -- solve

share|improve this answer
    
This is an eigenvalue problem. lambda and mu are not known before hand, so this will not work –  Harsh Jun 24 '11 at 7:05

Your Answer

 
discard

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

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