Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.