How to find a positive semidefinite matrix satisfying the following condition?

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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:

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

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

Answer 4

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