# sufficient conditions for linear combinations of indefinite matrices to be indefinite

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.

-
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
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
add comment

## 1 Answer

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 }$$

-
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
add comment