Solving linear equations including semi-positive definite matrix

Question

Suppose $A \in \mathbb{R}^{n \times n}$ is a positive semi-definite matrix. Can we solve the following for $x \in \mathbb{R}^n$?

\begin{equation} \begin{split} A(x-a) + \lambda I_{\bullet i}&=0\\ I_{\bullet i}^Tx&=0,\,\,\,\text{or }(x_i=0) \end{split} \end{equation} where $\lambda \in \mathbb{R}$, $a \in \mathbb{R}^n$, $I_{\bullet i}$ is the i-th column of the identity matrix, and $i$ is a fixed and given index. I did the following but cannot go further.

$x^TA(x-a) + \lambda x^TI_{\bullet i}=0$

$x^TA(x-a)=0$. Hence, $x- a \in N(A)$ or $x\in a+ N(A)$ and $\lambda=0$.

Also, $(x-a)^TAx=0$. Hence, $x \in N(A)$ and $Aa = \lambda I_{\bullet i}$ (I have no idea how to find $\lambda$ in this case).

Is there any other solutions for $x$ and consequently for $\lambda$?

Answer 1

Assuming that $a,i$ are given quantities (but not $\lambda$), the problem has a solution when

• $Ay=-e_i$ ($e_i:=I_{\bullet,i}$) has a solution $y_0$, i.e., whether $e_i\in\mathrm{im}A$, since the first condition is equivalent to $Ay=-\lambda e_i$ (for some $\lambda$);

For any $b\in N(A)$ such that $e_i^T(y_0+b)\ne0$, let $\lambda:=-e_i^Ta/e_i^T(y_0+b)$, so that $e_i^T(a+\lambda y_0+\lambda b)=0$, then the solution can be checked to be $$x=a+\lambda(y_0+b)$$ since $A(x-a)=\lambda Ay_0=-\lambda e_i$, and $e_i^Tx=e_i^T(a+\lambda y_0+\lambda b)=0$

[If $e_i^Ta=0$ then the solutions are $x=a+b$ for any $b\in N(A)$, since $(x-a)^TA(x-a)=-\lambda(x-a)^Te_i=0$ so $x-a\in N(A)$.]

---

If $e_i\notin\mathrm{im}(A)$, then the equation $Ay=-\lambda e_i$ can only be satisfied if $\lambda=0$ and $Ay=0$. Thus $x=a+y$ for some $y\in N(A)$. The other condition $e_i^Tx=0$ is then satisfied iff there is a non-empty intersection $(a+N(A))\cap e_i^\perp\ne\emptyset$. This is equivalent to $N(A)$ not being a subspace of $e_i^\perp$, i.e., $e_i\notin N(A)^\perp$.

Answer 2

We write $e_i$ for $I_{\bullet i}$. There are two possibilities:

1. $e_i\not\in\operatorname{range}(A)$, i.e. $AA^+e_i\ne e_i$. Since the LHS of $A(x-a)=-\lambda e_i$ lies inside $\operatorname{range}(A)$ but $e_i$ does not, we must have $\lambda=0$. The system of equations can then be rewritten as $$ \pmatrix{A\\ e_i^T}x=\pmatrix{Aa\\ 0}. $$ It is solvable if and only if $x=\pmatrix{A\\ e_i^T}^+\pmatrix{Aa\\ 0}$ is a solution.
2. $e_i\in\operatorname{range}(A)$, i.e. $AA^+e_i=e_i$. Then $e_i^TA^+e_i\ne0$ and one may verify that $(\lambda, x)=\left(\frac{a_i}{e_i^TA^+e_i},\ a-\lambda A^+e_i\right)$ is a solution.