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


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?

  • $\begingroup$ 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). $\endgroup$ – 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).

  • 1
    $\begingroup$ Do you mind a stupid question? How is the Lemma you provided related to Lemma 3.1.1 in Kleps paper? Kind regards /Olav $\endgroup$ – user12400 Jan 4 '13 at 21:19
  • $\begingroup$ @Suvrit: could you point out this Lemma in I.Klep&M.Schweighofer ? $\endgroup$ – Dima Pasechnik Jan 5 '13 at 4:26
  • $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Jan 5 '13 at 4:36
  • $\begingroup$ @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) $\endgroup$ – Suvrit Jan 5 '13 at 9:02
  • 2
    $\begingroup$ Perhaps one should also add that the condition in the lemma is easy to check using a semidefinite programming solver. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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