On the positive definiteness of a linear combination of matrices

Question

In my work in PDE, the following problem in linear algebra came up. Any help in this direction is appreciated.

QUESTION:

Let $m,n\in\mathbb{N}$ and let $A_1,\ldots, A_m\in M_n(\mathbb{R})$ be real, symmetric, indefinite matrices. I'm interested in conditions on $A_1,\ldots,A_m$ which ensures that the set

$$P:=\big\{\sum_{i=1}^{m}\lambda_i A_i:\lambda_i\in\mathbb{R}\big\}$$

contains a positive-definite matrix. I'm aware of the following result due to Hestenes-McShane (1940) which is suffcient but not necessary.

THEOREM (Hestenes-McShane)

Let $m,n\in\mathbb{N}$ and let $A,B_i\in M_n(\mathbb{R})$ be real symmetric matrices, for all $i=1,\ldots,m$. Let us write, for each $i=1,\ldots,m$,

$$Z_{i}:=\{x\in\mathbb{R}^n:\langle B_i x;x \rangle=0\}$$

Let us suppose that

1. $\langle A x;x \rangle>0$, for all $x\in \cap_{i=1}^{m}Z_i$, $x\neq 0$.

2. $B$ is indefinite on $\mathbb{R}^n$, for all non-zero $B\in\operatorname*{span}\{B_i:i=1,\ldots,m\}$.

3. For every non-zero subspace $S\subseteq \mathbb{R}^n$ satisfying $$S\cap\left(\cap_{i=1}^{m}Z_i\right)=\{0\},$$ there exists $B\in\operatorname*{span}\{B_i:i=1,\ldots,m\}$ such that $B$ is positive definite on $S$.

Then, there exists $B\in\operatorname*{span}\{B_i:i=1,\ldots,m\}$ such that $A-B$ is positive definite on $\mathbb{R}^n$.

Unfortunately, in my case, condition 3 is not satisfied. Has this result been improved later?

Answer 1

The following recent paper: "An exact duality theory for semidefinite programming based on sums of squares" by I. Klep, and M. Schweighofer (both are on MO I think) addresses exactly your question: When is there a $\lambda \in \mathbb{R}^m$ such that $\sum_i \lambda_iA_i \succeq 0$.

If you want something simpler, then the following Lemma, cf. L.Lovasz lecture notes, Lemma 3.2, might be of help (notice $\succ$ instead of $\succeq$).

Lemma. Let $A_i$ be real symmetric matrices. Then, the set $P_+ := \lbrace\sum_i \lambda_i A_i \succ 0\rbrace$ is empty if and only if there exists a semidefinite matrix $X \neq 0$, such that $\mbox{trace}(A_iX) = 0$ for all $i$.

Without the strict $\succ$ relation, the situation gets trickier (we don't have a perfect Farkas Lemma for SDPs).

Answer 2

A straightforward reformulation is in terms of polynomial inequalities is by taking $n$ consecutive chief submatrices $M_{KK}(\lambda)$ for $K=(1,\dots,k)$, $1\leq k\leq n$ of the matrix $M(\lambda)=\sum_{j=1}^m \lambda_j A_j\in \mathbb{R}[\lambda_1,\dots,\lambda_m]^{n\times n}$. Then $P$ contains a positive definite matrix if and only if the basic open semialgebraic set

$\{y\in \mathbb{R}^m\mid \det M_{KK}(y) \gt 0, \ K=(1,\dots,k), 1\leq k\leq n\}$ is nonempty.

At least these kinds of conditions were used in papers by L.Khachiyan and L.Porkolab, such as "On the complexity of semidefinite programs", J. Global Optim. 10 (1997). E.g. when $m$ is fixed, one gets a strong polynomial-time algorithm for checking non-emptiness of $P$.