# Optimal solution to a matrix equation, linear system

This problem has me completely stumped.

Given:

$A$ is a symmetric $n \times n$ matrix

$r = b - Ax$ with $r, b, x \in \mathbb{R}^n$ and $x$ is nonzero.

Show how to compute a symmetric $E \in \mathbb{R}^{n\times n}$ with minimal Frobenius norm so that $\left( A+E \right) x = b$.

Hint: Use the $QR$ factorization of $[x, r]$ and note that $Ex=r \Rightarrow \left( Q^T E Q \right) \left( Q^T x \right) = Q^T r$

Hint: First show that $E$ has minimal Frobenius norm iff $Range(E) = Span\left\{x, r\right\}$

I've filled three pages with scratch work and gotten nowhere. Obviously setting $$E=\frac{r x^T}{\Vert x \Vert_{2}^{2}}$$ satisfies $\left( A+E \right) x = b$ but the norm is not minimized. Any hints would be appreciated

-
The problem isn't that your solution doesn't minimize the norm; it does. The problem is that it's not symmetric. – joriki Nov 15 '11 at 2:56

The $QR$ factorization of $[x,r]$ yields a two-column upper-triangular matrix $R=[R_1,R_2]$, and $[x,r]=Q[R_1,R_2]$ implies $Q^T[x,r]=[R_1,R_2]$, so the equation in the hint is $Q^TEQR_1=R_2$. Since the Frobenius norms of $E$ and $A:=Q^TEQ$ coincide (you can see this from the trace form of the norm), the Frobenius norm of $A$ must be minimal. Since $R_1$ and $R_2$ only have entries in the first two rows, that means that $A$ only has entries in the first two rows and columns, and we can find it from
$$\pmatrix{a_{1}&a_{2}\\a_{2}&0}\pmatrix{r_{11}\\0}=\pmatrix{r_{21}\\r_{22}}\quad\longrightarrow\quad a_1=r_{21}/r_{11}\;,\quad a_2=r_{22}/r_{11}\;,$$
where $r_{11}\ne0$ since $x$ is non-zero. Then we can calculate $E=QAQ^T$. Since the first two columns of $Q$ span $x$ and $r$, it follows that $\operatorname{Range}(E)\subseteq\operatorname{Span}\{x,r\}$, but I'm not sure why the hint says to show this first.