Given the singular value decomposition $A=U\Sigma V^{*}$, we have assuming $A$ is full rank : $$ A^{*}A=V(\Sigma^{*}\Sigma)V^{*} $$ The eigenvalues of $A$ are equal to singular values of $A$. However I have an issue with something I can't seem to understand. The convention I am used to is that $\sigma_{1}>\sigma_{2}>\ldots>\sigma_{r}$ where $r=\operatorname{rank}(A)$ in this problem we have $\sigma_{1}<\sigma_{2}<\ldots<\sigma_{r}$
Question 1 : Why do we have the right to change the order of the singular values in the matrix $\Sigma$ and doesn't it effect the SVD decomposition of $A$ as seen in MATLAB's svd function which lists them in decreasing order?
I have seen in class that if $x=a_{1}e_{1}+\ldots+a_{r}e_{r}$ a vector written as a linear combination of the eigenvectors of $A$ with $a_{1}^{2}+\ldots+a_{r}^{2}=1$ then it follows that : $$ E(x)-E(e_{1})=x^{T}A^{*}Ax-e_{1}^{*}(A^{*}A)e_{1}\geq\sigma_{1}^{2}(a_{1}^{2}+\ldots+a_{r}^{2}-1)=0 $$
Question 2 : What does this essentially imply regarding solving least square problem
For your first question, you can always change the order of your elements in $\Sigma$, it will just change your $U$. However, because permutation matrices are orthogonal, you will have \begin{equation} U\Sigma V^T = (UP^{-1})(P\Sigma)V^T \end{equation} and so $UP^{-1}$ is your new unitary matrix, where $P$ is the permutation matrix that gives your desired ordering of singular values.
I'm not really sure what your second question is asking.