On the Positive Definiteness of a Linear Combination of Matrices

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:=\{\sum_{i=1}^{m}\lambda_i A_i:\lambda_i\in\mathbb{R}\}$$

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?

• Hi, previously I had recommended addition of the algebraic geometry tag; now, I removed one of the redundant tags and replaced it by the algebraic geometry tag; ideally, this kind of stuff falls under 'convex algebraic geometry', but that tag is too long so I did not add it. Hope you don't mind (feel free to rollback if you do not approve of the tag-edit). – Suvrit Jan 6 '13 at 16:20

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).

• Do you mind a stupid question? How is the Lemma you provided related to Lemma 3.1.1 in Kleps paper? Kind regards /Olav – user12400 Jan 4 '13 at 21:19
• @Suvrit: could you point out this Lemma in I.Klep&M.Schweighofer ? – Dima Pasechnik Jan 5 '13 at 4:26
• Or do you mean to say that this Lemma is not in I.Klep&M.Schweighofer, but something that follows from the general duality theory in convex programming? One direction ($P_+\neq\emptyset$ implies nonexistence of $X$) is easy, but the other seems to be not so obvious. – Dima Pasechnik Jan 5 '13 at 4:36
• @Dima: this Lemma is not in the cited paper; it is something simpler, that I saw in lecture notes somewhere. Once I find those notes again, I'll link them (it was originally proved by L. Lovasz if I recall correctly) – Suvrit Jan 5 '13 at 9:02
• Perhaps one should also add that the condition in the lemma is easy to check using a semidefinite programming solver. – Dima Pasechnik Jan 7 '13 at 9:46

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