Property of approximate solution of Ax = b that infinite number matrices $F$ satisfy $(A+F)\tilde{x} = b$ Let $\tilde{x}$ be an approximate solution of Ax = b, where A is a nonsingular $n \times n$ matrix , n > 1.
if we define $r = b - A\tilde{x}$,and define $E$ as the rank-one matrix $E = r\tilde{x}^T/(\tilde{x}^T\tilde{x})$ it is easy to show that $E$ satisfies $(A+E)\tilde{x} = b$, now I want to prove that an infinite number of matrices $F$ satisfy the relation $(A+F)\tilde{x} = b$ and also show that the rank-one matrix $E$ has the smallest two-norm among all matrices $F$ satisfying $(A+F)\tilde{x} = b$.
I become confused if approximate solution $\tilde{x}, A , b$ are fixed, then how can we have infinite number of matrices that satisfy this relation $(A+F)\tilde{x} = b$ ?  
 A: You have $r = b-A \tilde{x}$ and $E$ must satisfy
$(A+E) \tilde{x} = b$. This holds iff $E \tilde{x} = r$.
Hence the solution space is $S = \{E |E \tilde{x} = r \}$ which is 
an affine space (hence convex, and closed since we are in a finite dimensional space).
To show that $S$ is not finite, note that you have given an explicit solution in the question, $E_0 = { 1\over \|\tilde{x}\|^2} r \tilde{x}^T$. Now  just pick any $y$ that is orthogonal to $\tilde{x}$, then we see that $E_0+z y^T \in S$ for
any $z \in \mathbb{R}^n$.
Since $S$ is closed and convex it has a point of minimum norm
regardless of norm.
If by 'two norm' you mean the Frobenius norm, then we have the associated inner product $\langle X, Y \rangle = \operatorname{tr} (X^T Y)$.
If $E \in S$, then we see that $\langle E_0, E-E_0 \rangle = 0$ and
so $\|E\|^2 = \|E_0\|^2 + \|E-E_0\|^2$
from which we see that $E_0$ is the unique point of minimum
Frobenius norm.
\begin{eqnarray}
\langle E_0, E-E_0 \rangle &=& \operatorname{tr} (E_0^T (E-E_0)) \\
&=& \operatorname{tr} ( (E-E_0) E_0^T) \\
&=& \operatorname{tr} ( (E-E_0)  { 1\over \|\tilde{x}\|^2} \tilde{x} r ) \\
&=& 0
\end{eqnarray}
Where the latter line follows from the fact that $E_0 \tilde{x} = E \tilde{x} = r$.
If by 'two norm' you mean the induced by the Euclidean norm, then it
is more straightforward: It is easy to compute
$\|E_0\| = {\|r\| \over \|\tilde{x}\|}$ and if $E \in S$, then
we have 
$\|E \| \ge \| E { \tilde{x} \over \|\tilde{x}\|}  \| = \|  { r \over \|\tilde{x}\|}  \| = {\|r\| \over \|\tilde{x}\|}$.
A: $F$ satisfies a vastly under-determined system of linear equations, $n$ equations in $n^2$ unknowns. As it has a solution, it has an infinity of solutions.
For the optimal solution you can employ the Lagrange function
$$
L(F,\lambda)=\frac12{\rm trace}(F^TF)+λ^T((A+F)x-b)
$$
and compute its stationary points.
