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.
Best Answer
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}