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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
@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
up vote 1 down vote accepted

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.

share|cite|improve this answer
It is certainly possible there's a typo, but that wouldn't help my understanding. – jakev Feb 18 '11 at 4:40

Your Answer


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.