Vtyjkyuk

I'm reading the existence proof of singular value decomposition.

It considers $f:mathbbR^nto mathbbR, f(x) = x^TMx$. It talks about the gradient of $f$ and make it equal to a multiple of the gradient of $x^tx$. I suppose that it's because the constraint is the unit sphere, so that's why it made $x^tx = x_1^2 + cdots x_n^2$, right?

I'm trying to understand this so I took $f$ with a generic matrix $M$

$$f(x) =beginbmatrix
x_1 & cdots & x_n
endbmatrixbeginbmatrix
a_11 & a_12 & dots \
vdots & ddots & \
a_n1 & & a_nn
endbmatrixbeginbmatrix
x_1 \
vdots \
x_n
endbmatrix = \ x_1(a_11x_1 + a_12x_2 + cdots + a_1nx_n) + \x_2 (a_21x_1 + a_22x_2 + cdots + a_2nx_n) + \
cdots + \x_n(a_n1x_1+a_n2x_2 + cdots + a_nnx_n)$$

Taking the partials to construct the gradient vector, I can see that I'll end up with:

$$beginbmatrix
2a_11x_1 + a_21 + cdots a_n1 \
a_12 + 2a_2x_2 + cdots + a_n2 \
vdots \
a_1n + a_2ncdots + 2a_nnx_n\
endbmatrix $$

Now, I need to equal this with $lambda$ gradient of $x^tx$:
$$beginbmatrix
2x_1 \
2x_2 \
vdots \
2x_n\
endbmatrix$$

so:

$$beginbmatrix
2a_11x_1 + a_21 + cdots a_n1 \
a_12 + 2a_2x_2 + cdots + a_n2 \
vdots \
a_1n + a_2ncdots + 2a_nnx_n\
endbmatrix = lambda beginbmatrix
2x_1 \
2x_2 \
vdots \
2x_n\
endbmatrix $$

As an example, the first line becomes:

$2a_11x_1 + a_21 + cdots a_n1 = lambda 2x_1 implies lambda 2x_1 -2a_11x_1 = a_21 + cdots a_n1implies x_1(2lambda - 2a_11) = a_21 + cdots a_n1$

What should I do now? It says that I should end up with $Mu = lambda u$

Also, is there a more elegant way of calculating the gradients or it's just all this mess?

You made a mistake computing the gradient of

$$\ x_1(a_11x_1 + a_12x_2 + cdots + a_1nx_n) + \x_2 (a_21x_1 + a_22x_2 + cdots + a_2nx_n) + \
vdots \x_n(a_n1x_1+a_n2x_2 + cdots + a_nnx_n)$$
For example, the partial derivative of this with respect to $x_1$ is
$$
underbrace2a_11x_1+a_12x_2+dots+a_1nx_n_textfirst row+underbracea_21x_2+dots+a_n1x_n_textfirst term of remaining rows
$$
which you can recognize as the first entry of $(M+M^top)x$. Therefore, the Lagrange multiplier equation becomes
$$
(M+M^top)x=2lambda x
$$
If you are further given that $M$ is symmetric, this implies $Mx=lambda x$.