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.

In general, sum of indefinite matrices need not be indefinite. For example, $A=\begin{pmatrix}2&0\\0&-2\end{pmatrix}$, and $B=\begin{pmatrix}-1&0\\0&1\end{pmatrix}$ are indefinite matrices but matrix $A+B$ is positive definite. Do we have any sufficient conditions for the sum of general $n$th order indefinite matrices to be indefinite as well? Do we have conditions for any linear combination of those matrices to be indefinite as well? For example, the matrices $\begin{pmatrix}-1&0&0\\0&1&0\\0&0&1\end{pmatrix}$ and $\begin{pmatrix}1&0&0\\0&1&0\\0&0&-5\end{pmatrix}$ give indefinite matrix for any of its linear combinations.

share|improve this question
    
perhaps the convex hull? Just guessing here. Take linear combinations where the coefficients are positive and sum to 1. Your example has coefficients which sum to 2. Oh, wait, I see that doesn't work either. Curses. –  James S. Cook Aug 27 '12 at 13:07
3  
You first example is wrong; $A+B$ has eigenvalues $1$ and $-1$; you need $-1$ in $A$ and $2$ in $B$. –  joriki Aug 27 '12 at 13:52

1 Answer 1

up vote 2 down vote accepted

Suppose $A$ and $B$ are indefinite $n \times n$ symmetric matrices. Let $P_A$ and $N_A$ be the linear spans of the eigenvectors of $A$ for positive and negative eigenvalues respectively, similarly $P_B$ and $N_B$ for those of $B$. If $P_A \cap P_B \ne \{0\}$ and $N_A \cap N_B \ne \{0\}$, then $A+B$ is indefinite (and so is $s A + t B$ for any $s,t \ge 0$ with $s+t>0$). If $P_A \cap P_B, P_A \cap N_B, N_A \cap P_B$ and $N_A \cap N_B$ all $\ne \{0\}$, then any nontrivial linear combination of $A$ and $B$ is indefinite.

EDIT: For a less restrictive but more complicated sufficient condition: let $v_1, v_2, v_3$ be three nonzero vectors, let $a_i = v_i^T A v_i$ and $b_i = v_i^T B v_i$. Thus $v_i^T (s A + t B) v_i = s a_i + t b_i$. Let's say $b_1 < 0, b_2 < 0$ and $b_3 > 0$. If $a_1 b_3 - a_3 b_1 > 0$ and $a_2 b_3 - a_3 b_2 < 0$, then $\max(s a_1 + t b_1, s a_3 + t b_3) > 0 > \min(s a_2 + t b_2, s a_3 + t b_3)$ for any $s > 0$ and any real $t$, which implies that any nontrivial linear combination is indefinite.

EDIT: Here's an example of how we might find such vectors. Here are two randomly chosen $4 \times 4$ indefinite symmetric matrices.

$$ A = \pmatrix{-50 &-9 &-16 &10 \cr -9 &50 &-2 &12 \cr -16 &-2 &94 &25 \cr 10 &12 &25 &43 \cr },\ B = \pmatrix{-80 &-50 &31 &9 \cr -50 &77 &-48 &-61 \cr 31 &-48 &20 &86 \cr 9 &-61 &86 &65 \cr }$$

Start with two random vectors

$$ v_1 = \pmatrix{51 \cr 76 \cr -44 \cr 24 \cr }, \ v_2 = \pmatrix{60 \cr -95 \cr -20 \cr -25 \cr }$$

We have $a_1 = v_1^T A v_1 = 396374$, $a_2 = v_2^T A v_2 = 521125$, $b_1 = v_1^T B v_1 = -275000$, $b_2 = v_2^T B v_2 = 538000$. $a_1 + t b_1 = a_2 + t b_2$ at $t = t_0 = -124751/813000$, and $a_1 + t_0 b_1 > 0$. Since $b_1 > 0$ while $b_2 < 0$, we conclude that $\max(a_1 + t b_1, a_2 + t b_2) > 0$ for all real $t$. On the other hand, $a_1 + t b_1 < 0$ for $t > t_1 = 18017/12500$, while $a_2 + t b_2 < 0$ for $t < t_2 = -4169/4304$. If we can find $v_3$ with $a_3 + t_1 b_3 < 0$ and $a_3 + t_2 b_3 < 0$, then $\min(a_1 + t b_1, a_2 + t b_2, a_3 + t b_3 ) < 0$ for all $t$. It took Maple 166 random tries to find one, but it did:

$$ v_3 = \pmatrix{-74 \cr 0 \cr -19 \cr -43 \cr }$$

A more systematic approach might be to try optimization: e.g. minimize $r$ subject to $v^T (A + t_1 B) v \le r$, $v^T (A + t_2 B) v \le r$, and $v^T v \le 1$.
Maple's optimization package comes up with $r= -30.8962810393601$ for $$ v = \pmatrix{-0.915659 \cr 0.293371 \cr -0.254330 \cr -0.104005 \cr }$$

share|improve this answer
    
Thanks for your answer. I have a few questions on this regard: 1. Can you give some references for the proof of the first result? Or a proof idea? 2. For the second result, how can we find if there exists three vectors $v_1,v_2,v_3$ such that $a_1b_3-a_3b_1>0$ and $a_2b_3-a_3b_2<0$ are satisfied? Kindly explain. 3. Can we extend any of the two results for sum of linear combinations of $m$ indefinite matrices to be indefinite? –  Thirumulanathan D Aug 28 '12 at 6:40
    
1) If $v \in P_A \cap P_B$, then $v^T(sA+tB) v > 0$ when $s \ge 0$ and $t \ge 0$ with $s+t > 0$. Similarly for the other cases. –  Robert Israel Aug 28 '12 at 17:09
    
2) You might use random choice or numerical optimization, or some combination of the two. 3) Yes, but since there are $2^{m-1}$ possible choices of signs of coefficients in the linear combination to consider, it may not be practical if $m$ is large. –  Robert Israel Aug 28 '12 at 17:16
    
Many thanks for your clarifications. –  Thirumulanathan D Aug 29 '12 at 6:21

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.