How to find a positive semidefinite matrix satisfying the following condition? Consider such a problem:
$$\mathbf A\mathbf x=\mathbf b$$
where the vectors $\mathbf x$ and $\mathbf b$ are known.
I want to find a positive semidefinite matrix $\mathbf A$ satisfying the aforementioned equation.
What conditions do $\mathbf x$ and $\mathbf b$ need to satisfy?
Thanks a lot.
 A: If $x$ and $b$ are vectors, they at least have to satisfy $x \cdot b \geq 0$. You can see this by considering the quadratic form associated with $A$:
$$Q(x) = x^T A x = x^T b = x \cdot b \geq 0,$$
since $A$ is positive semidefinite if and only if the quadratic form is.
A: I have chosen to provide the general ($n$ dimensional case) as a separate answer. I will use the letter $Y$ instead of $B$, i.e., being given $X$ and $Y$, find a symmetric positive semi-definite matrix $A$ such that
$$AX=Y$$
Let $s=X^TY$ be the dot product of $X$ and $Y$.
As remarked by @Fenris, a necessary condition for the existence of $A$ is that $s \ge 0$.
It is in fact sufficient. Here is why.
Let $\{U_1, U_2, \cdots U_{n-1}\}$ be any basis of the orthogonal subspace to $X$; then a solution is
$$A=\sum_{k=1}^{k=n-1} \alpha_k U_kU_k^T+\dfrac1s YY^T$$
for any sequence $\alpha_1,\cdots \alpha_{n-1}$ of positive numbers (s is assumed $\ne 0$). Indeed,
$$AX=\sum_{k=1}^{k=n-1}  \alpha_k U_k\underbrace{U_k^TX}_0+\dfrac1s Y\underbrace{Y^TX}_s=Y$$
and for any vector $V$:
$$V^TAV=\left(\sum_{k=1}^{k=n-1}  \alpha_k V^T U_k U_k^T V\right)+\dfrac1s V^TYY^TV = \sum_{k=1}^{k=n-1} \alpha_k\left(U_k^T V\right)^2+\dfrac1s(Y^TV)^2 \ge 0$$
establishing that $A$ is positive semi-definite.
Remark: a very particular case is obtained by taking all the $\alpha_k=0$...
A: The equation $Ax=b$ is solvable by a positive semidefinite $A$ if and only if
$$
b=0\ \text{ or }\ x^\ast b>0.\tag{$\ast$}
$$
For necessity, suppose $A$ is positive semidefinite and $Ax=b$. Then $x^\ast b=x^\ast Ax$ is nonnegative. If it is zero, then for every real scalar $c$, we have
$$
0\le(b-cx)^\ast A(b-cx)=b^\ast Ab - cb^\ast Ax - cx^\ast Ab + c^2x^\ast Ax = b^\ast Ab - 2c\|b\|^2.
$$
Hence $b$ must be zero.
For sufficiency, if $(\ast)$ is satisfied, we can take $A=0$ when $b=0$, or $A=\frac{bb^\ast}{b^\ast x}$ when $x^\ast b>0$.
A: Let us give a separate treatment for the case $n=2$.
We are going to show that there exists an infinite number of spd (symmetric positive definite) matrices $A$ such that:
$$\underbrace{\begin{pmatrix}a&b\\b&c\end{pmatrix}}_A \underbrace{\binom{x_1}{x_2}}_x=\underbrace{\binom{y_1}{y_2}}_y \tag{1}$$
(we have changed $b$ into $y$ in order to avoid ambiguities with the lower left entry of $A$)
under the necessary condition found by @Fenris:
$$\text{Dot product:} \ \ x.b=x_1y_1+x_2y_2 > 0 \tag{2}$$
(please note that we take $>0$ instead of $\ge 0$).
WLOG, one can assume that the two vectors have unit norms
$$x_1^2+x_2^2=y_1^2+y_2^2=1 \tag{3}$$
(indeed, once we have found a solution $A$, we just have to multiply it by $\dfrac{\|b\|}{\|x\|}$.)
It is now easy to check that for any $d$, we have:
$$\underbrace{\begin{pmatrix}(dx_2^2+(y_1x_1-y_2x_2))&(x_1y_2+x_2y_1 - d x_1x_2)\\(x_1y_2+x_2y_1 - d x_1x_2)&(dx_1^2-(y_1x_1-y_2x_2))\end{pmatrix}}_A\binom{x_1}{x_2}=\binom{y_1}{y_2}\tag{4}$$
with $$\operatorname{trace}(A)=d \ \ \text{and} \ \ \det(A)=d(x_1y_1+x_2y_2)-\underbrace{(y_1^2+y_2^2)}_1.\tag{5}$$
If we take
$$d > \dfrac{1}{x_1y_1+x_2y_2},\tag{6}$$
The RHS in (6) being positive (see (2)), we have $\det(A)>0$ and $\operatorname{trace}(A)>0$.
Therefore, if (6) is fulfilled, $A$ given by (4) is symmetric positive definite.
Remarks:

*

*How has $A$ in (2) been found ? By writing condition (0) under the form:

$$\begin{pmatrix}x_1&x_2&0\\0&x_1&x_2\\1&0&1\end{pmatrix}\begin{pmatrix}a\\b\\c\end{pmatrix}=\begin{pmatrix}y_1\\y_2\\d\end{pmatrix} \ \iff 
\begin{pmatrix}a\\b\\c\end{pmatrix}=\begin{pmatrix}x_1&x_2&0\\0&x_1&x_2\\1&0&1\end{pmatrix}^{-1}\begin{pmatrix}y_1\\y_2\\d\end{pmatrix}
$$
giving the entries $a,b,c$ of $A$ in (2), $d$ bringing its very useful degree of freedom.


*For readers acquainted with pole-polar relationship, here is a nice graphical interpretation.

(1) can be interpreted as the fact that point $(x_1,x_2)$ is the pole of line $xy_1+yy_2=k$ with respect to the conic curve (an ellipse) with equation
$$ax^2+2bxy+cy^2=k_1\tag{7}$$
In fact, due to normalization (3), it is the particular case of tangent-point of tangency relationship... under the condition that the conic defined by (7) passes through point $(x_1;x_2)$, which means that
$$k_1=ax_1^2+2bx_1x_2+cx_2^2$$
The figure below represents different ellipses with equation (7), according to the value of $d$.

Fig. 1: The case where $x=(x_1,x_2)=(4,3)$ and $y=(y_1;y_2)=(2,1)$ (giving, by normalization, $x'=(0.8;0.6)$ materialized by a little circle); the (tangent) line has equation $xy_1+yy_2=k$, $k$ being taken such that this line passes through $x'$. The different ellipses correspond to different values of $d$.
