When is $(A + A^\top)$ PSD even though A is not PSD?

Question

I am wondering if there are any constraints which can be places on a matrix $A \in \mathbb{R}^{n \times n}$ to ensure that $A + A^\top$ is positive semidefinite (PSD) even though $A$ itself is not PSD.

It is easy to see that if $A$ is PSD, then...

$$ x^\top (A + A^\top)x = x^\top A x + x^\top A^\top x = 2 x^\top Ax \geq 0 $$

Can it ever be the case that $A$ is not PSD but $A + A^\top$ is? What would need to be satisfied?

EDIT:

I assume $A$ is not symmetric or triangular.

Answer 1

Let $x^T (A+A^T)x \geq 0$ and $x^TAx < 0$ (i.e. not positive semi-definite). We know that any matrix can be decomposed into symmetric and antisymmetric matrices that is $A=\frac{1}{2}(A+A^T)+\frac{1}{2}(A-A^T)$ and $x^T A^T x=x^TAx$ (i.e. scalars are symmetric). We have $$ x^T A x < 0 \implies \frac{1}{2} x^T(A+A^T)x < 0 $$

If $A$ negative definite, so is $(A+A^T)$ but this contradicts our assumption that $A+A^T$ is positive semi definite, therefore, $A$ must be positive semi definite.

Answer 2

If $A + A^\top = B + B^\top$, then $A - B = -(A - B)^\top$. That is, the difference between the two matrices is an anti-symmetric matrix $M$, i.e. satisfying $M = -M^\top$. And, adding any such matrix $M$ to $A$ will make $$(A + M) + (A + M)^\top = A + M + A^\top + M^\top = A + A^\top - M^\top + M^\top = A + A^\top.$$ That is, once we find a particular solution to $A + A^\top = P$, where $P$ is a fixed PSD matrix, then the remaining solutions will differ by an anti-symmetric matrix $M$. Taking the easy solution $A = P/2$, we see the solutions are: $$\left\{\frac{P}{2} + M : M = -M^\top\right\}.$$ All this should make sense if you've studied linear equations. The map $A \mapsto A + A^\top$ is linear, making $A + A^\top = P$ a non-homogeneous linear equation. The solution is formed by taking a particular solution $P/2$ and adding the nullspace of the linear map, which are all these $M$ matrices.

Also, we could take the particular solution to be a triangular matrix, which affirmatively answers your question in the comments. However, if we take the particular solution to be $P/2$, we have the advantage that we only require $M \neq 0$, and we will definitely get a non-symmetric (and hence not PSD) matrix! This is because, \begin{align} \left(\frac{P}{2} + M\right)^\top = \frac{P}{2} + M &\iff \frac{P^\top}{2} + M^\top = \frac{P}{2} + M \\ &\iff \frac{P}{2} + M^\top = \frac{P}{2} + M \\ &\iff M^\top = M \\ &\iff M^\top = -M^\top \\ &\iff 2M^\top = 0 \\ &\iff M = 0. \end{align}