# How to find a representative equation for a linear system

This is for a graduate level course on computational linear systems. I want to do it myself, without help, but it's been ten years since I took linear algebra and I'm not sure I understand what the first part is asking for. The problem states:

Find a solution $x = x^* = (x_1^*, x_2^*, x_3^*, x_4^*)^T$ to the LLS problem:

$$\left\| \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 0 & -e & 0 \\ e & 0 & 0 & 0 \\ 0 & 0 & 0 & e \\ 0 & e & 0 & 0 \\ -e & 0 & 0 & 0 \\ 0 & -e & 0 & 0 \\ 0 & 0 & 0 & e \\ 0 & 0 & e & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} - \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \right\|_2 \to \min$$

as a function of $e$.

1. Find a function $f(x) = f(x_1, x_2, x_3, x_4)$ such that $x$ minimizes $f(x)$ is solution $x^*$ to problem

In case it isn't clear from the formatting, we have an (4x9) matrix with a variable e (not the log base) multiplied by a vertical vector of x1,x2,x3,x4, take the difference of that and another vertical vector with one 1 and 8 zeros and minimize. At one point in the assignment, he calls them Normal Equations. I've looked those up in Wolfram Alpha, but I don't think it helps.

I'm stumped by the question labeled 1. What is the teacher asking for? This is just the beginning part. I think once I understand the question he's asking here I can move on to solving Cholesky's algorithm, etc.

-
@Calle thanks for formatting for me, but that superscript 2 is a subscript- not sure if it matters, but it's meant to be the second norm. – jakev Feb 18 '11 at 4:17
@6NSString: You want to write down a function, from $\mathbb{R}^4$ to $\mathbb{R}$, whose minimum corresponds precisely to finding the minimum of your problem. I suggest you try writing out what that norm is, in terms of $x_1$, $x_2$, $x_3$, and $x_4$, and see if that helps you figure out what he is asking for. – Arturo Magidin Feb 18 '11 at 4:20
It doesn't matter (if you minimize $\| \cdot \|_2^2$ you minimize $\| \cdot \|_2$). Actually, I was wondering a bit if it was a subscript or a superscript (and if it was a superscript, if it was the 2-norm). – Calle Feb 18 '11 at 4:21
@Arturo, a yes. Of course. That is, if $x$ minimizes $f(x)$, then $x = x^*$, the solution to the problem. – Calle Feb 18 '11 at 4:25
@Arturo I'm not sure I understand. I've gone ahead and produced Ax (or A * [x1,x2,x3,x4]). I square the elements, and then take the root. (this how I get the 2 norm, yes?). Okay, so how now to go from R4 to R? I don't think I've ever seen such a trick. – jakev Feb 18 '11 at 4:39

Okay, let's call the big matrix $A$ and the vector with 9 elements $b$.
Then, of course, you want a solution $x$ such that $Ax = b$, because then $Ax - b = 0$ and $\|Ax-b\| = 0$. My guess is that this is not possible for all $e$ (it is possible for $e = 0$, easy to check).
Now, what you then have is a linear least squares problem. That is, you can "solve" for the $x$ such that $Ax$ is as close as it gets to $b$.
In question 1, the teacher probably wants you to write down a function $f$, such that if $f(x)$ reaches it minimum at $x$, then $\|Ax - b\|$ is minimal too.